基于混合式算法的貨物裝載布局問題研究*

趙宏宇趙黎平

（1.中國科學院大學 北京 100094）（2.中國科學院空間應用工程與技術中心 北京 100094）

1 引言

三維空間的貨物裝載在地面物流、航空運輸、航天保證等方面有著很強的應用需求，但是通常伴隨著多種約束條件的組合優(yōu)化問題。三維空間的貨物裝載問題是NP-hard問題［1］，對于此類問題，迄今為止，還沒有找到通用的有效算法。大多數(shù)研究者傾向于接受NP完全問題（NP-Complete或NPC）和NP-Hard問題（或NPH）不存在有效算法這一猜想，認為這類問題的大型實例不能用精確算法求解，因此必須尋求這類問題的有效的近似算法。研究方法上，一些學者開展新方法的研究，Mathur Ksmlesh［2］提出了一種優(yōu)化一維裝載問題的啟發(fā)式算法。Pisinger David，Sidurd Mikkel［3］研究了二維裝箱問題。相對于一維和二維的裝箱問題，三維的裝載優(yōu)化問題研究地較少。更多的學者偏向于對某種算法的改進應用，陳迎春［4］，樂千榿［5］等用改進的遺傳算法解決三維裝箱問題，張軍［6］用禁忌搜索算法，曹先彬［7］用免疫遺傳算法解決相關問題，雷定猷［8］結(jié)合實際工作中的裝卸經(jīng)驗提出了基于中心骨架的布局方法。

當前的研究中都會包含如下兩部分內(nèi)容，即如何從六種空間狀態(tài)中確定每件貨物的狀態(tài)，以及如何劃分貨物安置進來后剩余空間。很多研究者都會把這兩個問題糅雜在一起，十分復雜。為了降低問題求解的復雜度，本文采用了降維的思想，引入了“層”“條”“塊”的概念（詳見圖1），一定程度上規(guī)避了貨物空間狀態(tài)和剩余空間劃分帶來的困難，使裝載過程清晰明了，空間劃分整齊劃一，同時給出了設定貨物空間狀態(tài)的原則。在單車裝載時將啟發(fā)式算法和數(shù)學規(guī)劃的方法結(jié)合起來，分別發(fā)揮了各自的優(yōu)勢。算法的主干是數(shù)學規(guī)劃法，在處理條的平整度時利用的是粒子群算法。進一步解決多車問題時，采用了遺傳算法獲得貨物分配方案，及利用單車的布局優(yōu)化算法尋找最佳裝載方案，從而解決了多車多貨物裝載布局優(yōu)化問題，取得了比較好的效果。

2 模型建立

問題的研究基于以下假設：

1）貨物和容器的形狀都是長方體。

2）貨物可以多層積載。

3）兩點運輸，不存在中途裝卸。

4）貨物多而車輛少，允許有剩余。

多車多件貨物裝載布局優(yōu)化模型可描述為N類若干件長方體裝載于多個車，車廂可以相同也可以不同，貨物從一地運往另一地，貨物積載層數(shù)無限制，允許有剩余貨物。目前，多數(shù)學者常以體積利用率、所用箱體數(shù)、載重利用率為優(yōu)化目標來開展相關研究，且以前者為最多。如何琨［9～11］等、趙中凱等［12］、Jose［13］和Kang［14～16］等。故本文的優(yōu)化目標是制定合理的分配方案和裝載方案，使容器的平均體積利用率最大。主要的約束條件是所裝貨物的總重不超過允許載重量、所裝貨物不越出車輛邊界、底面積大的條處于底面積小的條之下以保證穩(wěn)定性、貨物之間不重疊。

如圖1所示，以容器的左前下角為原點建立直角坐標系，長邊方向為x軸方向，底面垂直于x軸方向為y軸方向，垂直于底面方向為z軸方向。

Q為N類貨物集合，Qij代表第i類第j個貨物，μij代表貨物的裝載狀態(tài)。vij，gij分別代表Qij的體積和重量。Lij，Hij，Wij分別代表Qij的長度指向，寬度指向，和高度指向。X，Y，Z分別代表車輛的長寬高。車輛的最大體積為V，最大載重量為G。（Xij1，Yij1，Zij1）代表貨物Qij的左后下點坐標，（Xij2，Yij2，Zij2）代表貨物Qij的右前上點坐標。Hy表示當前條的沿Y方向厚度，Hz代表當前條沿Z方向的高度。

建立數(shù)學模型：

約束條件：

3 算法設計

引言中提到了現(xiàn)在常用的兩種算法，數(shù)學規(guī)劃法和啟發(fā)式算法。數(shù)學規(guī)劃的方法基于人工裝載經(jīng)驗來設計，其計算結(jié)果多數(shù)是可行解或局部最優(yōu)解。利用啟發(fā)式算法的裝載算法也存在一些問題，啟發(fā)式具有較強的全局尋優(yōu)能力，但其收斂性和搜索速度易受初始條件的影響，而初始條件的設置就是初始的貨物裝載方式，很難設置，但初始條件設置不當，就很容易出現(xiàn)“早熟”現(xiàn)象，使結(jié)果停滯不前。另一方面啟發(fā)式算法大多要進行編碼，當貨物量大且約束條件多時，對編碼所要求攜帶的信息就多，編碼長度可能達到幾千位，加之啟發(fā)式算法需要大量的粒子參與運算，編碼量又以幾百倍的規(guī)模增長，計算量太大。

所以本文在單車問題時把前文兩種方式結(jié)合起來，用數(shù)學規(guī)劃法整體布局，經(jīng)過合理處理后再用粒子群算法局部優(yōu)化；進而在多車問題上采用遺傳算法充分尋找最優(yōu)分配集合，充分利用了各種算法的特性，針對性地解決問題。

3.1 定序規(guī)則和定位規(guī)則

Dowsland K A［17］提出了一種觀點：裝載優(yōu)化問題都可以歸結(jié)為所采用的兩個規(guī)則，即定序規(guī)則和定位規(guī)則，采用的規(guī)則不同導致了算法的不同。定序規(guī)則是指待裝貨物以什么樣的順序進行裝載，公認有效的有體積遞減規(guī)則，最長邊遞減規(guī)則，底面積遞減規(guī)則等。定位規(guī)則是指將當前貨物以什么規(guī)則放入集裝器剩余空間的某個位置，公認有效的有占角策略，順放策略，面策略等。在生產(chǎn)實踐中有俗語“金角銀邊草肚皮”來表示最常用的是占角策略，就是將帶裝貨物先安置在空間的一個角，再沿一條邊填充，如此反復，最后占滿整個空間。由此George和Robinson［18］提出了按階段填充的方法，提出了“層”的概念，先盡量使某一層平整，然后將層拓展到整個空間，后來很多人也延續(xù)了這種按階段填充的思路［19］。

3.2 算法原理

算法采用占角策略，沿邊延伸，順序擺放，形成一個條，然后向所在平面另一方向延伸，平行于前面條的方向擺放，形成多個條直至填充滿整個層，爾后向垂直于層的方向延伸，直至填充滿整個空間。選擇平面時有三種選擇，在平面內(nèi)延伸時有兩個順序可以選擇，共六種拓展方式。

算法采用如下的拓展方式，以容器后側(cè)面為初始平面，即由原點始，先向x方向延伸，然后向z方向延伸，形成層后再向y方向拓展直至充滿整個空間。

體積遞減原則的目的是防止以下情況發(fā)生，即體積小的貨物先裝載而體積大的貨物后裝載時，雖然剩余空間的體積夠置入體積較大的貨物，但是剩余空間的邊長卻不滿足置入條件，而小件貨物則無這種問題。但大件貨物如不能置入，其對整體的體積利用率的影響很大。所以本文將體積遞減原則作為指導原則之一。

當一個物體置入待布空間后，剩余的可置入空間有多種分割方式，且隨著置入物體的數(shù)目增加，剩余空間會越來越不規(guī)則，越來越復雜。引入層的概念后就不用關注整個剩余空間按如何劃分，只需關注層的剩余空間，考慮如何使其更加平滑，層的空間維度比整個空間小的多，考慮起來更加容易。當層的厚度與待布貨物的尺寸相匹配時，可能出現(xiàn)層厚度方向不需要疊加貨物的情況，問題得到了很大的簡化。

當給定一個數(shù)值作為層的厚度，并以此為標準去遴選貨物裝載時，在實際應用中通常會出現(xiàn)滿足遴選條件的貨物數(shù)量不足以填充滿整個層，所以引入了“條”的概念，以條的厚度作為遴選標準。按階段填充，想要保證較高的體積利用率就需要保證層的平整性，而保證平整性的同時就無法保證體積遞減，二者一定程度上相互矛盾。所以算法采用了一個折中的辦法，同時考慮層平整度和體積遞減規(guī)則，操作過程會在下面的算法過程中體現(xiàn)。如圖2所示定義如下變量，Hmx、Hmy、Hmz分別為當前最大的可用于裝載貨物沿X軸、Y軸、Z軸方向尺寸；Hy為當前條厚度值；Hz為當前已裝載貨物沿Z軸方向尺寸。

圖2 空間裝載順序

3.3 裝載優(yōu)化算法

考慮體積遞減規(guī)則，首先安置體積最大的一類貨物，并且給出每個貨物的安置方位及這一條的厚度和高度。

Algorithm 1條長度方向填充算法

預定義：所有箱子的集合O=｛（序號，盒子信息）…｝，在每次填充的過程中剩余貨物集合定義為P，(Pinital=O).Hmx、Hmy、Hmz表示當前最大的可用于裝載貨物沿X軸、Y軸、Z軸方向尺寸，Hy，Hz分別表示當前條的寬度值和當前條沿著Z方向的高度，Vi代表某個貨物的體積，擺放的次數(shù)變量t初始值為1。

輸入：車輛的大?。鸏，W，H｝，各個箱子的尺寸｛li，wi，hi｝（其中箱子的編號為i）

輸出：條長度方向填充方案

1：放入貨物之前，計算Hmx、Hmy、Hmz。

2：從集合P中選擇貨物Pij，Pij服從Hmx、Hmy、Hmz的尺寸限制，更新Pnew←Pold-O，若無貨物滿足要求，則對下一空間進行填充。

3：如果t=1，選取P中體積最大的一類貨物N，統(tǒng)計P的棱長集合為Dim，統(tǒng)計N的棱長dim1，dim2，dim3按P中出現(xiàn)的頻率降序排列，指定dim1為貨物的寬度，并同時為此條的寬度Hy，dim2，dim3大者為貨物的長度，小者為貨物的高并同時指定為此條的高度。

4：如果t！=1，對Dim中每一條棱遍歷P，找到能匹配此棱長的貨物集，并計算體積和sumv，以max（sumv）所匹配的棱長作為Hy，若max（sumv）有多個值，則選數(shù)值最大的棱長為作Hy。

5：改變Pij尺寸指向使寬度接近且不小于Hy，長大于高。

6：對Pij根據(jù)其寬度與Hy的差值由小到大排序。若有多個貨物寬度相同，則將他們按體積遞減原則排序。

7：在Pij中挑選備選貨物集合E。按P中順序，從第一個開始依次選擇，并計算長度之和，當選入最后一件貨物后長度和大于Hmx時，改變其尺寸指向，嘗試使其滿足條件。然后從P中第二個貨物開始選擇，如此往復。

8：將Ei中貨物高度最大值指定為Hz。

9：依次檢查Ei中貨物高度與Hz差值是否小于thita1，若不滿足條件，則在Ei在P的補集中尋找貨物替代它，條件是其長寬值與當前貨物長度值只差小于給定值thita2、thita3，且高度與Hz之差小于thita1。

10：計算Ei中貨物長度和，選擇數(shù)值不大于Hmx，且與其差值小于thita4的集合。

11：從篩選過的E中選擇包含體積最大類貨物數(shù)量最多的集合，再從中選擇貨物長度和最大的集合作為條長度方向的裝載集合。

這樣處理貨物尺寸指向是因為放置體積最大貨物后長度方向可能還未填充滿，要用其他貨物繼續(xù)填充剩下的空間，所以要保證有匹配的貨物可以填充剩余的空間，就選擇在DIM中出現(xiàn)頻率最高的那條棱長為Hy。同時，如果能用較少數(shù)量的貨物在長度方向填充滿，就能更大概率地保證條的平整性，所以暫把棱長最大值作為長。而且在高度方向的值越小，每一層中容納條的數(shù)目就越多，使更多的貨物滿足條件填充進來，所以令剩下二者中數(shù)值較大的為長，較小的為高。

通過如上操作，我們得到了一個在x方向充分填充，且y方向和z方向被嚴格限制在Hy和Hz范圍內(nèi)的方案，且選擇過程充分考慮了體積遞減原則。

由于貨物的形狀和個數(shù)有限，現(xiàn)在得到的條很可能在高度和寬度上還不平整，要在這兩個方向上進行補全。補全的方式分為兩個部分。首先是將已布貨物的同類貨物捆綁形成塊，用同類貨物進行補全。同類貨物補全操作之后，可能在高度和寬度方向依然不平整，由于寬度方向的不平整來自長度和最大化的操作。所以注定寬度不平整的區(qū)域不會很長。所以我們重點關注高度方向上的不平整。高度方向依然不平整的原因是剩余貨物集中沒有與已布貨物同類的貨物，或者同類貨物不足，亦或者塊的高度不足以與條高度相匹配。

此時剩余空間的XZ截面呈階梯形，對不規(guī)則空間進行排布非常困難，所以我們還是尋求對長方體進行排布。由于條的寬度較小，必須用多于一排貨物填充的概率較小，所以把此問題轉(zhuǎn)化為二維矩形截面排布的問題。粒子群算法在解決二維排布的問題上簡單有效，故引入此算法解決條平整度問題。

Algorithm 2條平整度處理算法

預定義：Pij代表Ei中元素，是貨物對象。

輸入：條長度方向填充方案，填充貨物集對于P的補集

輸出：條的平整度補全方案

1：當選定裝載集合中Pij的高度或?qū)挾炔淮笥贖y或Hz的1/2時，從補集中選擇與Pij同類的貨物P′ij，改變其尺寸指向，將其與Pij捆綁，用以在高度或?qū)挾壬涎a全。

2：調(diào)整貨物，使其延X方向度度遞減，計算XOZ平面剩余空間，將截面剩余空間分割為若干矩形Qi，ishuyu1，2，3…

3：從P中選擇能置入Qi所代表的剩余空間的貨物，改變尺寸指向使Y方向盡量長。

4：對矩形內(nèi)排布的二維問題引入粒子群算法，一個粒子代表備選集合中貨物的左下坐標，初始化粒子時優(yōu)先安排體積大的貨物。

5：以落在矩形范圍內(nèi)貨物的體積之和sum-v作為評價函數(shù)，經(jīng)粒子群算法迭代后，得到評價函數(shù)最大值。

6：依次對Qi執(zhí)行步驟4，步驟5。以max（sum-v）所代表的裝載集合作為平整度補全方案。

7：將條上貨物按高度降序排列，將剩余空間集中于一側(cè)

Algorithm 3層的平整度處理及基于層的空間填充算法

輸入：車輛尺寸｛L，W，H｝，貨物集P

輸出：層的平整度補全方案

1：重復調(diào)用算法1，算法2。以層內(nèi)第一條的寬度作為層的寬度，其他條的寬度不大于層寬度。

2：高度方向延伸至邊界后，找出各條寬度不同帶來的剩余空間，在空間內(nèi)再調(diào)用算法1，算法2。貨物排布僅延高度方向延伸

3：將已填充的層空間從考慮的剩余空間中移除，重新計算Hmx、Hmy、Hmz。反復調(diào)用第一步、第二步，直到填充滿整個空間。計算體積利用率。

在多車問題上，分配方案是問題的關鍵。分配問題不同于某些候選解可以隨算法演化改變而改變的問題，比如在連續(xù)區(qū)間內(nèi)求最值問題。代表分配問題解的粒子隨算法演化的變化，不是粒子本身編碼變化了，而是編碼內(nèi)部順序的改變，因為貨物數(shù)和車輛數(shù)都是確定的，不能隨意改變。我們發(fā)現(xiàn)，遺傳算法的編碼和粒子的演化過程對粒子的操作，符合問題的特點，故采用了遺傳算法來解決分配問題。

Algorithm 4多車多貨物裝載算法

輸入：多車輛尺寸｛L，W，H｝，貨物集P

輸出：多車多貨物問題的各車裝載方案

1：引入遺傳算法，對種群進行初始化。先對每件貸物所要搭配的車輛進行隨機選擇，并將方案編碼。

2：將每一種編碼作為一個個體，統(tǒng)計每輛車待裝貨物集合。

3：調(diào)用上述算法，計算每輛車的體積利用率。計算平均利用率作為遺傳算法的評價函數(shù)。

4：每一代種群計算過后，保留最佳個體。其余個體進行選擇、交叉、變異產(chǎn)生新一代種群。

4 仿真與分析

表1 待裝載貨物詳細數(shù)據(jù)

類號12345678序號1～12 13～22 23～38 39～42 43～56 57～72 73～85 86～91長/cm 100 120 130 200 140 80 30 100寬/cm 70 100 20 200 80 40 60 100高/cm 50 110 10 120 140 100 100 50件重0.5 0.5 0.13 2.9 0.8 0.2 0.22 0.55件數(shù)48 40 64 16 56 64 52 24

應用算法得到最佳結(jié)果的裝載方式示意圖見圖3～圖6。

圖3 一號車裝載方案

圖4 二號車裝載方案

圖5 三號車裝載方案

圖6 四號車裝載方案

應用算法得到如下分配方案：車輛一［9，9，13，4，15，16，9，9］，車輛二［17，10，18，4，16，17，12，2］，車輛三［10，7，19，4，13，14，19，6］，車輛四［12，14，14，4，12，17，12，7］。四個列表分別代表四輛車的分配方案，列表中八個元素代表對應貨物類別的個數(shù)。共裝入348件貨物，未裝入16件，其中二類9件，七類7件。得到一號車體積利用率為93.8%、二號車為94.6%、三號車為87.8%、四號車為88.6%，平均體積利用率為91.2%。各車載重量分別為一號車44.42t、二號車為47.38t、三號車為43.25t、四號車為45.91t，均未超重。

根據(jù)文獻［20］的數(shù)據(jù)，多車情況下，當裝載貨物種類數(shù)與本文測試數(shù)據(jù)（8類）相近時，不同裝載算法在其各自的測試數(shù)據(jù)下得到的平均空間利用率介于80%～90%之間者居多，鮮有高于90%者，而本文空間利用率達到了91.2%?？梢娯浳锊季趾侠?，空間利用率高，且剩余空間集中、不呈碎片化。由于三維裝載問題的特性，貨物的數(shù)量、類別、尺寸，容器的尺寸等因素，都會對裝載效果產(chǎn)生影響，所以體積利用率只能在一定程度上說明算法性能，與此同時也可能會掩蓋算法的缺陷。但可以看出，雖然利用率較高，但是算法沒有找到最佳的分配方案。

5 結(jié)語

本文構(gòu)建了車輛載重量和有效容積約束等條件為主要約束的多車多件貨物的布局優(yōu)化模型。評價體系上考慮了體積利用率為評價指標。提出了一種解決多車多件貨物裝載布局問題的算法。算法應用降維的思想，降低了問題求解的復雜度。采用遺傳算法作為方案分配算法，裝載算法以數(shù)學規(guī)劃法為主干，處理條的平整度時采用了粒子群算法。對算法進行仿真實驗，仿真結(jié)果表明所提出的模型和算法能夠有效地制定利用率較高的多車多貨物的裝載布局方案。

本文中多車問題的分配方案是局部最優(yōu)解，這個問題是單純的啟發(fā)式算法優(yōu)化問題，要通過優(yōu)化方案分配算法來解決。由于分配問題是初值敏感型的，未來將改進遺傳算法初始種群的設定方法，使其適應初值敏感型問題的特點。與此同時還可以通過優(yōu)化遺傳算法，引入模擬退火算法等方法，增強方案分配算法全局最優(yōu)解搜索能力。