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

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

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

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

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

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

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

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

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

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

阿里因何獲獎？

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

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

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

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

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

 

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

 

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

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

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

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

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

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

 

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

 

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

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

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

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

一方面是功能上的擴展。

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

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

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

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

深度強化學習算法框架

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

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

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

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

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

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

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

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

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

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

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

深入生活的算法

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

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

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

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

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

還不僅僅是零售、城配等領域。

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

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

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

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

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

“貼地飛行”的科學家

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

但其實對于團隊而言，這個成績一開始并不在意料之中，一切也并非為獲獎而立項。

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

團隊成員坦言，在項目成立之初，不會想到今天的成績。

一開始，研發(fā)人員其實只是想要求解最簡單的單倉發(fā)多點的問題，因為在當時的業(yè)務場景下，這樣的情況占到了百分之六七十。

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

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

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

不過，回首向來蕭瑟處，一切也都是對菜鳥團隊幾年如一日下苦功的獎賞。

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

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

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

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

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

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

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

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

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

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

所以菜鳥在這次獎項中，能夠為中國物流領域?qū)崿F(xiàn)里程碑式的成績，天時地利人和，缺一不可。

菜鳥技術(shù)面

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

提起菜鳥，你會想起什么？

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

都是日常剛需的事情。

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

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

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

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

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

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

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

更完整認識菜鳥，是時候了。