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

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

?

考慮二維裝箱約束的多車場帶時間窗的車輛路徑問題模型及算法研究

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

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

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

車輛路徑問題；二維裝箱問題；量子粒子群算法；多車場；時間窗

1 引言

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

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

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

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

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

2 模型建立

2.1 問題描述

2.2 模型假設(shè)

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

(1)假設(shè)每個車場處均有一個儲貨量充足的倉庫，且每個車場的車輛僅從同一位置的倉庫裝貨；

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

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

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

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

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

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

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

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

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

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

2.3 數(shù)學模型

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

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

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

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

模型的決策變量有：

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

表1 模型符號及符號解釋

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

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

3 算法設(shè)計

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

3.1 量子粒子群算法

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

(16)

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

(17)

(18)

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

(19)

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

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

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

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

步驟4.對于粒子的每一個維，通過公式(17)得到一個隨機點；

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

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

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

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

3.1.1 改進的編碼方法

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

圖4 編碼方式示意圖

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

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

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

3.1.2 局部擾動

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

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

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

3.2.1 確定待裝貨物順序

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

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 確定可行裝貨位置

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

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

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

圖6 可行裝貨位置示意圖

在所有的可行裝貨位置中，我們下一步要做的事情就是根據(jù)當前貨物的形狀，選擇一個最理想的位置作為當前裝貨位置。在確定最理想裝貨位置的時候，我們應(yīng)當遵循一個最基本的原則，就是充分節(jié)省空間?；谶@樣的原則，我們給出如下規(guī)則對可行裝貨點進行排序，得到每個可行裝貨點的優(yōu)先級。如圖7所示，圖中白色區(qū)域為已放置貨物，灰色區(qū)域為剩余空間，R為待裝的下一個貨物。當剩余空間大小相同，而待裝貨物大小不同時，可以產(chǎn)生如下準則：

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

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

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

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

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

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

3.3 混合算法

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

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

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

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

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

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

步驟9.可行裝貨位置循環(huán)：若所有貨物均找到可行裝貨位置，算法終止，輸出當前最優(yōu)解；若有一個或多個貨物沒找到可行裝貨位置，且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ù)值試驗

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

4.1 基于標準算例庫的數(shù)值試驗

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

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

表2 與已有文獻計算結(jié)果對比

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

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

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

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

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

表3 顧客時間窗列表

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

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

5 結(jié)語

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

為了檢驗GLS-QPSO算法的效率和性能，本文在標準算例庫中隨機抽取了20個算例進行數(shù)值試驗，并將試驗結(jié)果與已有文獻中的結(jié)果進行對比。對比結(jié)果表明，GLS-QPSO算法在計算結(jié)果和計算時間上均有較為優(yōu)秀的表現(xiàn)，明顯優(yōu)于已有文獻中的算法。此外，為了檢驗本文所提出的2L-CVRP-MDTW模型的可解性，在原有算例的基礎(chǔ)上生成一個新算例進行數(shù)值試驗。新算例給出第二個車場的坐標，并給出每個顧客的服務(wù)時間窗。GLS-QPSO成功計算出新算例的最優(yōu)路徑，所有線路均滿足既定約束，并且服務(wù)顧客的開始時間均處于規(guī)定的時間窗內(nèi)。從這兩組數(shù)值試驗可以得出這樣的結(jié)論：一是，GLS-QPSO算法具有較好的效率和性能；二是，GLS-QPSO算法能夠很好的處理2L-CVRP-MDTW模型，并在有效時間內(nèi)給出問題的最優(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] 馬珊靜，陳峰，宋德朝,等. 越庫配送物流系統(tǒng)車輛調(diào)度算法的研究[J]. 現(xiàn)代制造工程， 2009,(1)：12-15.

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

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

[17] 顏瑞，張群，胡睿. 考慮三維裝箱約束的車輛路徑問題研究[J]. 中國管理科學， 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] 王征，張俊，王旭坪. 多車場帶時間窗車輛路徑問題的變領(lǐng)域搜索算法[J]. 中國管理科學， 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

國家自然科學基金青年項目(71602008)；北京市社會科學基金研究基地項目(16JDGLC032)；北京交通大學人才基金(B15RC00150)

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

1003-207(2017)07-0067-11

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

O224

A