基于最大最小蟻群算法的多卸載點車載裝箱模型研究

田 冉,孫林夫,唐慧佳,李斌勇

(西南交通大學 信息科學與技術學院，四川 成都 610031)

基于最大最小蟻群算法的多卸載點車載裝箱模型研究

田 冉,孫林夫,唐慧佳,李斌勇

(西南交通大學 信息科學與技術學院，四川 成都 610031)

針對多卸載點、多種貨物、多車承運中的箱式貨車裝箱問題，為需要在不同地點卸貨的貨物生成貨物裝卸序列。建立了基于體積、重量和裝卸距離的數學模型，定義了各類裝箱約束條件，首先按照裝箱規則和裝箱約束生成一個可行解作為蟻群算法的初始解，再根據螞蟻在貨物上尋路的特點定義了信息素和選擇概率公式，通過最大最小蟻群算法在一定的循環次數內求得最優解，從而達到最大化貨車的裝載利用率和體積利用率的目標。最后通過一個實例證明了該方法的合理性和有效性。

交通工程；多卸載點；車輛裝箱；最大最小蟻群算法

0 引 言

三維裝箱問題(Three-Dimensional Bin Packing Problem，3D-BPP)是一類復雜的具有約束條件的組合優化問題，在理論上屬于NP完全問題[1]。

國內外的專家學者對裝箱問題進行了大量的研究。研究內容主要可以分成兩種：①建立在簡化模型的基礎上，并未考慮在現實中實際存在的多目標和多約束的布局，僅是研究三維布局中的優化方法。如：K.A.Dowsland等[2]和F.G.Ortmann等[3]對裝箱中的布局問題進行了描述性工作，其中大部分是研究二維或三維的布局優化方法，目前常見的優化方法有數學規劃法、圖論法、啟發式方法、人工智能等方法；T.G.Crainic等[4]提出了一種二級禁忌搜索算法；O.D.Lara等[5]提出了基于蟻群算法的多目標求解算法；張德富等[6]提出了一個求解裝箱的混合模擬退火算法，通過復合塊的生成，基礎啟發式算法和模擬退火算法來尋找問題的近似最優解；Huang Wenqi等[7]提出了通過穴度方法求解一類裝箱問題的算法。衛家駿[8]在裝箱問題的降序最先適應算法和降序最優適應算法的基礎上，提出了一個改進的降序最優適應的集裝箱船配載算法。連志剛等[9]建立了符合集裝箱裝載實際的數學模型，并利用類粒子群算法對所建模型進行優化，實現了容器容積和承重量的最大發揮。②建立在多目標和多約束布局的基礎上，如：曹玲芝[10]探討了混合模擬退火算法在集裝箱裝載過程中的多目標、多約束優化的問題；靳志宏等[11]提出了一種GW節約算法與基于剩余空間的裝箱算法有機結合的交互式算法，并分別與配載優先和配送優先的單獨優化進行了對照仿真實驗。

這些研究中對集裝箱裝箱研究較多，對貨車裝箱的研究很少。需要指出的是車輛裝箱和集裝箱裝箱的并不一樣：集裝箱裝箱的一次性需要裝入的貨物類型較少，貨物的體積重量差別不大，且沒有在運輸過程中裝卸的需求；但是車輛裝箱正好相反，例如：在汽車配件的運輸過程中，需要裝箱的貨物體積、重量類型差別較大，而現有的研究并未有一個完整考慮體積、重量、裝卸順序的多種約束的方法來解決這一問題。同時對于汽車配件運輸來說，一車貨物可能有多個卸載點是實際存在的，但在多卸載點的研究大多集中在車輛線路規劃和車輛調度上，對于多卸載點的車輛該如何裝箱研究很少，因此研究多卸載點的車輛如何裝箱具有實際意義和應用價值。

針對這一問題，筆者構建了包含貨物體積、重量和裝卸順序的廂式貨車裝箱模型，在最大最小蟻群算法基礎上設計了相應的求解算法以求得最優的裝貨順序，并通過實例驗證了該模型的有效性。

1 問題描述

筆者主要針對多種貨物、多卸載點、多車承運中的裝箱問題進行研究?？啥x為：有大量的多種長方體貨物需要通過多個貨車運到多個卸載地點，為了方便貨物卸載，需要在裝車時滿足先“先上后下”的原則，同時需要在貨物完全裝入貨車后通過不同的擺放順序以滿足如下的各個約束，最終需求的承運車輛最少，需要的承運成本最低。在這一過程中定義如下約束：

1) 裝載貨物必須完全包含在車輛之中；

2) 裝載貨物的總體積和總重量不能超過車輛的容積和承重；

3) 任何兩個裝載貨物之間不能相互重疊；

4) 裝載貨物必須水平放置，即不能斜放；

5) 裝載的貨物不能懸空放置，即必須放在其它可壓貨物上或者托盤上；

6) 必須保證貨車的穩定性，即裝載貨物后的貨車重心必須限制在一定的范圍內；

7) 貨物必須滿足“先上后下”的原則。

由于問題的復雜性，同時進行約定：

1) 貨物為同一類型，即不存在化學品和食物混裝的現象；

2) 忽略貨物的擠壓變形，即只要貨物是可壓的就不會有變形現象出現；

3) 任意貨物的重心都為其幾何中心；

4) 不存在貨物顛倒放置的現象出現；

5) 約定所有的貨物都為規則的矩形件；

6) 約定貨車或者貨物的長≥寬≥高；

7) 所有的貨物都是可壓的；

8) 貨車僅從車輛尾部進行卸貨；

9) 所有貨車的型號相同。

2 數學模型

2.1 基本變量定義

采用坐標系為三維笛卡爾坐標系，以貨車車輛的長度方向為x軸，寬度方向為y軸，高度方向為h軸，車輛的左后下角為坐標原點(0，0，0)。設定k輛車輛的長寬高分別為Lk，Wk，Hk；所裝貨物t的長寬高分別為lt，wt，ht，如圖1。

圖1 貨車裝箱各參數定義Fig.1 The definition of truck packing parameters

2.1.1 貨物t的表示

貨物t可以用一個11元組(n，Ct，At，k，zt，xst，yst，zst，xet，yet，zet)來表示貨物裝車后的狀態。其中：C為貨物類型；A為卸貨地點；t為貨物ID；k為承運車輛ID；放置方向和空間方位則由后7位 (zt，xst，yst，zst，xet，yet，zet)表示。

當zst=1時，貨物t的長和貨車k的x軸平行，且寬與y軸平行；當zst=0時，貨物t的長和貨車k的y軸平行，且寬與x軸平行。貨物t的位置坐標為貨物t在貨車k內的左后下角坐標[0]-(xst，yst，zst)和右前上角坐標[4]-(xet，yet，zet)。例如：在圖1中貨物t的空間方位可以表述為(0，0，0，lt，wt，ht)。

2.1.2 貨物裝入車輛的情況

當貨物裝入車輛時后會產生3個尺寸和形狀不同的新的剩余空間(V1，V2，V3)[12]，所在位置分別處于圖1中已放入貨物t的(1)，(2)，(3)的3個方向。

剩余空間可以由6個字段的信息來描述，分別為剩余空間的左后下角的坐標和右前上角的坐標。例如在圖1中：當貨車k未裝載貨物時的剩余空間則可以描述為Vk=(0，0，0，Lk，Wk，Hk)，其中：Lk，Wk，Hk分別為貨車裝載空間的長、寬、高。

在裝載過程中的剩余空間則定義為

Vl=(xd,yd,zd,xu,yu,zu)l=1,2,…,|V|

式中：|V|為當前可用的剩余空間的個數。

2.1.3 貨車的載重信息

貨車的載重信息定義為Gk(第k輛車的最大承載重量)，貨車的承運信息表示為

2.1.4 貨物卸載的優先級確定

對每個貨物按照其卸貨地點的遠近定義其卸載優先級：

λt=Dt/Dmax

式中：Dt為貨物t從配送點到卸貨地點的距離； Dmax為待裝的所有貨物從配送點到卸貨地點的最遠距離，貨物卸載地點越遠其裝入的優先級越高。

2.2 裝箱約束條件

在實際的裝箱過程中會有很多約束條件，這里對各項約束進行定義：

1) 貨物t必須裝入車輛k內，不能超過車輛的邊界

2) 裝載貨物的總體積和總重量不能超過車輛的容積和承重

3) 任何兩個裝載貨物(t,r)之間不能相互重疊

4) 裝載貨物必須水平放置，即不能斜放：

ztk∈{1,0},?t∈{t|qtk=1}

5) 貨物不能懸空放置：

?t∈{t|zst>0,qtkl=1}；

?r,r∈{r|qrk=qtk,zer=zet,xsr≤xst,xer≥xet,ysr≤yst,yer≥yet};

6) 貨物必須滿足先上后下的原則

貨物的裝卸約束定義為：對于貨物t和貨物r，如果λt≥λr，必有xst≤xsr。

貨車裝載需要在多個地點卸貨的貨物時，卸貨地點相同的貨物的裝卸優先級相同，因此需要對同一地點卸貨的貨物進行裝載優化；當貨物優先級不同時，則需要滿足先上后下的卸載原則，因此必須滿足xst≤xsr。同時由于貨車車廂大都為后門卸貨，因此在同一y軸上的貨物即使卸載優先級不同也不影響貨物裝卸，所以y軸上不存在類似約束。而在z軸上，由于同一優先級的貨物可以重疊放置，因此z軸上也不存在類似約束。

7) 重心約束

貨車上放置貨物需要滿足車輛行駛安全的需要，因此需要滿足：

其中：(XGmin,XGmax),(YGmin,YGmax),(HGmin,HGmax)分別對應在x軸，y軸和高度h方向上的車輛重心的安全范圍。(xt,yt,ht)為貨物t的重心坐標。這里將車輛的重心近似為：

2.3 目標函數和適應度函數的定義

貨物裝車的主要目標是在車輛最少的情況下裝入全部待裝貨物，使得貨車的容積利用率和重量利用率最大，同時保證貨物的裝卸序列滿足多地點裝卸時先上后下的要求。筆者這里定義了3個目標函數：

2.3.1 空間利用函數

(1)

式中：Vt表示已經裝車的貨物t的體積，t∈[1，mj]；mj表示車輛j上所有裝車的貨物數量；CVj中j∈[1，n]表示第j輛車的容積。

2.3.2 重量利用函數

(2)

式中：Wt表示已經裝車的貨物t的重量；CWj表示車輛j的承載重量。

2.3.3 裝卸距離函數

D=∏dt

(3)

如果：λt≥λr，有xst≤xsr；則：dt=1，否則dt=0。t，r∈[1，mj]，且t≠r。

2.3.4 適應度函數

在滿足裝卸一體化的條件下，為了最大化空間利用率和重量利用率，定義適應度函數為

F()=(CR+WR)×D

(4)

只有在滿足裝卸的條件下，即裝卸距離函數D不為0時，再最大化空間利用率和重量利用率。

3 算法設計

貨物的裝載本身是一種組合優化問題，存在多種不同的組合方式，其主要目標就是如何在其中尋找適應度函數最大的最優解。而蟻群算法是一種基于群體的元啟發式算法，由M．Dorigo等[13]于1992年首先提出。目前蟻群算法以其正反饋，分布式等優點已經成功的應用于多個NP難的組合優化問題的求解，因此筆者將蟻群算法作為解決組合優化問題的辦法來解決裝卸一體化的裝箱問題。

但是由于蟻群算法[14]最初使用的是隨機策略確定尋路路徑，使得進化速度和收斂速度較慢，因此筆者通過兩個階段來實現蟻群的路徑尋優：一階段為首先通過在滿足裝卸約束的條件下按貨物卸載優先級從大到小和體積從大到小的原則求初始的可行解；二階段為在初始可行解的基礎上，根據重新定義了初始分配信息素、信息素揮發公式和選擇概率公式，再通過最大最小蟻群算法來尋找最優解。在蟻群算法尋找最優解的過程中不再隨機定義螞蟻的出發點，而是按照裝箱的特性固定為體積最大、運輸最遠的箱子為出發點。在信息素的揮發過程中再按照箱子上次的排序進行揮發，排序靠前的箱子揮發較少。在選擇箱子的過程中按照能見度和信息素的差異進行選擇，盡可能的選擇體積較為一致的箱子統一擺放。

3.1 求初始的可行解

一階段算法流程：

Step1:初始化車輛及貨物的相關信息，按照貨物的卸載優先級從大到小進行排序，貨物裝卸優先級相同的貨物則按照貨物體積從大到小進行排序。

Step2:在卸載優先級較大的待裝貨物集合中選擇體積最大的貨物體積和當前車輛等待裝入的剩余空間體積比較，如果貨物體積小于剩余空間體積，則放入貨物并更新待裝貨物集合和剩余空間集合，否則選擇體積次大的貨物進行比較。如果優先級最小、體積最小的最后一個待裝貨物的體積都大于車輛剩余空間體積，則增加運輸車輛，返回Step1繼續。當待裝貨物集合為空時，裝箱完成。

最后得到的裝箱順序即為一個初始解。但由于只考慮了貨物的卸載優先級和體積大小，結果并不一定完全滿足在2.2節中定義的各項約束，因此該初始解是一個可行解，但并非是一個強可行解，其為蟻群算法尋找最優的強可行解打下了基礎。

3.2 蟻群算法尋找最優解

這里不再如傳統的蟻群算法將信息素定義在各條子路徑上，而是將信息素定義為每個貨物的屬性，即將待裝的貨物看作是螞蟻需要尋路的路徑，貨物的裝箱順序即為螞蟻的尋路路徑。同時每次循環都是由多只螞蟻順序執行尋路操作，和傳統蟻群算法將不同螞蟻放到不同的點上開始尋路的方式不同，文中每只螞蟻的起點均為所有待裝貨物中的卸載優先級最大和體積最大的貨物。因為首先裝入的貨物是固定的，必然是體積最大、運輸最遠的。不同于傳統蟻群算法均分初始信息素，筆者將尋路順序定義在每個貨物的信息素中，將3.1節的初始裝箱算法所生成的解作為蟻群算法的初始解，以貨物的裝箱順序分配初始信息素，以所有的貨物都裝完作為一次螞蟻尋路完成的標志。

3.2.1 初始信息素定義

定義貨物t上的初始信息素τt為

(5)

3.2.2 信息素的更新

(6)

(7)

3.2.3 選擇概率

選擇概率為螞蟻在選擇了貨物t之后選擇下一個貨物r的概率：

(8)

ηtr為能見度，定義為

(9)

3.2.4 算法流程

二階段算法流程：

Step1：初始化最大循環次數n，螞蟻數量m，最大信息素τmax，最小信息素τmin；

Step2：初始化待裝貨物信息和車輛信息，根據3.1小節中求得初始解；

Step3：根據初始解，按照式(5)為每個貨物分配初始信息素；

Step4：在一次循環內，螞蟻按照選擇概率式(8)完成一次尋路，選擇下一個需要裝入的箱子時通過約束條件1)～6)判斷是否能夠裝入車輛，如果不能則增加車輛，返回step2；

Step5：如果該螞蟻的尋路路徑為當前最優路徑，則按式(6)更新信息素，否則按式(5)更新信息素。所有螞蟻一次尋路完成后，本次循環結束，本次循環的最優路徑作為下次循環的初始解，返回step3；

Step6：循環次數達到最大循環次數時終止，輸出當前最優路徑為最優解。

4 計算結果

車輛裝箱和集裝箱裝箱的選擇數據類型的不同點在于：集裝箱裝箱的一次性需要裝入的貨物類型少，且體積重量差別不大，但需要裝入的數量很多，沒有運輸過程中中途裝卸的需求。但車輛裝箱正好相反，在汽車企業配件運輸的過程中，需要裝箱的貨物類型是根據配件的大小，貨物的體積、重量類型差別較大，且有運輸過程中中途裝卸的需求。

筆者選擇的測試數據為某汽車廠備件中心一次發給承運商的承運單信息，一共有4種不同類型的貨物，且有中途裝卸的需求，有4個目的地?？梢钥偨Y為有7種、共50個貨物需要發往4個地方。貨物數量不多的原因是承運單上一次不會有超出車輛裝載性能十幾倍的裝箱需求，一般都是物流車輛承受能力的1～3倍，是可以讓承運商承受的裝運信息。貨物的相關數據如表1。

表1 裝箱數據contentTable 1 Packing data

測試參數選擇為：共30只螞蟻，循環最大次數為120次。車輛為中型后開門貨車，長寬高為5 m×2 m×2 m，最大承載重量為25 t。由于需要裝車的貨物總體積大于該類型貨車可裝箱的總體積，因此該訂單需要兩節貨車進行裝載。由于無論采用何種裝箱方法都必須滿足貨物必須裝完的必要約束條件，且總有一輛車是未滿載的狀態，因此無論何種算法，在裝完所有貨物后的總的車輛利用率肯定是一樣的。因此這里僅比較第一輛的車的裝箱評價數據，即使得第一輛車的體積利用率、重量利用率在滿足裝卸條件和運輸約束等條件下盡可能最大。評價數據越大則說明第一輛車的利用率越高，裝箱順序越合理。使用3.1節中的算法流程生成的可行解，可行解中包含了車輛1和車輛2的裝箱順序內容，其中車輛1的裝箱單如表2。

表2 車輛1的初始裝箱單Table 2 Initial packing list of car1

將該結果運用到3.2節中的蟻群算法中求最優解，通過100次循環得到每次循環的最優裝箱結果如圖2。

圖2 體積利用率Fig.2 Volume utilization rate

對于車輛1，從圖2的計算結果可以看出第10,69,79,99次循環時的裝箱結果最好且相同，其裝箱數量為40，體積利用率為0.758 1，重量利用率為0.742 5，得到的第99次循環的最優裝箱如表3。

表3 最優裝箱單Table 3 The optimum packing list

將文中方法求得的裝箱結果和使用滿足2.2節中的裝箱約束條件的貪心算法,按貨物體積大小進行裝箱的結果，以及不使用初始解的蟻群算法進行比較，結果如表4。

表4 裝箱結果比較Table 4 The comparison of packing results

從表4可以看出，文中算法在車輛1的體積利用率和重量利用率都是高于貪心算法的，說明文中算法是合理有效的。文中算法和不使用初始解的蟻群算法在結果上相差不多，但是在計算時間上，通過100次循環，文中算法用時43.1s，而不使用初始解的蟻群算法用時51.4s，文中算法在執行效率上明顯優于不使用初始解的蟻群算法。

5 結 論

貨車裝箱問題是不同于集裝箱裝箱的多約束的三維裝箱問題，其需要多點卸貨的需求是以往集裝箱裝箱所不需要考慮的。筆者基于此建立了基于體積利用率、重量利用率和裝卸距離的數學模型，并根據實際需要定義了貨物裝卸的相關約束。在求解方法上通過求得初始可行解作為蟻群算法的初始解，在最大最小蟻群算法的基礎上設計了相應的求解算法以求得最優的裝貨順序。并通過實例驗證了筆者提出的模型和算法對解決有多點卸貨需求的貨車裝箱問題是有效可行的，今后的研究將進一步圍繞如何細化各類裝箱約束和優化裝箱方法繼續進行。

[1] JOHNSON D S.計算機和難解性-NP完全性理論導論[M].張立昂,譯.北京:科學出版社,1990:124-125. JOHNSON D S.ComputerandIntractability-NPCompleteTheoryIntroduction[M].ZHANG Li’ang,Translate.Beijing:Science Press,1990:124-125.

[2] DOWSLAND K A,DOWSLAND W B.Packing problems[J].EuropeanJournalofOperationalReasearch,1992,56(1):2-14.

[3] ORTMANN F G,NTENE N,VAN VUUREN J H.New and improved level heuristics for the rectangular strip packing and variable-sized bin-packing problems[J].EuropeanJournalofOperationalResearch,2010,203(2):306-315.

[4] CRAINIC T G,PERBOLI G,TADEI R.“TS2PACK”:a two-level tabu search for the three-dimensional bin packing problem[J].EuropeanJournalofOperationalResearch,2009,195(3):744-760.

[5] LARA O D,LABRADOR M A.A multi-objective ant colony-based optimization algorithm for the bin packing problem with load balancing[C]// 2010IEEECongressonEvolutionaryComputation(CEC).IEEE,2010:1-8.

[6] 張德富,彭煜,朱文興,等.求解三維裝箱問題的混合模擬退火算法[J].計算機學報,2009,32(11):2147-2156. ZHANG Defu,PENG Yu,ZHU Wenxing,et al.A hybrid simulated annealing algorithm for the three-dimensional packing problem[J].ChineseJournalofComputers,2009,32(11):2147-2156.

[7] HUANG Wenqi,HE Kun.A caving degree approach for the single container loading problem[J].EuropeanJournalofOperationalresearch,2009,196(1):93-101.

[8] 衛家駿.一種集裝箱船配載問題改進算法探討[J].重慶交通大學學報(自然科學版),2009,28(5):969-972. WEI Jiajun,.A revised algorithm to solve container ships stowage problem[J].JournalofChongqingJiaotongUniversity(NaturalScience),2009,28(5):969-972.

[9] 連志剛,林蔚天,曹宇,等.基于類粒子群算法的集裝箱裝載模型優化研究[J].重慶交通大學學報(自然科學版),2014,33(2):126-130. LIAN Zhigang,LIN Weitian,CAO Yu,et al.Similar particle swarm optimization algorithm for the optimization of container loading model[J].JournalofChongqingJiaotongUniversity(NaturalScience),2014,33(2):126-130.

[10] 曹玲芝.求解三維裝箱問題的混合模擬退火算法研究[D].廣州:華南理工大學,2013:23-40. CAO Lingzhi.StudiesonHybridSimulatedAnnealingAlgorithmforThree-dimensionalBinPackingProblems[D].Guangzhou:South China University of Technology,2013:23-40.

[11] 靳志宏,于波,侯麗曉.廂式貨車配載與配送的聯合優化[J].交通運輸工程學報,2010,10(3):95-100. JIN Zhihong,YU Bo,HOU Lixiao.Integrated optimization on both vehicle filling and routing for van truck transportation[J].JournalofTrafficandTransportationEngineering,2010,10(3):95-100.

[12] LAYEB A,BOUSSALIA S R.A novel greedy quantum inspired cuckoo search algorithm for variable sized bin packing problem[J].InternationalJournalofMathematicsinOperationalResearch,2014,6(6):732-751.

[13] DORIGO M,BIRATTARI M.AntColonyOptimizationEncyclopediaofMachineLearning[M].U.S:Springer,2010:215-216.

[14] NING Xin,KA-CHI L,CHUN-KIT L M.Dynamic construction site layout planning using max-min ant system[J].AutomationinConstruction,2010,19(1):55-65.

Multi-Unloading Packing Problem Model Research Based on MMAS

TIAN Ran, SUN Linfu, TANG Huijia, LI Binyong

(College of Information Engineering and Technology, Southwest Jiaotong University, Chengdu 610031, Sichuan, P. R. China)

Aiming at the packing problems of container truck with multiple loading points, goods variety and multi-truck carriers, cargo loading and unloading sequence for different unloading locations was generated. Mathematical model was set up based on volume, weight and loading-unloading distance and the constraints to various packing types were defined. Firstly, a feasible solution generated as per packing rule and packing constraint served as initial solution by ant colony algorithm. Then, pheromone and selection probability formula was defined in accordance with characteristics of ants route seeking on goods to calculate the optimum solution within certain cycle numbers by max-min ant colony algorithm so as to achieve the goal of maximum loading utilization and maximum volume utilization of goods truck. Finally, the rationality and effectiveness of this method is justified by a practical case.

traffic engineering; multi-unloading point; vehicle loading; max-min ant colony algorithm

10.3969/j.issn.1674-0696.2016.02.32

2014-08-11；

2015-01-22

四川省科技支撐計劃項目(2014GZ0142)；汽車及工程機械多產業鏈業務協同服務平臺研發(2013AA040606)

田 冉(1981—)，男，河南南陽人，博士研究生，主要從事物聯網、數據挖掘等方面的研究。E-mail:troom@163.com。

U492.3+12; TP301

A

1674-0696(2016)02-156-07