摘要：隨著我國電子商務(wù)的繁榮發(fā)展，外賣、網(wǎng)購、快遞等電子商務(wù)活動已成為人們?nèi)粘Ｉ畹闹匾M成部分，訂單配送的及時性已成為評價各外賣平臺、快遞公司等電商企業(yè)服務(wù)質(zhì)量的重要指標之一。以騎行成本和路況成本為約束，建立最優(yōu)路徑規(guī)劃模型，設(shè)計基于蟻群算法的快遞投遞最優(yōu)路徑規(guī)劃算法，在給定時間窗內(nèi)以目標約束規(guī)劃出最優(yōu)投遞路徑，以合適的投遞成本實現(xiàn)訂單高效配送，降低投遞員的在路上的時間，提升電商企業(yè)的服務(wù)質(zhì)量。

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

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

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

1 概述

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

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

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

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

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

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

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

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

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

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

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

3 建立數(shù)學(xué)模型

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

1）騎行成本

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

α（lij）=dij×s

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

2）路況成本

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

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

4 應(yīng)用求解

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

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

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

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

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

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

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

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

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

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

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

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

Step1：螞蟻每經(jīng)過一節(jié)路徑，便在該段路徑上留下信息素。

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

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

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

Step5：算法結(jié)束，得到最優(yōu)路徑。

Step6：將最優(yōu)路徑規(guī)劃在地圖上可視化。

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

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

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

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

5 最終規(guī)劃

基于騎行成本和路況成本約束的最優(yōu)投遞路徑規(guī)劃算法描述如下：

Stepl：定義目標函數(shù)和適應(yīng)值函數(shù)。

Step2：初始化抽象拓撲圖。

Step3：計算初始成本。

Step4：計算、更新個體最優(yōu)和全局最優(yōu)，到達每個節(jié)點的成本。

Step5：算法迭代次數(shù)完成，獲得若干組次優(yōu)解，轉(zhuǎn)Step 6;否則轉(zhuǎn)Step3。

Step6：根據(jù)次優(yōu)解生成信息素初始分布，蟻群參數(shù)初始化。

Step7：分別求解每只螞蟻轉(zhuǎn)移概率值，以轉(zhuǎn)移概率值移動螞蟻。

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

Step9：達到迭代次數(shù)，結(jié)束。否則，輸入最優(yōu)值，轉(zhuǎn)Step7。

其最優(yōu)路徑規(guī)劃算法如圖3所示：

6 測試結(jié)果

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

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

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

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

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

注釋：

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

參考文獻：

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

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

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

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

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

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

[7] 徐倩.外賣平臺騎手派單與路徑?jīng)Q策協(xié)同優(yōu)化[D].大連：大連海事大學(xué)，2020.

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

[9] every__day.最短路徑：地圖軟件是如何計算出最優(yōu)出行路徑的？[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] 孟祥萍，片兆宇，沈中玉，等.基于方向信息素協(xié)調(diào)的蟻群算法[J].控制與決策，2013，28（5）：782-786.

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

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

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

收稿日期：2021-12-22

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