張長勇, 劉佳瑜, 王艷芳

(中國民航大學(xué)電子信息與自動(dòng)化學(xué)院，天津 300300)

集裝箱在運(yùn)輸過程中以其獨(dú)特的優(yōu)越性，使得在物流運(yùn)輸和裝載環(huán)節(jié)實(shí)現(xiàn)快速和高效作業(yè)，從根本上改變了傳統(tǒng)運(yùn)輸方式的落后面貌，對于經(jīng)濟(jì)社會(huì)的發(fā)展具有不可忽略的重要作用。目前郵包、快件等異構(gòu)型貨物的集裝箱裝載仍采用人工方式，裝載貨物過程不僅勞動(dòng)強(qiáng)度大、效率低，還會(huì)導(dǎo)致貨物損壞、實(shí)際裝載效果差等問題。因此研究強(qiáng)異構(gòu)型貨物的在線裝箱優(yōu)化問題，進(jìn)而實(shí)現(xiàn)貨物的自動(dòng)碼放，對于提高集裝箱容積利用率，減少作業(yè)人員數(shù)量，提高運(yùn)輸行業(yè)經(jīng)濟(jì)效益具有重要意義。

貨物的裝箱優(yōu)化問題屬于典型的裝箱問題。根據(jù)是否已知貨物信息可以將裝箱問題分為在線裝箱問題和離線裝箱問題兩種。在線裝箱算法在未知待碼放貨物相關(guān)信息并且需要在貨物到來時(shí)實(shí)時(shí)計(jì)算出貨物裝箱方案的一種碼放算法。目前在線裝箱問題中研究集中在一維和二維裝箱問題上。黃海等[1]提出綁定配對策略來解決未裝滿箱體數(shù)量問題，針對如何啟動(dòng)新箱體采用了間隔函數(shù)來實(shí)現(xiàn)；張明會(huì)等[2]對貨物進(jìn)行預(yù)處理實(shí)現(xiàn)將對應(yīng)貨物裝載進(jìn)入相對應(yīng)集裝箱中，獲得了1.423 6漸近競爭比；趙曉凡[3]為改進(jìn)整體裝箱率，采取只開兩個(gè)箱子的策略，其中一個(gè)裝體積小貨物，一個(gè)裝載大小體積的混合貨物；肖教燎等[4]提出一種非矩形改進(jìn)A形在線裝箱問題，其中只考慮貨物高度和半徑兩個(gè)因素；陳建新[5]改進(jìn)NF算法并提出最后物件置換算法和每個(gè)物件置換算法兩種具有置換功能的算法；Angelopoulos等[6]通過提出簡單和復(fù)雜兩種算法，從而對在線算法已知上下限進(jìn)行了改進(jìn)；Song等[7]通過研究CPU性能，將優(yōu)化主動(dòng)使用服務(wù)器數(shù)量這個(gè)問題抽象成為在線裝箱問題，并且針對在線裝箱算法進(jìn)行設(shè)計(jì)，實(shí)現(xiàn)與結(jié)果評估；Steven等[8]提出并驗(yàn)證Harmonic+1的漸近性能比至少是1.592 17。

很多學(xué)者采用元啟發(fā)式算法來提高算法性能及優(yōu)化裝載效果。于明正等[9]提出雙層遺傳算法實(shí)現(xiàn)算法在廣度和深度上的搜索，提高裝載率的同時(shí)保證碼放穩(wěn)定性；劉勝等[10]提出基于“箱子-片-條-層-實(shí)體”多層樹搜索算法滿足了擺放方向約束和完全支撐約束；何慶等[11]考慮多種實(shí)際約束提出將改進(jìn)遺傳與模擬退火算法結(jié)合建立并求解裝載模型；Brouer等[12]以班輪運(yùn)輸為研究背景，對搜索算法進(jìn)行設(shè)計(jì)與優(yōu)化。代愛民[13]提出在半在線基礎(chǔ)上的改進(jìn)遺傳算法。

目前中外學(xué)者對于一維貨物在線裝箱問題研究較多，而對于三維在線裝箱問題的研究偏少，且大多三維在線裝箱問題的研究并未考慮到實(shí)際的工程環(huán)境。為此在前人研究的基礎(chǔ)上，考慮異構(gòu)型貨物集裝箱裝載過程中存在的一些實(shí)際約束，建立以集裝箱空間利用率為優(yōu)化目標(biāo)的數(shù)學(xué)模型，結(jié)合模擬退火算法優(yōu)越的局部搜索能力以及算法可操作性強(qiáng)的特點(diǎn)，提出在線極值點(diǎn)(online improved extreme point,IE)算法與模擬退火(simulated annealing,SA)算法相結(jié)合的在線融合(IES)算法，實(shí)現(xiàn)異構(gòu)型貨物的在線裝箱優(yōu)化，并利用機(jī)場運(yùn)行的自助行李托運(yùn)系統(tǒng)采集的貨物數(shù)據(jù)驗(yàn)證算法的有效性。

1 問題描述

將貨物和集裝箱約束為三維長方體質(zhì)量塊，因此該模型簡化成為：規(guī)定集裝箱尺寸為W、H、D，貨物序列是長、寬、高為wi、hi、di，要求將實(shí)時(shí)到來貨物進(jìn)行順序裝載，使得集裝箱在滿足實(shí)際約束條件下求得最大空間利用率。

1.1 約束條件

研究模型是強(qiáng)異構(gòu)在線裝箱模型，任意兩件貨物質(zhì)量和尺寸均不相同。在實(shí)際在線裝箱過程中，需要考慮以下多種現(xiàn)實(shí)條件約束。

(1)體積和質(zhì)量約束，貨物總體積以及總質(zhì)量不得超過集裝箱所能容納最大容積和最大承載力。

(2)貨物姿態(tài)約束，考慮到貨物放置穩(wěn)定性在放置時(shí)將底面積較大一面平行于地面放置，貨物邊和面只可與集裝箱底面水平或者正交放置。

(3)貨物重疊約束，垛形中任意兩件貨物不能相互重疊嵌入。

(4)貨物裝載次序約束，在線裝箱考慮貨物到來次序，不能允許跳過。

1.2 條件假設(shè)

在實(shí)際在線裝箱環(huán)境中存在許多復(fù)雜現(xiàn)實(shí)問題，因此假設(shè)條件提出能夠降低問題復(fù)雜性，從而簡化數(shù)學(xué)模型，本文假設(shè)條件主要圍繞以下幾點(diǎn)：

(1)假設(shè)貨物均為規(guī)則長方體塊。

(2)假設(shè)目地為單一目地，無中轉(zhuǎn)。

(3)貨物重心在其幾何中心上。

鎮(zhèn)機(jī)關(guān)干部職工六十多人，班子成員和副科級以上就有十九個(gè)，宿舍樓只有二十四套。在當(dāng)時(shí)，能不能入住是身份地位的象征，年齡、工齡、任職年限是分房（包括選擇樓層、朝向）的依據(jù)。盡管只有五套分給中層干部，但接下來還有平房的重新分配，還有享受福利分房的“半邊戶”（配偶是農(nóng)村戶口）工作人員。盡管是平房，進(jìn)門就是客廳，也是水泥地面白灰墻，還有防蚊子蒼蠅的紗門紗窗，頂上釘著天花板，打架的老鼠掉不下來，屋后過道設(shè)有專門的廚房。這在當(dāng)時(shí)是從單一的“宿舍”朝舒適、方便居住的生活理念的一個(gè)巨大轉(zhuǎn)變。住房就像是貼在機(jī)關(guān)大門口的布告昭然若揭，一看就能分別出三六九等。

(4)不同貨物交錯(cuò)疊放時(shí)要求下層貨物承載能力優(yōu)于上層貨物，以此保證下層貨物不被損壞。

(5)貨物本身擠壓變形忽略不計(jì)。

1.3 模型建立

圖1為貨物碼放效果圖，以集裝箱左后下角為原點(diǎn)，底面為XY平面，垂直底面向上為Z軸建立坐標(biāo)系。

i(i∈1,2,…,n)為貨物序號；mi、vi依次為第i號貨物質(zhì)量、體積；M、V為集裝箱承載能力、容積；(xi,yi,zi)為第i號貨物在集裝箱中左、后、下角角點(diǎn)坐標(biāo)；為第i號貨物在集裝箱中右、前、上角端點(diǎn)坐標(biāo)圖1 貨物碼放效果圖Fig.1 Effect of cargo coding

為在集裝箱內(nèi)最大化貨物裝載數(shù)量以此達(dá)到集裝箱空間利用率最大，設(shè)目標(biāo)函數(shù)為

(1)

(2)

(3)

y′-y=h

(4)

(5)

p≠q

(6)

(7)

(8)

(9)

式(2)、式(3)為集裝箱容積和質(zhì)量約束，要求貨物總體積與總質(zhì)量小于集裝箱最大體積，最大承載能力；式(4)、式(5)為貨物姿態(tài)約束，式(4)表示只允許以貨物高度進(jìn)行旋轉(zhuǎn)，式(5)表示貨物只能保持與集裝箱方向水平或者正交；式(6)～式(8)表示貨物重疊約束，為了保持穩(wěn)定性，任意兩個(gè)貨物(p、q)之間不可重疊放置；式(9)表示考慮到貨物到來順序與裝載順序約束，要求實(shí)時(shí)碼放到來貨物，不可發(fā)生順序上跳躍。

2 算法設(shè)計(jì)

2.1 IE算法提出與優(yōu)化

在二維、三維狀態(tài)下“角點(diǎn)”示意圖如圖2所示。角點(diǎn)就是指可供下一件貨物左、后、下角放置點(diǎn)。此處首個(gè)角點(diǎn)為坐標(biāo)原點(diǎn)(0,0,0)，在三維裝箱中，角點(diǎn)可以概括為在當(dāng)前垛形外側(cè)包絡(luò)面內(nèi)具有階梯化形態(tài)兩件貨物橫、縱交叉點(diǎn)，在實(shí)際過程中要剔除虛假角點(diǎn)(x,y相同時(shí)z較大點(diǎn))。

圖2 角點(diǎn)示意圖Fig.2 Corner point diagram

IE在線碼放算法是通過離線裝箱極值點(diǎn)算法[14]來改進(jìn)得到，通過角點(diǎn)序列的實(shí)時(shí)更新來尋找下一個(gè)貨物碼放的空間坐標(biāo)。采用角點(diǎn)序列首角點(diǎn)匹配思想形成集裝箱自左向右階梯狀布局在線碼放形式。首先建立x-y二維坐標(biāo)系并得到二維角點(diǎn)，其次構(gòu)建三維坐標(biāo)系，即在二維坐標(biāo)系的基礎(chǔ)上增加z坐標(biāo)軸，使它從0開始以整數(shù)遞增，遞增每個(gè)整數(shù)成為層，在遍歷所有三維坐標(biāo)后完成三維角點(diǎn)的確定，完成到來貨物碼放之后更新存儲所有可放置角點(diǎn)序列等待下件貨物到來。

在線裝箱需要對實(shí)時(shí)到來每一件貨物規(guī)劃一個(gè)合理位置，最大化集裝箱裝載率相比時(shí)間快速性更為重要，為找到每件貨物最佳放置點(diǎn)，設(shè)置多條規(guī)則并賦予權(quán)重，規(guī)則權(quán)重比如表1所示。表1中，角點(diǎn)坐標(biāo)為(x,y,z)，N0為角點(diǎn)總個(gè)數(shù)，ni為按照規(guī)則i在角點(diǎn)總數(shù)中排序序號。規(guī)則1保證貨物按軸優(yōu)先級碼放，規(guī)則2、規(guī)則3為提高集裝箱容積利用率，最大化旁空間利用率；規(guī)則4針對碼放垛形穩(wěn)定性，使得整個(gè)垛形中心向中下位置靠近；在多次實(shí)驗(yàn)之后根據(jù)各個(gè)規(guī)則對最終裝載效果影響大小設(shè)置權(quán)重依次為0.4、0.2、0.2、0.2。在設(shè)置各種規(guī)則權(quán)重之后寫出具體優(yōu)化算法流程如圖4所示。

圖4 優(yōu)化算法流程Fig.4 Optimization algorithm flow

按照表1中規(guī)則，設(shè)置優(yōu)化函數(shù)為F，每個(gè)放置角點(diǎn)對應(yīng)一個(gè)優(yōu)化值，并按照降序排列優(yōu)化值f，以此來更新角點(diǎn)序列。為了防止出現(xiàn)過擬合現(xiàn)象，加入較小隨機(jī)數(shù)γ來保證規(guī)則合理性。表1規(guī)則可以簡化為

表1 規(guī)則及其權(quán)重設(shè)定Table 1 Rules and weight settings

(10)

2.2 融合算法設(shè)計(jì)

貨物在線碼放過程中所提出優(yōu)化算法易于陷入局部最優(yōu)循環(huán)，而且由于集裝箱空間受限，要求其數(shù)據(jù)量保持在100以內(nèi)，因此在優(yōu)化算法中增加模擬退火算法[15]來增加算法快速性并且尋求全局最優(yōu)解，通過增加降溫過程時(shí)間來保證解穩(wěn)定性。

模擬退火過程中鄰域選取是影響最終結(jié)果的關(guān)鍵部分，在實(shí)驗(yàn)中，其一鄰域是優(yōu)化值小范圍更新，其二鄰域是交換貨物兩種碼放姿態(tài)。兩種鄰域的不同都會(huì)影響到模擬退火最終結(jié)果，在計(jì)算過程中，上述提到兩種鄰域被等概率選取。如圖5所示即為融合算法具體流程圖。其中，用c來表示角點(diǎn)序列，優(yōu)化值用f表示，每個(gè)角點(diǎn)對應(yīng)著唯一f，c序列首個(gè)角點(diǎn)為待碼放貨物角點(diǎn)坐標(biāo)，最佳角點(diǎn)序列用cbest表示，初始溫度為tS，終止溫度為tE，當(dāng)前溫度用t表示，當(dāng)前角點(diǎn)序列中首角點(diǎn)剩余空間容積為Vb，最佳角點(diǎn)序列中首角點(diǎn)最大剩余空間為Vb,best，初始鄰域?yàn)長，當(dāng)前鄰域長度為Lt。

圖5 融合算法流程圖Fig.5 Flow chart of fusion algorithm

3 實(shí)例計(jì)算與結(jié)果分析

為測試上述提出的IES算法的性能，從某機(jī)場自助行李托運(yùn)系統(tǒng)實(shí)際采集獲取的真實(shí)貨物數(shù)據(jù)進(jìn)行驗(yàn)證。從大量數(shù)據(jù)中隨機(jī)選取的100件貨物信息作為實(shí)驗(yàn)數(shù)據(jù)，對算法的最終裝載布局進(jìn)行驗(yàn)證。部分貨物數(shù)據(jù)在表2中列出。

表2 待碼放貨物信息表Table 2 Cargo information to be coded

此處使用三維在線碼放問題，需要考慮很多實(shí)際約束，且針對的是實(shí)際裝載中航空貨物數(shù)據(jù)，所以通過比較兩種分配方案，即IE和IES算法所產(chǎn)生整體布局方案，采用MATLAB編程將布局方案可視化，更為直觀地比較算法整體布局效果。用碼放平臺去直觀地展示在線碼放每件貨物過程，手動(dòng)輸入待碼放貨物信息，點(diǎn)擊確認(rèn)按鈕之后，進(jìn)行在線碼放。第40、41件貨物碼放結(jié)果位置布局效果圖如圖6 所示，碼放貨物之后得出最終整體布局圖，IE和IES貨物布局情況如圖7所示，IES算法使貨物分配更合理緊湊，集裝箱容積率更大。

圖6 碼放第40件和第41件貨物效果圖Fig.6 The effect of stacking the 40th and 41st cargo

圖7 IE和IES整體布局圖Fig.7 IE and IES overall layout

為進(jìn)一步驗(yàn)證算法的碼放效果，采用兩種算法分別對5組貨物進(jìn)行在線裝箱規(guī)劃，得到的實(shí)驗(yàn)數(shù)據(jù)如表3所示。采用IE算法平均碼放貨物55件，而采用IES算法平均碼放貨物61件。IES的平均容積率達(dá)到89.17%，相比IE算法提高了10.34%，且IES集裝箱利用率更加均衡。究其原因，IES中加入了規(guī)則權(quán)重對算法進(jìn)行優(yōu)化，并且結(jié)合模擬退火算法使得算法局部以及全局尋優(yōu)能力提升，在較短時(shí)間內(nèi)能夠快速找到最優(yōu)解。

表3 兩種算法容積率對比Table 3 Comparison of floor area ratio of two algorithms

4 結(jié)論

(1) 在考慮實(shí)際裝載過程中的現(xiàn)實(shí)約束下，提出了一種適用于貨物裝箱的在線融合算法，通過設(shè)置碼放規(guī)則以及優(yōu)化函數(shù)來最大化地實(shí)現(xiàn)集裝箱容積率，為貨物的在線裝載問題提供了有效的解決辦法。

(2)在IE算法的基礎(chǔ)上增加了模擬退火算法避免算法出現(xiàn)局部最優(yōu)的情況，更好地尋求全局最優(yōu)解，進(jìn)一步提高裝載優(yōu)化效果，為在線裝載決策提供理論基礎(chǔ)。

(3)采集機(jī)場自助行李托運(yùn)系統(tǒng)實(shí)際獲取的真實(shí)貨物數(shù)據(jù)進(jìn)行實(shí)驗(yàn)驗(yàn)證，證明所提算法對強(qiáng)異構(gòu)貨物有著較好的適應(yīng)性與有效性。采用MATLAB軟件中的GUI界面實(shí)現(xiàn)貨物的可視化裝載，提高三維裝箱算法的工程性。