顏 瑞，張 群，胡 睿

?

考慮三維裝箱約束的多車場車輛路徑問題

顏 瑞1，張 群2，胡 睿2

（1.北京信息科技大學(xué)經(jīng)濟(jì)管理學(xué)院，北京 100192；2.北京科技大學(xué)東凌經(jīng)濟(jì)管理學(xué)院，北京 100083）

針對(duì)實(shí)際物流配送問題的特點(diǎn)，研究三維裝箱約束車輛路徑問題，首次建立考慮多車場的三維裝箱約束車輛路徑問題模型，并提出求解該問題的混合算法?；旌纤惴ú捎眠z傳算法求解車輛路徑問題，采用引導(dǎo)式局部搜索算法求解三維裝箱問題。通過計(jì)算標(biāo)準(zhǔn)算例檢驗(yàn)算法性能，試驗(yàn)結(jié)果表明混合算法能夠在較短時(shí)間內(nèi)得到質(zhì)量較高的近似最優(yōu)解。通過數(shù)值仿真檢驗(yàn)?zāi)Ｐ偷目山庑浴?/p>

車輛路徑問題；多車場；三維裝箱；遺傳算法

0引言

車輛路徑問題（Vehicle Routing Problem，VRP）和裝箱問題（Bin Packing Problem，BPP）都是經(jīng)典的組合優(yōu)化問題，且都屬于NP-Hard問題。在過去的幾十年里，對(duì)VRP和BPP的研究都取得了非常豐碩的成果，但是關(guān)于這兩個(gè)問題的研究是獨(dú)立進(jìn)行的。然而，現(xiàn)實(shí)的物流配送中有很多情況是需要同時(shí)考慮“裝箱”和“運(yùn)輸”這兩個(gè)問題的，比如家電、家具的送貨上門服務(wù)。這類配送問題通常具有相似的特征，比如運(yùn)輸工具是帶長方體封閉式車廂的貨車，貨物通常裝在長方體的包裝箱內(nèi)，車輛需要拼裝運(yùn)送不同體積、不同重量的貨物。對(duì)于這類問題，“裝箱”和“運(yùn)輸”這兩方面是不可分割、相互制約的，只有同時(shí)考慮這兩點(diǎn)才能即保證選擇的配送路線成本最低，又保證貨物可以全部合理地裝入車輛。近幾年，這類問題開始吸引國內(nèi)外學(xué)者的關(guān)注，并且已經(jīng)取得了一些成果。

Iori于2005年提出了二維裝箱約束限制容量車輛路徑問題（Two-Dimensional Loading Capacitated Vehicle Routing Problem，2L-CVRP）的模型，并提出啟發(fā)式算法和精確算法結(jié)合的方法進(jìn)行求解，通過大量的仿真計(jì)算檢驗(yàn)了問題的可解性和算法的可靠性[1]。2L-CVRP模型提出以后，學(xué)者們相繼提出了不同的算法對(duì)該模型進(jìn)行求解，改善了Iori最初的求解結(jié)果，這其中有分支切割法[2]、禁忌搜索算法[3]、文化基因算法[4]、模擬退火算法[5]以及改進(jìn)的禁忌搜索算法[6]。在2006年，Iori與Gendreau、Laporte等人合作提出了三維裝箱約束限制容量車輛路徑問題（Three-Dimensional Loading Capacitated Vehicle Routing Problem，3L-CVRP）的模型，并提出禁忌搜索算法進(jìn)行求解，根據(jù)實(shí)際案例設(shè)計(jì)了幾種不同約束下的模型并分別進(jìn)行求解[7]。隨后，Moura和Oliveira針對(duì)BPP和CVRP分別設(shè)計(jì)算法，采用層次方法求解BPP、采用貫序方法引導(dǎo)局部搜索的啟發(fā)式策略求解CVRP[8]。Fuellerer和Doerner等人采用蟻群算法求解3L-CVRP模型，并根據(jù)路徑和裝箱分別設(shè)計(jì)了信息素更新策略[9]。2010年，Iori和Martello對(duì)CVRP和BPP的研究進(jìn)行了系統(tǒng)的總結(jié)，明確了一些基本概念和基本問題，包括2L-CVRP、3L-CVRP及帶裝箱約束的裝卸一體旅行商問題（Traveling Salesman Problems with Pickup & Delivery and Loading Constraints， TSPPDL）等[10]。3L-CVRP考慮三維空間中的貨物和車廂，充分體現(xiàn)了實(shí)際物流配送情形，因此本文針對(duì)3L-CVRP進(jìn)行研究。

國內(nèi)關(guān)于CVRP和BPP聯(lián)合問題的研究成果相對(duì)較少。馬珊靜和陳峰等人研究了一維裝箱和車輛路徑的聯(lián)合問題，以最小化倉儲(chǔ)成本、運(yùn)輸成本和車輛運(yùn)營成本總和為目標(biāo)，提出了三種不同策略的兩階段啟發(fā)式算法進(jìn)行求解[11]。寧愛兵和熊小華等人研究了物流配送中的三維裝箱問題，考慮到三維裝箱和車輛路徑相結(jié)合的一些基本問題，并提出了一種求解三維裝箱問題的算法，但是文獻(xiàn)并沒有把兩個(gè)問題聯(lián)合起來進(jìn)行建模和求解[12]。王征和胡祥培等人針對(duì)易損、易碎物品的運(yùn)輸問題進(jìn)行研究，建立了較為完整的2L-CVRP數(shù)學(xué)模型，并提出了求解該模型的一個(gè)Memetic算法，算法中設(shè)計(jì)了一種基于深度優(yōu)先的裝箱問題求解策略，文獻(xiàn)采用Iori提出的標(biāo)準(zhǔn)算例進(jìn)行計(jì)算，全面分析了Memetic算法的求解效率、求解性能和魯棒性，試驗(yàn)取得了較為理想的結(jié)果[13]。

目前，對(duì)于3L-CVRP的研究均以經(jīng)典VRP模型為基礎(chǔ)，模型中只考慮一個(gè)配送中心的情況，這在理論上和實(shí)踐上存在很多不足。在經(jīng)典VRP模型的基礎(chǔ)之上，已經(jīng)發(fā)展出包括多車場、帶時(shí)間窗及不確定顧客需求量等諸多因素的VRP模型，而到目前為止3L-CVRP模型尚未建立考慮這些因素的模型，在理論上具有較大的研究空間?，F(xiàn)代商業(yè)模式對(duì)物流業(yè)的發(fā)展提出很高要求，最根本的要求是快速將貨物送達(dá)顧客，這需要物流企業(yè)具有較強(qiáng)的快速反應(yīng)能力和系統(tǒng)協(xié)調(diào)能力，而在一個(gè)城市或地區(qū)建立多個(gè)配送中心是實(shí)現(xiàn)這個(gè)目標(biāo)的途徑之一。在現(xiàn)代城市物流配送模式（比如電子商務(wù)網(wǎng)站的配送模式）中，銷售商通常在一個(gè)城市中擁有幾個(gè)配送中心，根據(jù)總配送距離最短的原則從不同的配送中心同時(shí)發(fā)貨，在較短的時(shí)間內(nèi)把貨物送給客戶，從整體上提高配送效率。因此，本文在研究三維裝箱約束車輛路徑問題的基礎(chǔ)之上，考慮多配送中心的情況，建立考慮三維裝箱約束多配送中心車輛路徑問題（Three-Dimensional Loading Multi-Depots Capacitated Vehicle Routing Problem，3L-MDCVRP）的混合數(shù)學(xué)模型。由于3L-MDCVRP模型是兩個(gè)NP-Hard問題的結(jié)合問題，因此為了在有效時(shí)間內(nèi)得到問題的最優(yōu)解，本文提出遺傳算法和引導(dǎo)式局部搜索算法相結(jié)合的混合算法進(jìn)行求解。

1模型建立

1.1問題描述

圖1 3L-CVRP可行配送方案示意圖

3L-CVRP模型假設(shè)：

2）每條線路上顧客的貨物總重量不能超過車輛最大載重，貨物總體積不能超過車廂最大容積，每輛車行駛距離不受限制；

3）每條回路上顧客需求的貨物必須全部裝入車廂，且滿足全部給定的裝箱約束；

4）貨物從車廂尾部的車門進(jìn)出，裝貨過程從車廂內(nèi)側(cè)左下角開始，假設(shè)裝貨工具可以把貨物擺放到車廂內(nèi)任意位置；

5）以所有車輛的行駛路程之和最小為目標(biāo)。

在模型假設(shè)中，有一個(gè)很重要的概念——裝箱約束。貨物裝箱除了要滿足車輛限重和車廂限容這兩個(gè)基本約束條件之外，還應(yīng)滿足符合實(shí)際操作的一些約束條件，比如貨物不能懸空放置、不能重疊放置以及交通法規(guī)限定的其他要求等。裝箱約束主要包括：

1）基本約束：貨物不能懸空放置、不能重疊放置，貨物總重和總裝載空間不能超過車輛載重和車廂容積。

2）方向性約束：貨物邊緣必須與相應(yīng)的車廂邊緣平行，每個(gè)貨物都是頂部朝上放置，且只能在水平面上做90°的旋轉(zhuǎn)，不能以其它角度或者在垂直面上旋轉(zhuǎn)，可參考圖2。

圖2 3L-CVRP可行裝箱方案示意圖

4）LIFO（Last-in-First-out）約束：為了縮短裝卸貨時(shí)間，貨物擺放位置需要滿足連續(xù)裝卸貨的要求，即先進(jìn)的貨物后出，先出的貨物后進(jìn)。具體描述為，當(dāng)車輛服務(wù)顧客的時(shí)候，可以從車尾門方向連續(xù)的卸載顧客的所有貨物（），且不用挪動(dòng)其他顧客的貨物。根據(jù)圖1的配送線路，線路1先經(jīng)過顧客1再經(jīng)過顧客2，那么在圖2.a的裝箱圖中，就不能出現(xiàn)（）放置于（）上方或者前方的情況。

5）易碎品約束：貨物可以分為易碎品和非易碎品。易碎品可以放置在易碎品和非易碎品之上，而非易碎品只能放置在非易碎品之上，即不能出現(xiàn)非易碎品放置在易碎品之上的情況。如圖2.a所示，易碎品可以放在易碎品之上。

本文建立的3L-MDCVRP在模型假設(shè)上有如下調(diào)整：一、有多個(gè)配送中心，每個(gè)配送中心均存儲(chǔ)和供應(yīng)足夠多的產(chǎn)品；二、每個(gè)配送中心均有相同數(shù)量相同型號(hào)的車輛，車輛從配送中心出發(fā)完成任務(wù)之后返回原配送中心。其他假設(shè)和裝箱約束均與3L-CVRP一致。

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

本文建立的3L-MDCVRP模型分為車輛路徑模型和三維裝箱模型兩個(gè)部分。

在建立模型之前，先給出模型中各個(gè)變量的符號(hào)和意義，如表1所示。

表1 模型變量及解釋

模型中的決策變量為：

建立多配送中心車輛路徑模型如下：

s.t.，，（2）

，，（3）

，，，（5）

，，（6）

，，，，（8）

，，，

模型解釋如下：目標(biāo)函數(shù)（1）表示最小化車輛行駛路程；式（2）表示所有顧客只被訪問一次；式（3）和式（4）表示車輛從某個(gè)配送中心出發(fā)，服務(wù)完所有顧客之后返回原配送中心；式（5）表示車輛進(jìn)入某節(jié)點(diǎn)，也必須從該節(jié)點(diǎn)離開；式（6）表示每輛車裝載貨物的重量之和不超過車輛限制載重；式（7）表示每輛車裝載貨物的體積之和不超過車輛限制容積；式（8）綁定了三維裝箱變量和車輛路徑變量；式（9）為支路消除約束，保證任何路線中只包含一個(gè)配送中心。

在建立三維裝箱模型之前，先建立一個(gè)笛卡爾坐標(biāo)系。坐標(biāo)系的坐標(biāo)軸分別對(duì)應(yīng)于車廂的長、寬和高，坐標(biāo)系的原點(diǎn)位于車廂內(nèi)側(cè)左下角，如圖3所示。貨物底部左后方的位置（離原點(diǎn)O最近的頂點(diǎn)）用坐標(biāo)表示，則有：

由于貨物大小不同，因此即使貨物總體積小于車廂容積，也有可能無法將所有貨物都裝入車廂?？紤]到這一點(diǎn)，本文以最大化裝入車廂內(nèi)貨物數(shù)為目標(biāo)建立三維裝箱模型，則可行解的目標(biāo)函數(shù)值等于總貨物數(shù)。三維裝箱模型如下：

s.t.，

，，（11）

，（12）

，

，

，，（14）

，，（15）

，，（16）

式（10）為目標(biāo)函數(shù)，最大化裝入車輛的總貨物數(shù)；式（11）保證了所有貨物都必須有支撐區(qū)域（不可懸空放置），且貨物不能堆疊；式（12）用以區(qū)分易碎品和非易碎品，取值為0表示貨物為易碎品，取值為1表示非易碎品，非易碎品不可放在易碎品之上；式（13）給出了決策變量；式（14）和式（15）計(jì)算貨物的長和寬；式（16）給出每輛車裝載貨物總數(shù)。模型中的變量和標(biāo)識(shí)參考文獻(xiàn)[14]和文獻(xiàn)[15]。

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

對(duì)于3L-MDCVRP這樣的NP-Hard問題，如何在較短的時(shí)間內(nèi)給出有效的解是非常重要的。處理獨(dú)立的車輛路徑問題和三維裝箱問題的時(shí)候，通常采用啟發(fā)式算法進(jìn)行求解，但是兩個(gè)問題結(jié)合起來之后，現(xiàn)有的啟發(fā)式算法已經(jīng)無法求解。本文設(shè)計(jì)3L-MDCVRP求解算法的基本思路為：1）先求出一個(gè)最優(yōu)配送線路，當(dāng)有了一個(gè)配送線路之后，每條線路上的顧客數(shù)及顧客需求貨物量就會(huì)確定下來；2）然后再對(duì)每輛車單獨(dú)設(shè)計(jì)裝箱方案，確保全部貨物裝箱并滿足所有裝箱約束；3）如果所有車輛都能完成裝箱，則最優(yōu)配送方案產(chǎn)生，否則，重新計(jì)算最優(yōu)配送線路并安排裝箱，如此循環(huán)。在此求解思路之上，本文提出一種改進(jìn)的遺傳算法和引導(dǎo)式局部搜索算法結(jié)合的混合算法進(jìn)行求解，改進(jìn)的遺傳算法（Genetic Algorithm，GA）求解車輛路徑問題，引導(dǎo)式局部搜索算法（Guided Local Search，GLS）求解裝箱問題。

在2.1節(jié)中提出改進(jìn)遺傳算法，在2.2節(jié)中給出引導(dǎo)式局部搜索啟發(fā)式算法，在2.3節(jié)中提出完整的混合啟發(fā)式算法。

2.1遺傳算法

遺傳算法是一種有效的全局搜索算法，由美國Michigan大學(xué)的J. Holland教授在1975年提出。遺傳算法是一種并行搜索算法，模擬自然進(jìn)化中的自然選擇和優(yōu)勝劣汰極值，主要包括染色體種群、選擇算子、交叉算子和變異算子等部分。本節(jié)給出遺傳算法各部分的策略，并根據(jù)3L-MDCVRP的特點(diǎn)提出一些改進(jìn)策略。

1）編碼規(guī)則。根據(jù)3L-MDCVRP模型中存在多個(gè)車場的特點(diǎn)，本文提出兩段式編碼方式，把染色體分為每個(gè)配送中心每輛車服務(wù)顧客數(shù)和車輛服務(wù)顧客順序。假設(shè)有2個(gè)配送中心、10個(gè)顧客、每個(gè)配送中心都有2輛車，則可給出一個(gè)染色體編碼方式，如圖4所示。

圖4 染色體編碼方案

圖4中給出的染色體可表示如下配送方案：配送中心1的第一輛車按順序服務(wù)顧客6和8，配送中心1的第二輛車按順序服務(wù)顧客2、10和5；配送中心2的第一輛車按順序服務(wù)顧客9、1和3，配送中心2的第二輛車按順序服務(wù)顧客7和4。

2）適應(yīng)度函數(shù)。一般文獻(xiàn)中采用目標(biāo)函數(shù)的倒數(shù)作為染色體適應(yīng)度，但是這樣計(jì)算出的適應(yīng)度值會(huì)比較小，且處理不同問題時(shí)取值范圍相差很大，因此泛化能力較差。本文提出如下公式作為適應(yīng)度函數(shù)：

3）選擇算子。選擇算子提供了遺傳進(jìn)化的驅(qū)動(dòng)力，驅(qū)動(dòng)力太大則遺傳搜索會(huì)過早終止，驅(qū)動(dòng)力太小則進(jìn)化過程會(huì)非常緩慢。本文采用Holland提出的輪盤賭選擇策略，其基本原理是根據(jù)每個(gè)染色體適應(yīng)度的比例來確定該個(gè)體的選擇概率或生存概率[16]。

4）交叉算子。交叉操作是交換兩個(gè)父代染色體部分基因的遺傳操作。根據(jù)交叉概率選擇進(jìn)入配對(duì)池的父代個(gè)體，把配對(duì)染色體的部分基因加以替換重組，產(chǎn)生子代個(gè)體。根據(jù)染色體編碼由兩部分組成的特點(diǎn)，本文提出一種混合交叉算子，具體操作方式為：第一部分采用均勻交叉；第二部分采用順序交叉。均勻交叉算子：首先隨機(jī)產(chǎn)生一個(gè)與染色體第一部分基因串等長的二進(jìn)制串，0表示不交換，1表示交換，根據(jù)二進(jìn)制串判斷是否交換父代個(gè)體對(duì)應(yīng)位置上的基因。由于染色體中沒有表示配送中心的基因，因此需要采用新的順序交叉算子。順序交叉算子：在父代染色體的第一部分基因串中隨機(jī)選擇一個(gè)基因，該基因?qū)?yīng)的數(shù)字作為第二部分基因串的交叉段，然后把交叉段內(nèi)的基因互換，把換出基因放在換入基因原來的位置上，當(dāng)父代基因?qū)?yīng)的數(shù)字不相同時(shí)，第二個(gè)父代向后移動(dòng)至數(shù)字相同位置，如找不到相同數(shù)字則取消本次交叉操作。如圖5所示，以A和B兩個(gè)父代個(gè)體為例進(jìn)行混合交叉操作，X為二進(jìn)制串，設(shè)產(chǎn)生的子代個(gè)體為C和D。

圖5 染色體交叉操作

圖6 染色體變異操作

6）非可行解調(diào)整。經(jīng)過交叉操作和變異操作，染色體對(duì)應(yīng)的解可能變成非可行解，因此需要對(duì)其進(jìn)行調(diào)整。顧客數(shù)是固定的，因此染色體第一部分基因串上的數(shù)字之和必須等于顧客數(shù)，當(dāng)基因值之和小于顧客數(shù)時(shí)，隨機(jī)選擇一個(gè)基因值加1，當(dāng)基因值之和大于顧客數(shù)時(shí)，隨機(jī)選擇一個(gè)基因值減1，重復(fù)操作至基因值之和與顧客數(shù)相等為止。在生成初始種群及進(jìn)行遺傳操作的時(shí)候，可能會(huì)有一些染色體不符合模型中的一個(gè)或多個(gè)約束條件。顯然對(duì)于本文的染色體編碼方式，所有染色體都自然滿足約束（2）、（3）、（8）和（9），因此，調(diào)整非可行解的時(shí)候只須檢查約束（4）、（5）、（6）和（7）。采用的約束控制策略是根據(jù)染色體對(duì)約束的違反程度降低其適應(yīng)度值。

6）記憶庫。為了減少3L-CVRP的求解時(shí)間，本文在遺傳算法中加入記憶庫機(jī)制，具體作用在后面給出，這里只給出記憶庫的形成原理。設(shè)定記憶庫的最大規(guī)模為，把每代種群中的最優(yōu)個(gè)體保存到記憶庫中，當(dāng)最優(yōu)個(gè)體數(shù)超過記憶庫規(guī)模時(shí)，去掉記憶庫中適應(yīng)度最小的個(gè)體。當(dāng)遺傳算法達(dá)到最大迭代次數(shù)之后，把當(dāng)前種群全部加入記憶庫中，按適應(yīng)度值從大到小排列所有個(gè)體，刪除適應(yīng)度較小的個(gè)體，維持記憶庫規(guī)模為。

2.2引導(dǎo)式局部搜索

本節(jié)討論如何把貨物裝入車廂內(nèi)，且滿足第1章中的裝載約束。一般裝箱問題以裝載貨物數(shù)最大為目標(biāo)，而3L-MDCVRP的裝箱問題中每輛車裝載的貨物數(shù)是固定的，因此其解空間僅是一般裝箱問題解空間的一個(gè)子集。針對(duì)這樣的特點(diǎn)，設(shè)計(jì)算法的時(shí)候只須要在局部進(jìn)行搜索即可，通過一系列的引導(dǎo)策略尋找問題的局部最優(yōu)解。3L-MDCVRP的裝箱過程包括確定貨物的裝載順序和尋找可行的裝貨位置兩個(gè)子問題，下面分別給出這兩個(gè)子問題的求解策略：

3）可行裝貨位置順序。初始可行裝貨位置均在（0,0,0）點(diǎn)上，如圖7-a所示。裝入一個(gè)貨物之后，可行裝貨位置更新，產(chǎn)生A1、A2和A3三個(gè)可行裝貨位置，如圖7-b所示。對(duì)于裝貨序列中的下一個(gè)待裝貨物，需要給出一個(gè)可行裝貨位置的順序，然后逐個(gè)掃描這些位置，直至找到一個(gè)滿足所有裝載約束的可行位置，每個(gè)貨物需要在兩個(gè)方向上進(jìn)行掃描（水平方向可旋轉(zhuǎn)90度）。本文采用引導(dǎo)式排序方法給出可行裝貨位置順序，引導(dǎo)式排序方法包括“Back-Left-Low”、“Left-Back-Low”、“Max-Touching-Area-Y”、“Max-Touching-Area-No-Walls-Y”、“Max-Touching-Area-X”及“Max-Touching-No-Walls-X”等六種[17]，依次選擇六種方法中的一個(gè)，直至找到可行裝載方案。六種規(guī)則的具體操作方法可參考文獻(xiàn)[17]。

圖7 可行裝貨位置示意圖

2.3混合啟發(fā)式算法

本文把改進(jìn)遺傳算法和裝箱啟發(fā)式算法結(jié)合起來，構(gòu)造求解3L-MDCVRP的引導(dǎo)式局部搜索遺傳算法（Guided Local Search Genetic Algorithm，GLSGA）。GLSGA的基本思路為：通過改進(jìn)遺傳算法得出VRP的近似最優(yōu)解，近似最優(yōu)解保存在記憶庫中；把記憶庫中的個(gè)體按適應(yīng)度值從大到小排列，選擇第一個(gè)解作為當(dāng)前車輛路線方案，然后調(diào)用裝箱問題的啟發(fā)式算法；如果找到可行裝箱方案，則返回最優(yōu)解，否則，選擇記憶庫中的下一個(gè)解作為車輛路線方案；如果記憶庫中所有車輛路線方案均找不到可行解，則返回遺傳算法重新求解VRP；重復(fù)算法直至找到可行解，或達(dá)到最大迭代次數(shù)。

GLSGA的具體步驟如下：

Step2.遺傳算法參數(shù)初始化：設(shè)定遺傳算法的種群規(guī)模和記憶庫規(guī)模，設(shè)定交叉概率和變異概率，確定最大迭代次數(shù)，令；

Step3.初始種群生成：對(duì)染色體進(jìn)行編碼，用隨機(jī)方法產(chǎn)生初始種群；

Step4.記憶庫更新：計(jì)算染色體適應(yīng)度，把當(dāng)前種群中的最優(yōu)個(gè)體保存進(jìn)記憶庫，若記憶庫規(guī)模超過，則去掉適應(yīng)度值較小的個(gè)體；

Step5.遺傳操作：對(duì)當(dāng)前種群進(jìn)行選擇、交叉和變異等遺傳操作；

Step7.近似最優(yōu)解集生成：遺傳算法終止，把當(dāng)前種群全部加入記憶庫中，并按適應(yīng)度值排列染色體，保留適應(yīng)度值最大的個(gè)染色體形成近似最優(yōu)解集；

Step10.初始裝貨序列：按照車輛服務(wù)顧客順序的相反順序排列貨物，相同顧客的貨物按照非易碎品在前、易碎品在后的順序排列；

Step13.可行裝貨位置循環(huán)：若所有貨物均找到可行裝貨位置，算法終止，輸出當(dāng)前最優(yōu)解；若有一個(gè)或多個(gè)貨物沒找到可行裝貨位置，且，令，返回Step12；若，轉(zhuǎn)Step14；

GLSGA算法流程如圖5所示。

圖5 GLSGA算法流程圖

3數(shù)值試驗(yàn)

數(shù)值試驗(yàn)平臺(tái)為：Matlab 7.1，計(jì)算機(jī)CPU為英特爾酷睿2、2.67GHz，2GB內(nèi)存，32位windows 7操作系統(tǒng)。

由于標(biāo)準(zhǔn)算例庫中的問題均為單配送中心問題，因此本人設(shè)計(jì)兩個(gè)數(shù)值模擬試驗(yàn)：第一個(gè)試驗(yàn)針對(duì)標(biāo)準(zhǔn)算例進(jìn)行計(jì)算，檢驗(yàn)GLSGA算法的有效性；第二個(gè)試驗(yàn)針對(duì)隨機(jī)數(shù)據(jù)進(jìn)行仿真，檢驗(yàn)?zāi)Ｐ偷目山庑浴?/p>

3.1標(biāo)準(zhǔn)算例庫試驗(yàn)

目前研究3L-CVRP問題的文獻(xiàn)較少，作者能夠搜集到的全部相關(guān)文獻(xiàn)均已附在參考文獻(xiàn)中。已發(fā)表的文獻(xiàn)均直接采用文獻(xiàn)[7]的模型，模型同時(shí)處理車輛路徑問題和裝箱問題，并提出一些不同的算法進(jìn)行求解，同時(shí)以文獻(xiàn)[7]給出的標(biāo)準(zhǔn)算例庫進(jìn)行數(shù)值試驗(yàn)。目前，該算例庫是僅有的3L-CVRP標(biāo)準(zhǔn)算例庫，針對(duì)文獻(xiàn)[7]的標(biāo)準(zhǔn)算例進(jìn)行數(shù)值試驗(yàn)，以檢驗(yàn)本文所提出新算法的性能。

算例庫中總計(jì)包括27個(gè)3L-CVRP標(biāo)準(zhǔn)算例。算例包含的信息有：配送中心坐標(biāo)，顧客數(shù)及顧客坐標(biāo)；每個(gè)顧客需求的貨物及其需求貨物的重量；每個(gè)貨物的長、寬、高，易碎品與非易碎品標(biāo)識(shí)；配送中心擁有車輛數(shù)，車輛最大載重，車廂的長、寬、高。貨物堆疊的時(shí)候，支撐面積與上層貨物底面積的比例最小值為=0.75。

為了在檢驗(yàn)算法性能的時(shí)候避開模型的影響，該試驗(yàn)直接采用文獻(xiàn)[7]的模型，使用本文設(shè)計(jì)的GLSGA算法進(jìn)行求解。表1給出滿足所有裝箱約束的計(jì)算結(jié)果，以及與其它文獻(xiàn)計(jì)算結(jié)果的比較。

表1 3L-CVRP算例計(jì)算結(jié)果及與其它方法比較

從計(jì)算結(jié)果上看，GLSGA算法的計(jì)算結(jié)果較TS算法和GTS算法有明顯的改善，27個(gè)標(biāo)準(zhǔn)算例的車輛行駛路程幾乎全部減少。與TS算法相比平均路程減少6.38%、最大減幅為14.95%，與GTS算法相比平均路程減少2.16%、最大減幅6.96%。從計(jì)算時(shí)間上看，GLSGA算法較TS算法和GTS算法有大幅度的降低，與TS算法相比平均時(shí)間減少57.06%、最大減幅為82.93%，與GTS算法相比平均時(shí)間減少40.89%、最大減幅為69.79%。通過與已有文獻(xiàn)的計(jì)算結(jié)果相比，表明GLSGA算法具有良好的計(jì)算性能和較高的計(jì)算效率。由于已有文獻(xiàn)的模型均采用Iori提出的基本3L-CVRP模型，而該試驗(yàn)直接在模型上運(yùn)行GLSGA算法，因此可以判斷本文得到的計(jì)算結(jié)果是由GLSGA算法產(chǎn)生的。

3.2隨機(jī)數(shù)據(jù)仿真試驗(yàn)

在驗(yàn)證了GLSGA算法的有效性之后，可以用該算法求解3L-MDCVRP模型。首先，給出一個(gè)有2個(gè)配送中心、20個(gè)顧客、每個(gè)配送中心有4輛車（車輛限重500、限容1000）的3L-MDCVRP實(shí)例，表2給出隨機(jī)產(chǎn)生的配送中心和顧客節(jié)點(diǎn)坐標(biāo)，表3、表4給出每個(gè)顧客需求的貨物規(guī)格。

計(jì)算得出5條線路，總有效路程為4.2435，所有車輛均滿足裝箱約束，最優(yōu)配送路徑如圖9所示。

R1={Depot1-13-11-12-10-Depot1}，總路程為1.0376，載貨總重為302，載貨總體積為795；

表2 隨機(jī)產(chǎn)生的配送中心和顧客節(jié)點(diǎn)坐標(biāo)

R2={Depot1-3-6-17-5-Depot1}，總路程為0.6697，載貨總重為342，載貨總體積為561；

R3={Depot1-15-9-18-20-Depot1}，總路程為0.5773，載貨總重為400，載貨總體積為508；

R4={Depot2-7-8-14-19-Depot2}，總路程為0.9359，載貨總重為391，載貨總體積為855；

R5={Depot2-16-2-1-4-Depot2}，總路程為1.023，載貨總重為426，載貨總體積為706。

表3每個(gè)顧客需求的貨物規(guī)格

顧客序號(hào)貨物序號(hào)顧客序號(hào)貨物序號(hào)顧客序號(hào)貨物序號(hào)顧客序號(hào)貨物序號(hào) 121,76171119169,22 223718,12125,25174 3308241331827,1 410,26,1698,21429,281914,15 51110201513206

表4貨物規(guī)格（長、寬、高及重量）

貨物序號(hào)長寬高重量貨物序號(hào)長寬高重量 1256121627640 2638891753773 3（易碎）3753018（易碎）26827 4864841976517 5654712065894 6862642126316 7485902253559 82867923（易碎）45633 9（易碎）376642476689 10335612554690 11（易碎）665982654383 123385227（易碎）47260 13274962882691 14773282985348 15383563074387

圖9 最優(yōu)配送路徑示意圖

4結(jié)論

本文研究多車場車輛路徑和三維裝箱相結(jié)合的組合優(yōu)化問題，在3L-CVRP模型中首次考慮多車場的情況，建立3L-MDCVRP模型，并提出遺傳算法和引導(dǎo)式局部搜索算法結(jié)合的GLSGA算法進(jìn)行求解，針對(duì)3L-MDCVRP問題的特點(diǎn)提出遺傳算法的改進(jìn)策略。本文設(shè)計(jì)了標(biāo)準(zhǔn)算例庫和隨機(jī)數(shù)據(jù)兩個(gè)數(shù)值試驗(yàn)，兩個(gè)試驗(yàn)均取得了非常理想的結(jié)果。首先采用27個(gè)標(biāo)準(zhǔn)算例檢驗(yàn)GLSGA算法的性能和效率，試驗(yàn)結(jié)果表明GLSGA算法能夠很好的處理3L-CVRP這類問題。然后根據(jù)3L-MDCVRP模型的要求隨機(jī)生成仿真數(shù)據(jù)進(jìn)行測試，試驗(yàn)結(jié)果表明3L-MDCVRP模型可以用GLSGA算法進(jìn)行求解。

3L-MDCVRP建立了考慮多車場和三維裝箱的物流配送模型，極大地滿足了實(shí)際物流配送的要求。下一步還可以考慮加入時(shí)間窗、多車型等更多因素的模型，并根據(jù)實(shí)際情況設(shè)計(jì)不同的目標(biāo)函數(shù)建立模型，從理論上進(jìn)一步完善3L-CVRP模型體系。

[1] Iori M. Meta-heuristic algorithm for combinatorial optimization problems[J]. 4OR: A Quarterly Journal of Operations Research, 2005, 3(2): 163-166.

[2] Iori M,Salazar-Gonzalez JJ, Vigo D. An exact approach for the vehicle routing problem with two-dimensional loading constraints[J]. Transportation Science, 2007, 41(2): 253-264.

[3] Gendreau M, Iori M, Laporte G,. A tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints[J]. Networks, 2008, 51(1): 4-18.

[4] Khebbache S, Prins C, Yalaoui A,. Memetic algorithm for two-dimensional loading capacitated vehicle routing problem with time windows[C]. International Conference on Computers and Industrial Engineering, 2009, 1(3): 1110-1113.

[5] Leung S, Zheng J, Zhang D,. Simulated annealing for the vehicle routing problem with two-dimensional loading constraints[J]. Flexible Services and Manufacturing Journal, 2010: 1-22.

[6] Leung SCH, Zhou X, Zhang D,. Extended guided tabu search and a new packing algorithm for the two-algorithm loading vehicle routing problem [J]. Computers & Operations Research, 2011, 38(1): 205-215.

[7] Gendreau M, Iori M, Laporte G,. A tabu search algorithm for a routing and container loading problem[J]. Transportation Science, 2006, 40(3): 342-350.

[8] Moura A, Oliveira J. An integrated approach to the vehicle routing and container loading problems[J]. OR Spectrum, 2009, 31(4): 775-800.

[9] Fuellerer G, Doerner KF, Hartl RF,. Metaheuristics for vehicle routing problems with three-dimensional loading constraints[J]. European Journal of Operational Research, 2010, 201(3): 751-759.

[10] Iori M, Martello S. Routing problems with loading constraints[J]. TOP, 2010, 18(1): 4-27.

[11] 馬珊靜，陳峰，宋德朝，越庫配送物流系統(tǒng)車輛調(diào)度算法的研究[J]. 現(xiàn)代制造工程，2009（1）：12-15，127.

[12] 寧愛兵，熊小華，馬良. 城市物流配送中的三維裝箱算法[J]. 計(jì)算機(jī)工程與應(yīng)用，2009，45（9）：207-208，211.

[13] 王征，胡祥培，王旭坪. 帶二維裝箱約束的物流配送車輛路徑問題[J]. 系統(tǒng)工程理論與實(shí)踐，2011，31（12）：2328-2341.

[14] Ruan QF, Zhang ZQ, Miao LX,. A hybrid approach for the vehicle routing problem with three-dimensional loading constraints[J]. Computers & Operations Research, 2011, 38(11): 1-11.

[15] Junqueira L, Morabito R, Yamashita DS. Three-dimensional container loading modes with cargo stability and load bearing constraints[J]. Computers & Operations Research, 2012, 39(1): 74-85.

[16] Holland J. Adaptation in Natural and Artificial System[M]. Cambridge: MIT Press, 1992.

[17] Tarantilis CD, Zachariadis EE, Kiranoudis CT. A Hybrid Metaheuristic Algorithm for the Integrated Vehicle Routing and Three-Dimensional Container-Loading Problem[C].Transactions on Intelligent Transportation Systems, 10(2): 255-271.

Multi-Depots Vehicle Routing Problem with Three-Dimensional Loading Constraints

YAN Rui1, ZHANG Qun2, HU Rui2

(1. School of Economics and Management, Beijing Information Science & Technology University, Beijing 100192, China;2. Dongling School of Economics and Management, University of Science & Technology Beijing, Beijing 100083, China)

The 3L-MDCVRP (Three-Dimensional Loading Multi-Depots Capacitated Vehicle Routing Problem, 3L-MDCVRP) is a new proposed optimization problem, which is a combination of loading problem and VRP problem based on multi-depots. There are several constraints for 3L-MDCVRP: 1) the demand of a certain set of customers; 2) a feasible placement of items within the loading space;and 3) a fleet of identical vehicles of limited capacity based onseveral depots.Loading items into vehicles and successive routing of vehicles along the road network are the most important problems in distribution management.

This paper addressed an important problem combining three-dimensional loading and multi-depots vehicle routing problems. A brand new solution has been proposed. The new algorithm was a combination of two intelligent algorithms and it passed the test with good performance.

Both the capacity vehicle routing problem and three-dimensional problem are NP-hard problems.Thus,the combinatorial problem 3L-MDCVRP is clearly also the case. Exact algorithmic methodologies are not expected to solve the real-world problems of large customers and item sets in a reasonable time. Therefore, we solve the problem by using a heuristics algorithm named Guided Local Search Genetic Algorithm (GLSGA), which makes use of fast packing heuristics for the loading. The hybrid algorithm combines two different heuristic information measures: a genetic algorithm for routing because of its specialty in finding local optima, and a guided local search algorithm for loading.

The algorithm was tested on the set of benchmark instances proposed by Gendreau and Iori. These instances were the only 3L-CVRP instances available in all publications. It had been shown that the new algorithm had a better performance than the benchmark approach when all loading restrictions were satisfied.Both the distance and calculationtime were significantly reduced.There was a 6.38% decrease compared with TS in distance and a 2.16% compared with GTS. In addition, there was a 57.06% reduction compared with TS in calculationtime and 40.89% compared with GTS.

After the efficiency of GLSGA had been proved, it was applied in an experiment of 3L-MDCVRP instance, which was generated randomly. The algorithm derived the solution pretty and all five results were available in the real delivery process after checking.This new GLSGA was capable of improving the efficiency of solving 3L-MDCVRP, which was quite meaningful in the distribution process since it was able to control logistics cost and increase the utilization of vehicles.

vehicle routing problem; multi-depots; three-dimensional packing; genetic algorithm

中文編輯：杜 ?。挥⑽木庉嫞篊harlie C. Chen

0224

A

1004-6062(2016)01-0108-09

10.13587/j.cnki.jieem.2016.01.013

2012-11-12

2013-09-09

國家重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)劃資助項(xiàng)目（973，子課題）(2010CB955903-1)；國家自然科學(xué)基金資助項(xiàng)目（71172168）

顏瑞（1986—），男，江蘇連云港人，博士研究生，研究方向：物流優(yōu)化、車輛路徑。