隨著業(yè)務(wù)規(guī)模的擴大，如何有效地優(yōu)化訂單結(jié)構(gòu)，合理高效地進行訂單調(diào)度和路徑規(guī)劃以提升整體配送效率顯得尤其重要。運籌OR帷幄有幸邀請到郝井華博士為我們剖析智能配送背后的秘密。

嘉賓介紹

郝井華

清華大學(xué)自動化系博士，美團點評研究員。加入美團前，在清華大學(xué)從事工業(yè)過程智能控制、智能優(yōu)化與調(diào)度技術(shù)的研發(fā)和應(yīng)用。發(fā)表學(xué)術(shù)論文30多篇，專利20項，獲國家科技進步獎和中國物流科技進步獎等。目前致力于解決即時配送業(yè)務(wù)中的智能調(diào)度、路徑規(guī)劃、動態(tài)定價、網(wǎng)絡(luò)規(guī)劃等難題，借助人工智能技術(shù)實現(xiàn)『最后一公里』配送業(yè)務(wù)的動態(tài)最優(yōu)化，更好地服務(wù)億萬用戶的即時配送需求。

1.  能否介紹您所在的算法團隊的情況？

美團外賣作為全球最大的外賣平臺，不但擁有最大規(guī)模的外賣訂單量和領(lǐng)先的市場份額，而且還建設(shè)了“美團配送”這個全球最大的即時配送網(wǎng)絡(luò)，以及行業(yè)領(lǐng)先的美團智能配送系統(tǒng)。如何讓配送網(wǎng)絡(luò)運行效率更高、用戶體驗更好是一項相當(dāng)困難的挑戰(zhàn)。這其中存在大量的復(fù)雜機器學(xué)習(xí)和運籌優(yōu)化問題，包括ETA、智能調(diào)度、網(wǎng)絡(luò)規(guī)劃、地圖優(yōu)化、動態(tài)定價、情景感知、智能運營等多個領(lǐng)域。

過去3年來，美團配送 AI 團隊持續(xù)在上述問題上投入，研發(fā)成果卓著。配送時長從50分鐘陸續(xù)縮短到30分鐘，配送 AI 項目獲得過4次公司級大獎，申請了60多項發(fā)明專利。團隊現(xiàn)有50余人，主要來自百度鳳巢、騰訊、阿里、滴滴、雅虎等一線互聯(lián)網(wǎng)公司以及清華、中科院、MIT 等知名科研機構(gòu)，研發(fā)實力和氛圍卓越。目前美團配送業(yè)務(wù)仍處于快速發(fā)展期，新的場景、新的技術(shù)難題不斷涌現(xiàn)，成長空間巨大。

2.  你們團隊每天的工作內(nèi)容是怎樣的？

在工作內(nèi)容上，團隊中的算法工程師會針對即時配送業(yè)務(wù)場景的特定運籌優(yōu)化或機器學(xué)習(xí)問題開展數(shù)據(jù)分析、模型和算法設(shè)計、開發(fā)和上線、效果評估等工作，推動 AI在業(yè)務(wù)場景中發(fā)揮作用，輔助或替代人工工作，產(chǎn)生業(yè)務(wù)價值。

以一個外賣訂單的履約過程為例：用戶打開美團外賣瀏覽商家時，每個商家的預(yù)計送達時間和配送費都是我們團隊利用算法考慮多類因素給出的；當(dāng)用戶下單后，訂單傳給智能配送系統(tǒng)，那么訂單誰來送、該怎么送、線路怎么規(guī)劃，以及應(yīng)該給騎手多少補貼，都要靠智能決策算法來完成。訂單交給騎手后，我們會建議騎手合理的配送順序，并研發(fā)騎手智能助手，在每個配送環(huán)節(jié)給騎手提供智能引導(dǎo)和安全提醒。

團隊在支撐配送業(yè)務(wù)快速迭代的同時，還在大規(guī)模實時優(yōu)化、深度強化學(xué)習(xí)、配送仿真平臺等技術(shù)方向上持續(xù)投入，研究探索驅(qū)動和引領(lǐng)配送業(yè)務(wù)發(fā)展的前沿智能技術(shù)，以達成極致的用戶體驗和配送效率。

3.  人工智能技術(shù)在美團配送系統(tǒng)中有哪些發(fā)揮的空間？

在美團配送業(yè)務(wù)場景下，人工智能技術(shù)有非常廣闊的研究和應(yīng)用空間。

首先從業(yè)務(wù)價值上看，美團外賣每天超過2000萬訂單，超過60萬名騎手在線下進行配送，我們通過人工智能技術(shù)來優(yōu)化提升騎手們的工作效率，即便只優(yōu)化1%的效果，經(jīng)過60萬名騎手的放大，也會產(chǎn)生巨大的經(jīng)濟效益和社會價值；

其次從研發(fā)領(lǐng)域上看，包括精準(zhǔn)感知、預(yù)測分析、智能決策和高效執(zhí)行。即時配送業(yè)務(wù)中的需求預(yù)測、訂單分配、路徑規(guī)劃、動態(tài)定價、ETA、網(wǎng)絡(luò)和運力規(guī)劃等業(yè)務(wù)問題，在學(xué)術(shù)上屬于大規(guī)模隨機優(yōu)化、海量數(shù)據(jù)機器學(xué)習(xí)領(lǐng)域，是對配送效率、成本/體驗有直接影響的預(yù)測或決策問題，關(guān)系到平臺的核心競爭力，而解決上述問題，需要用到大量關(guān)于系統(tǒng)建模、強化學(xué)習(xí)、運籌優(yōu)化、機器學(xué)習(xí)等人工智能領(lǐng)域的前沿技術(shù)。

4.  目前用戶的配送體驗如何？

我們主要綜合考慮配送時長、準(zhǔn)時率和置信度來衡量用戶的配送體驗。

配送時長反映了用戶下單到送達的等待時間，目前美團配送訂單的平均配送時長在30分鐘左右。

準(zhǔn)時率反映了我們給用戶承諾時間的可靠程度，目前美團配送的準(zhǔn)時率在98%左右。但是單純看準(zhǔn)時率這一指標(biāo)，并不是越高用戶體驗就一定越好，試想，如果每個用戶的 ETA 為2個小時，這樣準(zhǔn)時率可能是100%，但用戶體驗也不會好。所以，準(zhǔn)時率需要結(jié)合『置信度』的配對指標(biāo)來共同說明給用戶承諾時長設(shè)定的合理性，置信度反映了我們給用戶承諾的送達時間和實際送達時間的偏差程度。隨著系統(tǒng)算法策略的持續(xù)精細化，以及線下配送業(yè)務(wù)管理水平的持續(xù)提升，我們?yōu)橛脩舫兄Z的送達時間置信度也逐步提升。

5.  訂單分配、路徑規(guī)劃、動態(tài)定價目前的難點分別在哪里？

訂單分配和路徑規(guī)劃都屬于典型的運籌優(yōu)化問題，對應(yīng)的數(shù)學(xué)模型是 VRP。在即時配送場景下，解決上述問題的難點有兩方面：

1）大規(guī)模實時優(yōu)化。問題規(guī)模很大，是 NP-Hard 問題，同時又要求在很短的時間內(nèi)提供最優(yōu)方案，例如一次訂單分配過程涉及600個騎手200個訂單，其調(diào)度算法基本上也要在5秒鐘以內(nèi)，這對算法的設(shè)計提出了很大挑戰(zhàn)；

2）強隨機性。商家的出餐時間、用戶的交付時間（騎手到用戶樓下到交付完離開用戶的時間）、騎手行駛速度、交通狀況等都很很大的不確定性，這類場景的優(yōu)化存在很大難度。

動態(tài)定價的難點在于它是一個多領(lǐng)域交叉的問題，涉及到成本估計、價格彈性分析、運力和訂單預(yù)測、價值機制設(shè)計等方面，需要用到機器學(xué)習(xí)、博弈論、勞動經(jīng)濟學(xué)、運籌優(yōu)化等多個學(xué)科的理論和方法來解決。

6.  美團使用供應(yīng)鏈物流方面的商用軟件嗎？還是純自己研發(fā)的？

目前美團配送業(yè)務(wù)使用的軟件系統(tǒng)完全是自主研發(fā)，原因一方面是即時配送的業(yè)務(wù)復(fù)雜度很高，已有的商業(yè)軟件都無法完全滿足需求；另外就是即時配送行業(yè)的競爭態(tài)勢、業(yè)務(wù)形態(tài)變化都很快，采用自建技術(shù)開發(fā)團隊能夠比較好地支持業(yè)務(wù)策略的快速迭代。

如果把范圍放窄一點，單純針對算法場景，我們會使用一些開源的算法包來快速支持業(yè)務(wù)需求，這也是業(yè)內(nèi)的通常做法。但是對一些對業(yè)務(wù)有重要影響、已有開源算法包無法很好支持的算法場景，比如路徑規(guī)劃、訂單分配算法等等，我們會自主開發(fā)。

7.  商家和騎手的個性化數(shù)據(jù)是怎樣的？如何應(yīng)用到訂單分配中去？

實現(xiàn)高效的智能配送，需要能夠準(zhǔn)確地掌握每個商家、騎手以及用戶樓宇的個性化數(shù)據(jù)。目前，我們采用數(shù)據(jù)挖掘、機器學(xué)習(xí)、多傳感器融合等技術(shù)，對每日2400萬單的海量訂單及軌跡數(shù)據(jù)進行挖掘，得到有價值的信息。比如，用戶在這個商家下了單，什么時候可以出餐？這個跟時段（高峰、周末、閑時）以及菜品，購買數(shù)量，前序訂單情況等都有關(guān)系。另外，有的商家是在四層、五層的位置甚至更高，我們會獲取外賣小哥從停下電動車走到電梯處的時間、乘電梯的時間。針對騎手我們同樣需要挖掘大量的個性化數(shù)據(jù)，典型的有騎手的交通工具，所熟悉的商圈、小區(qū)，騎手的歷史配送準(zhǔn)時率、用戶評價、配送習(xí)慣，等等。

我們利用個性化數(shù)據(jù)的目標(biāo)是希望建立更準(zhǔn)確的優(yōu)化模型并求解，從而提升騎手的配送效率和用戶滿意度。比如騎手熟悉這塊區(qū)域，那么在智能派單中可能會多給你派這塊區(qū)域的訂單，以提升配送效率。如果一個商家的取貨時間特別長，那么就盡可能讓騎手一次性地從商家取盡量多的訂單，從而減少騎手的勞動付出。這些因素都要合理地反映在優(yōu)化模型中來。

8.  騎手和訂單之間的匹配以及接單后路徑規(guī)劃應(yīng)該是特別復(fù)雜的優(yōu)化問題，你們是怎么做到對如此復(fù)雜的問題進行求解的？ 

首先，我們面臨的這個問題屬于動態(tài)優(yōu)化問題，DVRP，要求短時間內(nèi)快速給出決策?？紤]到商家分散在區(qū)域的各個地方，即時配送過程無法采用分批次的方式，而是騎手在配送訂單的同時，訂單也在源源不斷的產(chǎn)生，我們需要把訂單動態(tài)地追加到騎手身上。這種模式要求算法采集數(shù)據(jù)的時刻，到算法求解完成將指令下達給騎手的時刻間隔不能特別長，如果比較長，就會產(chǎn)生信息不一致現(xiàn)象，必然惡化算法的應(yīng)用效果。我們一般是要求算法要在3-5秒鐘之內(nèi)完成所有計算。

其次，訂單分配問題可以簡單分解為兩個嵌套的子問題：外層是分配問題，內(nèi)層是騎手的線路規(guī)劃問題。評估一個分配方案的好壞是基于騎手路線規(guī)劃算法，評估完之后再去優(yōu)化新的訂單分配方案。這是一種標(biāo)準(zhǔn)的解法。在實際可能一次訂單分配針對50個訂單，200個騎手，那需要調(diào)數(shù)萬次的路徑規(guī)劃，所以騎手的線路規(guī)劃的時間要在幾毫秒之內(nèi)，不然幾萬次求解沒法在四五秒之內(nèi)完成。在這個方面，我們也迭代了很多個版本的算法，綜合運用了運籌優(yōu)化、圖論和機器學(xué)習(xí)的實用算法，同時后臺基于自研的分布式計算平臺，算法的時間性能有了很大改進。

最后，算法每次求解的問題是基于前一個問題的，因為前面分配的訂單會影響騎手的后續(xù)狀態(tài)，是一個動態(tài)的、帶時間窗口的VRP。整個優(yōu)化問題的目標(biāo)是一天之內(nèi)的指標(biāo)，而不是針對某一小段時刻。所以除了關(guān)注單次求解盡量達到最優(yōu)，還需要關(guān)注整個時間窗口維度上的最優(yōu)。

9.  騎手配送過程中的一些突發(fā)事件，是如何解決的？

配送過程中的突發(fā)情況有很多，例如騎手的車壞了、商家沒有按時出餐、用戶沒有接電話等等。對于這類突發(fā)事件，我們的解決原則是：算法處理一部分、規(guī)范化流程處理一部分、人工再處理剩下的，共同配合起來解決突發(fā)事件。

比如騎手到商家后，商家沒有按時出餐，騎手可以先配送其他訂單，這時算法會自動識別騎手身上訂單的超時風(fēng)險，并把訂單改派給更合理的騎手。如果發(fā)生了用戶沒有接電話的情況，騎手會按照流程上報異常情況，系統(tǒng)首先校驗是否屬實，確認后按照流程更改相應(yīng)考核，直至后續(xù)再次聯(lián)系上用戶進行配送。

10. 招聘的話你們希望招到什么樣的人才？

我們招聘算法工程師，主要從以下維度進行評估：

(1) 具備扎實的算法研發(fā)素養(yǎng)。掌握數(shù)據(jù)處理、機器學(xué)習(xí)、概率論、運籌學(xué)相關(guān)的基本理論和方法，并掌握人工智能算法從需求調(diào)研到研發(fā)、上線和效果評估的全流程。

(2) 清晰的邏輯思維和解決問題的能力。面對新的場景，能不能活學(xué)活用既有方法和策略解決問題，并根據(jù)數(shù)據(jù)的『蛛絲馬跡』來進行推理和判斷，對解決問題效果的好壞至關(guān)重要。

(3) 具有強烈的自我驅(qū)動力和學(xué)習(xí)成長意愿，能主動發(fā)現(xiàn)并解決問題，追求技術(shù)的極致，精益求精。

目前美團即時配送業(yè)務(wù)發(fā)展迅速，新的 AI 場景和技術(shù)難題不斷涌現(xiàn)，包括業(yè)務(wù)指標(biāo)預(yù)測、派單與路徑優(yōu)化、動態(tài)定價、騎手軌跡挖掘、網(wǎng)絡(luò)與運力規(guī)劃等等。團隊中仍有若干高級算法工程師/技術(shù)專家職位空缺，期待你的加入！

11. 請談一下運籌學(xué)在中國的現(xiàn)狀，對未來發(fā)展的展望。

首先，這些年來隨著移動互聯(lián)網(wǎng)的深入應(yīng)用發(fā)展，中國的制造業(yè)、服務(wù)業(yè)在數(shù)字化、信息化方面的重視和投入程度都有顯著提升，過程數(shù)據(jù)、業(yè)務(wù)數(shù)據(jù)的采集越來越完善，智能決策的數(shù)據(jù)基礎(chǔ)逐步具備。

其次，從外部環(huán)境看，粗放式發(fā)展的經(jīng)營模式目前在多數(shù)行業(yè)和企業(yè)都難以為繼，中國經(jīng)濟的『下半場』已經(jīng)開始。在這一時期，企業(yè)之間的競爭模式將逐步轉(zhuǎn)變?yōu)槌杀竞托实谋绕?，這就需要企業(yè)更多地從內(nèi)部挖潛增效，實現(xiàn)精細化高效運營,而運籌學(xué)是實現(xiàn)基于數(shù)據(jù)的精細化運營和高效決策的主要技術(shù)手段。

因此，一方面數(shù)據(jù)基礎(chǔ)已具備，另一方面應(yīng)用需求逐步趨于旺盛，所以運籌學(xué)在中國將迎來應(yīng)用的春天。過去幾年，美團、滴滴、京東、順豐、菜鳥等都在大量使用運籌學(xué)相關(guān)的理論和算法服務(wù)于自身的業(yè)務(wù)場景，就是很好的例子。

在美團配送業(yè)務(wù)上，已經(jīng)使用和正在使用運籌優(yōu)化技術(shù)的場景就包括路徑優(yōu)化、訂單分配、網(wǎng)絡(luò)規(guī)劃、定價、排班、騎手運營等。美團配送已積累了與即時配送相關(guān)的海量數(shù)據(jù)，包括每一棟樓宇、每個外賣商家的大量畫像數(shù)據(jù)以及路網(wǎng)、騎行路徑等信息，同時研發(fā)了智能配送系統(tǒng)，包含智能調(diào)度系統(tǒng)、定價與運營系統(tǒng)、網(wǎng)絡(luò)與運力規(guī)劃系統(tǒng)等，上述數(shù)據(jù)與系統(tǒng)是即時配送效率提升的能力基礎(chǔ)。美團配送會繼續(xù)努力實現(xiàn)數(shù)據(jù)的精準(zhǔn)化和系統(tǒng)的智能化，并和同行一起，推動即時配送領(lǐng)域的科學(xué)管理、決策和運營水平。