作者：何柱 守初 本華

編者按

車輛路徑規(guī)劃問題（Vehicle  Routing Problem,  VRP）是供應(yīng)鏈領(lǐng)域的經(jīng)典問題之一，有著極大的學(xué)術(shù)研究意義和實(shí)際應(yīng)用價(jià)值。近期，【阿里技術(shù)】撰文表示，阿里的菜鳥網(wǎng)絡(luò)團(tuán)隊(duì)經(jīng)過兩年的研發(fā)，已經(jīng)沉淀出了一套世界級(jí)的車輛路徑規(guī)劃求解引擎。目前，該求解引擎在車輛路徑規(guī)劃問題國(guó)際上最權(quán)威的評(píng)測(cè)平臺(tái)上打破了多項(xiàng)世界紀(jì)錄。這標(biāo)志著菜鳥網(wǎng)絡(luò)在此領(lǐng)域的技術(shù)研究已經(jīng)進(jìn)入世界前列。

本文轉(zhuǎn)載自【阿里技術(shù)】官方微信公眾號(hào)（ID：ali_tech）

問題介紹

車輛路徑規(guī)劃問題是運(yùn)籌優(yōu)化領(lǐng)域最經(jīng)典的優(yōu)化問題之一。在此問題中，有若干個(gè)客戶對(duì)某種貨物有一定量的需求，車輛可以從倉(cāng)庫(kù)取貨之后配送到客戶手中?？蛻酎c(diǎn)與倉(cāng)庫(kù)點(diǎn)組成了一個(gè)配送網(wǎng)絡(luò)，車輛可以在此網(wǎng)絡(luò)中移動(dòng)從而完成配送任務(wù)。在求解此問題過程中，需要優(yōu)化的決策變量為每個(gè)客戶的配送任務(wù)應(yīng)該分配到哪一輛車上，以及每輛車完成客戶配送任務(wù)的先后順序，優(yōu)化目標(biāo)為最小化使用的車輛數(shù)和車輛總行駛距離（通常情況下最小化車輛數(shù)為第一優(yōu)化目標(biāo)）。

以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}），以為決策變量，表示車輛k是否從i點(diǎn)行駛到j(luò)點(diǎn)。則標(biāo)準(zhǔn)的車輛路徑規(guī)劃問題可以使用以下數(shù)據(jù)規(guī)劃的形式描述：

其中，表達(dá)式（1）表示優(yōu)化目標(biāo)為最小化使用車輛數(shù)；表達(dá)式（2）表示每個(gè)點(diǎn)有且僅有一輛車負(fù)責(zé)配送其所需要的貨物；表達(dá)式（3）表示每輛車最多負(fù)責(zé)一條配送線路；表達(dá)式（4）表示網(wǎng)絡(luò)中的流量平衡條件；表達(dá)式（5）表示每輛車負(fù)責(zé)配送的貨物不超過其承載能力限制；表達(dá)式（6）為防止孤立子環(huán)出現(xiàn)的約束條件。

車輛路徑規(guī)劃問題在物流領(lǐng)域和生產(chǎn)領(lǐng)域的應(yīng)用非常廣泛。所以在實(shí)際應(yīng)用中也出現(xiàn)了一些在標(biāo)準(zhǔn)問題的基礎(chǔ)上增加了某些變化之后的變型問題。其中較為常見的包括：

• CVRP：Capacitated VRP, 限制配送車輛的承載體積、重量等。

• VRPTW：VRP with Time Windows, 客戶對(duì)貨物的送達(dá)時(shí)間有時(shí)間窗要求。

• VRPPD：VRP with Pickup and Delivery, 車輛在配送過程中可以一邊攬收一邊配送，在外賣O2O場(chǎng)景中比較常見。

• MDVRP： Multi-Depot VRP, 配送網(wǎng)絡(luò)中有多個(gè)倉(cāng)庫(kù)，同樣的貨物可以在多個(gè)倉(cāng)庫(kù)取貨。

• OVRP：Open VRP, 車輛完成配送任務(wù)之后不需要返回倉(cāng)庫(kù)。

• VRPB： VRP with backhauls, 車輛完成配送任務(wù)之后回程取貨。

以上各類問題之間的關(guān)系可以通過圖1表示：

圖1 VRP各類變型問題

經(jīng)典求解算法

車輛路徑規(guī)劃問題是典型的NP-hard問題，非常具有挑戰(zhàn)性。同時(shí)因?yàn)槠湓趯?shí)際應(yīng)用的巨大價(jià)值，學(xué)術(shù)界和工業(yè)界對(duì)此類問題的優(yōu)化算法的探索已經(jīng)持續(xù)了幾十年的時(shí)間。已有的經(jīng)典求解算法可以分為精確解算法和啟發(fā)式算法兩大類。

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

啟發(fā)式算法的思想為通過一系列啟發(fā)式的規(guī)則來構(gòu)造和改變解，從而逐步提升解的質(zhì)量。對(duì)于VRP而言，較為經(jīng)典的啟發(fā)式算法為Clarke-Wright算法等。此外，經(jīng)過不斷的探索研究，元啟發(fā)式算法被證明在求解VRP方面具有很好的效果和效率。一些經(jīng)過精心設(shè)計(jì)的元啟發(fā)式算法，例如模擬退火、禁忌搜索、遺傳算法、蟻群算法、變鄰域搜索、自適應(yīng)大規(guī)模鄰域搜索算法等在求解VRP上有著非常好的表現(xiàn)。

菜鳥車輛路徑規(guī)劃引擎研發(fā)歷程

階段一：核心基礎(chǔ)算法研發(fā)

在研發(fā)之初，菜鳥倉(cāng)配智能化算法團(tuán)隊(duì)充分調(diào)研了VRP領(lǐng)域的相關(guān)學(xué)術(shù)論文和軟件產(chǎn)品等，最終確定了以自適應(yīng)大規(guī)模鄰域搜索（Adaptive Large Neighborhood Search, ALNS）為核心算法進(jìn)行算法引擎的建設(shè)。相對(duì)于其它算法，ALNS算法的優(yōu)勢(shì)包括：

• 算法框架易于拓展，除了求解標(biāo)準(zhǔn)的VRP之外，還能夠求解VRPPD，MDVRP等變型問題；

• 相對(duì)于普通的Local Search類型的算法，ALNS在每一步搜索過程中能夠探索更大的解空間；

• ALNS算法在搜索過程中能夠自適應(yīng)地選擇合適的算子，從而對(duì)于不同類型的問題數(shù)據(jù)能夠有比較穩(wěn)定的良好求解結(jié)果；

• 通過設(shè)計(jì)實(shí)現(xiàn)不同類型的算子，ALNS可以實(shí)現(xiàn)不同的搜索策略，從而便于算法的升級(jí)拓展。

經(jīng)典的ALNS算法的主流程如圖2所示：

圖2 ALNS算法主流程

如圖2所示的ALNS算法的主要步驟為：

1. 使用一定的規(guī)則構(gòu)造一個(gè)初始解（即Initial過程）；

2. 基于算子的權(quán)重，選擇此次迭代過程中使用的Ruin算子和Insert算子；

3. 對(duì)此次迭代的初始解執(zhí)行Ruin操作，即將部分已經(jīng)被車輛服務(wù)的客戶點(diǎn)刪除，使初始解成為一個(gè)不可行解；

4. 對(duì)步驟（3）獲得的解執(zhí)行Insert操作，即對(duì)于還沒有被車輛服務(wù)的客戶點(diǎn)，將其插入到解中，盡量獲得一個(gè)可行解；

5. 基于優(yōu)化目標(biāo)函數(shù)評(píng)估步驟（4）獲得的新的解，并根據(jù)一定的策略決定是否接受新解；

6. 判斷是否達(dá)到終止條件。如果是，則終止計(jì)算，返回當(dāng)前找到的最好解；否則，基于此輪計(jì)算中算子的表現(xiàn)，更新算子的權(quán)重，并返回到步驟（2）。

以ALNS算法為核心，菜鳥倉(cāng)配智能化算法團(tuán)隊(duì)完成了第一版VRP優(yōu)化引擎的研發(fā)。對(duì)比測(cè)試結(jié)果表明其求解效果和效率顯著優(yōu)于jsprit等國(guó)際上流行的開源VRP Solver。在此基礎(chǔ)上，菜鳥倉(cāng)配智能化算法團(tuán)隊(duì)還對(duì)引擎進(jìn)行了服務(wù)化，從而更方便地服務(wù)于公司內(nèi)外部用戶。

階段二：算法體系豐富與升級(jí)

為了更好地服務(wù)于公司內(nèi)外部用戶，菜鳥倉(cāng)配智能化算法團(tuán)隊(duì)不斷對(duì)VRP優(yōu)化引擎的核心算法組件進(jìn)行了豐富與升級(jí)。主要體現(xiàn)在以下幾個(gè)方面：

1.完善功能：在原算法核心框架的基礎(chǔ)上，增加了對(duì)Pickup and Delivery(車輛一邊攬收一邊派送)、Multi Trip（車輛多趟派送）等類型問題的支持；而且通過對(duì)實(shí)際業(yè)務(wù)問題的抽象，總結(jié)出了不同類型的優(yōu)化目標(biāo)方程（例如最小化階梯定價(jià)的總成本、最小化配送時(shí)間等）以及約束條件（例如車輛行駛距離限制、車輛配送訂單數(shù)限制、車輛跨區(qū)數(shù)限制等）。從而使求解引擎能夠求解的問題更加全面廣泛。

2.豐富算子：為了提升引擎的求解效果和穩(wěn)定性，菜鳥倉(cāng)配智能化算法團(tuán)隊(duì)還在VRP求解引擎中增加了更加豐富的優(yōu)化算子，例如不同類型的局部搜索算子（例如Two-Opt, Three-Opt, Cross-Exchange等）、不同類型的中間結(jié)果接受策略（例如Greedy, Simulated Annealing等）。

3.提升效果：菜鳥倉(cāng)配智能化算法團(tuán)隊(duì)還嘗試了多種算法來提升引擎的求解效果，主要包括：

• Guided ejection search （GES）：此算法通過不斷嘗試刪減一輛車，并將此輛車服務(wù)的客戶添加到其它車輛上，從而實(shí)現(xiàn)降低車輛的使用數(shù)。此算法在降低車輛數(shù)方面具有非常好的效果；

• Fast local search （FLS）: 在搜索過程中，只搜索那些有希望改善當(dāng)前解的的鄰域空間，從而大幅降低搜索計(jì)算量，提升算法求解速度；

• Guided local serach （GLS）: 在搜索過程中對(duì)局部最優(yōu)解的某些特征施加懲罰項(xiàng)，從而改變搜索方向，避免陷入局部最優(yōu)；

• Edge assembly crossover （EAX）: 一種基于兩個(gè)解生成一個(gè)新的解的方法，新生成的解能夠很好的繼承父代個(gè)體的空間結(jié)構(gòu)；

• Branch-and-Price-Based Large Neighborhood Search：此算法將VRPTW問題分解為了Restricted Master Problem和Subproblem。其中在Restricted Master Problem中，基于一系列可行的路徑，通過求解Set Partition問題來獲得原問題的解；在Subproblem中，通過Tabu Search來搜索新的可行的路徑；

• Path-Relink：此算法的核心思想為通過從initial solution到guiding solution的逐步移動(dòng)，探索兩個(gè)解之間的廣闊的鄰域，從而有可能發(fā)現(xiàn)更好的解；

• Hybrid Cluster and Heuristics：此算法是針對(duì)超大規(guī)模的問題而設(shè)計(jì)，首先通過合適的聚類算法對(duì)客戶點(diǎn)進(jìn)行聚類，從而將原問題分解為多個(gè)小規(guī)模的子問題，然后并行求解，最終將子問題的解組裝成為原問題的解。

階段三：算法并行化升級(jí)

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

★ Population Island

Population Island的算法架構(gòu)如圖3所示。在算法執(zhí)行過程中，有若干個(gè)Island并行執(zhí)行計(jì)算，每個(gè)Island獨(dú)立地進(jìn)行演化，其中各有一個(gè)Master和若干Worker，其中Worker負(fù)責(zé)具體的搜索任務(wù)的計(jì)算執(zhí)行，Master負(fù)責(zé)任務(wù)的分配協(xié)調(diào)以及與其它Island之間的通信等。每隔一定的計(jì)算步數(shù)，各個(gè)Island的Master之間會(huì)相同通信，分享搜索過程中獲得的知識(shí)，從而提升整體的搜索效率。

圖3 Population Island并行化架構(gòu)

★ Parallel Memetic

Parallel Memetic的算法架構(gòu)如圖4所示。整個(gè)算法可以分為兩個(gè)階段，第一個(gè)階段的計(jì)算重點(diǎn)在于減少使用的車輛數(shù)（Delete Route），在此階段中，若干個(gè)Worker并行計(jì)算，并每隔一定的步數(shù)相互通信分享信息。第一階段結(jié)束之后，會(huì)獲得若干中間結(jié)果，將這些結(jié)果作為第二階段中每個(gè)Worker上的初始演化種群進(jìn)行計(jì)算。第二階段的計(jì)算重點(diǎn)在于降低車輛行駛距離（Reduce Distance），第二階段的Worker之間同樣有相互通信分享知識(shí)的機(jī)制，而且可以通過控制演化過程中父代個(gè)體的選擇機(jī)制來進(jìn)行動(dòng)態(tài)地調(diào)節(jié)Exploration與Exploitation。

圖4 Parallel Memetic并行化架構(gòu)

★ Central Pool

Central Pool的算法架構(gòu)如圖5所示。在算法中有若干個(gè)Worker負(fù)責(zé)具體的搜索任務(wù)，并將搜索得到的解返回到Central Pool中，由Central Manager對(duì)解進(jìn)行排序、篩選、聚類等處理，然后Central Manager會(huì)依據(jù)當(dāng)前Central Pool中的解集情況生成新的計(jì)算任務(wù)并發(fā)送給Worker執(zhí)行。Central Manager可以對(duì)解空間進(jìn)行合理的刻畫，并通過計(jì)算任務(wù)的管控分配在Exploration與Exploitation之間進(jìn)行平衡，從而提升求解效率。

圖5 Central Pool并行化架構(gòu)

已獲得成果

通過對(duì)優(yōu)化算法的不斷迭代升級(jí)，以及在工程架構(gòu)上的更新完善，菜鳥網(wǎng)絡(luò)的車輛路徑規(guī)劃引擎在服務(wù)內(nèi)外部客戶的同時(shí)也在技術(shù)沉淀上獲得了重大成果。

在VRP算法領(lǐng)域，最權(quán)威的評(píng)測(cè)對(duì)比平臺(tái)為歐洲獨(dú)立研究機(jī)構(gòu)SINTEF發(fā)起并管理的世界最好解榜單（Best Known Solution），其中包括了對(duì)Solomon數(shù)據(jù)集（1987年提出）和Gehring & Homberger數(shù)據(jù)集（1999年提出）共356份測(cè)試數(shù)據(jù)的世界紀(jì)錄。全世界最頂尖的優(yōu)化算法學(xué)者（例如Jakub Nalepa, D. Pisinger, Yuichi Nagata等）以及優(yōu)化技術(shù)公司（例如Quintiq等）都不斷地在此平臺(tái)上刷新世界紀(jì)錄，將車輛路徑規(guī)劃領(lǐng)域的技術(shù)逐漸地推向極致。

菜鳥網(wǎng)絡(luò)倉(cāng)配智能化算法團(tuán)隊(duì)在算法研發(fā)過程中也一直以此數(shù)據(jù)集為主要算法評(píng)估指標(biāo)。隨著算法的不斷升級(jí)優(yōu)化，在越來越多的數(shù)據(jù)上接近甚至持平世界紀(jì)錄。

最終，在2018年9月，倉(cāng)配智能化算法團(tuán)隊(duì)的算法終于獲得了比世界紀(jì)錄更好的結(jié)果，并經(jīng)過了平臺(tái)的驗(yàn)證，向全世界的研究者進(jìn)行了公開。截止到2019年4月初，菜鳥網(wǎng)絡(luò)在此評(píng)測(cè)數(shù)據(jù)集上共持有48項(xiàng)世界紀(jì)錄，持有數(shù)量在眾多研究團(tuán)隊(duì)中位居前列，這標(biāo)志著菜鳥在這項(xiàng)領(lǐng)域的技術(shù)進(jìn)入了世界頂尖水平，為菜鳥和集團(tuán)贏得了巨大的技術(shù)影響力。

總結(jié)及展望

在歷時(shí)兩年的研發(fā)過程中，菜鳥倉(cāng)配智能化算法團(tuán)隊(duì)的同學(xué)們付出了巨大的努力和心血。同時(shí)在這個(gè)過程中，集團(tuán)多個(gè)事業(yè)部的兄弟團(tuán)隊(duì)在算法研究、工程技術(shù)等方面也提供了很多很好的專業(yè)建議，在此表示衷心的感謝！

在之后的工作中，菜鳥倉(cāng)配智能化算法團(tuán)隊(duì)將會(huì)把VRP引擎打造成為更強(qiáng)大、穩(wěn)定、易用的優(yōu)化產(chǎn)品，為菜鳥和集團(tuán)的各項(xiàng)業(yè)務(wù)發(fā)展提供技術(shù)支持，并有計(jì)劃地向外輸出，為中國(guó)的物流行業(yè)賦能提效。

文章申明

Apr. 2019

文章作者：何柱 守初 本華