多時空配送任務驅動的無人車隊車輛數優化方法

鄭李萍，王建強，張玉召，董祚帆

（蘭州交通大學交通運輸學院，蘭州 730070）

（*通信作者電子郵箱xinxiwjq@126.com）

0 引言

具有精確導航和自動化配送特征的無人配送車（后文簡稱為無人車）受到物流企業的青睞，并將其應用于社區和園區等特定場景的快遞終端配送。已有研究表明由無人車參與的快遞終端配送模式具有眾多優勢。Boysen 等［1］提出由卡車和無人車協作完成市中心最后1 km 快遞配送有利于緩解市中心的擁堵；Ulmer等［2］提出將無人車與快遞取件站相結合以降低終端配送運營成本；Figliozzi［3］發現相較于電動車和傳統內燃機車，無人車有利于降低快遞配送中的碳排放。

物流配送過程存在時間的隨機性，通常做法是假設時間服從一定的概率分布。如Ehmke 等［4］在給定顧客服務水平的前提下，假設車輛的行駛時長服從正態分布；Gutierrez 等［5］假設具有不確定性的到達時間服從對數正態分布，并論證了其合理性；Binart 等［6］在模型構建時將時間離散化，假設服務時長服從離散三角形分布。

在任務驅動下的路徑優化研究中，已有成果關注對象主要是某一具體任務。如Wang 等［7］提出考慮個體出行者偏好的個性化路徑推薦算法，實現了從起點到目的地的最優路徑規劃；麻存瑞等［8］設計了一種采用自然數編碼的遺傳算法以尋找在一次配送中總時間最短的多車配送路徑方案；李玲玉等［9］針對單配送員多任務的配送路徑優化問題，設計出C-W（Clark-Wright）節約算法。解決方案主要是算法優化，如Yu等［10］提出一種改進分支定界算法優化車隊的行駛路徑；張毅等［11］針對人工魚群算法在機器人全局路徑規劃中容易陷入局部最優的缺陷，提出一種混合改進人工魚群算法；趙志學等［12］設計一種融合模擬退火算法的混合差分進化算法優化交通擁堵區域的物流配送線路。

在已有研究成果的基礎上，尚存在3 個問題有待于進一步探討：1）如何在滿足一定成功服務率的同時，確定并優化無人車隊數量依然是快遞終端配送面臨的巨大挑戰；2）如何利用網絡轉化方法進行路徑規劃缺乏研究；3）服務時長的設定也未充分考慮顧客的行走時長特征。

基于此，本文提出可靠車隊問題并進行了詳細描述，以確保在高成功服務率的前提下為配送中心規劃最小無人車隊車輛數。充分考慮顧客行走時長特征，假設無人車服務時長服從正態分布。網絡模型的構建與轉化的過程，也是將求解最小車隊車輛數通過最小路徑覆蓋問題轉化為網絡最大流問題的過程。最后設計了在大規模服務網絡計算中適用的Dijkstra-Dinic算法求解該問題。

1 問題描述

給定服務需求集合C，每一個服務ci∈C被定義為一個元組(ei，li，ni，qi)，其中ei、li分別表示預約服務時間窗的最早時刻和最晚時刻，ni表示服務地點，qi表示取/送貨物量。將可靠車隊問題定義為：將最晚時刻li作為無人車的目標開始服務時刻，在保證高成功服務率的前提下，使最小車輛數的車隊從配送中心出發，并在完成所有服務后返回配送中心。便于研究，本文假設如下：1）無人車在路段aij，以速度vij勻速行駛；2）所有車輛在初始時刻續航里程相同；3）顧客在最晚時刻li后到達服務點ni。

2 模型構建

通過構建最短路徑模型、服務網絡模型和最小車隊模型，將可靠車隊問題轉化為便于求解的最大流問題，如圖1所示。

圖1 模型構建流程Fig.1 Model construction process

2.1 最短路徑模型

用G(V，A)表示一個由有限個節點組成的交通網絡，其中V是節點集，V=Vser∪Vcro包括服務節點集Vser（包含配送中心集O）和路口節點集Vcro，A為路段集。ni表示節點集合中的任意一個節點，ni∈V；aij表示相鄰節點間路段，aij∈A。

對于最晚時刻不同的起訖點nr、ns，?nr，ns∈Vser，lr＜ls，建立距離最短路徑模型。

目標函數：

約束條件：

式中：dij為路段aij的距離，xij為決策變量xij∈{0，1}，(i，j) ∈A。

服務時長和等待時長是最短路徑規劃需要考慮的重要參數，考慮服務時長是為了確保高成功服務率，等待時長的設定是避免無人車提前到達服務點后因長時間等待而影響整體配送效率［13］。

服務時長Ti表示無人車在服務點ni從最晚時刻li到離開時刻ti的時間差，Ti=ti-li。本文假設Ti近似服從均值為μi、方差為σi2的正態分布，Ti∈N(μi，σi2)，σi2體現顧客到達服務點時刻的集中程度，σi2越小，顧客到達時刻越集中。當成功服務概率為1-α時，可靠服務時長的計算如式（3）所示，由于不考慮顧客提前到達，可靠服務時長區間為

式中：trs為起訖點nr，ns的行駛時長，計算方法如式（5）所示：

式中drs表示路段ars的長度。

無人車需要提前或準時在最晚時刻到達，如式（6）所示，圖2展示了無人車在相鄰起訖點nr，ns具體時間狀態。

圖2 無人車在相鄰起訖點間的時間狀態Fig.2 Time state between the adjacent origin-destination nodes of autonomous vehicle

若車輛在最晚時刻ls準時到達，則到達時刻=ls，到達即開始服務；若提前到達，則＜ls，此時無人車需要等到最晚時刻ls才開始服務。

2.2 服務網絡模型

在包括空間維、時間維的二維時空網絡中構造服務網絡，即服務序列網絡，用(M，E)表示。將物理節點ni∈Vser映射到時空網絡中形成帶時間索引的時空節點(i，t)（(i，t)∈M）。時空節點之間的連接形成了時空弧(i，j，t，t′)，表示一條從時空節點(i，t)到(j，t′)的有向時空路徑。圖3展示了服務網絡的轉化過程。

圖3（a）中包含配送中心O和6 個帶時間窗的服務節點。圖3（b）在時空網絡中刻畫無人車的行進狀態，其中行駛弧是指無人車在空間上從服務節點ni位移到nj，時間上從t時刻轉移到t′；等待弧的出現是因為車輛到達服務節點的時刻早于最晚時刻；服務弧是在服務節點裝/卸載貨物的過程。根據圖3（b）的服務序列，圖3（c）在時空網絡中形成服務網絡。

圖3 服務網絡轉化Fig.3 Service network transformation

給定服務網絡(M，E)中路徑R由一組時空弧的序列構成{(n1，n2，t1，t2)，(n2，n3，t2，t3)，…，(nk-1，nk，tk-1，tk)} ∈E，相 鄰服務節點時刻滿足式（7）：

式中：ti為離開服務節點ni的時刻，ti，i+1表示從服務節點ni到ni+1的行駛時長和Ti+1分別表示在服務節點ni+1的等待時長和服務時長（i=1，2，…，k-1)。路徑R中的節點集合被定義為M(R)=若兩個服務節點能被一條時空弧連接，表明這兩個服務節點可以被一輛車連續服務。文獻［14］提出并證明了在有向網絡中最小車隊數量求解相當于最小節點不相交路徑覆蓋問題。

定義1節點不相交路徑覆蓋。給定有向網絡(M，E)中，若一個路徑集合{R1，R2，…，Rh}滿足M=并且M(Ri) ∩M(Rj)=?（i≠j），則稱{R1，R2，…，Rh}為(M，E)的一個節點不相交路徑覆蓋。

有向網絡的最小路徑覆蓋求解是NP-hard 問題［15］，在大規模服務網絡的計算上是不可行的。但是，若該網絡為有向無環網絡，則最優解可以在多項式時間內找到。本文構建的服務網絡都是有向無環網絡，可以采用矛盾法進行證明。

證明 若服務網絡(M，E)中存在循環路徑，簡單起見，假設路徑R={(n1，n2，t1，t2)，(n2，n1，t2，t1)}，根據服務網絡的定義和式（7），則有：

很顯然，式（8）中t1＜t1是矛盾的；同理可以推斷出任意路 徑R={(n1，n2，t1，t2)，…，(nk-1，nk，tk-1，tk)，(nk，n1，tk，t1)}都有t1＜t1+t1，2++T2=t2，…，＜tk+tk，1++T1=t1，因此服務網絡中不存在循環的路徑。

圖3（c）節點不相交路徑覆蓋結果如圖4 所示，最小節點不相交路徑覆蓋數（最小車隊車輛數）為3。特別的，若存在單一節點的路徑覆蓋，無人車配送路徑為O-ni-O。

圖4 路徑覆蓋示例Fig.4 Path coverage sample

2.3 最小車隊模型

針對快遞終端配送，服務網絡有其獨特性，無人車隊從配送中心出發，完成服務后返回配送中心，即，每條路徑起點和終點都為配送中心O。因此，在二分圖基礎上設置超級源點O和超級匯點O′，形成容量網絡。二分圖是將服務節點集合中的每個節點，分別放置于兩列M1={n1，n2，…，nk}，M2=｛n1′，n2′…，nk′}，ni=ni′；將服務網絡中的邊(i，j，t，t′) ∈E映射到二分圖，連接兩列的節點形成二分圖的邊。

定義2容量網絡。在二分圖基礎上，設置超級源點O并連接到M1={n1，n2，…，nk}所有元素，超級匯點O′并連接到M2={n1′，n2′，…，nk′}所有元素，使弧容量uij=1，弧流量fij=0。容量網絡表示為(M′，E′，u，f)，其中：

圖5展示了服務網絡圖3（c）對應的容量網絡。

圖5 容量網絡Fig.5 Capacity network

定義3殘余網絡。對于容量網絡(M′，E′，u，f)，若弧容量uij被使用，則uij=0，弧(ni，nj)∈E′轉化為弧(nj，ni)∈E″，且uji=1，以此為原則，更新容量網絡，得到殘余網絡（M′，E″，u′，f′）。

定理1殘余網絡中若節點ni和nj間存在流，則(ni，nj)∈E′ 和(nj，ni)∈E″有且只存在其中一個，并且若uij′(uji′)=1，則uji′(uij′)=0。

證明 此定理可以用矛盾法證明，對于殘余網絡（M′，E″，u′，f′）的存在流的兩個節點n1、n2，若同時存在(ni，nj)∈E″，(nj，ni)∈E″，則fij′=1、fji′=1，也就是說服務節點ni與nj之間的容量為2，這與殘余網絡定義中的弧容量為1矛盾。因此，在殘余網絡中，(ni，nj)或(nj，ni)存在且僅存在1個。

定義4層次網絡。在殘余網絡中，超級源點O的層次為0，從超級源點到節點ni的最短路徑的弧容量之和β，稱為節點ni的層次。

定理2如果Ψ是二分圖的匹配數，則殘余網絡存在流F，使得F=Ψ。

證明 在定理1 中已經證明，殘余網絡中兩節點之間的弧容量為0 或1，如果{(ni，nj)|ni∈M1，nj∈M2，fij=1} 是二分圖中一個匹配，那么該匹配的流為1。由于每個節點只存在于一個匹配中，因此每增加一個匹配，流也增加1，則F=Ψ。有如下推論：

推論1 路徑覆蓋數Θ為服務節點的數量與流F之差，即Θ=‖Vser‖-F。

證明 如果匹配數為0，那么每個節點都是一條獨立的路徑O-ni-O′，ni∈Vser，路徑數為‖Vser‖；但是，除了超級源點O和超級匯點O′，殘余網絡中的路徑都是節點不相交的，意味著每個點只會被匹配一次。每增加一組匹配{(ni，nj)|ni∈M1，nj∈M2，fij=1}，即將兩個節點ni，nj合并到一條路徑上，O-ni-nj-O′，路徑數為‖Vser‖-1。同理可得，若有Ψ個匹配，路徑數為‖Vser‖-Ψ。根據定理2，可推出Θ=‖Vser‖-F。

推論2 最小路徑覆蓋數minΘ為服務節點與最大流maxF之差，即minΘ=‖Vser‖-maxF。

車輛續航里程和容量有限，需要滿足約束式（9）和（10）：

式中：D為無人車的續航里程，qi表示在服務節點ni的裝載/卸載貨物數量，若卸載qi＜0，裝載qi＞0，Q為無人車的容量。

3 算法設計

在確定起點和終點網絡中尋找最優路徑，Dijkstra 算法是一種高效可靠的方法［16］，同時Dinic算法在網絡最大流計算中效率較高，因此，本文設計Dijkstra-Dinic 算法求解模型，并插入One-stop算子有效地縮小了搜索空間。

One-stop 算子 在一次廣度優先搜索（Breadth First Search，BFS）后的深度優先搜索（Depth First Search，DFS）中，為層次為β的節點ni搜索層次為β+1 的節點時，只考慮存在流的節點nj，fij=1，ni∈M1，nj∈M2，并且在找到一條有效增廣路徑后就停止搜索。若層次網絡層次為β，每個層次平均有β′個元素，在下一層次中平均有β″個節點與之存在流，那么全搜索最多需要有β′β次，但是插入One-stop 算子，搜索次數最多為(β-1)*β′*β″。值得注意的是，一般相鄰兩層次的節點若存在流，說明可連接成有效增廣路徑，所以在眾多可連接的下一層次節點中，第一個節點往往就是可行的，即搜索次數基本控制在(β-1)*β′。算法流程如圖6所示。

圖6 Dijkstra-Dinic算法流程Fig.6 Flowchart of Dijkstra-Dinic algorithm

4 仿真分析

考慮在包括服務節點在內的625個節點、1 200條路段的網絡中進行仿真，路段長度為［180，600］的隨機整數（距離單位為m）。由于完整網絡圖較大，因此截取局部仿真場景如圖7所示。仿真場景包括服務節點249、349、449和549四種規模。相關數據假設如下所示：容量為100，續航里程90 km，速度為12 km/h，可預約時間9：00—21：00。假設服務時長Ti∈N(7，1.5)，不同可靠服務時長對應著不同的成功服務率，如表1所示。

表1 可靠服務時長與成功服務率Tab.1 Reliable service time and successful service rate

圖7 局部仿真路網Fig.7 Local simulation road network

圖8 展示了在服務節點分別為249、349、449 和549 的四種不同規模的服務網絡中，考慮成功服務率，最小車隊車輛數隨δ變化的情況。

圖8 四種可靠服務時長的最小車隊車輛數隨最大等待時長演化Fig.8 Evolution of the minimum vehicle number of fleet with maximum waiting time in four reliable service time cases

圖8 縱坐標采用對數顯示方法，圖形整體呈現凹形。當最大等待時長δ=0 時，最小車隊車輛數等于服務節點數，意味著每個服務節點都需要一輛車單獨服務。隨著δ的增大，不同服務網絡規模下的最小車隊車輛數都呈現下降趨勢，逐漸平緩并會趨向穩定。當達到一個臨界值，即使δ繼續增加，車輛數保持不變。趨向穩定的δ和最小車隊車輛數如圖9 和圖10所示。

從圖9 可以看出，當成功服務率相同時，最小車隊車輛數隨服務網絡規模增加而增加；在不同規模的服務網絡中，最小車隊車輛數與可靠服務時長呈正相關；而最大等待時長臨界值都在可靠服務時長為9 min 時保持最小。貨物如未成功配送，必然導致第二次配送。在首次配送中未成功服務的數量、配送效率以及第二次配送車輛數如表2所示。

圖9 四個服務網絡的最小車隊車輛數Fig.9 The minimum vehicle number of fleet in four service networks

根據表2，服務網絡規模越大，車輛的使用效率（每輛車成功服務的數量）也越高，雖然第二次配送的數量總體呈現增長趨勢，但是增長率越來越低。最小車隊車輛數和第二次配送車輛數的合計結果如圖10所示。

表2 車隊服務效率及第二次配送車輛數Tab.2 Fleet service efficiency and the number of secondary distribution vehicles

圖10 四個服務網絡的最大等待時長臨界值Fig.10 Critical value of maximum waiting time in four service networks

根據圖11，在服務節點數為249、449 和549 的服務網絡中，可靠服務時長為8 min 和9 min 時兩次配送的合計車輛數最小，但是可靠服務時長為8 min 時，最小車隊車輛數更少。當服務節點數為349時，可靠服務時長為9 min時更好。

圖11 四個服務網絡的兩次配送車輛合計數量Fig.11 Total number of vehicles for two deliveries in four service networks

本文算法是用Python 3.7編寫，在一臺CPU 為1.80 GHz、內存為8 GB的個人計算機上評估。Dijkstra-Dinic算法在大規模網絡計算中表現出良好的性能：在625個節點、1 200條邊的仿真場景中，等待時長和可靠服務時長為9 min，服務網絡規模為549，計算最小車隊共用時21.56 s。

5 結語

為了求解并優化無人配送車隊車輛數問題，本文構建了最短路徑模型、服務網絡模型和最小車隊模型，引入One-stop算子設計了Dijkstra-Dinic 算法求解模型，通過數值實驗驗證了模型和算法的可行性與有效性。主要結論有：1）可靠車隊的數量與可靠服務時長呈正相關，和等待時長則反之；2）在不同服務網絡規模中，可靠車隊的數量趨于穩定的最大等待時長臨界值不同，因此最大等待時長應與服務網絡規模相適應；3）可靠車隊的數量與服務網絡規模呈正相關，表明配送中心應根據服務區域范圍大小和需求量配置無人車隊車輛數；4）本文算法在大規模網絡計算中表現出良好的性能；并且網絡規模越大車隊利用效率越高；5）本文提出的可靠車隊方案有效地解決了配送中心車隊數量配置問題。

在已有研究的基礎上，本文服務時長的設定具有一定的合理性，接下來將以實際服務中顧客的行走時長數據為基礎，探討不同場景中（例如商業區、居住區、高層和底層社區）顧客的行走時長特征，為終端配送更精細化的管理提供參考。