菜鳥驛站無人配送車物流路徑規(guī)劃算法實證研究

汪 洋，孫 劍 （瀘州職業(yè)技術(shù)學(xué)院 人工智能與大數(shù)據(jù)學(xué)院，四川 瀘州 646000）

0 引 言

菜鳥車輛路徑規(guī)劃算法[1]是基于滿足多網(wǎng)點(diǎn)多線路不同車型的復(fù)雜性配送場景而研發(fā)的，是菜鳥網(wǎng)絡(luò)自主研發(fā)的車輛路徑優(yōu)化算法，在技術(shù)上融合了大規(guī)模鄰域搜索、超啟發(fā)式算法、基因算法、分布式并行化和增強(qiáng)學(xué)習(xí)；在公開數(shù)據(jù)集上，該算法已全面超過廣泛使用的開源產(chǎn)品Jsprit，在全球最權(quán)威的車輛路徑問題（Vehicle Routing Problem, VRP）評測系統(tǒng)中創(chuàng)造了多項世界紀(jì)錄。

菜鳥車輛路徑規(guī)劃算法已經(jīng)應(yīng)用于多項業(yè)務(wù)中。在車輛配送環(huán)節(jié)，車輛路徑規(guī)劃算法可以有效減少車輛使用數(shù)量和縮短車輛行駛距離；在倉庫內(nèi)部挑揀作業(yè)中，車輛路徑規(guī)劃算法可以縮短揀選人員的行走距離；在末端“最后一公里”校園配送中，車輛路徑規(guī)劃算法可以幫助無人配送車“小蠻驢”選擇最優(yōu)配送路線，有效縮短了車輛行駛距離，縮短了配送時間。

1 菜鳥車輛路徑規(guī)劃算法

1.1 車輛路徑規(guī)劃問題

車輛路徑規(guī)劃問題[2]是物流領(lǐng)域最經(jīng)典的優(yōu)化問題之一，具有極大的學(xué)術(shù)研究意義和實際應(yīng)用價值。在此問題中，有若干個客戶對某種貨物有一定量的需求，車輛可以從倉庫取貨之后配送到客戶手中?？蛻酎c(diǎn)與倉庫點(diǎn)之間組成了一個配送網(wǎng)絡(luò)，車輛可以在此網(wǎng)絡(luò)中移動而完成配送任務(wù)。在求解此問題的過程中，需要優(yōu)化的決策變量為每個客戶的配送任務(wù)應(yīng)該分配到哪一輛車上，以及每輛車完成客戶配送任務(wù)的先后順序，優(yōu)化目標(biāo)為最小化使用的車輛數(shù)和車輛總行駛距離。

以i，j表示配送網(wǎng)絡(luò)中的節(jié)點(diǎn)（i，j∈{0，1，2,…，N})，其中0表示倉庫點(diǎn)，其他表示客戶點(diǎn)，以k表示車輛（k∈{1，2，…，K}），xijk為決策變量，表示車輛k是否從i點(diǎn)行駛到j(luò)點(diǎn)，則標(biāo)準(zhǔn)的車輛路徑規(guī)劃問題[3]可以使用以下數(shù)據(jù)規(guī)劃形式描述，如公式（1）所示。

1.2 經(jīng)典求解算法

車輛路徑規(guī)劃問題是典型的NP-hard問題，學(xué)術(shù)界和工業(yè)界對此類問題的優(yōu)化算法的探索已經(jīng)持續(xù)了幾十年[4]。已有的經(jīng)典求解算法可以分為精確解算法和啟發(fā)式算法兩大類。

在精確解算法方面，最基本的方法為分支定界算法[5]，雖然其能夠從理論上保證在有限時間內(nèi)獲得最優(yōu)解，但是在實際計算中存在計算耗時巨大的情況。為了提高求解效率，研究者們先后提出了多種Branch-and-Cut方法，大幅縮短了算法的求解時間。但是對于實際應(yīng)用中較大規(guī)模的問題而言（例如超過200個點(diǎn)的問題），精確解算法依然無法能夠在合理的時間內(nèi)完成計算。

啟發(fā)式算法[6]的思想為通過一系列啟發(fā)式的規(guī)則來構(gòu)造和改變解，從而逐步提升解的質(zhì)量。對于VRP而言，較為經(jīng)典的啟發(fā)式算法為Clarke-Wright算法等。

1.3 菜鳥網(wǎng)絡(luò)的車輛路徑規(guī)劃引擎

1.3.1 ALNS算法

菜鳥倉配智能化算法團(tuán)隊首先確定了以自適應(yīng)大規(guī)模鄰域搜索（Adaptive Large Neighborhood Search, ALNS）為核心算法進(jìn)行算法引擎的建設(shè)。ALNS算法的優(yōu)勢有以下幾點(diǎn)：算法框架易于拓展，除了求解標(biāo)準(zhǔn)的VRP之外，還能夠求解VRPPD、MDVRP等變型問題；相對于普通的Local Search類型的算法，ALNS在每一步搜索過程中能夠探索更大的解空間；ALNS算法在搜索過程中能夠自適應(yīng)地選擇合適的算子，從而對于不同類型的問題數(shù)據(jù)有比較穩(wěn)定的良好求解結(jié)果；通過設(shè)計實現(xiàn)不同類型的算子，ALNS可以實現(xiàn)不同的搜索策略，從而便于算法的升級拓展。

1.3.2 ALNS算法體系的豐富與升級

ALNS核心算法確定后，菜鳥倉配智能化算法團(tuán)隊不斷對VRP優(yōu)化引擎的核心算法組件進(jìn)行豐富與升級，主要包括：a.完善功能：在原算法核心框架的基礎(chǔ)上，增加了對車輛一邊攬收一邊派送(Pickup and Delivery)、車輛多趟派送（Multi Trip）等類型問題的支持；而且通過對實際業(yè)務(wù)問題的抽象，總結(jié)出了不同類型的優(yōu)化目標(biāo)方程（例如最小化階梯定價的總成本、最小化配送時間等）以及約束條件（例如車輛行駛距離限制、車輛配送訂單數(shù)限制、車輛跨區(qū)數(shù)限制等），從而使求解引擎能夠求解的問題更加全面廣泛。b.豐富算子：為了提升引擎的求解效果和穩(wěn)定性，在VRP求解引擎中增加了更加豐富的優(yōu)化算子，例如不同類型的局部搜索算子（例如Two-Opt，Three-Opt， Cross-Exchange等）、不同類型的中間結(jié)果接受策略（例如Greedy，Simulated Annealing等）。

1.3.3 ALNS算法并行化升級

對于大部分啟發(fā)式算法而言，可以自然通過并行化計算來提升搜索效率和效果，例如并行計算評估多個相鄰解的質(zhì)量、向多個鄰域方向搜索或者使用多種策略搜索等，甚至并行使用多種算法進(jìn)行搜索等。所以為了進(jìn)一步提升VRP引擎的求解質(zhì)量，菜鳥倉配智能化算法團(tuán)隊對VRP引擎進(jìn)行了并行化升級。在此過程中，先后研發(fā)實現(xiàn)了三套并行化算法架構(gòu)，分別是Population Island，Parallel Memetic，Central Pool等。

1.4 菜鳥車輛路徑規(guī)劃算法應(yīng)用評價

2018年9月，菜鳥倉配智能化算法團(tuán)隊研發(fā)的車輛路徑規(guī)劃算法首次獲得了比世界紀(jì)錄更好的結(jié)果，并經(jīng)過了平臺的驗證。2018—2022年期間菜鳥智能路徑規(guī)劃算法已陸續(xù)打破60余項VRPTW和PDPTW計算模型的世界紀(jì)錄。這標(biāo)志著菜鳥在這項領(lǐng)域的技術(shù)進(jìn)入了世界頂尖水平，為菜鳥贏得了巨大的技術(shù)影響力。

菜鳥研發(fā)的車輛路徑規(guī)劃算法應(yīng)用于菜鳥無人物流車“小蠻驢”后，大幅提升了車輛的環(huán)境精細(xì)化理解能力，使車輛能夠識別“厘米級”障礙物。比如車輛在行駛途中遇到臨時拉起的警戒線，即便線寬僅有3厘米，物流車也能輕松識別并繞道而行。目前菜鳥無人物流車“小蠻驢”已在國內(nèi)多個高校實現(xiàn)L4級別的日常運(yùn)營，為消費(fèi)者“無接觸配送”快遞。包裹收取時間從常規(guī)的2小時縮短到30分鐘左右。

2 算法實證研究

2.1 實證研究對象

2.1.1 瀘州職業(yè)技術(shù)學(xué)院菜鳥驛站

瀘州職業(yè)技術(shù)學(xué)院菜鳥驛站是由瀘州職業(yè)技術(shù)學(xué)院和阿里巴巴校企合作、統(tǒng)一規(guī)劃打造的生產(chǎn)性實訓(xùn)基地，提供收件、派件、客服、代理記賬等多個實習(xí)實訓(xùn)崗位，為物流管理等相關(guān)專業(yè)學(xué)生提供真實實訓(xùn)環(huán)境，提高學(xué)生的實踐技能。目前該菜鳥驛站已擁有人工貨架50個、智能柜10個、無人配送物流車“小蠻驢”3輛，服務(wù)于全校近2萬名師生。據(jù)統(tǒng)計，目前該菜鳥驛站全年快遞單量已超過200萬件，平均每天快遞單量超過5 000件。2021年，瀘州職業(yè)技術(shù)學(xué)院菜鳥驛站成功入選“全國百強(qiáng)標(biāo)桿站點(diǎn)”，榮獲2021年度“全國好服務(wù)標(biāo)桿站點(diǎn)”稱號，成為全國首批達(dá)成4A好服務(wù)的校企站點(diǎn)。

2.1.2 菜鳥無人配送車“小蠻驢”

菜鳥已在全國300所高校校園中部署了無人配送物流車“小蠻驢”，執(zhí)行配送任務(wù)的無人車已接近600 輛，成為全球較大的一支快遞無人車隊。目前瀘州職業(yè)技術(shù)學(xué)院菜鳥驛站擁有3輛無人配送物流車“小蠻驢”，如圖1所示。行駛在校園道路上的“小蠻驢”均搭載了菜鳥自主研發(fā)的最先進(jìn)的車輛路徑規(guī)劃算法，實現(xiàn)了L4 級無人駕駛，可以根據(jù)情景自動生成最優(yōu)配送路線，并將包裹準(zhǔn)確派送到目的地（比如學(xué)生宿舍樓或教師辦公樓）。

圖1 行駛在校園中的菜鳥無人物流車“小蠻驢”

消費(fèi)者通過使用支付寶“菜鳥”小程序，選擇“無人車上門取件”并填寫相關(guān)信息即可完成無人車預(yù)約服務(wù)。無人配送物流車“小蠻驢”可以每天在工作時間內(nèi)不間斷循環(huán)往復(fù)地完成“預(yù)約、裝件、出發(fā)、返回”等任務(wù)，一天內(nèi)每輛無人車可以跑近100公里，最多派送500件快遞。通過無人車派送可以緩解菜鳥驛站庫容壓力，提升用戶取件體驗，讓離驛站較遠(yuǎn)的同學(xué)在樓下就能取件。新冠疫情期間，還可以緩解同學(xué)們到菜鳥驛站取件造成聚集的壓力。

2.1.3 瀘州職業(yè)技術(shù)學(xué)院校園整體布局

瀘州職業(yè)技術(shù)學(xué)院目前占地面積1 504畝，建筑總面積60萬平方米，整個校園整體布局呈典型的“日”字型結(jié)構(gòu)，道路屬于典型的棋盤式布局，如圖2所示。校園用地劃分較為整齊，有利于建筑布置，適合各類型車輛在其中穿梭行駛。校園中不同建筑物間點(diǎn)對點(diǎn)的直達(dá)行駛路線往往有多條。

圖2 瀘州職業(yè)技術(shù)學(xué)院校園布局圖

2.2 實證研究目的

由于無人配送物流車“小蠻驢”搭載的菜鳥車輛路徑規(guī)劃算法不開源，無法獲取到源代碼，如何憑借現(xiàn)有條件在校園中驗證該算法的有效性是本文開展實證研究的重點(diǎn)。根據(jù)查閱文獻(xiàn)得知，目前尚未有人針對菜鳥在高校投放的無人車選擇最優(yōu)配送路線的車輛路徑規(guī)劃算法開展實證研究。我們通過設(shè)計對比實驗，在瀘州職業(yè)技術(shù)學(xué)院校園內(nèi)開展菜鳥車輛路徑規(guī)劃算法的實證研究，得出的結(jié)論可以有力證明菜鳥車輛路徑規(guī)劃算法的有效性，填補(bǔ)了該算法實證的相關(guān)空白。

3 對比實驗

3.1 對比實驗設(shè)計

本文采用常見的“黑盒測試”方式來設(shè)計對比實驗。通過設(shè)置“出發(fā)地—目的地”，觀察、測算無人車“小蠻驢”選取的點(diǎn)對點(diǎn)派送路徑，即視為車輛路徑規(guī)劃算法經(jīng)過計算得出的“最優(yōu)選擇路徑”。以“點(diǎn)對點(diǎn)”其他派送路徑為實驗參照對象組，參照對象組實驗車輛可以選擇跟“小蠻驢”相同行駛速度的電動自行車代替。選取“派送時間”作為對比實驗中不同派送路徑的評價指標(biāo)。

以瀘州職業(yè)技術(shù)學(xué)院綜合樓坐班教師小王需要使用無人車“小蠻驢”派送快遞為實驗?zāi)M場景，“出發(fā)地—目的地”即為“菜鳥驛站—綜合樓”。通過提前觀察，發(fā)現(xiàn)從菜鳥驛站到達(dá)綜合樓，可以有4條路線供選擇，如表1所示。小王老師通過“菜鳥”小程序，選擇“無人車上門取件”后，通過觀察發(fā)現(xiàn)“小蠻驢”選取的是路線②作為車輛配送行駛路線。

表1 “菜鳥驛站—綜合樓”可供選擇配送路徑

3.2 對比實驗結(jié)果

首先通過觀察、計時測試了菜鳥物流無人車“小蠻驢”在正常狀態(tài)下行駛的平均速度為2.43m/s。首先測試菜鳥物流無人車“小蠻驢”在行駛路徑②狀態(tài)下花費(fèi)的時間，然后選取電動自行車，給予車輛同樣2.43m/s的配速用以測試行駛路徑①③④狀態(tài)下花費(fèi)的時間。為了盡可能確保測試得到的車輛行駛花費(fèi)時間的準(zhǔn)確性，將每條路徑的行駛測試次數(shù)設(shè)定為10次，然后求取10次結(jié)果的平均值，從而得到每條路徑的平均花費(fèi)時間，對比實驗結(jié)果如表2所示。

表2 對比實驗結(jié)果

3.3 實驗結(jié)果分析

通過對比實驗結(jié)果，發(fā)現(xiàn)菜鳥物流無人車“小蠻驢”經(jīng)過計算選取的物流配送路徑②行駛平均花費(fèi)時間僅為330.6s，均優(yōu)于其余路徑①③④的行駛花費(fèi)時間。實驗結(jié)果表明，菜鳥物流無人車自動選取的“點(diǎn)對點(diǎn)”派送路徑即為派送“最優(yōu)選擇路徑”，也有力證明了菜鳥無人配送車中物流路徑規(guī)劃算法的有效性。

3.4 減碳值估算

菜鳥積極響應(yīng)國家“雙碳”戰(zhàn)略，歷經(jīng)6年艱辛研發(fā)，最終成為引領(lǐng)物流行業(yè)數(shù)智化技術(shù)“減碳”目標(biāo)的先行者和標(biāo)準(zhǔn)制定者。以搭載了車輛路徑規(guī)劃算法的菜鳥物流無人車“小蠻驢”為例，無人車可以根據(jù)情景自動生成最優(yōu)配送路線，每趟行程其實都是一次“減碳”之旅。

以行程平均花費(fèi)時間每減少1s可以實現(xiàn)減碳量0.1g為標(biāo)準(zhǔn)來計算。從“菜鳥驛站—綜合樓”總共有4條不同選擇路徑，平均花費(fèi)時間為436.6s。無人車“小蠻驢”在行駛路徑②下平均花費(fèi)時間為330.6s，一趟行程可以節(jié)約106s，成功實現(xiàn)減碳量10.6g。

4 結(jié) 語

本文針對菜鳥自主研發(fā)的車輛路徑規(guī)劃算法開展了一系列實證研究，通過在瀘州職業(yè)技術(shù)學(xué)院校園內(nèi)設(shè)計科學(xué)嚴(yán)謹(jǐn)?shù)膶Ρ葘嶒?，證明了車輛路徑規(guī)劃算法的有效性。本文開展的校園內(nèi)實證研究未來可以進(jìn)一步拓展到菜鳥物流在校園外的城際配送、物流周轉(zhuǎn)過程中的車輛路徑規(guī)劃算法的驗證中。