帶時(shí)間窗的同時(shí)取送貨車輛路徑問題求解算法

閆 軍，常 樂，王璐璐，趙 彤

(1.蘭州交通大學(xué) 甘肅省物流與信息技術(shù)研究院，甘肅 蘭州 730070；2.蘭州交通大學(xué) 機(jī)電技術(shù)研究所，甘肅 蘭州730070；3.呼和浩特鐵路局集團(tuán)公司包頭貨運(yùn)中心，內(nèi)蒙古 包頭 014000)

車輛路徑問題 (vehicle routing problem，VRP) 是物流生產(chǎn)活動(dòng)中的核心環(huán)節(jié)，也是組合優(yōu)化和運(yùn)籌學(xué)領(lǐng)域的研究熱點(diǎn)[1]。在實(shí)際的物流服務(wù)中，時(shí)間窗和取送貨服務(wù)是需要滿足的現(xiàn)實(shí)要求，所以帶時(shí)間窗的同時(shí)取送貨的車輛路徑問題 (pickup and delivery problem with time windows, PDPTW)得到越來越多的關(guān)注[2]。

起初解決多車輛的PDPTW問題主要是依靠精確算法，從1991年Dumas等[3]的列生成算法到Furtado等[4]設(shè)計(jì)基于特殊有效不等式的分支切線方法。精確算法雖然無法求解大規(guī)?？蛻舻膶?shí)際案例，但豐富了PDPTW的數(shù)學(xué)模型，為目前的啟發(fā)式算法求解問題提供基礎(chǔ)。本文也以此為基礎(chǔ)建立優(yōu)化模型。Nanry等[5]最早使用響應(yīng)式禁忌啟發(fā)搜索算法對PDPTW進(jìn)行求解，并進(jìn)行25、50和100個(gè)客戶規(guī)模的數(shù)據(jù)實(shí)驗(yàn)。Li等[6]在禁忌搜素算法的基礎(chǔ)上混合模擬退火算法進(jìn)行研究，而且將其研究的數(shù)據(jù)集進(jìn)行公布作為PDPTW的研究基礎(chǔ)。吳璟莉[7]使用遺傳算法對擁有10個(gè)客戶規(guī)模的多車、多貨物倉庫進(jìn)行PDPTW問題的求解。為減少運(yùn)行的車輛數(shù)目，Nagata等[8]運(yùn)用引導(dǎo)式彈射搜索算法來對問題進(jìn)行求解，實(shí)驗(yàn)證明可以有效減少車輛數(shù)。Zou等[9]使用混合粒子群算法對PDPTW進(jìn)行求解，目的是為優(yōu)化多目標(biāo)的PDPTW問題。蟻群算法被用來進(jìn)行PDPTW問題的求解，首次出現(xiàn)于2017年。Tchoupo等[10]強(qiáng)化蟻群算法局部優(yōu)化能力后，與以往實(shí)驗(yàn)結(jié)果進(jìn)行對比，發(fā)現(xiàn)其方法在98.2%的數(shù)據(jù)實(shí)驗(yàn)上取得相同或更好的結(jié)果，證明了蟻群算法在此類問題上的有效性。

本文在考慮客戶規(guī)定時(shí)間窗和退送貨需求的條件下，研究企業(yè)物流配送的最小化成本，建立車輛路徑問題優(yōu)化數(shù)學(xué)模型。首先運(yùn)用K-means聚類算法將具有相同屬性的客戶劃分成不同服務(wù)區(qū)域，綜合考慮時(shí)間窗、與倉庫的相對位置及與其他客戶的距離因素；然后在每個(gè)服務(wù)區(qū)域內(nèi)運(yùn)用蟻群算法對單個(gè)車輛進(jìn)行PDPTW問題求解，為提高螞蟻的搜索能力，建立Q-leaning機(jī)制來改進(jìn)蟻群算法內(nèi)螞蟻的學(xué)習(xí)能力。

1 問題描述及模型構(gòu)建

1.1 問題描述與符號說明

PDPTW定義在圖G(N,A)上 ，節(jié)點(diǎn)集為N={0,1,···,2n+1}，其中，0和2n+1分別表示起點(diǎn)和終點(diǎn)，它們可以表示同一位置。子集P={1,···,n}?N和D={n+1,···,2n}?N將一節(jié)點(diǎn)劃分為取貨點(diǎn)和送貨點(diǎn)兩個(gè)節(jié)點(diǎn)集。節(jié)點(diǎn)i∈N的 需求量為qi，m輛容量為Cap的運(yùn)輸車，從倉庫N=0出發(fā)，按一定順序通過所有節(jié)點(diǎn)，然后返回倉庫，每一輛車只能服務(wù)一條線路，當(dāng)?shù)竭_(dá)節(jié)點(diǎn)i時(shí)車的負(fù)載和時(shí)間分別為Qi和Bi， 其中，Bi要 滿足時(shí)間窗 [ei,li]的 要求。邊集為A={(i,j):i,j∈N,i≠j}， 當(dāng)且僅當(dāng)車輛從節(jié)點(diǎn)i到 節(jié)點(diǎn)j時(shí)，令xij為 等于1的二進(jìn)制變量，Cij為運(yùn)輸?shù)某杀?，tij為i節(jié) 點(diǎn)到j(luò)節(jié)點(diǎn)的車輛行駛時(shí)間[11]。

本文研究的PDPTW可描述為在不超過客戶規(guī)定的時(shí)間窗和運(yùn)輸車輛的載貨量的約束下，找到不超過m條路徑使運(yùn)輸成本最小，并且盡可能地平衡各路徑的總長度，通過這樣的路徑規(guī)劃為客戶提供同時(shí)取送貨的服務(wù)，并且車輛最終返回倉庫。

1.2 模型建立

基于以上問題描述與符號，建立以下PDPTW兩指標(biāo)數(shù)學(xué)模型。

目標(biāo)函數(shù)(1)使總的路徑成本最小化。式(2)和(3)保證每個(gè)節(jié)點(diǎn)僅被訪問一次，時(shí)間變量和負(fù)載變量的一致性分別由式(4)和(5)確保，其中，常數(shù)M被定義為足夠大的數(shù)字，時(shí)間窗和車輛容量分別由式(6)和(7)保證。此外，式(4)和(6)消除子路徑。式(8)滿足取貨點(diǎn)和送貨點(diǎn)的優(yōu)先級關(guān)系。約束(9)～(13)進(jìn)行路徑信息的索引，保證車輛與路徑的配對關(guān)系。其中，v表示儲存路徑信息，當(dāng)節(jié)點(diǎn)i屬于第一條路徑時(shí)vi=1。 最后，約束條件(14)使兩指標(biāo)變量變得完整。

2 聚類處理的蟻群算法設(shè)計(jì)

算法分為兩步：1) 對配送點(diǎn)進(jìn)行區(qū)域劃分，根據(jù)所劃分區(qū)域情況明確每一區(qū)域具體的取送貨量以及整個(gè)配送活動(dòng)的運(yùn)行車輛數(shù)目；2) 根據(jù)第1) 步的數(shù)據(jù)進(jìn)行具體的單車輛線路規(guī)劃。具體流程如下。

2.1 基于K-means算法的區(qū)域分割聚類處理的蟻群算法設(shè)計(jì)

本文對于PDPTW問題進(jìn)行客戶節(jié)點(diǎn)聚類，與傳統(tǒng)的K-means聚類方法不同的是要考慮配送車輛的容量限制、倉庫與客戶點(diǎn)的位置關(guān)系(根據(jù)倉庫的位置進(jìn)行客戶點(diǎn)的聚類)的影響。因此本文為適應(yīng)PDPTW的實(shí)際需求，在K-means劃分區(qū)域的基礎(chǔ)上進(jìn)行修正。具體流程如下。

根據(jù)擁有的運(yùn)輸汽車數(shù)量設(shè)定聚類數(shù)范圍，計(jì)算平均BWP也就是avgBWP值來判斷整體的聚類有效性。當(dāng)平均BWP值最大時(shí)，對應(yīng)的聚類數(shù)便是最佳聚類數(shù)kopt。

2.2 基于Q-learning的蟻群算法

初始的多車輛復(fù)雜VRP經(jīng)過聚類處理后變成簡單的單車輛VRP，故求解的計(jì)算量減少，所以此階段需要算法有很強(qiáng)的局部搜索能力。蟻群算法中螞蟻的轉(zhuǎn)移概率引入強(qiáng)化學(xué)習(xí)機(jī)制，使蟻群算法的收斂能力得到提高[13]。

式中， H E(r,u)是一種啟發(fā)式函數(shù)，在本文中用來評價(jià)節(jié)點(diǎn)r移動(dòng)到s的優(yōu)劣。 δ 、β是權(quán)衡學(xué)習(xí)經(jīng)驗(yàn)矩陣和啟發(fā)式函數(shù)相對重要性的參數(shù)。f是屬于[0,1]的隨機(jī)值，而f0是 大于0小于1的一個(gè)參數(shù)，當(dāng)f≤f0時(shí) 選擇下一個(gè)節(jié)點(diǎn)s， 否則隨機(jī)產(chǎn)生屬于[0,1]的數(shù)s。通過輪盤賭的方式與式(19)所計(jì)算的概率值Pk(r,s)進(jìn)行比較選擇下一節(jié)點(diǎn)。路徑上的信息素依靠學(xué)習(xí)經(jīng)驗(yàn)矩陣的循環(huán)迭代進(jìn)行更新，AQ根據(jù)式(20)進(jìn)行更新。

圖1 基于Q-learning的蟻群算法結(jié)構(gòu)Figure 1 Ant colony algorithm structure based on Q-learning

3 算例實(shí)驗(yàn)與結(jié)果分析

為檢驗(yàn)設(shè)計(jì)算法的有效性，本文設(shè)計(jì)兩個(gè)實(shí)驗(yàn)。實(shí)驗(yàn)1為驗(yàn)證加入聚類分析的作用，將普通多車量VRP問題作為模型，運(yùn)用本文方法和文獻(xiàn)中的其他方法分別求解，得出結(jié)果進(jìn)行對比。實(shí)驗(yàn)2為驗(yàn)證本文提出的模型和算法在大規(guī)模車輛路徑問題中的適用性，采取300個(gè)節(jié)點(diǎn)規(guī)模PDPTW問題的算例進(jìn)行實(shí)驗(yàn)分析。

本文算法在Matlab 2018a上進(jìn)行實(shí)驗(yàn)，并在一臺搭載1.9GHz的AMD四核A10處理器和8GB內(nèi)存的計(jì)算機(jī)上實(shí)現(xiàn)，蟻群數(shù)設(shè)為100，進(jìn)行50次迭代。算法涉及參數(shù)根據(jù)控制變量法實(shí)驗(yàn)得出，每次只變動(dòng)某一參數(shù)進(jìn)行實(shí)驗(yàn)，確定合適的參數(shù)值，具體參數(shù)設(shè)置如表1所示。

表1 參數(shù)設(shè)置Table 1 parameter settings

實(shí)驗(yàn)1運(yùn)用Wang等[14]提出的關(guān)于VRPSPDTW的標(biāo)準(zhǔn)算例，并且將本文提出的KQ-SA (結(jié)合K-means的Q-learning蟻群算法)與Wang等[14]提出的并行模擬退火算法 (parallel-simulated annealing, p-SA)和王超等[15]的離散布谷鳥算法 (discrete cuckoo search, DCS)進(jìn)行對比實(shí)驗(yàn)。本文應(yīng)用環(huán)境為大規(guī)模車輛路徑問題，所以采用的算例節(jié)點(diǎn)數(shù)為25、50、100的各3組算例進(jìn)行實(shí)驗(yàn)。節(jié)點(diǎn)數(shù)為100的算例路徑規(guī)劃如圖2和圖3所示，圖中五角星為倉庫位置。

圖2 節(jié)點(diǎn)聚類結(jié)果Figure 2 Clustering results of nodes

圖3 節(jié)點(diǎn)路線規(guī)劃結(jié)果Figure 3 Node route planning results

每個(gè)算例進(jìn)行10次，取最優(yōu)結(jié)果所需車輛數(shù)目(number vehicle, NV)和行駛距離(travel distanced, TD)記錄，如表2所示。其中行駛距離單位為km。由表2可知，KQ-AG可以的中小規(guī)模中的算例中可以得到與當(dāng)前國際最優(yōu)解相近似的解，并且在100個(gè)節(jié)點(diǎn)的算例中能夠得出優(yōu)于文獻(xiàn)中的計(jì)算結(jié)果。

表2 實(shí)驗(yàn)1算法結(jié)果對比Table 2 Comparison of algorithm results of Experiment 1

實(shí)驗(yàn)2 收集文獻(xiàn)中PDPTW問題算例實(shí)驗(yàn)結(jié)果最優(yōu)的數(shù)據(jù)，并將其作為對照組與本文的所建模型和算法進(jìn)行對比，表3展示了15組300客戶規(guī)模的實(shí)驗(yàn)對比結(jié)果。

從表3中數(shù)據(jù)可以看出，本文模型和求解算法在計(jì)算時(shí)長上有很突出的進(jìn)步，這主要是使用了聚類方法簡化計(jì)算的復(fù)雜度。表中標(biāo)粗?jǐn)?shù)據(jù)為總行駛距離最優(yōu)解，本文提出的方法在15組實(shí)驗(yàn)中有6組低于文獻(xiàn)的最優(yōu)解，有5組優(yōu)于文獻(xiàn)的解，其余得出相同解。本文方法在減少行駛距離時(shí)的優(yōu)勢不明顯，低于文獻(xiàn)最優(yōu)解的實(shí)驗(yàn)中發(fā)現(xiàn)，倉庫在偏離配送點(diǎn)較遠(yuǎn)的位置，聚類的優(yōu)勢效果沒有體現(xiàn)出來。綜合15輪實(shí)驗(yàn)數(shù)據(jù)，本問題提出的模型和解決算法可以求解出較優(yōu)的結(jié)果，并且在縮短計(jì)算時(shí)間方面有較好的表現(xiàn)。

表3 實(shí)驗(yàn)2算法結(jié)果對比Table 3 Comparison of algorithm results of Experiment 2

4 結(jié)語

本文建立兩指標(biāo)的PDPTW問題模型，較三指標(biāo)體系更簡單計(jì)算速度更快。為解決大規(guī)模算例計(jì)算量大的問題，本文對客戶節(jié)點(diǎn)首先進(jìn)行聚類處理，然后進(jìn)行具體路徑求解，并且在使用K-means算法時(shí)，引入BWP指標(biāo)來提升聚類的效果。為了提高蟻群算法的搜素能力，使用Q-leaning自適應(yīng)蟻群算法對單獨(dú)車輛的路徑進(jìn)行規(guī)劃。本文提出的方法具有較強(qiáng)的適用性，在中小規(guī)模的案例中均能有較好表現(xiàn)，并且在計(jì)算大規(guī)模的算例時(shí)，縮短計(jì)算時(shí)間有比較大的突破。本文在縮短路徑距離方面能力一般，接下來的研究主要是在聚類方面，如何能夠解決偏離客戶節(jié)點(diǎn)的倉庫位置對路徑規(guī)劃的影響。

(責(zé)任編輯: 劉敏儀)