MIT和亞馬遜舉辦的路徑優(yōu)化比賽——

US$175000的解決方案分享

不久前

MIT和亞馬遜聯(lián)合舉辦的

最后一公里配送的路徑優(yōu)化比賽結(jié)束了（點擊閱讀全文，查看比賽鏈接）

前三名總共獲得US$175000。

今天小編借著這個比賽的機(jī)會給大家介紹下相關(guān)的運(yùn)籌優(yōu)化知識和各路高手的解法。

目錄/contents

1. 比賽簡介 

問題背景 

數(shù)據(jù)集結(jié)構(gòu) 

成績評價 

2. 前3名的解決方案簡介 

第1名 

第2名 

第3名 

3. 第1名的解決方案及細(xì)節(jié)分析 

模型

具體求解步驟 

（1）先將ATSP轉(zhuǎn)化為TSP 

（2）用zone-id得到cluster 

（3）從歷史數(shù)據(jù)得到軟約束 

對于step2 通過深度優(yōu)先搜索將有向圖變成 palm tree 結(jié)構(gòu) 

對于step3 從palm tree得到強(qiáng)連通分量 以及 分量路徑 

（4）用改進(jìn)后的LKH-3求解 

結(jié)果 

題外話環(huán)節(jié) 

參考資料

比賽簡介

問題背景

最后一公里配送問題，指的就是區(qū)域配送中心到末端設(shè)施這一段的配送問題。司機(jī)需要在配送中心裝載好貨物，按順序訪問多個末端設(shè)施進(jìn)行收貨或送貨操作，最后回到配送中心。

這個送貨的路徑在比賽中被稱作route（如下圖所示）；配送中心是這條route的起點和終點，稱做station；訪問的末端設(shè)施，收件人寄件人的具體地址則被稱作stop（圖中圓點）；圖中stop的顏色相同說明歸屬于同一個zone；圖中stop的標(biāo)號說明訪問這個stop的次序；而我們需要確定的就是這個次序，即stop sequence。

數(shù)據(jù)集結(jié)構(gòu)

詳見，官方data_structures文檔

https://github.com/MIT-CAVE/rc-cli/blob/main/templates/data_structures.md

主要是

· route的實際stop sequence

· route的信息（如出發(fā)時間、日期、出發(fā)地點等）

· stop的信息（如stop的經(jīng)緯度，是否送貨，stop所屬的zone id等）

· package的信息（如包裹的大小、包裹規(guī)定送達(dá)的時間窗等）

· stop之間的travel time

成績評價

而如何評價一個sequence的好壞呢？這就是這個最后一公里問題不同尋常的地方了。不同于傳統(tǒng)路徑規(guī)劃問題中配送距離或時間越短則說路徑越好，而這里的路徑好壞是人為評分的結(jié)果，分為高中低三個檔次，這里可能包含了司機(jī)的主觀經(jīng)驗。

故舉辦方會提供歷史上6112條route的信息，其中有2718條評分高的route。參賽者在測試算法效果時，可將每條評分高的route的信息（如訪問的stop的經(jīng)緯度位置、包裹的尺寸等）輸入算法中，輸出每條route預(yù)測的stop sequence。通過計算預(yù)測的和實際的sequence間的相似程度，可以衡量算法預(yù)測出來的sequence的好壞。對所有的route重復(fù)上述操作即可獲得總得分submission score，進(jìn)而衡量算法的好壞。流程如下圖所示：

參賽者提交完最終版算法之后，舉辦方將輸入的route替換成3000條新的route，重復(fù)上圖流程后，根據(jù)得到的submission score對所有隊伍由低到高進(jìn)行排名。具體的計算方式如下式所列：

submission score 越低越好

這里舉個栗子，如下表，序列A為依次訪問站點1、2、3、4，序列B為依次訪問站點2、4、3、1，則a[i]為B[i]在A中的位置，當(dāng)a中的元素不嚴(yán)格按照升序排列，即A和B為相同序列時SD(A,B)會大于0，否則為0；SD(A,B)越大，說明A和B的差異越大。ERPnorm(A,B)表示的是A和B每位間的正則化行程距離，ERPe(A,B)表示A轉(zhuǎn)換成B需要的最少操作數(shù)，即把3放在4前面，把1放在2前面共兩次操作。ERPnorm(A,B)/ERPe(A,B)表示平均每次ERP操作所涉及的兩個站點之間的正則化行程時間。

小知識：編輯距離

字符串的編輯距離，通常用來衡量兩個字符串的差異化程度。最常見的編輯距離是Levenshtein距離，由俄羅斯的數(shù)學(xué)家Vladimir Levenshtein在1965年提出。是指利用字符操作，把字符串A轉(zhuǎn)換成字符串B所需要的最少操作數(shù)。其中，字符操作包括：刪除一個字符、插入一個字符、修改一個字符。一般來說，兩個字符串的編輯距離越小，則它們越相似。

例如對于字符串 if 和 iff ，可以通過插入一個 f 或者刪除一個'f'來達(dá)到目的。

總的來說，就是將實際的sequence作為一個最高基準(zhǔn)，參賽方根據(jù)已有的信息預(yù)測的sequence和實際sequence越接近，說明其算法越好。雖說和機(jī)器學(xué)習(xí)很像，但遺憾的是，這次比賽中排行榜前三的隊伍都是采用優(yōu)化算法來求解的，接下來就給大家介紹一下~

前3名的解決方案簡介

第1名

Local Search with Learned Constraints for Last Mile Routing

該篇文章將原始問題建模成帶約束的非對稱旅行商問題。具體的約束從歷史數(shù)據(jù)中學(xué)得，主要包括簇約束、優(yōu)先級約束。最后采用改進(jìn)的LKH算法進(jìn)行求解。

第2名 

Last-Mile Delivery Trajectory Prediction Using Hierarchical TSP with Customized Cost Matrix

該篇文章將原始問題建模成多層次TSP問題（高層次將zone作為TSP中的城市，低層次的將stop作為TSP中的stop），并自定義成本矩陣（主要根據(jù)zone的層級關(guān)系調(diào)整行駛時間矩陣），分層次調(diào)用GLPK進(jìn)行求解，最后對得到的sequence進(jìn)行修正（根據(jù)歷史數(shù)據(jù)判斷是否需要將sequence翻轉(zhuǎn)，即A->B->C變?yōu)镃->B->A） 。

第3名 

Data-Driven Vehicle Routing in Last-Mile Delivery

該篇文章也是將原始問題建模成TSP問題，不過它通過對歷史數(shù)據(jù)的描述性分析，用zone_id來調(diào)整成本矩陣，直接調(diào)用遺傳算法求解，然后調(diào)整超參數(shù)，得到最優(yōu)模型后，再求得stop sequence。

第1名的解決方案及細(xì)節(jié)分析

Cook, W等人用此解決方案獲得了第1名

也拿到了US$100,000，(羨慕??

   模 型  

目標(biāo)函數(shù)：時間 + 懲罰系數(shù)*軟約束的懲罰

硬約束：

簇約束(cluster constraint): stop只能與相同cluster的stop進(jìn)行拼接

硬約束(hard-constraint)：在任何時候都必須滿足的約束

cluster指的是根據(jù)某種規(guī)則將stop聚類得到的。文中多次聚類得到 cluster, super cluster, super-super cluster, top-level cluster 如無特殊說明，后續(xù)用 cluster 指代這4種

軟約束：

優(yōu)先級約束(precedence constraint): stop(或cluster)之間有先后順序。e.g. : precedence(a,b) a必須在b之前先訪問。

路徑約束(path constraint): stop(或cluster)之間有先后順序，并且相連。e.g.:path(a,b) 訪問a后必須馬上訪問b。

鄰居約束(neighbor constraint): stop(或cluster)之間必須相連。e.g.:path(a,b) a必須是b的上一個或下一個。

軟約束(soft-constraint)：一種盡可能滿足的“希望”

原文中還考慮了一種軟約束，稱為binary disjunction，是針對以上3種約束而建立的另一個約束。例如，binary disjunction(A,B)表示模型中同時考慮約束A或約束B，滿足其一即可避免懲罰

 具體求解步驟 

（1）先將ATSP轉(zhuǎn)化為TSP

可以參見往期的文章

非對稱TSP問題（Asymmetric Travelling Salesman Problem）轉(zhuǎn)換為對稱TSP問題

https://mp.weixin.qq.com/s/Df5CxbK4bVgTTIVbTZHWSg

（2）用zone-id得到cluster

一個stop是帶有 zone-id 屬性的，該屬性與實際sequence有很大的聯(lián)系，往往同一個zone下stop訪問完了，才會訪問下一個zone。

大部分參賽隊伍都通過分析歷史數(shù)據(jù)知道了這點，并且以此來作為改進(jìn)TSP求解的一個重點

一個zone-id由4部分組成 [符號]-[數(shù)字].[數(shù)字][符號] ，例如 A-2.2E ，所以作者根據(jù)以此得到4種層級的cluster。比如4部分都相同的為最底層的cluster。super-cluster則有3部分相同，例如 A-2.2[符號] 與 A-2.2E 是屬于同一個 super-cluster 。以此類推

（3）從歷史數(shù)據(jù)得到軟約束

這里是小編認(rèn)為文章最精彩的部分，也是其與眾不同之處。限于篇幅，這里僅以最底層的cluster優(yōu)先級約束(即以zone的訪問順序)為例說明。

其中用到的重要概念

強(qiáng)連通分量(strongly connected components): 有向圖G中，任意兩個頂點都強(qiáng)連通(stronglyconnected)，即互相有可達(dá)的有向路徑。則稱G為強(qiáng)連通分量。

分量路徑(component path): 以分量（本文指的是強(qiáng)連通分量）為單位組成的路徑

將歷史數(shù)據(jù)中的一條route的sequence通過如下步驟分成分量路徑 4

step1:由歷史的stop sequence構(gòu)建有向圖

step2:通過深度優(yōu)先搜索將有向圖變成 palm tree 結(jié)構(gòu)

step3:從palm tree得到強(qiáng)連通分量 以及 分量路徑

對于step1很簡單，不再此贅述。

對于step2 通過深度優(yōu)先搜索將有向圖變成 palm tree 結(jié)構(gòu)

可以先拿一個簡單的無向圖例子

首先，會按字母順序從A開始訪問，然后查找A能抵達(dá)且未訪問過的節(jié)點{B, H, F}，然后按字母順序訪問B，然后查找B能抵達(dá)且未訪問過的節(jié)點{C, G}，則按字母順序訪問C，然后查找C能抵達(dá)且未訪問過的節(jié)點{D, H}，然后按字母順序訪問D，然后查找D能抵達(dá)且未訪問過的節(jié)點{E, G}，則按字母順序訪問E，然后查找E能抵達(dá)且未訪問過的節(jié)點{F，H}，然后按字母順序訪問F，然后查找F能抵達(dá)且未訪問過的節(jié)點{G}，然后按字母順序訪問G，此時發(fā)現(xiàn)G 不存在能抵達(dá)且未訪問過的節(jié)點，則回頭找G的上一個點即F，發(fā)現(xiàn)F也不存在能抵達(dá)且未訪問過的節(jié)點，則再回頭找F的上一個點即E，然后發(fā)現(xiàn)此時能抵達(dá)且未訪問過的節(jié)點{H}，則訪問H，此時已經(jīng)訪問完所有，停止搜索。

然后就得到了圖中(c)的實線部分，再把(a)中剩下的路徑以虛線畫到(c)，就得到了 palm tree 結(jié)構(gòu)

注意到palm tree 結(jié)構(gòu)中實線部分是原始有向圖中的節(jié)點間訪問時的“主干”路徑；而虛線則能夠“走回頭路”，即構(gòu)成環(huán)的部分

則對于有向圖而言，同理可得到(b) palm tree結(jié)構(gòu)

再然后再遍歷每條虛線，如果虛線的重點到起點是可以通過實線可達(dá)的，則所經(jīng)過的節(jié)點和邊構(gòu)成一個強(qiáng)連通子圖。

比如對于虛線邊(5, 3)，發(fā)現(xiàn)3到5可以通過實線邊3->4->5，可達(dá)。則點{3,4,5}和邊{(3,4),(4,5),(5,3)}組成的圖是一個強(qiáng)連通子圖。

再將考慮指向這個強(qiáng)連通子圖的線，比如實線(2,3)，則需要從{3,4,5}中找一個虛線路徑抵達(dá)2，發(fā)現(xiàn)沒有，則不納入；再比如虛線(7, 4)，則要從{3,4,5}中找一個實線路徑抵達(dá)7，發(fā)現(xiàn)(3,7)可以，則7和對應(yīng)的邊也納入強(qiáng)連通子圖。

其實就是縮小了尋找的范圍，考慮虛線時，則需要找一個實線路徑可達(dá)；考慮實線時，則需要找一個虛線路徑可達(dá)

以此反復(fù)即可找到各個盡可能大的強(qiáng)連通分量即圖(c)。

對于step3 從palm tree得到強(qiáng)連通分量 以及 分量路徑

這時有趣的地方來了，強(qiáng)連通分量的路徑是單向的，在圖c中強(qiáng)連通分量的路徑是紅色箭頭所示，這表明{1,2,8}必須要在{3,4,5,7}前訪問，也就是說優(yōu)先級由高到低是{1,2,8} > {3,4,5,7} > {6}

這時可能好奇，那歷史中有這么多條sequence，得到的優(yōu)先級有沖突怎么？

· 對于歷史數(shù)據(jù)中的1條sequence，發(fā)現(xiàn)優(yōu)先級a>b時，則precedence(a,b) =precedence(a,b) +1 *weight；若優(yōu)先級a<b時，則precedence(a,b)=precedence(a,b) -1*weight。最后統(tǒng)計完所有sequence就可以得到，precedence(a,b) 的正負(fù)來判斷a和b優(yōu)先級<="" p="">

· weight是根據(jù)route的sequence的質(zhì)量high, medium, low依次為2, 1.5, 1

· 更進(jìn)一步，precedence(a,b) 優(yōu)先級大小也是可以利用的。

（4）用改進(jìn)后的LKH-3求解

作者主要用到

Concorde求解器（用來查看最優(yōu)時的結(jié)果）和

LKH-3求解算法（最終提交時采用的求次優(yōu)解的方法，因為比賽有運(yùn)行時間限制）。

TSP領(lǐng)域公認(rèn)比較出名的求解器/求解算法：

(1)求精確最優(yōu)解——Concorde

Concorde原始版本是用ANSIC編程語言編寫的。Concorde的TSP求解器已用于獲得所有110個

TSPLIB實例的最優(yōu)解；最大的城市有85900個。

Concorde官網(wǎng)

(https://www.math.uwaterloo.ca/tsp/concorde.html)

Concorde的python易用版本

(https://github.com/jingw2/pyconcorde)

(2)啟發(fā)式求近似最優(yōu)解——LKH

最新的LKH-3

(http://webhotel4.ruc.dk/~keld/research/LKH-3/)

不僅可以快速求解：

TSP: Symmetric traveling salesman problem

ATSP: Asymmetric traveling salesman problem

HCP: Hamiltonian cycle problem

HPP: Hamiltonian path problem

還可以求解：

ACVRP: Asymmetric capacitated vehicle routing problem

ADCVRP: Asymmetric distance constrained vehicle routing problem

BWTSP: Black and white traveling salesman problem

CCVRP: Cumulative capacitated vehicle routing problem

CTSP: Colored traveling salesman problem

CVRP: Capacitated vehicle routing problem

CVRPTW: Capacitated vehicle routing problem with time windows

DCVRP: Distance constrained capacitated vehicle routing problem

1-PDTSP: One-commodity pickup-and-delivery traveling salesman problem

m-PDTSP: Multi-commodity pickup-and-delivery traveling salesman problem

m1-PDTSP: Multi-commodity one-to-one pickup-and-delivery traveling salesman problem

MLP: Minimum latency problem

MTRP: Multiple traveling repairman problem

MTRPD: Multiple traveling repairman problem with distance constraints

mTSP: Multiple traveling salesmen problem

OCMTSP: Open close multiple traveling salesman problem

OVRP: Open vehicle routing problem

PDPTW: Pickup-and-delivery problem with time windows

PDTSP: Pickup-and-delivery traveling salesman problem

PDTSPF: Pickup-and-delivery traveling salesman problem with FIFO loading

PDTSPL: Pickup-and-delivery traveling salesman problem with LIFO loading

RCTVRP: Risk-constrained cash-in-transit vehicle routing problem

RCTVRPTW: Risk-constrained cash-in-transit vehicle routing with time windows

SOP: Sequential ordering problem

STTSP: Steiner traveling salesman problem

TRP: Traveling repairman problem

TSPDL: Traveling salesman problem with draft limits

TSPPD: Traveling salesman problem with pickups and deliveries

TSPTW: Traveling salesman problem with time windows

VRPB: Vehicle routing problem with backhauls

VRPBTW: Vehicle routing problem with backhauls and time windows

VRPMPD: Vehicle routing problem with mixed pickup and delivery

VRPMPDTW: Vehicle routing problem with mixed pickup and delivery and time windows

VRPSPD: Vehicle routing problem with simultaneous pickup and delivery

VRPSPDTW: Vehicle routing problem with simultaneous pickup-delivery and time windows

想知道其他求解TSP方法也可以看看我們的往期文章

https://mp.weixin.qq.com/s/eAb5bLoTQxwD6EuPavuRjQ

結(jié)果

作者原文比較散亂

沒有整理結(jié)果

小編在此整理了下作者實驗的結(jié)果

LKH-AMZ是作者對LKH-3進(jìn)行了一些約束條件方面的擴(kuò)展

題外話環(huán)節(jié)

作者原文中還是很多其他細(xì)節(jié)的

比如訓(xùn)練集和測試集的劃分、ATSP的3-opt和4-opt、路徑合并、敏感性分析等等

朋友們是進(jìn)一步了解這些細(xì)節(jié)呢

還是想看一下第2、3名的解決方案呢