徐 鵬,盧翰林

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

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

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

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

2.1 第一階段算法

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

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

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

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

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

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

7) 重復執(zhí)行步驟2)～6)若干次,返回結(jié)果,每個質(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算法,我們將客戶群進行更簡潔高效的聚類計算,將SMP-VRP轉(zhuǎn)化為SMP-TSP,大大降低了原問題的復雜度。

2.2 第二階段算法

(18)

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

(19)

(20)

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

(21)

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

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

(22)

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

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

(23)

(24)

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

3 算例測試

為驗證所提出的模型和算法,本文模擬京東物流在南京某一片區(qū)(如圖1所示)的城市配送業(yè)務(wù)生成了5組算例,5組算例的客戶數(shù)量均設(shè)為100。路網(wǎng)數(shù)據(jù)是通過OpenStreetMap獲取的真實路網(wǎng)數(shù)據(jù),任意兩個物流節(jié)點之間的路徑數(shù)量設(shè)為3條。京東物流在該區(qū)域的配送中心的經(jīng)緯度坐標數(shù)據(jù)通過百度地圖獲得,客戶的經(jīng)緯度坐標與需求、車輛的額定載重根據(jù)調(diào)研獲取的數(shù)據(jù)模擬生成,方法如下:客戶的需求在[1, 100] (單位: unit)之間隨機均勻產(chǎn)生;配送車輛的額定載重為500 unit;路網(wǎng)中任意兩點間路徑的固定通行成本為兩點間最短路的長度并取整,任意兩點間路徑的固定通行成本的波動在其[0.5, 1]倍之間隨機均勻產(chǎn)生。算法代碼基于Python3.8編寫,并調(diào)用了OSMnx、NetworkX、PyTSP等軟件包,測試平臺為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 測試結(jié)果的對比分析

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

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

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

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

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

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

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

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

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

4 結(jié)語

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