閆 軍，常 樂(lè)，王璐璐，趙 彤

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

車輛路徑問(wèn)題 (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í)取送貨的車輛路徑問(wèn)題 (pickup and delivery problem with time windows, PDPTW)得到越來(lái)越多的關(guān)注[2]。

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

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

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

1.1 問(wèn)題描述與符號(hào)說(shuō)明

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)輸車，從倉(cāng)庫(kù)N=0出發(fā)，按一定順序通過(guò)所有節(jié)點(diǎn)，然后返回倉(cāng)庫(kù)，每一輛車只能服務(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ò)客戶規(guī)定的時(shí)間窗和運(yùn)輸車輛的載貨量的約束下，找到不超過(guò)m條路徑使運(yùn)輸成本最小，并且盡可能地平衡各路徑的總長(zhǎng)度，通過(guò)這樣的路徑規(guī)劃為客戶提供同時(shí)取送貨的服務(wù)，并且車輛最終返回倉(cāng)庫(kù)。

1.2 模型建立

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

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

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

算法分為兩步：1) 對(duì)配送點(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ì)

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

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

2.2 基于Q-learning的蟻群算法

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

式中， H E(r,u)是一種啟發(fā)式函數(shù)，在本文中用來(lái)評(píng)價(jià)節(jié)點(diǎn)r移動(dòng)到s的優(yōu)劣。 δ 、β是權(quán)衡學(xué)習(xí)經(jīng)驗(yàn)矩陣和啟發(fā)式函數(shù)相對(duì)重要性的參數(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。通過(guò)輪盤賭的方式與式(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問(wèn)題作為模型，運(yùn)用本文方法和文獻(xiàn)中的其他方法分別求解，得出結(jié)果進(jìn)行對(duì)比。實(shí)驗(yàn)2為驗(yàn)證本文提出的模型和算法在大規(guī)模車輛路徑問(wèn)題中的適用性，采取300個(gè)節(jié)點(diǎn)規(guī)模PDPTW問(wèn)題的算例進(jìn)行實(shí)驗(yàn)分析。

本文算法在Matlab 2018a上進(jìn)行實(shí)驗(yàn)，并在一臺(tái)搭載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]的離散布谷鳥(niǎo)算法 (discrete cuckoo search, DCS)進(jìn)行對(duì)比實(shí)驗(yàn)。本文應(yīng)用環(huán)境為大規(guī)模車輛路徑問(wèn)題，所以采用的算例節(jié)點(diǎn)數(shù)為25、50、100的各3組算例進(jìn)行實(shí)驗(yàn)。節(jié)點(diǎn)數(shù)為100的算例路徑規(guī)劃如圖2和圖3所示，圖中五角星為倉(cāng)庫(kù)位置。

圖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)前國(guó)際最優(yōu)解相近似的解，并且在100個(gè)節(jié)點(diǎn)的算例中能夠得出優(yōu)于文獻(xiàn)中的計(jì)算結(jié)果。

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

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

從表3中數(shù)據(jù)可以看出，本文模型和求解算法在計(jì)算時(shí)長(zhǎng)上有很突出的進(jìn)步，這主要是使用了聚類方法簡(jiǎ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)勢(shì)不明顯，低于文獻(xiàn)最優(yōu)解的實(shí)驗(yàn)中發(fā)現(xiàn)，倉(cāng)庫(kù)在偏離配送點(diǎn)較遠(yuǎn)的位置，聚類的優(yōu)勢(shì)效果沒(méi)有體現(xiàn)出來(lái)。綜合15輪實(shí)驗(yàn)數(shù)據(jù)，本問(wèn)題提出的模型和解決算法可以求解出較優(yōu)的結(jié)果，并且在縮短計(jì)算時(shí)間方面有較好的表現(xiàn)。

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

4 結(jié)語(yǔ)

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

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