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

嘉賓介紹

郝井華

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

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

美團外賣作為全球最大的外賣平臺，不但擁有最大規模的外賣訂單量和領先的市場份額，而且還建設了“美團配送”這個全球最大的即時配送網絡，以及行業領先的美團智能配送系統。如何讓配送網絡運行效率更高、用戶體驗更好是一項相當困難的挑戰。這其中存在大量的復雜機器學習和運籌優化問題，包括ETA、智能調度、網絡規劃、地圖優化、動態定價、情景感知、智能運營等多個領域。

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

2.  你們團隊每天的工作內容是怎樣的？

在工作內容上，團隊中的算法工程師會針對即時配送業務場景的特定運籌優化或機器學習問題開展數據分析、模型和算法設計、開發和上線、效果評估等工作，推動 AI在業務場景中發揮作用，輔助或替代人工工作，產生業務價值。

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

團隊在支撐配送業務快速迭代的同時，還在大規模實時優化、深度強化學習、配送仿真平臺等技術方向上持續投入，研究探索驅動和引領配送業務發展的前沿智能技術，以達成極致的用戶體驗和配送效率。

3.  人工智能技術在美團配送系統中有哪些發揮的空間？

在美團配送業務場景下，人工智能技術有非常廣闊的研究和應用空間。

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

其次從研發領域上看，包括精準感知、預測分析、智能決策和高效執行。即時配送業務中的需求預測、訂單分配、路徑規劃、動態定價、ETA、網絡和運力規劃等業務問題，在學術上屬于大規模隨機優化、海量數據機器學習領域，是對配送效率、成本/體驗有直接影響的預測或決策問題，關系到平臺的核心競爭力，而解決上述問題，需要用到大量關于系統建模、強化學習、運籌優化、機器學習等人工智能領域的前沿技術。

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

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

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

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

5.  訂單分配、路徑規劃、動態定價目前的難點分別在哪里？

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

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

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

動態定價的難點在于它是一個多領域交叉的問題，涉及到成本估計、價格彈性分析、運力和訂單預測、價值機制設計等方面，需要用到機器學習、博弈論、勞動經濟學、運籌優化等多個學科的理論和方法來解決。

6.  美團使用供應鏈物流方面的商用軟件嗎？還是純自己研發的？

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

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

7.  商家和騎手的個性化數據是怎樣的？如何應用到訂單分配中去？

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

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

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

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

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

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

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

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

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

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

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

(1) 具備扎實的算法研發素養。掌握數據處理、機器學習、概率論、運籌學相關的基本理論和方法，并掌握人工智能算法從需求調研到研發、上線和效果評估的全流程。

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

(3) 具有強烈的自我驅動力和學習成長意愿，能主動發現并解決問題，追求技術的極致，精益求精。

目前美團即時配送業務發展迅速，新的 AI 場景和技術難題不斷涌現，包括業務指標預測、派單與路徑優化、動態定價、騎手軌跡挖掘、網絡與運力規劃等等。團隊中仍有若干高級算法工程師/技術專家職位空缺，期待你的加入！

11. 請談一下運籌學在中國的現狀，對未來發展的展望。

首先，這些年來隨著移動互聯網的深入應用發展，中國的制造業、服務業在數字化、信息化方面的重視和投入程度都有顯著提升，過程數據、業務數據的采集越來越完善，智能決策的數據基礎逐步具備。

其次，從外部環境看，粗放式發展的經營模式目前在多數行業和企業都難以為繼，中國經濟的『下半場』已經開始。在這一時期，企業之間的競爭模式將逐步轉變為成本和效率的比拼，這就需要企業更多地從內部挖潛增效，實現精細化高效運營,而運籌學是實現基于數據的精細化運營和高效決策的主要技術手段。

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

在美團配送業務上，已經使用和正在使用運籌優化技術的場景就包括路徑優化、訂單分配、網絡規劃、定價、排班、騎手運營等。美團配送已積累了與即時配送相關的海量數據，包括每一棟樓宇、每個外賣商家的大量畫像數據以及路網、騎行路徑等信息，同時研發了智能配送系統，包含智能調度系統、定價與運營系統、網絡與運力規劃系統等，上述數據與系統是即時配送效率提升的能力基礎。美團配送會繼續努力實現數據的精準化和系統的智能化，并和同行一起，推動即時配送領域的科學管理、決策和運營水平。