基于蟻群算法的快遞投遞最優(yōu)路徑規(guī)劃設(shè)計(jì)

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

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

中圖分類號(hào)：TP311.5? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2022）04-0086-04

1 概述

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

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

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

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

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

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

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

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

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

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

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

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

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

1）騎行成本

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

α（lij）=dij×s

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

2）路況成本

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

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

4 應(yīng)用求解

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

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

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

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

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

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

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

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

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

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

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

文獻(xiàn)[12，13]給出的蟻群算法可描述為：

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

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

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

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

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

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

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

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

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

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

5 最終規(guī)劃

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

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

Step2：初始化抽象拓?fù)鋱D。

Step3：計(jì)算初始成本。

Step4：計(jì)算、更新個(gè)體最優(yōu)和全局最優(yōu)，到達(dá)每個(gè)節(jié)點(diǎn)的成本。

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

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

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

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

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

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

6 測試結(jié)果

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

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

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

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

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

注釋：

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

[9] every__day.最短路徑：地圖軟件是如何計(jì)算出最優(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] 劉炳姣，石琴，仇多洋，等.基于改進(jìn)蟻群算法的行駛工況構(gòu)建及精度分析[J].合肥工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2017，40（10）：1297-1302.

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

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

收稿日期：2021-12-22

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