MIT和亞馬遜舉辦的路徑優(yōu)化比賽—— US$175000的解決方案分享
MIT和亞馬遜舉辦的路徑優(yōu)化比賽——
US$175000的解決方案分享
不久前
MIT和亞馬遜聯(lián)合舉辦的
最后一公里配送的路徑優(yōu)化比賽結(jié)束了（點擊閱讀全文，查看比賽鏈接）
前三名總共獲得US$175000。
今天小編借著這個比賽的機會給大家介紹下相關(guān)的運籌優(yōu)化知識和各路高手的解法。
目錄/contents
1.?比賽簡介?
問題背景?
數(shù)據(jù)集結(jié)構(gòu)?
成績評價?
2.?前3名的解決方案簡介?
第1名?
第2名?
第3名?
3.?第1名的解決方案及細節(jié)分析?
模型
具體求解步驟?
（1）先將ATSP轉(zhuǎn)化為TSP?
（2）用zone-id得到cluster?
（3）從歷史數(shù)據(jù)得到軟約束?
對于step2?通過深度優(yōu)先搜索將有向圖變成?palm tree?結(jié)構(gòu)?
對于step3?從palm tree得到強連通分量 以及 分量路徑?
（4）用改進后的LKH-3求解?
結(jié)果?
題外話環(huán)節(jié)?
參考資料
比賽簡介
問題背景
最后一公里配送問題，指的就是區(qū)域配送中心到末端設(shè)施這一段的配送問題。司機需要在配送中心裝載好貨物，按順序訪問多個末端設(shè)施進行收貨或送貨操作，最后回到配送中心。
這個送貨的路徑在比賽中被稱作route（如下圖所示）；配送中心是這條route的起點和終點，稱做station；訪問的末端設(shè)施，收件人寄件人的具體地址則被稱作stop（圖中圓點）；圖中stop的顏色相同說明歸屬于同一個zone；圖中stop的標號說明訪問這個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ī)定送達的時間窗等）
· stop之間的travel time
成績評價
而如何評價一個sequence的好壞呢？這就是這個最后一公里問題不同尋常的地方了。不同于傳統(tǒng)路徑規(guī)劃問題中配送距離或時間越短則說路徑越好，而這里的路徑好壞是人為評分的結(jié)果，分為高中低三個檔次，這里可能包含了司機的主觀經(jīng)驗。
故舉辦方會提供歷史上6112條route的信息，其中有2718條評分高的route。參賽者在測試算法效果時，可將每條評分高的route的信息（如訪問的stop的經(jīng)緯度位置、包裹的尺寸等）輸入算法中，輸出每條route預測的stop sequence。通過計算預測的和實際的sequence間的相似程度，可以衡量算法預測出來的sequence的好壞。對所有的route重復上述操作即可獲得總得分submission score，進而衡量算法的好壞。流程如下圖所示：
參賽者提交完最終版算法之后，舉辦方將輸入的route替換成3000條新的route，重復上圖流程后，根據(jù)得到的submission score對所有隊伍由低到高進行排名。具體的計算方式如下式所列：
submission score?越低越好
這里舉個栗子，如下表，序列A為依次訪問站點1、2、3、4，序列B為依次訪問站點2、4、3、1，則a[i]為B[i]在A中的位置，當a中的元素不嚴格按照升序排列，即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ù)學家Vladimir Levenshtein在1965年提出。是指利用字符操作，把字符串A轉(zhuǎn)換成字符串B所需要的最少操作數(shù)。其中，字符操作包括：刪除一個字符、插入一個字符、修改一個字符。一般來說，兩個字符串的編輯距離越小，則它們越相似。
例如對于字符串 if 和 iff ，可以通過插入一個 f 或者刪除一個'f'來達到目的。
總的來說，就是將實際的sequence作為一個最高基準，參賽方根據(jù)已有的信息預測的sequence和實際sequence越接近，說明其算法越好。雖說和機器學習很像，但遺憾的是，這次比賽中排行榜前三的隊伍都是采用優(yōu)化算法來求解的，接下來就給大家介紹一下~
前3名的解決方案簡介
第1名
Local?Search?with?Learned?Constraints?for?Last?Mile?Routing
該篇文章將原始問題建模成帶約束的非對稱旅行商問題。具體的約束從歷史數(shù)據(jù)中學得，主要包括簇約束、優(yōu)先級約束。最后采用改進的LKH算法進行求解。
第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進行求解，最后對得到的sequence進行修正（根據(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名的解決方案及細節(jié)分析
Cook, W等人用此解決方案獲得了第1名
也拿到了US$100,000，(羨慕??
? ?模 型 ?
目標函數(shù)：時間?+?懲罰系數(shù)*軟約束的懲罰
硬約束：
簇約束(cluster constraint): stop只能與相同cluster的stop進行拼接
硬約束(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ù)知道了這點，并且以此來作為改進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ù)得到軟約束
這里是小編認為文章最精彩的部分，也是其與眾不同之處。限于篇幅，這里僅以最底層的cluster優(yōu)先級約束(即以zone的訪問順序)為例說明。
其中用到的重要概念
強連通分量(strongly connected components):?有向圖G中，任意兩個頂點都強連通(stronglyconnected)，即互相有可達的有向路徑。則稱G為強連通分量。
分量路徑(component path):?以分量（本文指的是強連通分量）為單位組成的路徑
將歷史數(shù)據(jù)中的一條route的sequence通過如下步驟分成分量路徑?4
step1:由歷史的stop sequence構(gòu)建有向圖
step2:通過深度優(yōu)先搜索將有向圖變成?palm tree?結(jié)構(gòu)
step3:從palm tree得到強連通分量 以及 分量路徑
對于step1很簡單，不再此贅述。
對于step2?通過深度優(yōu)先搜索將有向圖變成?palm tree?結(jié)構(gòu)
可以先拿一個簡單的無向圖例子
首先，會按字母順序從A開始訪問，然后查找A能抵達且未訪問過的節(jié)點{B, H, F}，然后按字母順序訪問B，然后查找B能抵達且未訪問過的節(jié)點{C, G}，則按字母順序訪問C，然后查找C能抵達且未訪問過的節(jié)點{D, H}，然后按字母順序訪問D，然后查找D能抵達且未訪問過的節(jié)點{E, G}，則按字母順序訪問E，然后查找E能抵達且未訪問過的節(jié)點{F，H}，然后按字母順序訪問F，然后查找F能抵達且未訪問過的節(jié)點{G}，然后按字母順序訪問G，此時發(fā)現(xiàn)G?不存在能抵達且未訪問過的節(jié)點，則回頭找G的上一個點即F，發(fā)現(xiàn)F也不存在能抵達且未訪問過的節(jié)點，則再回頭找F的上一個點即E，然后發(fā)現(xiàn)此時能抵達且未訪問過的節(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)
再然后再遍歷每條虛線，如果虛線的重點到起點是可以通過實線可達的，則所經(jīng)過的節(jié)點和邊構(gòu)成一個強連通子圖。
比如對于虛線邊(5, 3)，發(fā)現(xiàn)3到5可以通過實線邊3->4->5，可達。則點{3,4,5}和邊{(3,4),(4,5),(5,3)}組成的圖是一個強連通子圖。
再將考慮指向這個強連通子圖的線，比如實線(2,3)，則需要從{3,4,5}中找一個虛線路徑抵達2，發(fā)現(xiàn)沒有，則不納入；再比如虛線(7, 4)，則要從{3,4,5}中找一個實線路徑抵達7，發(fā)現(xiàn)(3,7)可以，則7和對應(yīng)的邊也納入強連通子圖。
其實就是縮小了尋找的范圍，考慮虛線時，則需要找一個實線路徑可達；考慮實線時，則需要找一個虛線路徑可達
以此反復即可找到各個盡可能大的強連通分量即圖(c)。
對于step3?從palm tree得到強連通分量 以及 分量路徑
這時有趣的地方來了，強連通分量的路徑是單向的，在圖c中強連通分量的路徑是紅色箭頭所示，這表明{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
· weight是根據(jù)route的sequence的質(zhì)量high, medium, low依次為2, 1.5, 1
· 更進一步，precedence(a,b)?優(yōu)先級大小也是可以利用的。
（4）用改進后的LKH-3求解
作者主要用到
Concorde求解器（用來查看最優(yōu)時的結(jié)果）和
LKH-3求解算法（最終提交時采用的求次優(yōu)解的方法，因為比賽有運行時間限制）。
TSP領(lǐng)域公認比較出名的求解器/求解算法：
(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進行了一些約束條件方面的擴展
題外話環(huán)節(jié)
作者原文中還是很多其他細節(jié)的
比如訓練集和測試集的劃分、ATSP的3-opt和4-opt、路徑合并、敏感性分析等等
朋友們是進一步了解這些細節(jié)呢
還是想看一下第2、3名的解決方案呢
（挖坑）
參考資料
1. Cook, W., Held, S., & Helsgaun, K. (2021). Local Search with Learned Constraints for Last Mile Routing. In Winkenbach, M., Parks, S., &Noszek, J. (Eds.),?Technical Proceedings of the 2021 Amazon Last Mile Routing Research Challenge?(pp. XXI.1–XXI.12). MIT Libraries. https://hdl.handle.net/1721.1/131235
2. Xiaotong Guo, Baichuan Mo and Qingyi Wang. (2021). Last-Mile Delivery Trajectory Prediction Using Hierarchical TSP with Customized?Cost Matrix. In Winkenbach, M., Parks, S., & Noszek, J. (Eds.),?Technical Proceedings of the 2021 Amazon Last Mile Routing Research Challenge?(pp. II.1–II.12). MIT Libraries. https://hdl.handle.net/1721.1/131235
3. Okan Arslan and Rasit Abay. (2021). Data-Driven Vehicle Routing in Last-Mile Delivery. In Winkenbach, M., Parks, S., & Noszek, J.(Eds.),echnical Proceedings of the 2021 Amazon Last Mile Routing Research Challenge?(pp. VI.1–VI.14). MIT Libraries. https://hdl.handle.net/1721.1/131235
4. Tarjan, R. (1972). Depth-first search and linear graph algorithms.?SIAM Journal on Computing, 1?, 146-160.doi:10.1137/0201010.
5. Helsgaun, K. (2017). An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing?problems.?Technical Report Roskilde Universitet. URL: http://akira.ruc.dk/~keld/research/LKH/LKH-3_REPORT.pdf.
- END -
文案：丘潤文、王月婷(華南理工大學工商管理學院研究生一年級）、謝旖(華南理工大學工商管理學院研究生二年級）
指導老師：朱文斌（華南理工大學工商管理學院）
排版：程欣悅（荊楚理工學院本科四年級）
如對文中內(nèi)容有疑問，歡迎交流。PS：部分資料來自網(wǎng)絡(luò)。
如有需求，可以聯(lián)系：朱文斌（華南理工大學工商管理學院：[email protected]）丘潤文（華南理工大學工商管理學院研究生一年級：[email protected]）程欣悅（荊楚理工學院本科四年級：[email protected]）
【END】