隨機多路徑車輛路徑問題及其算法

徐 鵬,盧翰林

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

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

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

1 問題描述與建模

minE[f(X,Θ)]

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

s.t.

(8)

(9)

2 算法設計

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

2.1 第一階段算法

K-means算法是目前人工智能領域常用的一種基于無監督學習的聚類算法,可以將數據集中的樣本劃分成若干個不相交的子集[12]。本文以配送車輛的額定載重為約束,采用具有約束的K-means算法實現對客戶的分組,具體步驟如下:

1) 輸入原始數據:包括每個客戶的經緯度坐標、每個客戶的貨運需求量以及配送車輛的額定載重Q;

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

4) 按順序將客戶逐一分配給距其最近且有剩余服務能力的質心;

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

6) 更新每個質心的坐標,即用每個質心所服務客戶的經度、緯度坐標的均值代替其當前的經度、緯度坐標;

7) 重復執行步驟2)～6)若干次,返回結果,每個質心所服務的客戶即為一組。

minE[g(X,Θ)]

(10)

s.t.

(11)

(12)

(13)

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

(14)

(15)

s.t.

(16)

(17)

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

2.2 第二階段算法

(18)

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

(19)

(20)

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

(21)

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

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

(22)

式中,|Tij|max表示任意兩點間路徑數量的最大值;fDET表示以兩點間最短路構成的確定型TSP的目標函數值;|N|表示節點的數量;m表示任意兩點間最短路距離的最小值。

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

(23)

(24)

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

3 算例測試

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

圖1 所研究區域的路網圖Fig.1 Road network map of the studied area

3.1 測試結果的對比分析

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

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

3.2 測試結果的穩定性分析

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

圖2 路徑數為3的求解質量圖Fig.2 Solution quality based on 3 paths

圖3 路徑數為4的求解質量圖Fig.3 Solution quality based on 4 paths

圖4 路徑數為5的求解質量圖Fig.4 Solution quality based on 5 paths

3.3 不同路徑數目對成本影響測試

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

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

3.4 配送車輛載重對成本影響測試

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

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

4 結語

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