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

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

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

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

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

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

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

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

0 引 言

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

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

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

針對這一問題，筆者構(gòu)建了包含貨物體積、重量和裝卸順序的廂式貨車裝箱模型，在最大最小蟻群算法基礎(chǔ)上設(shè)計(jì)了相應(yīng)的求解算法以求得最優(yōu)的裝貨順序，并通過實(shí)例驗(yàn)證了該模型的有效性。

1 問題描述

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

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

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

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

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

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

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

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

由于問題的復(fù)雜性，同時進(jìn)行約定：

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

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

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

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

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

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

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

8) 貨車僅從車輛尾部進(jìn)行卸貨；

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

2 數(shù)學(xué)模型

2.1 基本變量定義

采用坐標(biāo)系為三維笛卡爾坐標(biāo)系，以貨車車輛的長度方向?yàn)閤軸，寬度方向?yàn)閥軸，高度方向?yàn)閔軸，車輛的左后下角為坐標(biāo)原點(diǎn)(0，0，0)。設(shè)定k輛車輛的長寬高分別為Lk，Wk，Hk；所裝貨物t的長寬高分別為lt，wt，ht，如圖1。

圖1 貨車裝箱各參數(shù)定義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)來表示貨物裝車后的狀態(tài)。其中：C為貨物類型；A為卸貨地點(diǎn)；t為貨物ID；k為承運(yùn)車輛ID；放置方向和空間方位則由后7位 (zt，xst，yst，zst，xet，yet，zet)表示。

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

2.1.2 貨物裝入車輛的情況

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

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

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

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

式中：|V|為當(dāng)前可用的剩余空間的個數(shù)。

2.1.3 貨車的載重信息

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

2.1.4 貨物卸載的優(yōu)先級確定

對每個貨物按照其卸貨地點(diǎn)的遠(yuǎn)近定義其卸載優(yōu)先級：

λt=Dt/Dmax

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

2.2 裝箱約束條件

在實(shí)際的裝箱過程中會有很多約束條件，這里對各項(xiàng)約束進(jìn)行定義：

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

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。

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

7) 重心約束

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

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

2.3 目標(biāo)函數(shù)和適應(yīng)度函數(shù)的定義

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

2.3.1 空間利用函數(shù)

(1)

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

2.3.2 重量利用函數(shù)

(2)

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

2.3.3 裝卸距離函數(shù)

D=∏dt

(3)

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

2.3.4 適應(yīng)度函數(shù)

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

F()=(CR+WR)×D

(4)

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

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

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

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

3.1 求初始的可行解

一階段算法流程：

Step1:初始化車輛及貨物的相關(guān)信息，按照貨物的卸載優(yōu)先級從大到小進(jìn)行排序，貨物裝卸優(yōu)先級相同的貨物則按照貨物體積從大到小進(jìn)行排序。

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

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

3.2 蟻群算法尋找最優(yōu)解

這里不再如傳統(tǒng)的蟻群算法將信息素定義在各條子路徑上，而是將信息素定義為每個貨物的屬性，即將待裝的貨物看作是螞蟻需要尋路的路徑，貨物的裝箱順序即為螞蟻的尋路路徑。同時每次循環(huán)都是由多只螞蟻順序執(zhí)行尋路操作，和傳統(tǒng)蟻群算法將不同螞蟻放到不同的點(diǎn)上開始尋路的方式不同，文中每只螞蟻的起點(diǎn)均為所有待裝貨物中的卸載優(yōu)先級最大和體積最大的貨物。因?yàn)槭紫妊b入的貨物是固定的，必然是體積最大、運(yùn)輸最遠(yuǎn)的。不同于傳統(tǒng)蟻群算法均分初始信息素，筆者將尋路順序定義在每個貨物的信息素中，將3.1節(jié)的初始裝箱算法所生成的解作為蟻群算法的初始解，以貨物的裝箱順序分配初始信息素，以所有的貨物都裝完作為一次螞蟻尋路完成的標(biāo)志。

3.2.1 初始信息素定義

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

(5)

3.2.2 信息素的更新

(6)

(7)

3.2.3 選擇概率

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

(8)

ηtr為能見度，定義為

(9)

3.2.4 算法流程

二階段算法流程：

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

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

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

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

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

Step6：循環(huán)次數(shù)達(dá)到最大循環(huán)次數(shù)時終止，輸出當(dāng)前最優(yōu)路徑為最優(yōu)解。

4 計(jì)算結(jié)果

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

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

表1 裝箱數(shù)據(jù)contentTable 1 Packing data

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

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

將該結(jié)果運(yùn)用到3.2節(jié)中的蟻群算法中求最優(yōu)解，通過100次循環(huán)得到每次循環(huán)的最優(yōu)裝箱結(jié)果如圖2。

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

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

表3 最優(yōu)裝箱單Table 3 The optimum packing list

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

表4 裝箱結(jié)果比較Table 4 The comparison of packing results

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

5 結(jié) 論

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

[1] JOHNSON D S.計(jì)算機(jī)和難解性-NP完全性理論導(dǎo)論[M].張立昂,譯.北京:科學(xué)出版社,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].計(jì)算機(jī)學(xué)報(bào),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] 衛(wèi)家駿.一種集裝箱船配載問題改進(jìn)算法探討[J].重慶交通大學(xué)學(xué)報(bào)(自然科學(xué)版),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] 連志剛,林蔚天,曹宇,等.基于類粒子群算法的集裝箱裝載模型優(yōu)化研究[J].重慶交通大學(xué)學(xué)報(bào)(自然科學(xué)版),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].廣州:華南理工大學(xué),2013:23-40. CAO Lingzhi.StudiesonHybridSimulatedAnnealingAlgorithmforThree-dimensionalBinPackingProblems[D].Guangzhou:South China University of Technology,2013:23-40.

[11] 靳志宏,于波,侯麗曉.廂式貨車配載與配送的聯(lián)合優(yōu)化[J].交通運(yùn)輸工程學(xué)報(bào),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

四川省科技支撐計(jì)劃項(xiàng)目(2014GZ0142)；汽車及工程機(jī)械多產(chǎn)業(yè)鏈業(yè)務(wù)協(xié)同服務(wù)平臺研發(fā)(2013AA040606)

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

U492.3+12; TP301

A

1674-0696(2016)02-156-07