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

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

車(chē)輛路徑規(guī)劃問(wèn)題是運(yùn)籌優(yōu)化領(lǐng)域最經(jīng)典的優(yōu)化問(wèn)題之一。在此問(wèn)題中，有若干個(gè)客戶(hù)對(duì)某種貨物有一定量的需求，車(chē)輛可以從倉(cāng)庫(kù)取貨之后配送到客戶(hù)手中?？蛻?hù)點(diǎn)與倉(cāng)庫(kù)點(diǎn)組成了一個(gè)配送網(wǎng)絡(luò)，車(chē)輛可以在此網(wǎng)絡(luò)中移動(dòng)從而完成配送任務(wù)。在求解此問(wèn)題過(guò)程中，需要優(yōu)化的決策變量為每個(gè)客戶(hù)的配送任務(wù)應(yīng)該分配到哪一輛車(chē)上，以及每輛車(chē)完成客戶(hù)配送任務(wù)的先后順序，優(yōu)化目標(biāo)為最小化使用的車(chē)輛數(shù)和車(chē)輛總行駛距離（通常情況下最小化車(chē)輛數(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)，其它表示客戶(hù)點(diǎn)），以k表示車(chē)輛（k∈{1,2,…,K}），以[圖片上傳失敗...(image-4ad9e3-1554866885896)]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在研發(fā)之初，菜鳥(niǎo)倉(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等變型問(wèn)題；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Guided local serach （GLS）: 在搜索過(guò)程中對(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問(wèn)題分解為了Restricted Master Problem和Subproblem。其中在Restricted Master Problem中，基于一系列可行的路徑，通過(guò)求解Set Partition問(wèn)題來(lái)獲得原問(wèn)題的解；在Subproblem中，通過(guò)Tabu Search來(lái)搜索新的可行的路徑；

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

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

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

對(duì)于大部分啟發(fā)式算法而言，可以天然地通過(guò)并行化計(jì)算來(lái)提升搜索效率和效果，例如并行地計(jì)算評(píng)估多個(gè)相鄰解的質(zhì)量、向多個(gè)鄰域方向進(jìn)行搜索或者使用多種策略進(jìn)行搜索等，甚至并行地使用多種算法進(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

Population Island的算法架構(gòu)如圖3所示。在算法執(zhí)行過(guò)程中，有若干個(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ì)相同通信，分享搜索過(guò)程中獲得的知識(shí)，從而提升整體的搜索效率。

Parallel Memetic

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

Central Pool

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

通過(guò)對(duì)優(yōu)化算法的不斷迭代升級(jí)，以及在工程架構(gòu)上的更新完善，菜鳥(niǎo)網(wǎng)絡(luò)的車(chē)輛路徑規(guī)劃引擎在服務(wù)內(nèi)外部客戶(hù)的同時(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ì)錄，將車(chē)輛路徑規(guī)劃領(lǐng)域的技術(shù)逐漸地推向極致。

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

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

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

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

閱讀原文

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