考慮二維裝箱約束的多車場(chǎng)帶時(shí)間窗的車輛路徑問(wèn)題模型及算法研究

顏 瑞，朱曉寧，張 群，戚耀元，藺俞錚

(1. 北京信息科技大學(xué)，北京 100192；2.北京科技大學(xué)，北京 100083)

?

考慮二維裝箱約束的多車場(chǎng)帶時(shí)間窗的車輛路徑問(wèn)題模型及算法研究

顏 瑞1，朱曉寧2，張 群2，戚耀元2，藺俞錚1

(1. 北京信息科技大學(xué)，北京 100192；2.北京科技大學(xué)，北京 100083)

研究包含時(shí)間窗、多車場(chǎng)因素的二維裝箱車輛路徑問(wèn)題，建立相應(yīng)的數(shù)學(xué)模型，并提出求解該問(wèn)題的一種新的混合算法，混合算法由量子粒子群算法和引導(dǎo)式局部搜索算法組成。其中，量子粒子群算法用于求解車輛路徑問(wèn)題，引導(dǎo)式局部搜索算法用于求解可行裝箱方案。在引導(dǎo)式局部搜索算法中，提出一種基于最小浪費(fèi)原則的啟發(fā)式裝箱規(guī)則，以靈活確定待裝貨物和裝貨空間之間的匹配關(guān)系，減少重復(fù)確定裝箱方案所消耗的時(shí)間。設(shè)計(jì)了兩組數(shù)值試驗(yàn)：第一組基于標(biāo)準(zhǔn)算例庫(kù)，并將混合算法計(jì)算結(jié)果與已有文獻(xiàn)中的結(jié)果進(jìn)行對(duì)比；第二組基于隨機(jī)生成的新算例，新算例給出多車場(chǎng)和時(shí)間窗數(shù)據(jù)，用于演示混合算法對(duì)新模型的計(jì)算過(guò)程和計(jì)算結(jié)果。兩組數(shù)值試驗(yàn)的結(jié)果表明，混合算法在效率和性能方面均有較好的表現(xiàn)，計(jì)算結(jié)果和計(jì)算時(shí)間均優(yōu)于已有文獻(xiàn)，且混合算法能夠較好的求解包含時(shí)間窗、多車場(chǎng)因素的二維裝箱車輛路徑問(wèn)題模型。

車輛路徑問(wèn)題；二維裝箱問(wèn)題；量子粒子群算法；多車場(chǎng)；時(shí)間窗

1 引言

二維裝箱約束的車輛路徑問(wèn)題(Two-Dimensional Loading Capacitated Vehicle Routing Problem，2L-CVRP)是帶容量約束的車輛路徑問(wèn)題(Capacitated Vehicle Routing Problem，CVRP)和二維裝箱問(wèn)題(Two-Dimensional Bin Packing Problem，2BPP)的聯(lián)合優(yōu)化問(wèn)題，近年來(lái)逐漸引起了相關(guān)領(lǐng)域?qū)W者的關(guān)注?，F(xiàn)實(shí)的物流配送中有很多情況歸屬于2L-CVRP。比如，由于易碎、易損等原因，在物流配送過(guò)程中經(jīng)常存在貨物不可相互疊放的情況，那么貨物能否裝車就取決于貨物底面能否拼裝入車廂底面中。對(duì)于這類問(wèn)題，“裝箱”和“運(yùn)輸”這兩方面是不可分割、相互制約的，只有綜合考慮這兩點(diǎn)才能既保證選擇的配送路線成本最低，又保證貨物可以全部合理地裝入車廂。由于CVRP和2BPP均屬于NP-hard問(wèn)題[1-3]，且配送物品能否順利裝箱、裝箱順序等都會(huì)影響車輛配送任務(wù)的分配及配送路徑的規(guī)劃。因此2L-CVRP的啟發(fā)式求解策略難以提煉，大規(guī)模問(wèn)題的求解效率有待提高。2L-CVRP由Iori于2005年最早開始研究，目前為止大部分相關(guān)文獻(xiàn)均注重研究更高效的求解算法，鮮有在模型方面進(jìn)行改進(jìn)的研究成果[2]。

很多學(xué)者提出了不同的算法對(duì)2L-CVRP問(wèn)題進(jìn)行求解，改善了Iori最初求解結(jié)果。Gendreau等[4]提出了禁忌搜索算法用于優(yōu)化裝箱問(wèn)題的求解策略，算法中對(duì)于非可行解賦予一定的懲罰值，設(shè)計(jì)了一種不同線路中客戶交換的鄰域搜索策略，并運(yùn)用分支定界法檢測(cè)裝箱可行性。Zachariadis等[3]在Gendreau等人的研究成果之上，結(jié)合禁忌搜索算法與引導(dǎo)性局部搜索策略，提出了引導(dǎo)性禁忌搜索算法，在一定程度上降低了產(chǎn)生低質(zhì)量解的可能性，提高了算法的效率。Leung等[5]改進(jìn)了引導(dǎo)性禁忌搜索算法，并融入模擬退火算法的思想，進(jìn)一步提升了算法求解精度。Fllellerera等[6]以蟻群算法為主導(dǎo)，融入了同時(shí)考慮裝箱和路徑的啟發(fā)式策略，并對(duì)2L-CVRP的四個(gè)變種問(wèn)題分別進(jìn)行了研究，在Iori提出的標(biāo)準(zhǔn)算例庫(kù)上取得了較好的測(cè)試結(jié)果。Duhamel等[7]將貪婪隨機(jī)自適應(yīng)搜索算法與進(jìn)化迭代局部搜索算法 (GRASP×ELS) 相結(jié)合，計(jì)算結(jié)果與之前文獻(xiàn)中的結(jié)果相比有了較明顯的改善，但其模型并未考慮貨物的裝卸順序。2010年，Iori和Martello[8]對(duì)CVRP和BPP的研究進(jìn)行了系統(tǒng)的總結(jié)，明確了一些基本概念和基本問(wèn)題，包括2L-CVRP、3L-CVRP及帶裝箱約束的裝卸一體旅行商問(wèn)題(Traveling Salesman Problems with Pickup & Delivery and Loading Constraints， TSPPDL)等。文獻(xiàn)[9,10]針對(duì)2L-CVRP的有向有序的變種問(wèn)題，分別提出了兩種分支定界法進(jìn)行求解。Zachariadis等[11]近期又提出了一種改進(jìn)的元啟發(fā)式算法，該算法顯示出了良好的性能并且改善了很多標(biāo)準(zhǔn)算例庫(kù)中已有的最優(yōu)結(jié)果。文獻(xiàn)[12]應(yīng)用分支切割法求解3L-CVRP問(wèn)題，該算法使用了幾種技術(shù)來(lái)修剪樹枝和削減枚舉樹，在較短的計(jì)算時(shí)間內(nèi)得出較佳的解決方案。最近，Wei等[1]提出了可變鄰域搜索算法解決路徑規(guī)劃問(wèn)題，并采用基于“skyline”啟發(fā)式搜索策略的算法檢驗(yàn)裝箱約束，并通過(guò)標(biāo)準(zhǔn)算例庫(kù)驗(yàn)證了該方法的有效性，但是其研究主要針對(duì)的是無(wú)向有序2L-CVRP問(wèn)題。Zachariadis等[13]研究了同時(shí)考慮客戶加載需求和裝箱約束的二維配送車輛路徑優(yōu)化問(wèn)題，這是2L-CVRP的一個(gè)變種問(wèn)題。從管理的角度來(lái)看，服務(wù)的交付和選擇可能會(huì)帶來(lái)可觀的成本節(jié)約，但在合理時(shí)間內(nèi)完成廣義負(fù)載限制的計(jì)算是比較困難的，雖然其在算法中增加了后進(jìn)先出約束，并禁止路徑重排，在提高計(jì)算速度的同時(shí)降低了最優(yōu)解質(zhì)量。

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

在基本的2L-CVRP問(wèn)題中，僅假設(shè)有一個(gè)中心車場(chǎng)，客戶的需求被定義為若干個(gè)有重量的二維矩形物體，而車輛擁有相同的載重限制和裝載空間限制。相比2L-CVRP問(wèn)題，本文所研究的考慮二維裝箱約束的多車場(chǎng)帶時(shí)間窗車輛路徑問(wèn)題更具有普適性，現(xiàn)實(shí)中大量的物流車輛調(diào)度問(wèn)題都可以歸結(jié)為此類問(wèn)題：車輛分布于不同物理地點(diǎn)上的車場(chǎng)，他們要將貨物合理地裝入車廂，并且用最低的成本在要求的時(shí)間范圍內(nèi)將指定數(shù)量的物品送達(dá)顧客，最后返回車場(chǎng)。將時(shí)間窗加入車輛配送路徑問(wèn)題方面已有一些研究成果。Errico等[18]研究考慮硬時(shí)間窗和隨機(jī)服務(wù)時(shí)間的車輛路徑優(yōu)化問(wèn)題，并改進(jìn)了標(biāo)簽算法，通過(guò)適當(dāng)選擇標(biāo)簽組件，制定上下邊界的部分路徑從而降低成本，取得了較好的解決方案。Keskin和Catay[19]研究了帶時(shí)間窗的電動(dòng)汽車車輛路徑問(wèn)題。但是上述文獻(xiàn)并未綜合考慮裝箱約束和多車場(chǎng)問(wèn)題。文獻(xiàn)[20]研究了多車場(chǎng)帶時(shí)間窗CVRP問(wèn)題，建立了該問(wèn)題的整數(shù)規(guī)劃數(shù)學(xué)模型，提出了一種改進(jìn)變鄰域搜索算法，但未考慮裝箱約束。“二維裝箱”、“多車場(chǎng)”與“時(shí)間窗”分別在問(wèn)題的空間、時(shí)間、流程等方面施加了多重約束，使原本具有NP復(fù)雜性的問(wèn)題更加難以求解。

在第2章中，給出考慮二維裝箱約束的多車場(chǎng)帶時(shí)間窗車輛路徑問(wèn)題(Two-Dimensional Loading Capacitated Vehicle Routing Problem with Multi-Depots and Time Window，2L-CVRP-MDTW)的基本概念和假設(shè)，并在此基礎(chǔ)之上建立完整的數(shù)學(xué)模型。在第3章中，提出量子粒子群算法和引導(dǎo)式局部搜索算法結(jié)合的混合算法，詳細(xì)描述算法的策略和實(shí)施步驟。在第4章中，進(jìn)行了兩組數(shù)值試驗(yàn)，分析混合算法的性能和效率，演示2L-CVRP-MDTW模型的求解過(guò)程進(jìn)行。

2 模型建立

2.1 問(wèn)題描述

2.2 模型假設(shè)

本文對(duì)2L-CVRP-MDTW模型做出如下假設(shè)：

(1)假設(shè)每個(gè)車場(chǎng)處均有一個(gè)儲(chǔ)貨量充足的倉(cāng)庫(kù)，且每個(gè)車場(chǎng)的車輛僅從同一位置的倉(cāng)庫(kù)裝貨；

(2)確定若干條回路作為車輛行駛路線，每條線路的總距離不能超過(guò)車輛最大行駛距離，所有回路均從車場(chǎng)出發(fā)并返回車場(chǎng)，每個(gè)顧客僅能在一條回路上，每條回路上的顧客僅由一輛車服務(wù)；

(3)每條線路上顧客的貨物總重量不能超過(guò)車輛載重、貨物總占地面積不能超過(guò)車廂面積；

(4)每條線路上顧客需求的貨物必須全部裝入車廂，且滿足全部給定的裝箱約束：貨物不能重疊放置，貨物邊緣必須與相應(yīng)車廂邊緣平行，貨物不可旋轉(zhuǎn)，在服務(wù)當(dāng)前顧客時(shí)不用挪動(dòng)其他顧客的貨物(后進(jìn)先出原則)；

(5)貨物從車廂尾部的車門進(jìn)出，假設(shè)裝貨工具可以把貨物擺放到車廂內(nèi)任意位置；

(6)車輛必須在顧客的時(shí)間窗內(nèi)為其提供服務(wù)，不考慮車輛進(jìn)出車場(chǎng)的時(shí)間窗；

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

圖1給出了一個(gè)2L-CVRP-MDTW模型示意圖，模型包括2個(gè)車場(chǎng)、9個(gè)顧客和21個(gè)貨物。

圖1 2L-CVRP-MDTW模型示意圖

模型中的線路有兩條：車場(chǎng)Ⅰ- 1 - 2 - 3 - 4 - 5 -車場(chǎng)Ⅰ；車場(chǎng)Ⅱ- 6 - 7 - 8 - 9 -車場(chǎng)Ⅱ。車輛裝載方案如圖2所示。

圖2 2L-CVRP-MDTW模型裝箱方案示意圖

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

在建立數(shù)學(xué)模型之前，需要先建立一個(gè)笛卡爾坐標(biāo)系。坐標(biāo)系的坐標(biāo)軸分別對(duì)應(yīng)車廂的長(zhǎng)和寬，坐標(biāo)系的原點(diǎn)對(duì)應(yīng)車廂左上角。貨物左上角的位置用坐標(biāo)(x,y)表示，則有：

從而可以將車廂分割成若干個(gè)網(wǎng)格，如圖3所示。

圖3 車廂網(wǎng)格圖和笛卡爾坐標(biāo)系

表1給出數(shù)學(xué)模型中所用到的符號(hào)。

模型的決策變量有：

其中，i,i′=1,…,n+T,p=1,2,…,Pt,t=1,…,T。

表1 模型符號(hào)及符號(hào)解釋

基于上述定義，建立2L-CVRP-MDTW的數(shù)學(xué)模型如下：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

0≤xik≤W-wik,k=1,2,…,mi,i=1,2,…,n,

(8)

0≤yik≤L-lik,k=1,2,…,mi,i=1,2,…,n,

(9)

(10)

(11)

max(llkk′ii′,wwkk′ii′)≥0,k=1,2,…,mi,k′=1,2,…,mi′,i,i′=1,2,…,n,若i=i′,則k≠k′,

(12)

(13)

(14)

(15)

式(1)為目標(biāo)函數(shù)，表示最小化車輛行駛總路程；式(2)表示每個(gè)顧客僅能在一條回路上；式(3)～(5)表示車輛進(jìn)入某個(gè)節(jié)點(diǎn)則必須從該節(jié)點(diǎn)離開；式(6)表示每輛車裝載的貨物不能超過(guò)車輛載重；式(7)表示每輛車所裝載貨物的總面積不超過(guò)車輛底面積；式(8)和式(9)表示貨物不能超過(guò)車廂邊界；式(10)、式(11)和式(12)表示貨物不能重疊放置；式(13)表示滿足后進(jìn)先出原則；式(14)和式(15)表示在時(shí)間窗內(nèi)服務(wù)顧客。

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

目前，已有文獻(xiàn)中的優(yōu)化算法均不能夠直接用于求解2L-CVRP-MDTW模型。在分別研究考慮二維裝箱約束、多車場(chǎng)和時(shí)間窗等因素的車輛路徑問(wèn)題求解算法的基礎(chǔ)之上，本文提出一種結(jié)合量子粒子群算法和引導(dǎo)式局部搜索算法的混合算法求解2L-CVRP-MDTW模型。本節(jié)將詳細(xì)描述混合算法的基本原理、各部分策略和實(shí)施步驟。本文模型和算法中的符號(hào)或有重復(fù)，但符號(hào)的意義完全不同，符號(hào)的意義僅在對(duì)應(yīng)的模型或算法中進(jìn)行解釋。

3.1 量子粒子群算法

美國(guó)學(xué)者Kennedy和Eberhart受到鳥群覓食行為的啟發(fā)提出了粒子群算法(Particle Swarm Optimization，PSO)，PSO具有精度高、收斂快和容易實(shí)現(xiàn)等優(yōu)點(diǎn)[21]。算法提出后不久就被用于求解VRP問(wèn)題，目前已有許多運(yùn)用PSO求解VRP及其變種問(wèn)題的文獻(xiàn)[22-23]。在標(biāo)準(zhǔn)PSO中，種群由一定數(shù)量的粒子組成，每個(gè)粒子的位置均代表一個(gè)可行解。在多維搜索空間中，每個(gè)粒子均按照某個(gè)特定速度向更好的解移動(dòng)。

(16)

pid=φ*Pid+(1-φ)*Pgd,φ=rand(0,1),

(17)

(18)

其中，M表示粒子群中粒子的數(shù)目；d為粒子維度；mbest表示在所有粒子中每個(gè)粒子搜索到的最優(yōu)位置的平均值，本文采用最接近平均適應(yīng)值的粒子所在的位置；Pi=(Pi1,Pi2,…,Pid)表示第i個(gè)粒子的最優(yōu)位置；Pgd表示所有粒子中最佳粒子所在的位置；pid表示在Pid和Pgd之間的一個(gè)隨機(jī)點(diǎn)，在第i個(gè)粒子d維空間的一個(gè)位置；φ和u是在[0,1]之間均勻分布的隨機(jī)數(shù)；α是QPSO算法的參數(shù)，稱為收縮-擴(kuò)張系數(shù)，一般采用線性遞減的方式取值，其公式為：

(19)

量子粒子群優(yōu)化算法過(guò)程如下：

步驟1.初始化種群，粒子的初始位置通過(guò)隨機(jī)方式產(chǎn)生；

步驟2.對(duì)于每一個(gè)粒子，計(jì)算其適應(yīng)值，保存每個(gè)粒子歷史最優(yōu)值Pid,以及所有粒子的最優(yōu)值Pgd；

步驟3.根據(jù)公式(16)計(jì)算mbest,即最接近所有粒子的平均適應(yīng)值的粒子所在位置；

步驟4.對(duì)于粒子的每一個(gè)維，通過(guò)公式(17)得到一個(gè)隨機(jī)點(diǎn)；

步驟5.通過(guò)公式(18)獲得一個(gè)新的位置Xid；

步驟6.執(zhí)行局部擾動(dòng)操作；

步驟7.重復(fù)步驟2-步驟6，直至達(dá)到最大迭代次數(shù)。

為了便于實(shí)現(xiàn)，將時(shí)間窗約束作為懲罰項(xiàng)一并計(jì)入適應(yīng)值中，懲罰參數(shù)設(shè)定為足夠大的正整數(shù)。

3.1.1 改進(jìn)的編碼方法

考慮到多車場(chǎng)和時(shí)間窗的因素，現(xiàn)有文獻(xiàn)中的編碼方式均不適用。因此，本文構(gòu)造了一種新的編碼方式，即用4×n的矩陣形式進(jìn)行編碼。如圖4所示，第一行Client為客戶編號(hào)，第二行Xd為車場(chǎng)編號(hào)，第三行Xv為車輛編號(hào)，第四行Xt為車輛行駛順序。4×n矩陣式編碼方式增加了粒子的維數(shù)，而維數(shù)的增加并未顯著增加PSO算法的計(jì)算復(fù)雜性，這點(diǎn)已經(jīng)被相關(guān)研究證實(shí)[18]。

圖4 編碼方式示意圖

在圖4的例子中，第一列表示：從第一個(gè)配送中心出發(fā)的第一輛車輛服務(wù)顧客1，且顧客1位于該車輛的第一個(gè)拜訪順序上。由此，可寫出編碼示例的所有線路，如圖5所示。

圖5 編碼示例對(duì)應(yīng)的全部路徑

以上所給出的粒子編碼與解碼方式能夠保證使每個(gè)客戶都得到服務(wù)，并限制每個(gè)客戶僅能由一輛車完成，降低了尋優(yōu)過(guò)程中產(chǎn)生非可行解的幾率。

3.1.2 局部擾動(dòng)

為了提高QPSO的尋優(yōu)效率，本文采用2-opt和線路內(nèi)部搜索兩個(gè)方法進(jìn)行局部擾動(dòng)，這兩種方法類似于遺傳算法中的變異算子。2-opt作用于兩條線路上，具體操作方法是：隨機(jī)選擇兩條線路，并隨機(jī)選擇兩個(gè)位置，將兩條線路上的對(duì)應(yīng)節(jié)點(diǎn)進(jìn)行互換。線路內(nèi)部搜索作用于單條線路上，具體操作方法是：隨機(jī)選擇一條線路，并隨機(jī)選擇兩個(gè)位置，將兩個(gè)位置對(duì)應(yīng)的節(jié)點(diǎn)進(jìn)行互換。

3.2 引導(dǎo)式局部搜索算法

由3.1中的量子粒子群算法可求解得最優(yōu)線路，并可以確定每條線路上有哪些客戶，以及每條線路由哪輛車服務(wù)。本節(jié)討論如何將貨物裝入各自車廂內(nèi)，且滿足所有裝載約束。一般的裝箱問(wèn)題以裝載貨物數(shù)最大為目標(biāo)，而在2L-CVRP-MDTW的裝箱問(wèn)題中每輛車裝載的貨物數(shù)量和形狀是固定的，因此其解空間僅是一般裝箱問(wèn)題解空間的一個(gè)子集。針對(duì)這樣的特點(diǎn)，我們將設(shè)計(jì)一系列引導(dǎo)策略搜索問(wèn)題的局部最優(yōu)解。2L-CVRP-MDTW的裝箱過(guò)程包括確定待裝貨物順序和確定可行裝貨位置兩個(gè)子問(wèn)題，下面分別給出這兩個(gè)子問(wèn)題的求解策略。

3.2.1 確定待裝貨物順序

對(duì)于一條給定的配送線路而言，該線路上的所有客戶及客戶順序也是固定的。如第2章所描述的，在服務(wù)當(dāng)前客戶時(shí)不用挪動(dòng)其他客戶的貨物，因此同一條線路上的貨物應(yīng)首先按照服務(wù)客戶的順序逆向安排，遵循后進(jìn)先出原則。因此，不同客戶的貨物裝箱順序是固定的，但是同一個(gè)客戶的貨物裝箱順序不唯一。本文提出兩種裝箱規(guī)則以確定同一個(gè)客戶的貨物裝箱順序：O1規(guī)則按照裝箱底面積l·w降序排列；O2規(guī)則按照貨物長(zhǎng)度l降序排列。首先按O1原則排序，如果兩個(gè)貨物底面積相同，則按O2原則排序。對(duì)于第2章中的例子來(lái)講，兩條線路上的貨物順序可排列為：

Rout1:I52-I51-I41-I33-I32-I31-I21-I23-I22-I12-I13-I11,

Rout2:I62-I63-I61-I71-I72-I81-I82-I92-I91。

3.2.2 確定可行裝貨位置

車廂的可行裝貨位置指的是裝貨列表中的下一個(gè)貨物能夠放置的位置。每裝入一個(gè)貨物之后，可行裝貨位置會(huì)發(fā)生變化。通常可行裝貨位置并不唯一，那么我們需要對(duì)可行裝貨位置按某種規(guī)則進(jìn)行排序。已發(fā)表的文獻(xiàn)中給出了幾種確定可行裝貨位置的方法，但是這些方法通常僅按照固定的規(guī)則逐一嘗試，容易造成后面的貨物不能全部裝入車廂，需要進(jìn)行重復(fù)計(jì)算，降低了求解效率。因此，本文給出一種新的基于匹配規(guī)則的啟發(fā)式裝箱方法，充分考慮到貨物與位置之間的匹配關(guān)系，將待裝貨物放在最合適的位置上，盡可能充分節(jié)省空間，以提高一次裝箱成功率。

對(duì)于列表中的第一個(gè)貨物，我們通常將它放置在車廂的左下角(車門在正上方)，即圖6中的點(diǎn)O(0, 0)處。需要注意的是，當(dāng)我們描述把貨物放在某個(gè)位置時(shí)，則表示該貨物左下角的坐標(biāo)落在該位置點(diǎn)上。此外，由于所有貨物占據(jù)的網(wǎng)格數(shù)均為整數(shù)，因此某個(gè)點(diǎn)被貨物占據(jù)的意思就是，包含該點(diǎn)且處于其右上方的網(wǎng)格被該貨物占據(jù)。例如，點(diǎn)O處放置一個(gè)貨物，則(0, 0)、(0, 1)、(1, 0)和(1, 1)所組成的網(wǎng)格被該貨物占據(jù)。當(dāng)裝入一些貨物之后可能會(huì)出現(xiàn)一系列新的裝貨位置。如圖6所示，在裝入A后，可行裝貨位置列表更新為：

position_list={a(0,W,L-lA),b(1,W-1,L-lA),c(2,W-2,L)}。

圖6 可行裝貨位置示意圖

在所有的可行裝貨位置中，我們下一步要做的事情就是根據(jù)當(dāng)前貨物的形狀，選擇一個(gè)最理想的位置作為當(dāng)前裝貨位置。在確定最理想裝貨位置的時(shí)候，我們應(yīng)當(dāng)遵循一個(gè)最基本的原則，就是充分節(jié)省空間。基于這樣的原則，我們給出如下規(guī)則對(duì)可行裝貨點(diǎn)進(jìn)行排序，得到每個(gè)可行裝貨點(diǎn)的優(yōu)先級(jí)。如圖7所示，圖中白色區(qū)域?yàn)橐逊胖秘浳铮疑珔^(qū)域?yàn)槭Ｓ嗫臻g，R為待裝的下一個(gè)貨物。當(dāng)剩余空間大小相同，而待裝貨物大小不同時(shí)，可以產(chǎn)生如下準(zhǔn)則：

a.貨物與可行區(qū)長(zhǎng)寬相等，適應(yīng)值為1，如圖7(a)。

b.貨物寬度與可行區(qū)寬度相等，貨物長(zhǎng)度小于可行區(qū)長(zhǎng)度，適應(yīng)值為2，如圖7(b)。

c.貨物長(zhǎng)度與可行區(qū)長(zhǎng)度相等，貨物寬度小于可行區(qū)寬度，適應(yīng)值為3，如圖7(c)。

d.貨物寬度小于可行區(qū)寬度，貨物長(zhǎng)度小于可行區(qū)長(zhǎng)度，適應(yīng)值為4，如圖7(d)。

e.貨物寬度大于可行區(qū)寬度或貨物長(zhǎng)度大于可行區(qū)長(zhǎng)度，適應(yīng)值為無(wú)窮大，即貨物無(wú)法放置于該位置。

圖7 可行裝貨位置的適應(yīng)值

3.3 混合算法

本文把量子粒子群算法和引導(dǎo)式局部搜索算法結(jié)合起來(lái)，構(gòu)造求解2L-CVRP-MDTW的引導(dǎo)式局部搜索量子粒子群算法(Guided Local Search - Quantum-behaved Particle Swarm Optimization Algorithm，GLS-QPSO)。GLS-QPSO算法的基本思路為：通過(guò)量子粒子群算法得到VRP的近似最優(yōu)解集，近似最優(yōu)解集中保存適應(yīng)度靠前的若干粒子；把最優(yōu)解集中的粒子按適應(yīng)度從大到小排列，選擇第一個(gè)粒子作為當(dāng)前車輛路線方案，然后調(diào)用引導(dǎo)式局部搜索算法；如果找到可行裝箱方案，則返回最優(yōu)解，否則，依次選擇最優(yōu)解集中的下一個(gè)解作為車輛路線方案；如果最優(yōu)解集中所有車輛路線方案均找不到可行解，則返回量子粒子群算法重新求解VRP；重復(fù)算法直至找到可行解，或達(dá)到最大迭代次數(shù)。若達(dá)到最大迭代次數(shù)仍未找到最優(yōu)解，則應(yīng)考慮減少顧客或貨物數(shù)量，或者增加車輛總數(shù)，然后重新執(zhí)行GLS-QPSO算法。

GLS-QPSO算法的具體步驟如下：

步驟1. GLS-QPSO算法初始化：設(shè)定最大循環(huán)次數(shù)T,令t=0；

步驟2.執(zhí)行QPSO算法流程，詳見3.1；

步驟3.生成近似最優(yōu)解集：QPSO算法結(jié)束之后，按適應(yīng)度從大到小排列當(dāng)前粒子，保留靠前的BestSize個(gè)粒子形成近似最優(yōu)解集；

步驟4.引導(dǎo)式局部搜索算法參數(shù)初始化：令i=1,j=1,k=1；

步驟5. 產(chǎn)生車輛路線方案：選擇近似最優(yōu)解集中的第i個(gè)解，作為當(dāng)前車輛路線方案；

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

步驟7.最終裝貨序列：按照Oj規(guī)則調(diào)整裝貨順序，確定最終裝貨序列；

步驟8.可行裝貨位置：按照第k個(gè)啟發(fā)式方法掃描所有可能裝貨位置，按裝貨序列給每個(gè)貨物都找到可行裝貨位置；

步驟9.可行裝貨位置循環(huán)：若所有貨物均找到可行裝貨位置，算法終止，輸出當(dāng)前最優(yōu)解；若有一個(gè)或多個(gè)貨物沒(méi)找到可行裝貨位置，且k<6,令k=k+1,返回步驟8；若k≥6,轉(zhuǎn)步驟10；

步驟10.裝貨序列循環(huán)：若j<3,令j=j+1,返回步驟7；若j≥3,轉(zhuǎn)步驟11；

步驟11.近似最優(yōu)解集循環(huán)：若i

步驟12.總循環(huán)：若t

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

本文設(shè)計(jì)了兩組數(shù)值試驗(yàn)。第一組數(shù)值試驗(yàn)基于已有標(biāo)準(zhǔn)算例庫(kù)，用于檢驗(yàn)GLS-QPSO算法的性能和效率。第二組數(shù)值試驗(yàn)基于隨機(jī)生成的算例，用于演示GLS-QPSO算法對(duì)2L-CVRP-MDTW模型的求解過(guò)程和計(jì)算效果。

4.1 基于標(biāo)準(zhǔn)算例庫(kù)的數(shù)值試驗(yàn)

Gendreau等[4]中給出了180個(gè)2L-CVRP算例，這些算例均是在Toth和Vigo[25]所給出的36個(gè)CVRP算例的基礎(chǔ)上轉(zhuǎn)化而來(lái)。隨后，有一些設(shè)計(jì)不同算法求解2L-CVRP的問(wèn)題的文獻(xiàn)陸續(xù)發(fā)表出來(lái)，均采用Gendreau等[4]的算例進(jìn)行數(shù)值試驗(yàn)，其中Leung等[5]的計(jì)算結(jié)果較好。

從180個(gè)算例中隨機(jī)抽取20個(gè)進(jìn)行數(shù)值試驗(yàn)，在這20個(gè)算例中車廂規(guī)格相同(長(zhǎng)為40、寬為20)。將本文計(jì)算結(jié)果與Duhamel等[4]和Duhamel等[7]的優(yōu)化結(jié)果進(jìn)行對(duì)比，如表2所示，“Best”表示最優(yōu)路徑，“Time”表示計(jì)算時(shí)間，“Gap”表示最優(yōu)解和時(shí)間的降低幅度。

表2 與已有文獻(xiàn)計(jì)算結(jié)果對(duì)比

注：“Gap”值為正表示本文結(jié)果優(yōu)于已有結(jié)果，為負(fù)表示本文結(jié)果劣于已有結(jié)果。

從表2中的對(duì)比結(jié)果可以發(fā)現(xiàn)，本文的計(jì)算結(jié)果在最短路徑和計(jì)算時(shí)間上均有較好表現(xiàn)。其中，最短路徑比Gendreau等[4]平均減少11.23%，比Duhamel等[7]平均減少1.07%，本文在計(jì)算結(jié)果上與Duhamel等[7]相當(dāng)。計(jì)算時(shí)間比Gendreau等[4]平均減少619.10秒，比Duhamel等[7]平均減少96.36秒，本文在計(jì)算時(shí)間上具有明顯優(yōu)勢(shì)。Gendreau等[4]采用禁忌搜索算法進(jìn)行求解，優(yōu)點(diǎn)在于邏輯清晰、容易實(shí)現(xiàn)，缺點(diǎn)在于處理大規(guī)模問(wèn)題時(shí)效果較差。

4.2 基于隨機(jī)數(shù)據(jù)的數(shù)值試驗(yàn)

由于2L-CVRP-MDTW模型沒(méi)有現(xiàn)成算例，因此本文將給出一個(gè)新算例，并用新算例演示模型求解過(guò)程和結(jié)果。本文在標(biāo)準(zhǔn)算例0201的基礎(chǔ)上，通過(guò)新增一個(gè)新車場(chǎng)，并為每個(gè)顧客指定時(shí)間窗，從而形成一個(gè)多車場(chǎng)、帶時(shí)間窗的二維裝箱車輛路徑問(wèn)題算例。原始數(shù)據(jù)參考標(biāo)準(zhǔn)算例庫(kù)，新車場(chǎng)坐標(biāo)為(35，45)，顧客時(shí)間窗見表3。

假設(shè)所有車輛8:00開始出發(fā)，17:00返回各自車場(chǎng)。原始算例中的節(jié)點(diǎn)坐標(biāo)沒(méi)有單位，本文假設(shè)所有節(jié)點(diǎn)坐標(biāo)的單位均為千米，且假設(shè)車輛行駛速度為50千米/小時(shí)。計(jì)算出的最優(yōu)路徑如圖8所示。

表3 顧客時(shí)間窗列表

圖8 新算例車輛最優(yōu)路線示意圖

在圖9中有兩條路線存在交叉現(xiàn)象，可以看出線路交叉是為了滿足時(shí)間窗約束。

5 結(jié)語(yǔ)

本文研究了2L-CVRP的一個(gè)變種問(wèn)題，在傳統(tǒng)2L-CVRP模型中綜合考慮多車場(chǎng)和時(shí)間窗因素，給出變種問(wèn)題的目標(biāo)和約束，并建立2L-CVRP-MDTW模型。為了更好的求解2L-CVRP-MDTW模型，本文提出了一種基于量子粒子群算法和引導(dǎo)式局部搜索算法相結(jié)合的混合算法。量子粒子群算法在傳統(tǒng)粒子群算法的基礎(chǔ)上，給每個(gè)粒子增加量子行為，提高粒子的搜索能力，并從整體上提高粒子群算法的性能。引導(dǎo)式局部搜索給出一種新的啟發(fā)式裝箱規(guī)則，即根據(jù)最小浪費(fèi)原則靈活確定待裝貨物與裝貨空間之間的匹配關(guān)系。

為了檢驗(yàn)GLS-QPSO算法的效率和性能，本文在標(biāo)準(zhǔn)算例庫(kù)中隨機(jī)抽取了20個(gè)算例進(jìn)行數(shù)值試驗(yàn)，并將試驗(yàn)結(jié)果與已有文獻(xiàn)中的結(jié)果進(jìn)行對(duì)比。對(duì)比結(jié)果表明，GLS-QPSO算法在計(jì)算結(jié)果和計(jì)算時(shí)間上均有較為優(yōu)秀的表現(xiàn)，明顯優(yōu)于已有文獻(xiàn)中的算法。此外，為了檢驗(yàn)本文所提出的2L-CVRP-MDTW模型的可解性，在原有算例的基礎(chǔ)上生成一個(gè)新算例進(jìn)行數(shù)值試驗(yàn)。新算例給出第二個(gè)車場(chǎng)的坐標(biāo)，并給出每個(gè)顧客的服務(wù)時(shí)間窗。GLS-QPSO成功計(jì)算出新算例的最優(yōu)路徑，所有線路均滿足既定約束，并且服務(wù)顧客的開始時(shí)間均處于規(guī)定的時(shí)間窗內(nèi)。從這兩組數(shù)值試驗(yàn)可以得出這樣的結(jié)論：一是，GLS-QPSO算法具有較好的效率和性能；二是，GLS-QPSO算法能夠很好的處理2L-CVRP-MDTW模型，并在有效時(shí)間內(nèi)給出問(wèn)題的最優(yōu)解。

[1] Wei Lijun, Zhang Zhenzhen, Zhang Defu, et al. A variable neighborhood search for the capacitated vehicle routing problem with two-dimensional loading constraints [J]. European Journal of Operational Research, 2015, 243(3):798-814.

[2] Iori M. Meta-heuristic algorithm for combinatorial optimization problems [J]. 4OR, 2005, 3(2): 163-166.

[3] Zachariadis E E, Tarantilis C D, Kiranoudis C T. A guided Tabu search for the vehicle routing problem with two-dimensional loading constraints [J]. European Journal of Operational Research, 2009, 195( 3): 729-743.

[4] Gendreau M, Iori M, Laporte G, et al. A Tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints [J]. Networks,2008,51(2):469-477.

[5] Leung SCH, Zheng Jiemin, Zhang Defu, et al. Simulated annealing for the vehicle routing problem with two-dimensional loading constraints [J]. Flexible Services & Manufacturing Journal, 2010, 22(1): 61-82.

[6] Fuellerer G, Doerner K F, Hartl R F, et al. Ant colony optimization for the two-dimensional loading vehicle routing problem [J]. Computers & Operations Research, 2007, 36(3): 655-673.

[7] Duhamel C, Lacomme P, Quilliot A, et al. A multi-start evolutionary local search for the two-dimensional loading capacitated vehicle routing problem [J]. Computers & Operations Research, 2011, 38(3): 617-640.

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

[9] Iori M, Juan-José, Salazar-Gonzá, et al. An exact approach for the vehicle routing problem with two-dimensional loading constraints [J]. Transportation Science, 2007, 41(2): 253-264.

[10] Bruno LP, Pedro H, Flavio K, et al. A branch-and-cut approach for the vehicle routing problem with two-dimensional loading constraints [J]. Transportation Science, 2007, 41(2):253-264.

[11] Zachariadis EE, Tarantilis C D, Kiranoudis CT. Integrated distribution and loading planning via a compact metaheuristic algorithm [J]. European Journal of Operational Research, 2013, 228(1): 56-71.

[12] Hokama P, Miyazawa KF, Xavier C E. A branch-and-cut approach for the vehicle routing problem with loading constraints [J]. Expert Systems With Applications, 2016,47: 1-13.

[13] Zachariadis E E, Tarantilis D C, Kiranoudis T C. The vehicle routing problem with simultaneous pick-ups and deliveries and two-dimensional loading constraints [J]. European Journal of Operational Research, 2016,251(2): 369-386.

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

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

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

[17] 顏瑞，張群，胡睿. 考慮三維裝箱約束的車輛路徑問(wèn)題研究[J]. 中國(guó)管理科學(xué)， 2015， 23(1)：128-132.

[18] Errico F, Desaulniers G, Gendreau M, et al. A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times [J]. European Journal of Operational Research, 2016,249(1): 55-66.

[19] Keskin M, Catay B. Partical recharge strategies for the electric vehicle routing problem with time windows [J]. Transportation Research Part C:Emerqing Technologies, 2016,65:111-127.

[20] 王征，張俊，王旭坪. 多車場(chǎng)帶時(shí)間窗車輛路徑問(wèn)題的變領(lǐng)域搜索算法[J]. 中國(guó)管理科學(xué)， 2011，19(2)： 99-103.

[21] Kennedy J, Eberhart R C. Swarm intelligence [M]. San Francisco:Morgan Kaufman Publishers,2001.

[22] Ai T, Kachitvichyanukul V. A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery [J]. Computers & Operations Research, 2009, 36(5): 1693-1702.

[23] Wu Z. Optimization of distribution route selection based on particle swarm algorithm [J]. International Journal of Simulation Modelling, 2014, 13 (2): 230-242.

[24] Sun Jun, Xu Wenbo, Feng Bin. A global search strategy of quantum-behaved particle swarm optimization [C]//Proceedings of the 2004 IEEE Conference on Cybernetics and Intelligent Systems, Singapore,December 1-3,2004.

[25] Toth P, Vigo D. The vehicle routing problem, chapter branch-and-bound algorithms for the capacitated VRP [J]. Siam Monographs on Discrete Mathematics & Applications, 2002, 94(2-3): 127-153.

Research ofthe Model and Algorithm for Two-dimensional Multi-depots Capacitated Vehicle Routing Problem with Time Window Constrain

YAN Rui1, ZHU Xiao-ning2, ZHANG Qun2, QI Yao-yuan2, LIN Yu-zheng1

(1.Beijing Information Science and Technology University,Beining 100192,China;2.University of Science and Technology Beijing,Beijing 100083,China)

Both vehicle routing problem (VRP) and bin packing problem (BPP) are important, typical combinatorial optimization problems, and are frequently and independently studied in the past few decades. In recent years, some attention has been devoted to their combined optimization, called 2L-CVRP (two-dimensional capacitated vehicle routing problem), which is a combination of two important NP-hard optimization problems in distribution logistics. In the 2L-CVRP, clients demand are defined as sets of rectangular weighted items, while vehicles have a weight capacity and a rectangular two-dimensional loading surface. The objective of the 2L-CVPR is to serve all the customers and load the corresponding items into the vehicles, through a road network, with minimum total cost.

Problem description：In this paper, a multi-depots capacitated vehicle routing problem with time window where client demand is composed of two-dimensional weighted items is addressed (2L-CVRP-MDTM).The model and an improved hybrid algorithm to solve the problem are proposed. The hybrid algorithm GLS-QPSO is composed by the Quantum-behaved Particle Swarm Optimization algorithm which is applied to solve the vehicle routing problem and Guided Local Search algorithm which is used to identify the feasible packing solutions.

Method：New loading heuristic rules are proposed in Guided Local Search algorithm based on the principle of minimize the waste to get better results of the matching relationship between the items and the corresponding packing positions in shorter time. Through the algorithm we can get the tours, and identify the clients covered by the vehicles, as well as vehicles in the routes. All the items demanded by the clients need to be loaded in the vehicles with the related constrains. In fact, there are two aspects that packing algorithm needs to consider. One is to determine the next loading item, and another is to determine the feasible loading position.

Computational experiments: Twenty of these 2L-CVRP standard instances are selected randomly, and loading surface (L,W) is fixed as (40,20) for all instances. The 20 selected instances are changed to two depots instances to testify the proposed algorithm in this paper by adding a new depot. We calculate the center of the clients, and then select a point between the first depot and the center randomly as the second depot.

Results：We compare the improved hybrid algorithm with the known best solutions, and the other is based on the new instances which include multi-depots with time window constrain. We calculate the center of the clients, and then select a point between the first depot and the center randomly as the second depot. The results of the numerical experiments show that the proposed hybrid algorithm has better performances in terms of both the calculation results and computing time comparing with the selected recent literature. The computational results show that the proposed algorithm is effective in finding high quality solutions and the practical recharging option may significantly improve the 2L-CVRP-MDTM which a new variant of the 2L-CVRP considering vehicles start from several different depots with time window constrains.

vehicle routing problem; two-dimensional packing problem; Quantum-behaved Particle Swarm Optimization algorithm; multi-depots; time window

2015-11-22；

2016-03-01

國(guó)家自然科學(xué)基金青年項(xiàng)目(71602008)；北京市社會(huì)科學(xué)基金研究基地項(xiàng)目(16JDGLC032)；北京交通大學(xué)人才基金(B15RC00150)

顏瑞(1986-)，男(漢族)，江蘇連云港人，北京信息科技大學(xué)經(jīng)濟(jì)管理學(xué)院，講師，博士，研究方向：物流優(yōu)化、智能算法，E-mail:yr1900@163.com.

1003-207(2017)07-0067-11

10.16381/j.cnki.issn1003-207x.2017.07.008

O224

A