中國物流供應(yīng)鏈“零的突破”！阿里路徑規(guī)劃算法入圍運(yùn)籌學(xué)“奧斯卡”

魚羊 發(fā)自 凹非寺
量子位 報(bào)道 | 公眾號(hào) QbitAI

最新消息，中國物流力量，剛在全球運(yùn)籌和管理科學(xué)界的最高榮譽(yù)中，實(shí)現(xiàn)零的突破！

1月15日，國際運(yùn)籌學(xué)與管理科學(xué)學(xué)會(huì)（INFORMS）公布了2021年Franz Edelman杰出成就獎(jiǎng)總決賽名單，阿里巴巴憑借領(lǐng)先的路徑規(guī)劃算法及新零售實(shí)踐，首度闖進(jìn)總決賽。

INFORMS評(píng)價(jià)稱，阿里開創(chuàng)了新零售模式，通過技術(shù)優(yōu)化了倉配流程，可在極短時(shí)間內(nèi)實(shí)現(xiàn)80%~90%的最優(yōu)性能。

Franz Edelman杰出成就獎(jiǎng)，是全球運(yùn)籌和管理科學(xué)界的最高工業(yè)應(yīng)用獎(jiǎng)，被譽(yù)為運(yùn)籌學(xué)的“奧斯卡”。該獎(jiǎng)項(xiàng)重點(diǎn)獎(jiǎng)勵(lì)世界各國、地區(qū)，在運(yùn)籌和管理學(xué)領(lǐng)域做出突出貢獻(xiàn)、并帶來重大應(yīng)用價(jià)值的研究項(xiàng)目或成果。

入圍者不僅要在學(xué)術(shù)上有創(chuàng)新，還要經(jīng)過業(yè)界的檢驗(yàn)，在實(shí)際落地的過程中明確產(chǎn)生價(jià)值。

在以往的獲獎(jiǎng)名單中，物流領(lǐng)域有過美國亞馬遜、沃爾瑪?shù)绕髽I(yè)的項(xiàng)目成果，普遍在實(shí)際業(yè)務(wù)中產(chǎn)生了數(shù)億美元以上的效益。自該獎(jiǎng)項(xiàng)1972年首次頒發(fā)以來，獲獎(jiǎng)項(xiàng)目更是已累計(jì)產(chǎn)生2500多億美元價(jià)值。

但該領(lǐng)域內(nèi)，中國在此之前尚屬空白地帶，獎(jiǎng)項(xiàng)設(shè)立50年來，這是首次有中國物流供應(yīng)鏈領(lǐng)域企業(yè)入圍。

所以阿里物流供應(yīng)鏈拿出的究竟是怎樣的算法？又能給我們的日常生活帶來了怎樣的改變？

阿里因何獲獎(jiǎng)？

物流路徑規(guī)劃問題，屬于典型的NP-hard問題。

結(jié)合零售場景簡單來解釋，其實(shí)就是如何快速實(shí)時(shí)地規(guī)劃倉內(nèi)的揀貨路線，以及騎手的配送路線的問題。

具體而言，在倉內(nèi)，路徑規(guī)劃算法需要綜合消費(fèi)者訂單、商品在貨架的位置、揀選員傳輸給打包員的懸掛鏈速度等因素，指引揀貨員進(jìn)行更合理的工作。

在倉外，算法又需靠考慮配送員與商家的距離、商家備貨時(shí)間等動(dòng)態(tài)因素，分配距離近、工作量合理的配送員取貨。

這里挑戰(zhàn)主要在于以下三點(diǎn)：

 

• 不確定性：首先，在即時(shí)倉儲(chǔ)配送模式下，顧客隨時(shí)可能下單，需求存在隨機(jī)性；其次，城市交通擁堵問題會(huì)帶來通行時(shí)間的不確定性；最后，到達(dá)顧客所在位置后的配送交付同樣存在不確定性，比如登記信息、等待電梯等帶來的耗時(shí)。
• 在倉內(nèi)空間有限的情況下，規(guī)劃符合業(yè)務(wù)需求的路徑：在倉內(nèi)作業(yè)階段，以盒馬為例，每個(gè)批次有2-5個(gè)客戶訂單，每個(gè)客戶訂單包含任意4-8種商品，這些商品分散在倉內(nèi)各個(gè)分區(qū)內(nèi)，每個(gè)分區(qū)揀選完通過懸掛鏈傳送到質(zhì)檢臺(tái)打包，派送地址相近的訂單還要進(jìn)行集包，而后傳輸出庫。因此倉內(nèi)路徑的優(yōu)化需要同時(shí)考慮揀貨路徑和配送路徑，并盡可能同時(shí)到達(dá)懸掛鏈，不在這個(gè)過程中造成堵塞。
• 嚴(yán)格的求解時(shí)間：由于訂單即時(shí)性的需求，這樣的路徑優(yōu)化需要在極短時(shí)間內(nèi)完成，以留下足夠的實(shí)際操作時(shí)間。

 

為此，阿里協(xié)同旗下菜鳥、盒馬、Lazada等各業(yè)務(wù)方，打造了基于大規(guī)模領(lǐng)域搜索和深度強(qiáng)化學(xué)習(xí)的路徑規(guī)劃算法方案，實(shí)現(xiàn)了用＜0.01秒的時(shí)間，得到最優(yōu)解98%~99%的最優(yōu)性。

阿里巴巴供應(yīng)鏈與運(yùn)籌優(yōu)化小組介紹，阿里VRP路徑規(guī)劃，雛形始于2016年菜鳥，并在豐富的倉儲(chǔ)和配送協(xié)同中持續(xù)打磨，可支持半小時(shí)到2小時(shí)內(nèi)送達(dá)的新業(yè)態(tài)，在預(yù)測(cè)、庫存等方向處于業(yè)界前沿，未來將探索新零售更多可能。

自適應(yīng)大規(guī)模鄰域搜索算法框架

自適應(yīng)大規(guī)模鄰域搜索算法（ALNS），是2016年菜鳥開始建設(shè)路徑規(guī)劃算法系統(tǒng)之初，就擇定的技術(shù)路線。

當(dāng)時(shí)，國內(nèi)外行業(yè)內(nèi)的多數(shù)玩家選擇的都是成熟的開源算法，比如jsprit和opt-planner等。但出于對(duì)后期技術(shù)發(fā)展天花板被限制的擔(dān)憂，菜鳥還是選擇了自主開發(fā)的路徑。

而自適應(yīng)大規(guī)模鄰域搜索（ALNS）算法框架的優(yōu)勢(shì)在于：

 

• 易于拓展，除了求解標(biāo)準(zhǔn)的VRP（車輛路徑規(guī)劃）之外，還能夠求解其各種變型問題；
• 相對(duì)于局部搜索類型的算法，ALNS在每一步搜索過程中能夠探索更大的解空間；
• ALNS算法在搜索過程中能夠自適應(yīng)地選擇合適的算子，對(duì)于不同類型的數(shù)據(jù)都能有比較魯棒的求解效果；
• 便于算法升級(jí)拓展，通過設(shè)計(jì)實(shí)現(xiàn)不同類型的算子，ALNS可以實(shí)現(xiàn)不同的搜索策略。

 

這樣的選擇，其實(shí)有點(diǎn)無知者無畏的態(tài)度在里面。

該小組核心成員友竹在事后回想時(shí)，這樣說道。

好在以ALNS算法為核心的第一版VRP優(yōu)化引擎研發(fā)完成后，研發(fā)人員們很快看到了效果：對(duì)比測(cè)試結(jié)果表明，其求解效果和效率顯著優(yōu)于jsprit等國際上流行的開源VRP Solver。

在此之后，團(tuán)隊(duì)又從兩方面出發(fā)，進(jìn)一步對(duì)VRP優(yōu)化引擎的核心算法組件進(jìn)行了豐富和升級(jí)。

一方面是功能上的擴(kuò)展。

比如在原算法核心框架的基礎(chǔ)上，增加了對(duì)Pickup and Delivery（車輛一邊攬收一邊派送）、Multi Trip（車輛多趟派送）等類型問題的支持；并且通過對(duì)實(shí)際業(yè)務(wù)問題的抽象，總結(jié)出不同類型的優(yōu)化目標(biāo)方程（例如最小化階梯定價(jià)的總成本、最小化配送時(shí)間等）以及約束條件（例如車輛行駛距離限制、車輛配送訂單數(shù)限制、車輛跨區(qū)數(shù)限制等），從而使求解引擎能夠求解的問題更加全面廣泛。同時(shí)，還研發(fā)了一套領(lǐng)域特定語言（DSL），調(diào)用者僅需定義相應(yīng)的業(yè)務(wù)邏輯，與數(shù)據(jù)和核心算法相解耦，即可完成問題的求解。

另一方面則是技術(shù)上的探索。

比如為了進(jìn)一步提升VRP引擎的求解質(zhì)量，對(duì)其進(jìn)行并行化升級(jí)，先后研發(fā)實(shí)現(xiàn)了三套并行化算法架構(gòu)：

包括基于odps-graph實(shí)現(xiàn)的island分布式模型，基于spark實(shí)現(xiàn)的central pool模型，最后是充分利用GPU并行計(jì)算的優(yōu)勢(shì)，使用原生的CUDA C編程接口，將計(jì)算和數(shù)據(jù)更新等并行度較高的模塊放在GPU上執(zhí)行。在大規(guī)模數(shù)據(jù)集上測(cè)試發(fā)現(xiàn)，相比于使用CUBLAS，這一方案可以獲得40倍的加速，相對(duì)于原先的單機(jī)版本，可以加速近一千倍。

深度強(qiáng)化學(xué)習(xí)算法框架

在啟發(fā)式算法的路線之外，阿里路徑規(guī)劃算法系統(tǒng)還引入了另一條技術(shù)路線，就是深度強(qiáng)化學(xué)習(xí)（DRL）。

核心原因同樣是業(yè)務(wù)場景的需求：比如外賣、打車這樣的場景，需要在毫秒級(jí)的時(shí)間內(nèi)返回結(jié)果。

深度強(qiáng)化學(xué)習(xí)算法框架，提供了一系列基于圖神經(jīng)網(wǎng)絡(luò)的增強(qiáng)學(xué)習(xí)算法來求解VRP。

其中，圖神經(jīng)網(wǎng)絡(luò)算法以點(diǎn)（坐標(biāo)和需求）和邊（點(diǎn)間距離和時(shí)間）作為輸入，配合兩類解碼器分別解碼這兩類特征，并結(jié)合有監(jiān)督學(xué)習(xí)的方法來訓(xùn)練相應(yīng)模型。

另外，研究人員還將深度強(qiáng)化學(xué)習(xí)和自適應(yīng)大規(guī)模鄰域搜索進(jìn)行了組合，以ALNS算法結(jié)果作為樣本來訓(xùn)練DRL模型，更快速地求解VRP問題。

這樣的組合拳之下，阿里VRP優(yōu)化引擎實(shí)際早已霸氣外露。

在入圍Franz Edelman杰出成就獎(jiǎng)之前，該引擎已經(jīng)拿下不少世界第一。

比如2018年9月，在VRP算法領(lǐng)域最權(quán)威的評(píng)測(cè)對(duì)比平臺(tái)——?dú)W洲獨(dú)立研究機(jī)構(gòu)SINTEF發(fā)起并管理的Best Known Solution榜單上，路徑規(guī)劃算法就在VRPTW（客戶對(duì)貨物的送達(dá)時(shí)間有時(shí)間窗要求）上打破了世界紀(jì)錄。

而截至2020年10月，VRP路徑規(guī)劃算法在這一榜單上取得了36個(gè)VRPTW實(shí)例和23個(gè)PDVRPTW實(shí)例的已知最優(yōu)解，是國內(nèi)首家在這兩個(gè)問題上同時(shí)取得如此多世界紀(jì)錄的物流供應(yīng)鏈公司。

但既然能入圍Franz Edelman杰出成就獎(jiǎng)，自然還得在產(chǎn)業(yè)應(yīng)用中有真章。

在阿里供應(yīng)鏈&運(yùn)籌優(yōu)化技術(shù)小組的牽線之下，該算法已經(jīng)在阿里集團(tuán)內(nèi)部開源，并被各個(gè)不同業(yè)務(wù)的算法團(tuán)隊(duì)敞開懷抱接納：盒馬、菜鳥、Lazada等平臺(tái)早已應(yīng)用多時(shí)。算法帶來的價(jià)值正不斷在這些深入人們生活的業(yè)務(wù)場景中積累，而對(duì)于技術(shù)人員而言，亦省卻了重復(fù)造輪子的負(fù)擔(dān)。

深入生活的算法

點(diǎn)一份盒馬，足不出戶，30分鐘到1小時(shí)內(nèi)就能有高品質(zhì)生鮮菜品下鍋。

你如今已經(jīng)習(xí)以為常的便捷背后，正是路徑規(guī)劃算法這樣的AI技術(shù)在發(fā)揮作用。

阿里供應(yīng)鏈與運(yùn)籌優(yōu)化技術(shù)小組介紹，以倉庫揀貨為例，由于商品分布在倉庫里各個(gè)不同的庫位上，如果沒有合理的路徑規(guī)劃，揀貨員難免在反復(fù)尋找的過程中浪費(fèi)很多時(shí)間、精力。

在用上了路徑規(guī)劃算法之后，揀貨員就可以走最短的路，揀最快的貨：原來一天要走2萬多步，現(xiàn)在只需要走1萬多步。

而在城配方面，對(duì)一個(gè)倉所覆蓋的訂單進(jìn)行調(diào)度，最早是地圖上人工框選來完成的，甚至是通過Excel按照文本地址來進(jìn)行分組。由于配送點(diǎn)數(shù)眾多，再加上實(shí)時(shí)落單的特性，調(diào)度時(shí)需兼顧車輛的裝載率、里程、對(duì)區(qū)域的熟悉度等因素，花費(fèi)的決策時(shí)間長達(dá)30-40分鐘。而對(duì)AI而言，分鐘級(jí)即可完成調(diào)度，這就給倉庫留下了足夠的生產(chǎn)時(shí)間，也通過更優(yōu)的組合，提高了車效。

還不僅僅是零售、城配等領(lǐng)域。

實(shí)際上，物流路徑規(guī)劃算法背后的技術(shù)積累，可以說打造出了一把能用在各個(gè)不同業(yè)務(wù)中的“屠龍寶刀”。

以阿里自身的業(yè)務(wù)為例，大規(guī)模鄰域搜索算法和深度強(qiáng)化學(xué)習(xí)算法這兩套通用框架，同樣可以解決犀牛智造的機(jī)器加工調(diào)度問題，為自動(dòng)化生產(chǎn)規(guī)劃最佳的加工路線。

同樣，這套算法也可以遷移到打車領(lǐng)域的調(diào)度、拼車決策上。

在阿里內(nèi)部的歡行打車平臺(tái)上，由于路徑規(guī)劃算法的引入，在同樣的運(yùn)力下，可以使下班高峰期的打車成單率，從60%提高到90%。

所以如果更加簡單粗暴理解，這一套算法，就讓菜鳥展現(xiàn)出了“頭部外賣平臺(tái)+頭部打車平臺(tái)”具備的核心技術(shù)實(shí)力。

“貼地飛行”的科學(xué)家

阿里供應(yīng)鏈與運(yùn)籌優(yōu)化技術(shù)小組中，有不少博士畢業(yè)后就致力于讓技術(shù)在實(shí)際業(yè)務(wù)場景中產(chǎn)生價(jià)值的研發(fā)人員。而此次入圍運(yùn)籌學(xué)“奧斯卡”決賽圈，對(duì)于他們而言無疑是極大的鼓勵(lì)。

但其實(shí)對(duì)于團(tuán)隊(duì)而言，這個(gè)成績一開始并不在意料之中，一切也并非為獲獎(jiǎng)而立項(xiàng)。

值得指出的是，早在2016年，菜鳥就開啟了物流路徑規(guī)劃算法系統(tǒng)的研發(fā)工作，不是為了刷榜，不是為了拿獎(jiǎng)，就是為了解決實(shí)際業(yè)務(wù)中的痛點(diǎn)而已。

團(tuán)隊(duì)成員坦言，在項(xiàng)目成立之初，不會(huì)想到今天的成績。

一開始，研發(fā)人員其實(shí)只是想要求解最簡單的單倉發(fā)多點(diǎn)的問題，因?yàn)樵诋?dāng)時(shí)的業(yè)務(wù)場景下，這樣的情況占到了百分之六七十。

而當(dāng)算法在應(yīng)用之中，價(jià)值得到驗(yàn)證，更多的業(yè)務(wù)需求也就被提到了研發(fā)人員面前，比如多倉發(fā)貨，比如外賣同時(shí)取送貨……研發(fā)人員也就在這個(gè)過程中不斷地去分解目標(biāo)，通過打榜驗(yàn)證求解效果，不斷迭代、完善功能。

歸根結(jié)底，最開始是從業(yè)務(wù)痛點(diǎn)出發(fā)，為了解決實(shí)際場景的問題。

我們?nèi)ゴ蚱聘鞣NBest Known Solution，主要是為了驗(yàn)證算法的價(jià)值。

不過，回首向來蕭瑟處，一切也都是對(duì)菜鳥團(tuán)隊(duì)幾年如一日下苦功的獎(jiǎng)賞。

團(tuán)隊(duì)透露，在菜鳥人工智能部有上百名員工，博士就占了1/3，一直希望用最前沿的科學(xué)技術(shù)方法，求解現(xiàn)實(shí)業(yè)務(wù)中的最優(yōu)解。

而無論菜鳥還是整個(gè)阿里經(jīng)濟(jì)體，正恰如其分地提供了最好的演武場，讓他們得以實(shí)現(xiàn)“貼地飛行”的務(wù)實(shí)理想。

比如場景的豐富度。從各種淘系訂單，到四通一達(dá)的包裹，再到各種社區(qū)零售店的日常補(bǔ)貨，每一個(gè)來到菜鳥的研發(fā)人員，都有在實(shí)際大流量場景中，檢驗(yàn)算法好壞的機(jī)會(huì)。

當(dāng)然，還有一些凡爾賽式的總結(jié)。

前面也說道，VRP問題屬于典型的NP-hard問題，在面對(duì)實(shí)際狀況時(shí)，不僅問題規(guī)模大，求解難度也十分巨大。

舉個(gè)例子，在求解n!復(fù)雜度問題時(shí)（即TSP，VRP退化最簡單的情形），若n=30，每秒運(yùn)算100億億次的超級(jí)計(jì)算機(jī)就得花上8萬年的時(shí)間。

而現(xiàn)在利用上阿里本身豐富的軟硬件資源，加上高效的搜索策略，算法研發(fā)人員就可以更低成本地打造高性能、高可靠的解決方案。比如基于阿里云的MaxCompute（原ODPS）數(shù)據(jù)倉庫，或菜鳥自研的Minas包裹數(shù)據(jù)引擎，對(duì)于實(shí)際場景中的大規(guī)模問題，研發(fā)人員可以避免傳統(tǒng)的人工干預(yù)和模型簡化，直接從數(shù)據(jù)庫中讀取原生問題進(jìn)行建模，然后直接導(dǎo)入高可靠的分布式求解器GreedSolver，在較小的延遲內(nèi)獲取高精度解，為業(yè)務(wù)提效賦能。

還有團(tuán)隊(duì)成員結(jié)合自身經(jīng)歷發(fā)出這樣的感慨：

以應(yīng)屆博士生身份進(jìn)入菜鳥人工智能團(tuán)隊(duì)時(shí)，一開始不會(huì)被設(shè)置明確的KPI，能享受到一個(gè)比較寬松的技術(shù)環(huán)境，有充分的空間去思考去觀察，并發(fā)起自己認(rèn)為有意義、感興趣的研究項(xiàng)目。

而在這個(gè)成長的過程中，得益于阿里的業(yè)務(wù)土壤，又能夠以戰(zhàn)養(yǎng)戰(zhàn)，讓技術(shù)在實(shí)際業(yè)務(wù)中快速得到檢驗(yàn)。

所以菜鳥在這次獎(jiǎng)項(xiàng)中，能夠?yàn)橹袊锪黝I(lǐng)域?qū)崿F(xiàn)里程碑式的成績，天時(shí)地利人和，缺一不可。

菜鳥技術(shù)面

實(shí)際上，這也展示了菜鳥通常被易于忽略的那一面。

提起菜鳥，你會(huì)想起什么？

菜鳥驛站，亦或是淘寶退換貨時(shí)的上門取件？

都是日常剛需的事情。

但這次入圍運(yùn)籌學(xué)“奧斯卡”，展現(xiàn)了菜鳥的另一面——硬核技術(shù)面，而且說明接地氣也可以很科技。

并且對(duì)于菜鳥，還不止是物流路徑規(guī)劃算法。

在影響每個(gè)人的日常中，電子面單的應(yīng)用，讓每個(gè)包裹都擁有了獨(dú)一無二的“身份證”，實(shí)現(xiàn)了全程流轉(zhuǎn)均能被機(jī)器自動(dòng)識(shí)別分撥，無需人工分揀的包裹數(shù)字化，構(gòu)建了物流領(lǐng)域物聯(lián)網(wǎng)的基礎(chǔ)。

以及菜鳥驛站對(duì)于末端取件的數(shù)字化：包裹到站，智能中臺(tái)一站式完成快遞上架、編碼、通知；自助無感取件，匹配智能云監(jiān)控，掃描一下，即可帶走；刷臉寄件，方便秒寄；還有菜鳥無人車的安全無接觸配送……

只是商業(yè)和業(yè)務(wù)場景上的成功，讓菜鳥易于被忽略業(yè)務(wù)生態(tài)之上的AI、前沿技術(shù)力量。

而且這樣的技術(shù)之力，不僅會(huì)推動(dòng)中國的快遞乃至物流行業(yè)的數(shù)字化變革，也正在面向更廣泛的應(yīng)用場景遷移、輸出，讓我們每一個(gè)人的生活變得更加便捷、高效。

這也是菜鳥的技術(shù)面，值得被更長久關(guān)注的最重要原因。

更完整認(rèn)識(shí)菜鳥，是時(shí)候了。