基于整數(shù)線性規(guī)劃方法的集裝箱裝載布局優(yōu)化問題研究

1、文獻(xiàn)：基于整數(shù)線性規(guī)劃方法的集裝箱裝載布局優(yōu)化問題研究文獻(xiàn)的研究背景經(jīng)濟(jì)學(xué)家和企業(yè)界將現(xiàn)代物流稱之為“第三利潤源泉”，而現(xiàn)代物流對我國經(jīng)濟(jì)發(fā)展的影響越來越大，扮演著越來越重要的角色。經(jīng)濟(jì)全球化是當(dāng)今世界經(jīng)濟(jì)發(fā)展的客觀進(jìn)程，經(jīng)濟(jì)一體化是實(shí)現(xiàn)經(jīng)濟(jì)全球化這一目標(biāo)必經(jīng)的歷史階段。幾十年以來，隨著經(jīng)濟(jì)一體化進(jìn)程的推進(jìn)，貿(mào)易全球化以及國際航運(yùn)業(yè)的快速發(fā)展，現(xiàn)代物流水平已然成為影響企業(yè)競爭力的關(guān)鍵因素，我國的物流行業(yè)面臨著前所未有的發(fā)展機(jī)遇。集裝箱是現(xiàn)代物流中最常用的運(yùn)輸方式之一，被廣泛地應(yīng)用在鐵路運(yùn)輸，輪船裝載，給運(yùn)輸業(yè)帶來了新的變革，具有顯而易見的優(yōu)越性。集裝箱運(yùn)輸(containertransport

2、)，是指以集裝箱這種大型容器為載體，將貨物集合組裝成集裝單元，以便在現(xiàn)代流通領(lǐng)域內(nèi)運(yùn)用大型裝卸機(jī)械和大型載運(yùn)車輛進(jìn)行裝卸、搬運(yùn)作業(yè)和完成運(yùn)輸任務(wù)，從而更好地實(shí)現(xiàn)貨物“門到門”運(yùn)輸?shù)囊环N新型、高效率和高效益的運(yùn)輸方式。我國集裝箱運(yùn)輸業(yè)欣欣向榮。十六大以來，隨著國際化、工業(yè)化、城鎮(zhèn)化進(jìn)程的深入，我國對外貿(mào)易交流日益頻繁，沿海港口作為我國對外物資交流的重要窗口，發(fā)揮了重要的支撐保障作用。目前，我國己經(jīng)成為世界港口大國，全國港口貨物吞吐量和集裝箱吞吐量連續(xù)九年位居世界第一位。2011年下半年我國港口經(jīng)濟(jì)保持良好發(fā)展態(tài)勢,港航生產(chǎn)繼續(xù)保持較快增長，并逐步趨于平穩(wěn)。2011年，沿海港口完成貨物吞吐量73.

3、3億噸，比2001年的16億噸凈增約57.3億噸，年均增量約5.7億噸，年均增長16.4%。煤炭、原油、鐵礦石和集裝箱四大貨類的吞吐量分別達(dá)到17.1億噸、4億噸、11.5億噸和1.6億噸，分別是2001年的4.2倍、2.5倍、7.4倍和6.1倍。在全球排名前20名的億噸大港中，我國占了12個(gè)。目前，大陸有8個(gè)港口進(jìn)入世界港口吞吐量的前十位，5個(gè)港口進(jìn)入世界港口集裝箱吞吐量的前十位，上海港貨物吞吐量、集裝箱吞吐量均居世界第一。集裝箱吞吐量占全球港口集裝箱總吞吐量的近1/4。公路、航空、鐵路、水運(yùn)、管道是五種主要的現(xiàn)代化運(yùn)輸方式。這五種不同的運(yùn)輸方式使用了不同的運(yùn)輸工具、不同的運(yùn)輸設(shè)備、線路，水

4、運(yùn)中最常使用的現(xiàn)代化運(yùn)輸工具之一集裝箱，歷經(jīng)了一個(gè)漫長的發(fā)展過程，從初始階段經(jīng)過發(fā)展階段，最終達(dá)到成熟階段，其全面應(yīng)用時(shí)間還不長，存在利用率不高的問題。據(jù)調(diào)查，一個(gè)20英尺集裝箱，容積是33mA3,一般可裝載的容積為25mA3,集裝箱利用率約為75%;一個(gè)40英尺集裝箱，容積是67mA3、一般裝55mA3,集裝箱利用率約為82%。而在某些情況下，又會(huì)存在包裝箱本身裝載不飽滿，那就會(huì)使集裝箱實(shí)際利用率更低，造成很大的浪費(fèi)，這是當(dāng)下運(yùn)輸?shù)默F(xiàn)狀。因此，如何能最大限度提高集裝箱管理水平，提高集裝箱利用率，已成為當(dāng)務(wù)之急。文獻(xiàn)闡述的主要內(nèi)容集裝箱裝載問題具有現(xiàn)實(shí)意義。本文主要針對單個(gè)集裝箱、弱異類貨物的

5、問題，做了詳細(xì)分析和研究。目前，求解集裝箱問題常用的方法是啟發(fā)式算法，通過在解的空間域內(nèi)不斷搜索尋找最優(yōu)解，啟發(fā)式算法存在局限性。集裝箱裝載問題屬于組合優(yōu)化問題，用整數(shù)線性規(guī)劃求解在理論上是可行的，例如生產(chǎn)規(guī)劃、調(diào)度、路由、投資問題以及一些復(fù)雜的組合優(yōu)化問題都可以用整數(shù)線性規(guī)劃方法求解。整數(shù)線性規(guī)劃方法可以將數(shù)值約束與目標(biāo)結(jié)合應(yīng)用到規(guī)劃領(lǐng)域中。本文基于裝箱問題的實(shí)際約束條件，建立裝箱問題的數(shù)學(xué)模型，增強(qiáng)裝箱方案的實(shí)用性，嘗試采用整數(shù)線性規(guī)劃方法求解集裝箱裝載問題，通過布局約束轉(zhuǎn)換，將裝箱模型進(jìn)行線性化處理，求解可行域內(nèi)的最優(yōu)解。對于模型求解，本文采用CPLEX優(yōu)化軟件，其提供了解決實(shí)際的大型優(yōu)

6、化問題所需的能力，能夠以最快的速度最可靠地實(shí)現(xiàn)基本算法以解決困難的數(shù)學(xué)優(yōu)化問題，為有限時(shí)間內(nèi)得到可行域內(nèi)的最優(yōu)解提供了可能。本文的另一個(gè)重要工作是集裝箱裝載布局優(yōu)化仿真平臺(tái)的設(shè)計(jì)及構(gòu)建。經(jīng)過布局優(yōu)化計(jì)算，獲得了不同類型、同一類型貨物在集裝箱內(nèi)的空間位置及方向約束，對于計(jì)算規(guī)模數(shù)量較大的箱體而言，一方面需要驗(yàn)證裝箱貨物在理論指導(dǎo)的前提下布局的有效性，如避免懸置、重疊現(xiàn)象；另一方面，也需要將最終結(jié)果給生產(chǎn)現(xiàn)場以實(shí)際指導(dǎo)，輔助工人又快又好的完成整個(gè)裝載過程。本文所設(shè)計(jì)的布局優(yōu)化仿真實(shí)驗(yàn)平臺(tái)，具有開放式數(shù)據(jù)接口。不僅適用本文所提出的方法，也適用于其他優(yōu)化方法所獲得的實(shí)驗(yàn)結(jié)果。文獻(xiàn)內(nèi)容安排如下：第一章緒

7、論論述本文的研究背景、意義及集裝箱裝載布局優(yōu)化領(lǐng)域的國內(nèi)外研究狀況，進(jìn)一步概述裝箱問題的研究方法及其存在問題，為本文的研究工作做好鋪墊。第二章集裝箱裝載布局優(yōu)化問題綜述介紹了集裝箱裝載問題，并重點(diǎn)分析了裝箱問題的一般數(shù)學(xué)模型以及在裝箱過程中涉及的約束條件，并按照不同的標(biāo)準(zhǔn)別裝箱問題進(jìn)行分類。第三章集裝箱裝載布局優(yōu)化問題的算法綜述歸納總結(jié)現(xiàn)有的解決集裝箱裝載問題的常用算法，介紹了各個(gè)算法的相關(guān)知識(shí)，并介紹了這些算法的研究與應(yīng)用現(xiàn)狀。第四章整數(shù)線性規(guī)劃方法求解集裝箱問題基于前二章對集裝箱裝載布局優(yōu)化問題的充分了解以及對己有的求解方法的分析。本章通過了解問題具有的約束及使用資源的性質(zhì)，進(jìn)而建立裝箱問

8、題的數(shù)學(xué)模型，包括設(shè)計(jì)己知變量、決策變量，實(shí)現(xiàn)各種約束的表達(dá)以及線性化處理等，最終應(yīng)用CPLEX進(jìn)行程序?qū)崿F(xiàn)。第五章集裝箱裝載布局優(yōu)化仿真實(shí)現(xiàn)搭建仿真平臺(tái)，仿真實(shí)現(xiàn)裝箱過程，給出貨物裝載效果圖，采用不同算例進(jìn)行性能測試。第六章總結(jié)與展望總結(jié)本文所做的重點(diǎn)工作，對今后的研究工作進(jìn)行展望。文獻(xiàn)中運(yùn)用的模型或方法文獻(xiàn)采用整數(shù)線性規(guī)劃方法求解集裝箱裝載問題，探索集裝箱裝載問題的數(shù)學(xué)本質(zhì)，將實(shí)際問題轉(zhuǎn)化為數(shù)學(xué)模型，將目標(biāo)函數(shù)、約束條件線性化，然后通過數(shù)學(xué)方法，利用優(yōu)化軟件IBMILOGCPLEXOptimizationStudio(CPLEX)進(jìn)行求解。整數(shù)線性規(guī)劃解決組合優(yōu)化問題在理論上足可行的，例如

9、生產(chǎn)規(guī)劃、調(diào)度、路由、投資問題以及一些復(fù)雜的組合優(yōu)化問題都可以用整數(shù)線性規(guī)劃方法求解。用整數(shù)線性規(guī)劃求解組合優(yōu)化問題的優(yōu)勢主要有以下幾點(diǎn)：第一，整數(shù)線性規(guī)劃方法能提供一種自然的方法；第二，它允許將數(shù)值約束與目標(biāo)相結(jié)合，應(yīng)用到規(guī)劃領(lǐng)域中。整數(shù)線性規(guī)劃方法的描述：本文采用基于整數(shù)線性規(guī)劃方法求解集裝箱裝載問題，因此對于數(shù)學(xué)模型首先需要做線性化處理。為了便于計(jì)算與求解，我們對問題做如下假設(shè)：貨物的尺寸是整數(shù)；貨物只可以沿著集裝箱的坐標(biāo)軸放置，即垂直放置或是水平放置；采用的坐標(biāo)系為三維笛卡爾坐標(biāo)系，集裝箱的長、寬、高分別對應(yīng)笛卡爾坐標(biāo)系的X、Y、Z軸方向。(x,y,z)貨物在集裝箱的左前下角坐標(biāo)點(diǎn)；在

10、裝載過程中，放入集裝箱的貨物可以向下、向前、向左移動(dòng)，直到它的底面、前面、左面與其它貨物或是集裝箱相鄰；貨物到達(dá)同一目的地；可忽略貨物本身的擠壓變形；貨物的重心為其幾何中心。集裝箱裝載問題的數(shù)學(xué)模型描述如下：(1) l,w,h,g分別表示第i(i=1,m)類貨物的長度、寬度、高度、重量，L，W，H，G分別表示集裝箱的長度、寬度、高度、最大承載重量。本文裝箱問題的目標(biāo)函數(shù)為最大化集裝箱的空間利用率，由于集裝箱的容積是固定的，所以最大化4.1 所示：集裝箱空間利用率，即最大化裝入貨物的體積，如公式(2) (x，y，z)滿足以下集合：4.5(3) 集裝箱裝載容積的約束，裝入貨物的總體積要小于或等干集

11、裝箱的最大裝載容積，如公式所示：(4)集裝箱的承重能力的約束，裝入貨物的總重量不能超過集裝箱的最大承載重量，如公式4.6:本文將利用CPLEX進(jìn)行求解，首先對集裝箱裝載問題的數(shù)學(xué)模型做線性化處理，引進(jìn)如下變量：( xi,yi,zi)：貨物的左后下角坐標(biāo)；( Xli,Zli,Ywi,Zhi)：二進(jìn)制變量，判斷貨物i是如何平行與集裝箱坐標(biāo)軸擺放的，可以決定貨物/的放置方向，長度方向。若平行于x軸，則Xli=1,否則尤Xli=0;長度方向若平行于Z軸，則乙i=1,否則Zii=0;寬度方向若平行Y軸，則Ki=1,否則Ki=0;高度方向若平行于z軸，則Zhi=1,否則Zhi=0。( aij,bij,ci

12、j)：二進(jìn)制變量，定義貨物i與貨物j的相對擺放位置，若貨物i在貨物j的前面、右面或是上面，則變量分別為1，否則為0；模型線性化后的約束條件如下：公式(4.12)-(4.14)保證貨物i和貨物j彼此不重疊。公式(4.15)-(4.17)Xli,Zli,Ywi,Zhi用來計(jì)算貨物的長、寬、高與集裝箱的x、yz軸的相對對位置夭系，保證了貨物不超過集裝箱。(4.18)限制了兩個(gè)貨物i與j的相對位置。(4.19)-(4.26)保證了決定貨物位置的二進(jìn)制變量可以恰當(dāng)取值以反應(yīng)實(shí)際貨物的位置。要求：參考第一題文獻(xiàn)中的模型或方法試給出一個(gè)研究初步方案(三級研究提綱)題目：基于整數(shù)規(guī)劃的轎車物流配載優(yōu)化的研究摘要第一章緒論1.1 課題研究背景、目的及意義1.1.1 研究背景1.1.2 目的及意義1.2 國內(nèi)外研究現(xiàn)狀1.2.1 配載優(yōu)化問題簡介1.2.2 配載優(yōu)化的相關(guān)問題1.2.3 國內(nèi)外配載優(yōu)化的研究現(xiàn)狀1.3 目前研究存在的問題1.4 本文的研究目標(biāo)和研究內(nèi)容1.4.1 主要研究目標(biāo)1.4.2 主要研究內(nèi)容第二章轎運(yùn)車配載優(yōu)化系統(tǒng)的總體方案設(shè)計(jì)2.1 引言2.2 系統(tǒng)設(shè)計(jì)需求分析2.3 系統(tǒng)解決方案分析2.3.1 配載模型描述2.3.2 解決方案選取2.3.3 系統(tǒng)功能框圖2.4 系統(tǒng)開發(fā)環(huán)境分析2.5 本章小結(jié)第三章基于整數(shù)規(guī)劃的轎