菜鳥(niǎo)驛站無(wú)人配送車物流路徑規(guī)劃算法實(shí)證研究

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

1.3.1 ALNS算法

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

1.3.2 ALNS算法體系的豐富與升級(jí)

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

1.3.3 ALNS算法并行化升級(jí)

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

1.4 菜鳥(niǎo)車輛路徑規(guī)劃算法應(yīng)用評(píng)價(jià)

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

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

2 算法實(shí)證研究

2.1 實(shí)證研究對(duì)象

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

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

2.1.2 菜鳥(niǎo)無(wú)人配送車“小蠻驢”

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

圖1 行駛在校園中的菜鳥(niǎo)無(wú)人物流車“小蠻驢”

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

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

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

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

2.2 實(shí)證研究目的

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

3 對(duì)比實(shí)驗(yàn)

3.1 對(duì)比實(shí)驗(yàn)設(shè)計(jì)

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

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

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

3.2 對(duì)比實(shí)驗(yàn)結(jié)果

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

表2 對(duì)比實(shí)驗(yàn)結(jié)果

3.3 實(shí)驗(yàn)結(jié)果分析

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

3.4 減碳值估算

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

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

4 結(jié) 語(yǔ)

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