基于蟻群算法的快遞投遞最優路徑規劃設計

摘要：隨著我國電子商務的繁榮發展，外賣、網購、快遞等電子商務活動已成為人們日常生活的重要組成部分，訂單配送的及時性已成為評價各外賣平臺、快遞公司等電商企業服務質量的重要指標之一。以騎行成本和路況成本為約束，建立最優路徑規劃模型，設計基于蟻群算法的快遞投遞最優路徑規劃算法，在給定時間窗內以目標約束規劃出最優投遞路徑，以合適的投遞成本實現訂單高效配送，降低投遞員的在路上的時間，提升電商企業的服務質量。

關鍵詞：訂單配送;成本約束;時間窗;蟻群算法;路徑規劃

中圖分類號：TP311.5? ? ? 文獻標識碼：A

文章編號：1009-3044（2022）04-0086-04

1 概述

近年來，隨著人民生活水平的逐步提高，年輕一代在日常工作與生活學習中的壓力也越來越大，“懶人經濟”逐漸興起，并帶動外賣、快遞等一眾本地生活業務迅猛發展。與此同時，隨著勞動成本的提高和作業效率要求的提高，技術革新的步伐也在加快。

隨著我國O2O電子商務發展的興起和日益繁榮，外賣、快遞等網上購物下單交易的市場規模在日漸擴大，據不完全統計，我國網購市場日均交易高達上億單①。面對如此龐大的市場需求，對于網購訂單的及時配送就顯得尤為重要。各大快遞公司與平臺為投遞員提供有效的路徑規劃調度與優化則是至關重要的一步。

目前各外賣平臺、快遞公司相互之間的競爭日趨激烈，訂單配送的及時性是影響配送體驗亦是顧客網購體驗的重要指標。對于各類服務平臺與派送企業，需要以不斷提高用戶訂單派送的送貨及時性和派送準確性為服務最終目標，與此同時盡可能地減少不必要的成本支出以大幅降低派送成本，以期能夠達到提高派送用戶體驗和降低送貨服務成本這兩者之間的最佳平衡點。這些正是各類企業賴以生存的根基和發展關鍵所在，這也正是本文對此展開深入研究所依托的一個現實行業背景。

本文將快遞員投遞與路徑決策模型中的協同優化問題[1-2]綜合分析歸結為帶時間窗的及時投遞配送最優路徑模型規劃問題[3]。根據路徑模型和協同問題分析各約束條件下的不同特點，設計快遞投遞最優路徑規劃算法研究。最后，根據實際調研與實驗數據綜合整理，進行綜合分析，證明了這種算法的應用效率和計算精度[4-5]。

研究結果表明，本文算法能夠有效地幫助快遞投遞員在高峰時期有大體量的配送訂單的情況下高效地規劃出最優路徑，進而有效地改善快遞企業高成本以及快遞投遞員低效率導致低收入的問題[6]。

2 快遞派送過程中的路徑分析

快遞配送投遞是指用戶在電商平臺向商家下單購物，商家委托有合作的快遞企業在一定期限內運送商品至用戶手中的商業活動。其中，用戶當地的快遞站點收到其他分公司運送過來的快件后需及時分配給快遞員，再由快遞員派送至用戶的收貨地點，完成“最后一公里”的派送。快遞員按照成功派送的快件數取得勞動報酬。因此，派送效率、派送過程中的路徑規劃對于快遞員的收入有著至關重要的影響。

當快遞員從快遞站點分配到快件開始，便需要思考派送的路徑。派送過程中會受到以下幾方面現實的問題：

1）購物用戶的地理位置相對分散，且又存在單個用戶多個快件的情況。

2）配送路況難以預料。各路段的限速情況、車道數、擁擠程度特別是道路口紅綠燈等待時間。尤其是晚高峰時期，又極易發生交通事故。

3）特殊極端天氣可能影響普通快遞的正常配送。特殊極端天氣（例如雨雪天氣、短時極端惡劣天氣）時，造成道路濕滑，會大大影響快遞員送貨的速度[7]。

3 建立數學模型

從快遞企業和快遞員的角度分析快件派送路徑規劃問題，建立快遞投遞最優路徑規劃的數學模型。由快遞員需要承受的派送快件成本基本有以下幾個方面：

1）騎行成本

快遞員在派送過程中的騎行成本和派送的距離有著緊密的聯系。快遞員和目標用戶收件地址的訂單派送順序影響著最終的派送距離，有著極大的進一步優化空間。我們可以將騎行成本由下式表示：

α（lij）=dij×s

此處記s是快遞員派送過程中派送單位距離的騎行成本，dij表示從節點i至節點j段路徑，α（lij）是從上一騎行節點i至下一騎行節點j的騎行成本。

2）路況成本

從上一騎行節點i至下一騎行節點j的任意一段路徑，存在影響快遞員配送速度的一系列外在現實約束條件，即路況成本。文獻[8]給出的該部分從道路限速、紅綠燈等待時間、單向車道數三方面考慮設定。

在文獻[8]中，β表示路況成本，dij表示從節點i至節點j段路徑，l為單位路徑長度，perf表示段位路徑的路況成本，包括在配送過程中從i節點到j節點的紅綠燈停等總時間light（tk）、道路限速f（v）、單向車道數N。若取單位路徑長度為無窮小，則在該段路徑內快遞員的騎行速度可視為勻速，則派送單位距離的記為v，v應當小于該段路徑限制的最高時速V。

4 應用求解

將地圖抽象成圖可以高效地解決本路徑規劃問題。以各地的主要交叉路口為該地圖的每個節點，以每個交叉路口的節點與交叉路口節點之間的每條道路為一條圖的邊，以每條道路的路徑長度為邊的權重。如果這條路徑有方向且為單向的，那么就可以在地圖上畫出兩個節點之間的一條有向邊;如果該段路徑是有方向的且是雙向的，則在兩個節點之間以不同方向分別畫一條邊。這樣，將整個地圖抽象到一個有向加權重圖中。到目前為止，我們要解決的問題是找到有向加權圖的兩個頂點之間的最短路徑。

如圖1所示為抽象路徑拓撲，以A、B為起始點為例，騎行成本D1可由A、B之間的具體路徑長度確定，路況成本D2則由A、B段路徑上兩次紅綠燈、限速40公里（設定權值為0.4）及當時的擁擠程度（初始化權值為0.5）來確定。將各節點之間各要素權值帶入算法中優化迭代，即可求出起始點間的最優路徑。

若忽略騎行成本路況成本等等一系列限制條件，則經典算法最短路徑算法可以很好地解決這個問題，更加準確地說，是單源最短路徑算法。文獻[9]中單源最短路徑算法，它的主要核心邏輯是：

1）設置一個初始的數組nodes，然后利用這個數組來添加設定的初始節點行駛至每一個其他節點的記路徑長度length。

2）將初始節點到其余節點的距離設置為∞，起始頂點的length值初始化為0，并且需要把它添加進優先隊列之中。

3）從這個優先隊列中取出length最小的節點，此處可以記為node_min，然后考察這個節點可達的所有節點node_next。假若最小節點的距離值length加上最小節點node_min與下一節點node_next之間邊的權重w小于下一節點node_next當前的距離值length，即存在另一條更短的路徑，它經過最小節點node_min到達下一節點node_next。將該節點node_next的距離值length更新為node_min的length值加上邊的權重w。然后，把node_next加入優先級隊列中。

3）重復步驟2），直到找到頂點t或者隊列為空。

4）額外設置兩個變量數組pioneer_node和 array。前者的作用是為了還原最短路徑，它記錄每個頂點的前驅節點。運用遞歸的方法，輸出最優規劃路徑。以array數組規避將同一個頂點重復加入優先級隊列中。當某個頂點的距離值length執行更新操作后，若該頂點節點已存在于優先級隊列中，則無須重復添加進去。

單源最短路徑算法并不完全適用于快遞投遞最優路徑規劃問題。因為在該問題下還需要考慮到騎行成本與路況成本。以路況成本中紅綠燈等待時間為例。每經過一條邊，就要經過一個邊的紅綠燈。實際上，對于該約束條件，我們只不過需要把每條邊的最終權值相應改為1即可，算法還是不變，可以接著使用本文先前所述的最短路徑算法。不過，邊的初始和最終權值為1，也就相當于無權圖了，同時亦可以靈活地運用廣度優先搜索算法求出最終的最短路徑即最優規劃方案。

確定派單路徑規劃，運用蟻群算法思想，在處理完成當前時間段內參與配單的所有快遞員對所有訂單價值判斷后，采用km帶權二分圖完全匹配算法，提供快遞員與訂單之間的最優匹配。快遞員在分配訂單后，還需解決單快遞員多訂單的情況下，在最短時間內完成訂單的處理，即一類不需要形成回路旅行商變體[10-11]。

針對該問題，文獻[9]在分配訂單較少的情況下可以直接采用動態規劃遍歷所有情況得出最優解，但是當分配訂單較多的情況下，其傳統算法的遍歷時間復雜度高達O（n！），故本文基于蟻群算法構建快遞員訂單派送路徑規劃算法，其基本概念源于螞蟻尋食，是在初始點經過多個需求點后，返回原點的過程中通過信息素的方式標記各自行走路徑，參照信息素的濃度選擇方向[12]。

文獻[12，13]給出的蟻群算法可描述為：

Step1：螞蟻每經過一節路徑，便在該段路徑上留下信息素。

Step2：初次遇見路徑節點即路口，隨機選擇其中任一路徑。選擇路徑的同時，釋放信息素以反映該路徑的長度等相關信息。

Step3：路徑的直線長度越長，留在該螞蟻路徑上的螞蟻信息素含量濃度相對越低，反之則信息素含量濃度越高。此后每當其中有一只螞蟻再次覓食來到一個路口時，系統便會自動選擇一個信息素含量濃度較高的路徑并進行再次覓食。

Step4：信息素濃度較高的路徑被蟻群多次重復覓食，其留在路徑上的信息素濃度隨之增加，最終形成最優路徑。

Step5：算法結束，得到最優路徑。

Step6：將最優路徑規劃在地圖上可視化。

文獻[12-13]給出的蟻群算法流程圖如圖2所示。

在該算法實現上，預先給定迭代次數，首次迭代過程中隨機設置信息素，后續迭代過程中根據之前迭代留下的信息素濃度判斷下一個到達點，最后記錄遍歷完所有點后，將走過的路徑和長度在這次迭代結束后進行比較，得出此次迭代得到的最短路徑及長度，重新更新信息素后開啟下一個迭代[13-14]。

由于路徑選擇概率與路徑長度成反比，算法迭代完成后形成的信息濃度最高者即為求解的最短或較短路徑。文獻[12-13]在此過程中路徑選擇概率具體如下：

該路徑選擇概率公式主要是計算所有可選節點的能見度和信息素冪乘積占總比，i和j分別作為起點和重點;能見度是i和j之間距離導數即[ηik]=1/dij;[τik]是時間為[τ]時從i到j的信息素濃度;allowedk表示沒有信息素的節點集合;α，β作為加權值常數即騎行成本與路況成本。

5 最終規劃

基于騎行成本和路況成本約束的最優投遞路徑規劃算法描述如下：

Stepl：定義目標函數和適應值函數。

Step2：初始化抽象拓撲圖。

Step3：計算初始成本。

Step4：計算、更新個體最優和全局最優，到達每個節點的成本。

Step5：算法迭代次數完成，獲得若干組次優解，轉Step 6;否則轉Step3。

Step6：根據次優解生成信息素初始分布，蟻群參數初始化。

Step7：分別求解每只螞蟻轉移概率值，以轉移概率值移動螞蟻。

Step8：更新移動螞蟻的最優值、位置和信息素。

Step9：達到迭代次數，結束。否則，輸入最優值，轉Step7。

其最優路徑規劃算法如圖3所示：

6 測試結果

基于pycharm集成開發工具，使用python語言編寫代碼實現算法。調用高德地圖提供的API將最終的規劃路徑可視化，其路徑規劃如圖4～圖6所示。

圖4所示，以鳳起路、武林門為起始點與終點，將其接緯度坐標帶入算法運行得到最優路徑規劃路線。

圖5所示，以蘭州植物園、第940醫院為起始點與終點，將其接緯度坐標帶入算法運行得到最優路徑規劃路線。

圖6所示，以西北民族大學蘭州體育館為起始點與終點，將其接緯度坐標帶入算法運行得到最優路徑規劃路線。

如圖7所示是最優路徑規劃算法的迭代結果，平均路徑長度與最短路徑長度曲線最終趨于平緩，與測試預期符合得很好。

注釋：

① https：//www.chinairn.com/scfx/20201209/164700190.shtml.

參考文獻：

[1] 宋夢培.粒子群算法和蟻群算法的集成及其應用研究[D].吉首：吉首大學，2020.

[2] 張超.粒子群算法與蟻群算法的改進研究[D].西安：西安工程大學，2019.

[3] 王征，張俊，王旭坪.多車場帶時間窗車輛路徑問題的變鄰域搜索算法[J].中國管理科學，2011，19（2）：99-109.

[4] 周裊，葛洪偉，蘇樹智.基于信息素的自適應連續域混合蟻群算法[J].計算機工程與應用，2017，53（6）：156-161.

[5] 黃松，田娜，紀志成.基于自適應變異概率粒子群優化算法的研究[J].系統仿真學報，2016，28（4）：874-879.

[6] 王荃菲.快餐外賣配送路徑方案研究[D].北京：北京交通大學，2017.

[7] 徐倩.外賣平臺騎手派單與路徑決策協同優化[D].大連：大連海事大學，2020.

[8] 劉士新，劉玲，張濤.求解VRPBTW的變鄰域搜索算法[J].東北大學學報（自然科學版），2008，29（3）：316-319.

[9] every__day.最短路徑：地圖軟件是如何計算出最優出行路徑的？[EB/OL] （2019-03-18）.[2021-11-17].https：//blog.csdn.net/every__day/article/details/88633171.

[10] 董紅宇，黃敏，王興偉，等.變鄰域搜索算法綜述[J].控制工程，2009，16（S2）：1-5，13.

[11] 孟祥萍，片兆宇，沈中玉，等.基于方向信息素協調的蟻群算法[J].控制與決策，2013，28（5）：782-786.

[12] 劉炳姣，石琴，仇多洋，等.基于改進蟻群算法的行駛工況構建及精度分析[J].合肥工業大學學報（自然科學版），2017，40（10）：1297-1302.

[13] 李妍峰，李軍，高自友.大規模鄰域搜索算法求解時變車輛調度問題[J].管理科學學報，2012，15（1）：22-32.

[14] 王志中.基于改進蟻群算法的移動機器人路徑規劃研究[J].機械設計與制造，2018（1）：242-244.

收稿日期：2021-12-22

作者簡介：樂靖雯（2002—），女，貴州天柱人，本科在讀。