ALNS算法求解帶軟時間窗同時取送貨的PCVRP問題

李 琳，陳 瑩

(沈陽航空航天大學 理學院，沈陽 110136)

車輛路徑問題(Vehicle Routing Problem,VRP)在物流行業(yè)有著很大的應(yīng)用價值。龐燕等[1]總結(jié)了VRP的變體及其求解方法。在文獻中，大多數(shù)VRP的變體問題假設(shè)配送中心具有足夠數(shù)目的車輛可以滿足所有客戶的需求。在這類問題中，規(guī)劃配送路線時，所有的客戶都要被服務(wù)。但在實際生活中，存在不同客戶可能存在不同的優(yōu)先級和利潤、每個客戶不需要在特定的某天被強制訪問、現(xiàn)有的車輛不能一次性滿足所有客戶的需求等情況。因此本文研究獎金收集車輛路徑問題(Prize Collecting Vehicle Routing Problem,PCVRP)。PCVRP中由于實際配送條件的限制導(dǎo)致現(xiàn)有的車輛不能一次性滿足所有客戶的需求，只能服務(wù)部分客戶。被服務(wù)的客戶會給予車輛一定的獎金，被訪問客戶的總需求至少達到一個預(yù)定值。它的目標是使總運輸成本最小化，同時使所有車輛收集到的獎金最大化。

目前對PCVRP的研究較少，對PCVRP需要進行更加深入的研究。文獻[2-6]是基于帶容量約束的VRP(CVRP)模型建立的PCVRP模型。其中文獻[2-4]的目標函數(shù)是最小化總行駛距離和使用的車輛數(shù)目、最大化獎金收集。Long等[2]提出了一種基于Pareto的進化算法求解PCVRP。Li等[3]對建立的PCVRP模型，提出了兩級自適應(yīng)變鄰域搜索算法，將PCVRP轉(zhuǎn)化為等價的旅行商問題(TSP)，并對提出的算法進行了評價。Tang等[4]針對PCVRP問題，提出了基于循環(huán)轉(zhuǎn)移的超大規(guī)模鄰域迭代局部搜索算法。對100個客戶的問題進行計算并驗證了算法的可行性。文獻[5-6]在上述基礎(chǔ)上增加了未被服務(wù)客戶對車輛的懲罰。Anurag等[5]提出了一種混合邊緣重組方法求解PCVRP，基于CVRP的11個標準算例對算法進行了驗證。Christos等[6]設(shè)計了分支剪切算法求解PCVRP，使用真實案例評估了有效不等式的有效性。現(xiàn)有文獻中對PCVRP的求解側(cè)重于啟發(fā)算法，其中Li等[3]使用自適應(yīng)變鄰域搜索算法求解了200個客戶的PCVRP問題，Tang等[4]使用大規(guī)模鄰域搜索算法求解了100個客戶的PCVRP問題。自適應(yīng)大鄰域搜索算法(Adaptive Large Neighborhood Search,ALNS)是從大鄰域搜索算法(LNS)擴展而來的[7]，既滿足自適應(yīng)機制，也對大規(guī)模的問題有較好的求解效果。文獻[8-10]分別使用ALNS對VRP的不同變體求解，結(jié)果表明ALNS求解VRP的不同變體時速度更快、結(jié)果更好。

目前的文獻中PCVRP的模型基本只存在送貨需求。為了更符合實際配送條件，本文在現(xiàn)有的PCVRP模型基礎(chǔ)上加入了時間窗約束和同時取送貨需求，建立了單目標帶軟時間窗同時取送貨的獎金收集車輛路徑問題(PCVRPTWSPD)的模型。在原有的目標函數(shù)中加入了時間窗懲罰，設(shè)計了ALNS算法對PCVRPTWSPD模型進行求解。為驗證本文算法的有效性，對solomon算例[11]進行改造，構(gòu)造12組不同規(guī)模的PCVRPTWSPD算例，實驗結(jié)果表明ALNS在此類問題的求解時尋優(yōu)能力更強。

1 模型的建立

1.1 問題描述

本文研究的模型是單目標的PCVRPTWSPD，目標函數(shù)為最小化總成本與收集到獎金間的差值?？偝杀景ㄜ囕v總行駛成本、車輛使用成本、時間窗懲罰。模型為單配送中心，擁有數(shù)量已知的同質(zhì)型車輛，車輛的容量為C。假設(shè)車輛勻速行駛，速度為v。車輛的集合為K={1,2,…,m},?k∈K，單位運行成本為W，每輛車的使用成本為F。客戶點的集合為V={1,2,…,n}，客戶總數(shù)為N。0表示配送中心。cij表示客戶i和客戶j之間的距離。di和gi表示客戶i的送貨和取貨需求，pi表示車輛在客戶i收取的獎金。被訪問客戶的總需求至少達到一個預(yù)定值Q，即至少有Q個客戶被服務(wù)。本文被服務(wù)的客戶以隨機的方式選取。車輛從配送中心出發(fā)最終回到配送中心。eti和lti表示規(guī)定最早到達客戶i的時間和最晚到達客戶i的時間。ti表示車輛實際到達客戶i的時間。如果tilti，車輛仍可以對客戶i進行服務(wù)但需要接受相應(yīng)的懲罰。f1和f2表示車輛早到的懲罰費用和晚到的懲罰費用。sti表示車輛在客戶i的服務(wù)時間。

1.2 數(shù)學模型

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

(8)

xijk∈{0,1};

(9)

yik∈{0,1};

(10)

式(1)為目標函數(shù)。式(2)表示車輛從配送中心出發(fā)時載貨量不超過車輛的容量限制。式(3)表示預(yù)先給定的客戶需求必須被滿足。式(4)表示在客戶點完成取送貨之后車輛載重不超過車輛最大容量。式(5)和式(6)表示每個客戶點最多只能被一輛車訪問一次。式(7)避免出現(xiàn)子回路。式(8)表示車輛從客戶i到達客戶j的時間。式(9)和式(10)為決策變量，如果車輛k由客戶i行駛到客戶j，則xijk為1，否則為0；如果車輛k服務(wù)客戶i，則yik為1，否則為0。

2 求解算法

本文使用ALNS對模型求解。其基本思想是輸入一個初始解，根據(jù)權(quán)重選擇一組destroy和repair方法對初始解進行破壞重建得到新解。判斷新解的質(zhì)量對新解進行評分，根據(jù)評分對destroy和repair方法的權(quán)重更新，直到滿足終止條件輸出最優(yōu)解。

2.1 初始解

一個高質(zhì)量的初始解可以提高ALNS的收斂速度，在較短的時間內(nèi)得到更好的解決方案。本文使用插入法[9]構(gòu)造初始解。本文建立的模型帶軟時間窗約束，因此在生成初始解時優(yōu)先考慮行駛距離最小的客戶點，允許時間窗存在偏差。其基本思想是隨機選取被服務(wù)的客戶，在被服務(wù)的客戶集M中隨機選擇一個客戶點v1，設(shè)L為M中未被選取的客戶點集合，計算v1到L中各點的距離，選擇與v1距離最小的客戶點插入。如果超過車輛的最大裝載(即不滿足約束(2)和(4))，則將客戶點插入到新的路線中。循環(huán)前面的步驟直到集合L為空。

2.2 destroy和repair方法

為增強算法的尋優(yōu)能力，本算法為每組destroy和repair方法分配了權(quán)重ρ，該方法可以在較短的時間內(nèi)有效地使用鄰域變換方法，并提高算法的收斂速度。在迭代過程中，根據(jù)每組destroy和repair方法被分配的權(quán)重在所有方法的權(quán)重和中的占比φj，選擇其中一組對當前解x進行鄰域變換。φj越大，對應(yīng)的這組destroy和repair方法被選到的概率越大。即ρ越大，對應(yīng)的這組destroy和repair方法被選到的概率越大。每組權(quán)重占比φj的計算方法如公式(11)。參考Li等[3]的內(nèi)容，根據(jù)本文模型特點設(shè)計了5組destroy和repair方法。

(11)

(1)路徑內(nèi)插入(inner-insertion)：隨機選擇一條配送路線m。刪除m中的一個客戶點v并插入到m的其他位置。

(2)路徑間插入(outer-insertion)：隨機選擇兩條配送路線m1和m2。在m1和m2中分別隨機刪除一個客戶點vm1和vm2,將vm2隨機插入到m1中，vm1隨機插入到m2中。判斷兩條新路徑m1_vm2和m2_vm1是否滿足約束(2)和(4)。如果m1_vm2或m2_vm1不滿足，則新建一條路徑，將vm2或vm1插入到新的路徑中。

(3)路徑間交換(outer-swap)：隨機選擇兩條配送路線m1和m2。在m1和m2中分別隨機選擇一個客戶點vm1和vm2，交換vm1和vm2的位置。判斷兩條新路徑m1_vm2和m2_vm1是否滿足約束(2)和(4)。如果m1_vm2或m2_vm1不滿足，則新建一條路徑，將vm2或vm1插入到新的路徑中。

(4)路徑間兩交換(2-outer-swap)：隨機選擇兩條配送路線m1和m2。在m1和m2中分別隨機選擇兩個客戶點vm1-1、vm1-2和vm2-1、vm2-2，交換vm1-1、vm1-2和vm2-1、vm2-2的位置。判斷兩條新路徑m1_vm2-12和m2_vm1-12是否滿足約束(2)和(4)。如果m1_vm2-12和m2_vm1-12不滿足，則新建一條路徑，將vm2-1、vm2-2或vm1-1、vm1-2插入到新的路徑中。

(5)路徑內(nèi)交換(inner-swap)：隨機選擇一條配送路線m，在m中隨機選擇兩個客戶點v1和v2，交換v1和v2的位置。

2.3 權(quán)重更新

在迭代過程中會對得到的新解χ′進行評分。如果χ′是全局最優(yōu)解，則得分為ω1；如果χ′優(yōu)于當前解x，則得分為ω2；如果χ′被接受，則得分為ω3；如果χ′被拒絕，則得分為ω4。其中ω1>ω2>ω3>ω4。令ψ=max(ω1,ω2,ω3,ω4)，則根據(jù)公式(12)對每組destroy和repair方法的權(quán)重ρj進行更新。設(shè)初始權(quán)重為ρ=(1,…,l)。本算法ω1、ω2、ω3、ω4的取值參考Ropke[7]，即ω1=1、ω2=0.4、ω3=0.25、ω4=0.1。

ρj=λρj+(1-λ)ψ,λ∈[0，1]

(12)

2.4 接受準則和終止準則

當新解χ′產(chǎn)生后，需要判斷它是否被接受。本算法借鑒模擬退火算法的接受準則：如果χ′優(yōu)于x，則接受χ′。如果χ′劣于x，則以一定的概率p接受χ′，避免算法過早陷入局部最優(yōu)。p的計算方法如式(13)所示。本算法采取的終止準則是把最大迭代數(shù)作為算法停止的標準。

p=eF(x)-F(x′)/T

(13)

2.5 算法步驟

最后得到ALNS的具體步驟如下：

Step 1:通過插入法得到一個初始解x，計算x的目標函數(shù)值，令當前最優(yōu)解xb=x；初始化destroy和repair方法的權(quán)重ρ=(1,…,1)；

Step 2:通過公式(11)選擇一種destroy和repair方法對x進行鄰域變換，得到一個新解χ′；

Step 3:判斷χ′的目標函數(shù)值是否小于xb的目標函數(shù)值，如果是則xb=χ′,x=χ′，否則轉(zhuǎn)下一步；

Step 4:判斷χ′是否優(yōu)于當前解x，如果是，更新當前解x=χ′，否則轉(zhuǎn)下一步；

Step 5:判斷χ′是否滿足接受準則，如果滿足，則x=χ′，如果不滿足x=x；

Step 6:更新ρ；

Step 7: 判斷是否滿足停止準則，如果滿足，輸出最優(yōu)解xb，否則轉(zhuǎn)Step 2。

3 仿真實驗

現(xiàn)有文獻中對PCVRP的研究只帶有送貨需求，還沒有對帶時間窗和同時取送貨PCVRP模型的研究和求解，所以目前還沒有PCVRPTWSPD算例對算法進行測試，為此本文構(gòu)造了12組計算PCVRPTWSPD模型的算例。選取Solomon標準算例[11]中的RC101、RC104、RC107前10、25、50和100個客戶點，根據(jù)周蓉等[12]擴展 Solomon算例的方法生成配送和取貨需求，其他基礎(chǔ)數(shù)據(jù)不變。將新生成的算例命名為Rcdp101、Rcdp104和Rcdp107。對單位配送成本、車輛早到和遲到的懲罰、車輛出行成本的設(shè)置參照鄧愛民等[13]的參數(shù)設(shè)置。其中配送成本為W=1元/公里，車輛早到的懲罰為f1=3元/小時，車輛遲到的懲罰為f2=6元/小時，車輛出行成本為F=20元/輛。假設(shè)至少滿足的客戶需求Q=0.8N，即至少80%的客戶被服務(wù)，被服務(wù)的客戶給予的獎金在[1,10]內(nèi)隨機生成，即pi=rand(1,10)。

為驗證算法的有效性，本文進行了3組實驗。針對不同規(guī)模的算例，本算法的迭代次數(shù)取值為：大規(guī)模(100個客戶點)算例的迭代次數(shù)是400、中規(guī)模(50、25個客戶點)算例的迭代次數(shù)是300、小規(guī)模(10個客戶點)算例的迭代次數(shù)是100。本算法使用Python3.7編程，在CoreI7 CPU@1.80GHz 1.99GHz的筆記本上運行。

實驗1選取文獻[14]的求解帶軟時間窗同時取送貨VRP的算例，使用本文算法求解。針對文獻[14-16]給出的計算結(jié)果從使用車輛數(shù)(NV)和車輛行駛距離(Z)兩個方面與遺傳算法[15]、模擬退火算法[16]和布谷鳥算法[14]運行結(jié)果進行比較。

表1列出了本文算法運行10次獲得的平均值與遺傳算法[15]、模擬退火算法[16]和布谷鳥算法[14]運行結(jié)果的比較。分別使用GA、SA、MCS、ALNS表示遺傳算法[15]、模擬退火算法[16]、布谷鳥算法[14]和本文算法。其中將遺傳算法[15]的計算結(jié)果作為標準1，其他算法列出的結(jié)果均是與遺傳算法[15]的比值。加粗部分表示本文算法與其他算法的求解結(jié)果相比，本文算法的求解結(jié)果更好。

對于本文算法，從行駛距離方面看，只有R101/10和R101/25兩個算例的求解結(jié)果沒有其他算法好。其中C101/25的改進最大，與GA計算結(jié)果的比值為0.63，SA和MCS與GA計算結(jié)果的比值分別為0.99、0.98。在12個算例中更新了10個算例的最優(yōu)解。在算例規(guī)模超過50個客戶點時，從表1中可以看到本算法的計算結(jié)果比其他算法更好。從車輛使用數(shù)量上來看，除了算例R011/10，其他全部減少。綜合比較可以得出，相較于其他3種算法，ALNS在尋優(yōu)求解時可避免過早陷入局部最優(yōu)，在求解大規(guī)模問題時優(yōu)勢明顯，在合理的時間內(nèi)算法的求解質(zhì)量更好。

表1 ALNS與其他算法的結(jié)果對比

實驗2選取本文構(gòu)造的12組PCVRPTWSPD算例。使用本文提出的ALNS分別對隨機生成的初始解和插入法生成的初始解進行改進。

表2是使用本文的ALNS對PCVRPTWSPD算例求解10次的平均值。ALNS-random表示使用本文提出的ALNS對隨機生成的初始解改進的計算結(jié)果，ALNS-insert表示使用本文提出的ALNS對提出的插入法生成的初始解改進的計算結(jié)果。COST表示目標函數(shù)值，即總成本與收集到獎金的差值。TIME表示算法的運行時間。P表示ALNS-insert計算結(jié)果與ALNS-random計算結(jié)果的比值。若比值大于1，說明ALNS-random的計算結(jié)果更好，若比值小于1，說明ALNS-insert的計算結(jié)果更好。從表2中可以得到對于兩種生成初始解的方法，算法運行時間相差不多，并且運行時間較短。對于100個客戶點的算例也可以在較短的時間內(nèi)得到解決方案。觀察P值可以得到對于PCVRPTWSPD的12組算例，使用插入法生成初始解在較短的時間內(nèi)得到的解決方案更有效。隨著算例規(guī)模的增加，P值逐漸減小，即ALNS-insert的計算結(jié)果比ALNS-random的計算結(jié)果有效。也就是說本文提出的插入法可以提供一個高質(zhì)量的初始解來提高ALNS的收斂速度，在較短時間內(nèi)得到更好的解決方案。

表2 ALNS改進兩種方法生成的初始解

表3 PCVRPTWSPD實驗計算結(jié)果比較

實驗3對于本文構(gòu)造的12組PCVRPTWSPD模型的算例，分別使用禁忌搜索算法、遺傳算法、離散粒子群算法和本文算法進行求解。為驗證本文算法的有效性，其中禁忌搜索算法、遺傳算法和離散粒子群算法的初始解均根據(jù)本文的插入法生成。

表3是使用4種算法對PCVRPTWSPD算例求解10次的平均值。TS、GA、DPSO、ALNS分別表示禁忌搜索算法、遺傳算法、離散粒子群算法和本文提出的自適應(yīng)大鄰域搜索算法的計算結(jié)果。COST表示目標函數(shù)值，即最小化的總成本與收集到獎金的差值。加粗的部分表示每個算例的最優(yōu)值。最后一列BEST(COST)表示ALNS求解每個算例的最優(yōu)解。從表3中可以看出，對于10個客戶點的算例，本文算法的計算結(jié)果雖然不是最優(yōu)值，但可以達到其他算法的求解效果。隨著算例規(guī)模的增加，其余的9組算例的最優(yōu)值都是通過本文算法得到的。公式(min(TS,GA,SA)-ALNS/ALNS)×100%表示本文算法對每個算例的改進程度，式中TS、GA、SA、ALNS分別表示TS、GA、SA和本文算法的計算結(jié)果。對于算例Rcdp101/25、Rcdp101/50、Rcdp101/100分別改進了6.40%、27.56%、10.18%。對于算例Rcdp104/25、Rcdp104/50、Rcdp104/100分別改進了17.93%、28.09%、5.11%。對于算例Rcdp107/25、Rcdp107/50、Rcdp107/100分別改進了19.80%、15.27%、15.61%。綜合分析可知本文算法對求解大規(guī)模的PCVRPTWSPD問題更有效，得到的結(jié)果更好。

綜合上述3組實驗的結(jié)果，可以得到本文提出的ALNS對解決大規(guī)模的PCVRPTWSPD存在優(yōu)勢，得到的解決方案更有效，驗證了本文算法的有效性與合理性。

4 結(jié)論

本文研究了VPR的變體PCVRP，建立了單目標的PCVRPTWSPD的模型。設(shè)計了ALNS求解模型，采用插入法生成初始解，通過自適應(yīng)策略選擇destroy和repair方法對解改進，并以一定概率接受沒有改進的解，避免算法過早陷入局部最優(yōu)。構(gòu)造了12組算例并對算法進行測試。實驗結(jié)果表明ALNS對大規(guī)模算例有更好的求解效果，并能在小規(guī)模問題上達到其他算法的運算效果。未來可以在本文模型的基礎(chǔ)上對根據(jù)實時交通信息建立動態(tài)的帶軟時間窗同時取送貨的獎金收集車輛路徑問題的模型，為城市物流配送提供更好的解決方案，更好地服務(wù)企業(yè)。