摘要：已有的經(jīng)典求解算法可以分為精確解算法和啟發(fā)式算法兩大類。所以還有一大部分研究集中于啟發(fā)式算法領(lǐng)域。此外，經(jīng)過不斷的探索研究，元啟發(fā)式算法被證明在求解方面具有很好的效果和效率。

阿里妹導(dǎo)讀：車輛路徑規(guī)劃問題（Vehicle Routing Problem, VRP）是物流領(lǐng)域最經(jīng)典的優(yōu)化問題之一，具有極大的學(xué)術(shù)研究意義和實際應(yīng)用價值。菜鳥網(wǎng)絡(luò)高級算法專家胡浩源帶領(lǐng)倉配智能化算法團隊經(jīng)過兩年的研發(fā)，逐步沉淀出了一套完善、強大的車輛路徑規(guī)劃求解引擎，為菜鳥內(nèi)外部多項業(yè)務(wù)提供了技術(shù)支持。通過不斷地對算法進行探索打磨，我們終于在車輛路徑規(guī)劃問題最權(quán)威的評測平臺上打破了多項世界紀(jì)錄，標(biāo)志著菜鳥網(wǎng)絡(luò)在此領(lǐng)域的技術(shù)研究已經(jīng)進入世界前列。

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

以i,j表示配送網(wǎng)絡(luò)中的節(jié)點（i,j∈{0,1,2,…,N}), 其中0表示倉庫點，其它表示客戶點），以k表示車輛（k∈{1,2,…,K}），以[圖片上傳失敗...(image-4ad9e3-1554866885896)]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Edge assembly crossover （EAX）: 一種基于兩個解生成一個新的解的方法，新生成的解能夠很好的繼承父代個體的空間結(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的逐步移動，探索兩個解之間的廣闊的鄰域，從而有可能發(fā)現(xiàn)更好的解；

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

階段三：算法并行化升級

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

Population Island

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

Parallel Memetic

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

Central Pool

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

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

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

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

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

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

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

閱讀原文

本文來自云棲社區(qū)合作伙伴“?阿里技術(shù)”，如需轉(zhuǎn)載請聯(lián)系原作者。