隨機(jī)多路徑車輛路徑問題及其算法

徐 鵬,盧翰林

(河海大學(xué) 土木與交通學(xué)院,江蘇 南京 210098)

近年來,以小批量、多頻次、多品種、時(shí)效性強(qiáng)為主要特征的城市配送業(yè)務(wù)增長(zhǎng)迅猛。以快遞業(yè)為例,根據(jù)國(guó)家郵政局統(tǒng)計(jì),我國(guó)快遞業(yè)務(wù)量從2012年的56.85億件增長(zhǎng)到2022年的1 105.8億件[1],十年間增長(zhǎng)了近20倍。面對(duì)早已擁堵不堪的城市道路,規(guī)模龐大的城市配送業(yè)務(wù)讓“最后一公里”[2]難題變得更加嚴(yán)峻。因此,為城市配送業(yè)務(wù)提供核心解決方案的車輛路徑問題(vehicle routing problem,VRP),受到物流研究人員和從業(yè)人員的關(guān)注[3]。針對(duì)不同的應(yīng)用場(chǎng)景,國(guó)內(nèi)外學(xué)者對(duì)經(jīng)典的VRP進(jìn)行了各種各樣的拓展[4-6],取得了豐碩的研究成果。王勇等[7]通過引入客戶信用度的測(cè)度方法,建立了考慮客戶信用度的VRP模型,并設(shè)計(jì)了一種遺傳-禁忌搜索混合算法,不僅可以優(yōu)化配送路線,降低成本,還能保證客戶的滿意度;張冬青等[8]針對(duì)配送車輛在真實(shí)路網(wǎng)中行駛時(shí)間的隨機(jī)性,建立了考慮時(shí)空相關(guān)隨機(jī)行駛時(shí)間的VRP模型,并設(shè)計(jì)了一種結(jié)合可變鄰域下降算法的混合粒子群算法,解決了時(shí)空相關(guān)下的車輛路徑規(guī)劃問題;Agussurja等[9]針對(duì)客戶需求的隨機(jī)性,建立了多周期的隨機(jī)VRP模型,并利用隨機(jī)動(dòng)態(tài)規(guī)劃方法進(jìn)行了求解,解決隨機(jī)多期末端騎行共享問題;柳伍生等[10]從城市配送的發(fā)展趨勢(shì)出發(fā),建立了 “無人機(jī)-車輛”聯(lián)合配送的VRP模型,并設(shè)計(jì)了一種帶末端優(yōu)化的模擬退火算法,以最小化總運(yùn)輸成本和總運(yùn)輸時(shí)間為目標(biāo),并解決了路徑規(guī)劃中的多個(gè)約束條件。

目前的VRP模型已經(jīng)可以解決大規(guī)模的車輛路徑規(guī)劃問題,但仍有一些挑戰(zhàn)和改進(jìn)的空間。一方面,目前幾乎所有的VRP模型都假定任意兩個(gè)節(jié)點(diǎn)之間只有一條路徑,沒有考慮多路徑的情況,然而在現(xiàn)實(shí)的城市路網(wǎng)中兩個(gè)物流節(jié)點(diǎn)之間往往存在多條路徑;另一方面,目前大多數(shù)隨機(jī)VRP模型考慮的是客戶需求的隨機(jī)性,很少考慮車輛通行成本或時(shí)間的隨機(jī)性,雖有少數(shù)的VRP模型考慮了車輛通行成本或時(shí)間的隨機(jī)性,但通常假定通行成本或時(shí)間服從某種概率分布或是時(shí)間依賴的,然而在現(xiàn)實(shí)的城市路網(wǎng)中兩個(gè)物流節(jié)點(diǎn)之間的任一路徑由于受到交通擁堵、道路施工、天氣狀況等因素的影響具有高度的不確定性,這種不確定性一般很難利用某種概率分布進(jìn)行描述。為此,本文對(duì)經(jīng)典的VRP進(jìn)行了新的拓展研究,考慮了任意兩個(gè)物流節(jié)點(diǎn)之間存在多條路徑且每條路徑的通行成本或時(shí)間真正不確定性的情況,簡(jiǎn)稱為隨機(jī)多路徑(stochastic multi-path vehicle routing problem,SMP-VRP),以期為第三方物流企業(yè)開展城市配送提供更加合理有效的技術(shù)支持。

1 問題描述與建模

minE[f(X,Θ)]

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

s.t.

(8)

(9)

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

VRP屬于NP-hard組合優(yōu)化問題,求解難度較大,可想而知SMP-VRP的求解難度更大[11]。為此,本文設(shè)計(jì)了一種具有較高求解效率的兩階段算法。為降低問題求解的復(fù)雜度,算法的第一階段采用具有約束的K-means算法對(duì)客戶進(jìn)行分組,為VRP問題提供了快速的初始解,降低問題計(jì)算的時(shí)間?；诳蛻舻姆纸M結(jié)果,SMP-VRP可被拆分成若干個(gè)隨機(jī)多路徑旅行商問題(stochastic multi-path traveling salesman problem,SMP-TSP);算法的第二階段,為解決通行成本的不確定性,先將SMP-TSP轉(zhuǎn)化成等價(jià)的情景規(guī)劃問題(deterministic equivalent problem,DEP),再近似成確定型規(guī)劃問題(deterministic approximation problem,DAP),并加以求解。

2.1 第一階段算法

K-means算法是目前人工智能領(lǐng)域常用的一種基于無監(jiān)督學(xué)習(xí)的聚類算法,可以將數(shù)據(jù)集中的樣本劃分成若干個(gè)不相交的子集[12]。本文以配送車輛的額定載重為約束,采用具有約束的K-means算法實(shí)現(xiàn)對(duì)客戶的分組,具體步驟如下:

1) 輸入原始數(shù)據(jù):包括每個(gè)客戶的經(jīng)緯度坐標(biāo)、每個(gè)客戶的貨運(yùn)需求量以及配送車輛的額定載重Q;

3) 將客戶按其貨運(yùn)需求量從大到小降序排列;

4) 按順序?qū)⒖蛻糁鹨环峙浣o距其最近且有剩余服務(wù)能力的質(zhì)心;

5) 若所有客戶均被分配,則轉(zhuǎn)入步驟6),若有客戶無法進(jìn)行分配,則令M=M+1,返回步驟2),如此直至所有客戶均完成分配;

6) 更新每個(gè)質(zhì)心的坐標(biāo),即用每個(gè)質(zhì)心所服務(wù)客戶的經(jīng)度、緯度坐標(biāo)的均值代替其當(dāng)前的經(jīng)度、緯度坐標(biāo);

7) 重復(fù)執(zhí)行步驟2)～6)若干次,返回結(jié)果,每個(gè)質(zhì)心所服務(wù)的客戶即為一組。

minE[g(X,Θ)]

(10)

s.t.

(11)

(12)

(13)

Xij∈{0,1},?(i,j)∈A

(14)

(15)

s.t.

(16)

(17)

通過K-means算法,我們將客戶群進(jìn)行更簡(jiǎn)潔高效的聚類計(jì)算,將SMP-VRP轉(zhuǎn)化為SMP-TSP,大大降低了原問題的復(fù)雜度。

2.2 第二階段算法

(18)

約束條件為式(11)～(14)以及

(19)

(20)

雖然DEP模型屬確定型模型,但在現(xiàn)實(shí)中要全面劃分各種交通情景非常困難,而且路徑隨機(jī)通行成本的概率分布也很難得知。根據(jù)Fadda等[15]的研究,在現(xiàn)實(shí)的城市路網(wǎng)中路徑的隨機(jī)通行成本具有明顯的左尾漸進(jìn)獨(dú)立性,不論路徑的隨機(jī)通行成本服從正態(tài)分布還是耿貝爾、拉普拉斯、均勻、Logistic等常見分布,DEP模型均可近似成如下的確定型規(guī)劃問題(DAP):

(21)

約束條件為式(11)～(14)。

β=7.84/(2|Tij|maxfDET/|N|-m)

(22)

式中,|Tij|max表示任意兩點(diǎn)間路徑數(shù)量的最大值;fDET表示以兩點(diǎn)間最短路構(gòu)成的確定型TSP的目標(biāo)函數(shù)值;|N|表示節(jié)點(diǎn)的數(shù)量;m表示任意兩點(diǎn)間最短路距離的最小值。

由于DAP模型的目標(biāo)函數(shù)只體現(xiàn)了求解決策變量Xij的成本開銷,因此SMP-TSP模型的目標(biāo)函數(shù)值需通過以下的蒙特卡洛仿真步驟得到:

(23)

(24)

至此,通過求解每一個(gè)SMP-TSP,即可得到SMP-VRP的解。在算法的第二階段,通過將SMP-TSP問題轉(zhuǎn)化為DEP問題,再轉(zhuǎn)化為DAP問題求解,大大降低了原問題的求解難度;通過蒙特卡洛仿真來近似求解DAP模型,大大提高了模型在現(xiàn)實(shí)交通情景中的適用性。

3 算例測(cè)試

為驗(yàn)證所提出的模型和算法,本文模擬京東物流在南京某一片區(qū)(如圖1所示)的城市配送業(yè)務(wù)生成了5組算例,5組算例的客戶數(shù)量均設(shè)為100。路網(wǎng)數(shù)據(jù)是通過OpenStreetMap獲取的真實(shí)路網(wǎng)數(shù)據(jù),任意兩個(gè)物流節(jié)點(diǎn)之間的路徑數(shù)量設(shè)為3條。京東物流在該區(qū)域的配送中心的經(jīng)緯度坐標(biāo)數(shù)據(jù)通過百度地圖獲得,客戶的經(jīng)緯度坐標(biāo)與需求、車輛的額定載重根據(jù)調(diào)研獲取的數(shù)據(jù)模擬生成,方法如下:客戶的需求在[1, 100] (單位: unit)之間隨機(jī)均勻產(chǎn)生;配送車輛的額定載重為500 unit;路網(wǎng)中任意兩點(diǎn)間路徑的固定通行成本為兩點(diǎn)間最短路的長(zhǎng)度并取整,任意兩點(diǎn)間路徑的固定通行成本的波動(dòng)在其[0.5, 1]倍之間隨機(jī)均勻產(chǎn)生。算法代碼基于Python3.8編寫,并調(diào)用了OSMnx、NetworkX、PyTSP等軟件包,測(cè)試平臺(tái)為Windows 11;具有約束的K-means算法的迭代次數(shù)設(shè)置為300次;蒙特卡洛仿真的交通情景設(shè)置為100種、迭代次數(shù)設(shè)置為10次。

圖1 所研究區(qū)域的路網(wǎng)圖Fig.1 Road network map of the studied area

3.1 測(cè)試結(jié)果的對(duì)比分析

為驗(yàn)證該算法的先進(jìn)性,本文模擬了京東物流的日常配送模式——基于經(jīng)驗(yàn)的車輛路徑安排,即按照最近鄰域搜索算法安排車輛路徑。其中,每組算例運(yùn)行10次,10次結(jié)果取均值計(jì)入表中,結(jié)果如表1所示。其中,算例1求解的均值結(jié)果表現(xiàn)出的優(yōu)越性為最好,配送成本降低約8.4%,算例5的求解結(jié)果為最低,約6.0%,其余算例的配送成本的節(jié)約則在此之間。數(shù)據(jù)表明,兩階段算法對(duì)比最近領(lǐng)域搜索算法能夠帶來7.1%的平均配送成本節(jié)約,這說明本文提出的兩階段算法比最近鄰域搜索算法更具優(yōu)勢(shì)。

表1 基于不同組織方法的配送成本Tab.1 Distribution cost based on different organizational methods

3.2 測(cè)試結(jié)果的穩(wěn)定性分析

為考察多路徑對(duì)兩階段算法求解結(jié)果穩(wěn)定性的影響,分別以客戶節(jié)點(diǎn)之間路徑數(shù)量為3、4、5進(jìn)行運(yùn)算,計(jì)算結(jié)果繪制箱線圖(如圖2、3、4)。5組算例在每種路徑數(shù)目下各進(jìn)行10次運(yùn)算,將結(jié)果繪制成箱型圖。根據(jù)圖顯示結(jié)果,整體數(shù)據(jù)沒有離群點(diǎn),說明數(shù)據(jù)比較均衡,沒有過多的異常數(shù)據(jù);根據(jù)圖中的中位線位置分析,客戶節(jié)點(diǎn)之間可能存在多條路徑,而算例2的期望成本明顯高于其他算例,這表明多路徑條件下,算例計(jì)算出的期望成本取決于算例本身的組成結(jié)構(gòu)。此外,其他算例的期望成本差距不大。因此,合理地選擇客戶進(jìn)行服務(wù)可以避免高額的配送成本投入。需要注意的是,在多路徑條件下,算例的組成結(jié)構(gòu)會(huì)對(duì)期望成本產(chǎn)生較大的影響,因此在選擇客戶進(jìn)行服務(wù)時(shí),需要進(jìn)行合理的規(guī)劃和優(yōu)化,才能夠有效地降低配送成本并提高服務(wù)質(zhì)量。圖中直觀地反映了每組算例求解結(jié)果的波動(dòng)情況,可以看出波動(dòng)較小,求解結(jié)果較為穩(wěn)定,且該性質(zhì)并不因?yàn)槁窂綌?shù)目的變化而變化。

圖2 路徑數(shù)為3的求解質(zhì)量圖Fig.2 Solution quality based on 3 paths

圖3 路徑數(shù)為4的求解質(zhì)量圖Fig.3 Solution quality based on 4 paths

圖4 路徑數(shù)為5的求解質(zhì)量圖Fig.4 Solution quality based on 5 paths

3.3 不同路徑數(shù)目對(duì)成本影響測(cè)試

為考察多路徑對(duì)配送成本的影響,將計(jì)算結(jié)果取均值繪制柱狀圖,如圖5所示。在同一組算例中,路徑數(shù)為3得到的期望配送成本是最高的,路徑數(shù)為5得到的期望配送成本是最低的。不難看出,隨著兩節(jié)點(diǎn)的路徑數(shù)目的增加,配送成本變得越低。在現(xiàn)實(shí)生活中,當(dāng)配送車輛在客戶節(jié)點(diǎn)之間存在著更多的路徑選擇,就能做出更優(yōu)的選擇結(jié)果,從而更好地減少配送成本。

圖5 不同路徑數(shù)對(duì)配送成本的影響Fig.5 Impact of different numbers of paths on distribution cost

3.4 配送車輛載重對(duì)成本影響測(cè)試

本文還通過修改配送車輛的載重,來觀察載重對(duì)配送成本的影響。分別選擇載重為300、400、500 unit,對(duì)每組算例進(jìn)行10次運(yùn)算,取均值計(jì)入圖中(如圖6所示)。根據(jù)圖中所示,隨著車載的加大,配送成本顯著降低。載重的調(diào)整會(huì)影響配送路徑的選擇和客戶的分組,更大容量的載重使得配送車輛攜帶更多的貨物,能夠服務(wù)更多的客戶,從而降低成本。盡量避免某些需要較多物資的客戶被單獨(dú)分配,這意味著需要進(jìn)行多次配送,增加了成本。適當(dāng)提高載重限制,可以在保證客戶需求和貨物配送的同時(shí),減少配送車輛的數(shù)量和降低配送成本。

圖6 載重對(duì)配送成本的影響Fig.6 Impact of capacity on distribution cost

4 結(jié)語(yǔ)

本文在經(jīng)典VRP的基礎(chǔ)上,考慮了配送車輛在客戶節(jié)點(diǎn)之間路徑選擇的多樣性,及其路徑上的各種不確定的環(huán)境因素,將問題轉(zhuǎn)變成隨機(jī)、多路徑車輛問題,建立的隨機(jī)多路徑VRP模型更加契合現(xiàn)實(shí)的城市配送運(yùn)作環(huán)境?；诂F(xiàn)實(shí)城市交通網(wǎng)絡(luò),考慮客戶節(jié)點(diǎn)之間的多路徑,并通過求解DAP模型解決環(huán)境因素,設(shè)計(jì)了一套兩階段算法。通過算例測(cè)試分析可以發(fā)現(xiàn),本文提出的兩階段算法在SMP-VRP問題的路徑規(guī)劃中展現(xiàn)出了明顯的優(yōu)勢(shì),相比于基于經(jīng)驗(yàn)的車輛路徑安排,兩階段算法可以帶來平均7.1%的配送成本節(jié)約;大量的測(cè)試數(shù)據(jù)顯示,計(jì)算結(jié)果是穩(wěn)定的,具有可靠性;通過分別改變客戶節(jié)點(diǎn)之間的路徑數(shù)量以及車載的大小,發(fā)現(xiàn)實(shí)驗(yàn)結(jié)果能很好地契合現(xiàn)實(shí)生活中實(shí)際情況,具有現(xiàn)實(shí)意義和應(yīng)用價(jià)值。因此,本文提出的兩階段算法是一種可行、穩(wěn)定而有效的優(yōu)化配送成本的方法,可以在實(shí)際中得到更廣泛的應(yīng)用。