作者：何柱 守初 本華

編者按

車輛路徑規(guī)劃問題（Vehicle  Routing Problem,  VRP）是供應鏈領域的經典問題之一，有著極大的學術研究意義和實際應用價值。近期，【阿里技術】撰文表示，阿里的菜鳥網絡團隊經過兩年的研發(fā)，已經沉淀出了一套世界級的車輛路徑規(guī)劃求解引擎。目前，該求解引擎在車輛路徑規(guī)劃問題國際上最權威的評測平臺上打破了多項世界紀錄。這標志著菜鳥網絡在此領域的技術研究已經進入世界前列。

本文轉載自【阿里技術】官方微信公眾號（ID：ali_tech）

問題介紹

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

以i,j表示配送網絡中的節(jié)點（i,j∈{0,1,2,…,N}), 其中0表示倉庫點，其它表示客戶點），以k表示車輛（k∈{1,2,…,K}），以為決策變量，表示車輛k是否從i點行駛到j點。則標準的車輛路徑規(guī)劃問題可以使用以下數據規(guī)劃的形式描述：

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

車輛路徑規(guī)劃問題在物流領域和生產領域的應用非常廣泛。所以在實際應用中也出現了一些在標準問題的基礎上增加了某些變化之后的變型問題。其中較為常見的包括：

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

• VRPTW：VRP with Time Windows, 客戶對貨物的送達時間有時間窗要求。

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

• MDVRP： Multi-Depot VRP, 配送網絡中有多個倉庫，同樣的貨物可以在多個倉庫取貨。

• OVRP：Open VRP, 車輛完成配送任務之后不需要返回倉庫。

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

以上各類問題之間的關系可以通過圖1表示：

圖1 VRP各類變型問題

經典求解算法

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

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

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

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

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

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

• 算法框架易于拓展，除了求解標準的VRP之外，還能夠求解VRPPD，MDVRP等變型問題；

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

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

• 通過設計實現不同類型的算子，ALNS可以實現不同的搜索策略，從而便于算法的升級拓展。

經典的ALNS算法的主流程如圖2所示：

圖2 ALNS算法主流程

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

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

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

3. 對此次迭代的初始解執(zhí)行Ruin操作，即將部分已經被車輛服務的客戶點刪除，使初始解成為一個不可行解；

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

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

6. 判斷是否達到終止條件。如果是，則終止計算，返回當前找到的最好解；否則，基于此輪計算中算子的表現，更新算子的權重，并返回到步驟（2）。

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

階段二：算法體系豐富與升級

為了更好地服務于公司內外部用戶，菜鳥倉配智能化算法團隊不斷對VRP優(yōu)化引擎的核心算法組件進行了豐富與升級。主要體現在以下幾個方面：

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

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

3.提升效果：菜鳥倉配智能化算法團隊還嘗試了多種算法來提升引擎的求解效果，主要包括：

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

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

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

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

• 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的逐步移動，探索兩個解之間的廣闊的鄰域，從而有可能發(fā)現更好的解；

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

階段三：算法并行化升級

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

★ Population Island

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

圖3 Population Island并行化架構

★ Parallel Memetic

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

圖4 Parallel Memetic并行化架構

★ Central Pool

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

圖5 Central Pool并行化架構

已獲得成果

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

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

菜鳥網絡倉配智能化算法團隊在算法研發(fā)過程中也一直以此數據集為主要算法評估指標。隨著算法的不斷升級優(yōu)化，在越來越多的數據上接近甚至持平世界紀錄。

最終，在2018年9月，倉配智能化算法團隊的算法終于獲得了比世界紀錄更好的結果，并經過了平臺的驗證，向全世界的研究者進行了公開。截止到2019年4月初，菜鳥網絡在此評測數據集上共持有48項世界紀錄，持有數量在眾多研究團隊中位居前列，這標志著菜鳥在這項領域的技術進入了世界頂尖水平，為菜鳥和集團贏得了巨大的技術影響力。

總結及展望

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

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

文章申明

Apr. 2019

文章作者：何柱 守初 本華