本文訂單分配問題為例，闡述該問題的本質特點、模式變遷、方案架構和關鍵要點，為大家在解決業務優化問題上提供一個案例參考。

最近兩年，外賣的市場規模持續以超常速度發展。近期美團外賣訂單量峰值達到1600萬，是全球規模最大的外賣平臺。目前各外賣平臺正在優質供給、配送體驗、軟件體驗等各維度展開全方位的競爭，其中，配送時效、準時率作為履約環節的重要指標，是外賣平臺的核心競爭力之一。

要提升用戶的配送時效和準時率，最直接的方法是配備較多的配送員，擴大運力規模，然而這也意味著配送成本會很高。所以，外賣平臺一方面要追求好的配送體驗，另一方面又被配送的人力成本掣肘。怎么在配送體驗和配送成本之間取得最佳的平衡，是即時配送平臺生存的根基和關鍵所在。

隨著互聯網時代的上半場結束，用戶增長紅利驅動的粗放式發展模式已經難以適應下半場的角逐。如何通過技術手段，讓美團外賣平臺超過40萬的騎手高效工作，在用戶滿意度持續提升的同時，降低配送成本、提高騎手滿意度、驅動配送系統的自動化和智能化，是美團配送技術團隊始終致力于解決的難題。

在過去一年多時間里，美團配送團隊在機器學習、運籌優化、仿真技術等方面，持續發力，深入研究，并針對即時配送場景特點將上述技術綜合運用，推出了用于即時配送的“超級大腦”——O2O即時配送智能調度系統。

系統首先通過優化設定配送費以及預計送達時間來調整訂單結構；

在接收訂單之后，考慮騎手位置、在途訂單情況、騎手能力、商家出餐、交付難度、天氣、地理路況、未來單量等因素，在正確的時間將訂單分配給最合適的騎手，并在騎手執行過程中隨時預判訂單超時情況并動態觸發改派操作，實現訂單和騎手的動態最優匹配；同時，系統派單后，為騎手提示該商家的預計出餐時間和合理的配送線路，并通過語音方式和騎手實現高效交互；

在騎手送完訂單后，系統根據訂單需求預測和運力分布情況，告知騎手不同商圈的運力需求情況，實現閑時的運力調度。

通過上述技術和模式的引入，持續改善了用戶體驗和配送成本：

訂單的平均配送時長從2015年的41分鐘，下降到32分鐘，進一步縮短至28分鐘，另一方面，在騎手薪資穩步提升的前提下，單均配送成本也有了20%以上的縮減。

本文將以外賣場景下上述調度流程中的關鍵問題之一——訂單分配問題為例，闡述該問題的本質特點、模式變遷、方案架構和關鍵要點，為大家在解決業務優化問題上提供一個案例參考。

一、外賣訂單分配問題描述

外賣訂單的分配問題一般可建模為帶有若干復雜約束的DVRP（Dynamic Vehicle Routing Problem）問題。

這類問題一般可表述為：

有一定數量的騎手，每名騎手身上有若干訂單正在配送過程中，在過去一段時間（如1分鐘）內產生了一批新訂單，已知騎手的行駛速度、任意兩點間的行駛距離、每個訂單的出餐時間和交付時間（騎手到達用戶所在地之后將訂單交付至用戶所需的時間），那么如何將這批新訂單在正確的時間分配至正確的騎手，使得用戶體驗得到保證的同時，騎手的配送效率最高。

下圖是外賣配送場景下一個配送區域上眾多騎手的分布示意圖。

二、即時配送訂單分配模式的演進

在O2O領域，訂單和服務提供方的匹配問題是一個非常關鍵的問題。

在外賣行業發展初期，主要依賴騎手搶單模式和人工派單模式。

搶單模式的優勢是開發難度低，服務提供者（如司機、騎手）的自由度較高，可以按照自身的需要進行搶單，但其缺點也很明顯：騎手/司機只考慮自身的場景需求，做出一個局部近優的選擇。

然而由于每個騎手掌握的信息有限又只從自身利益出發來決策，導致配送整體效率低下，從用戶端來看，還存在大量訂單無人搶或者搶了之后造成服務質量無法保證（因為部分騎手無法準確預判自己的配送服務能力）的場景，用戶體驗比較差。

人工派單的方式，從訂單分配的結果上來看，一般優于搶單模式。

在訂單量、騎手數相對比較少的情形下，有經驗的調度員可以根據訂單的屬性特點、騎手的能力、騎手已接單情況、環境因素等，在騎手中逐個比對，根據若干經驗規則挑選一個比較合適的騎手來配送。一般而言，人工調度一個訂單往往至少需要半分鐘左右的時間才能完成。

然而，隨著外賣訂單規模的日益增長，在熱門商圈（方圓3公里左右）的高峰時段，1分鐘的時間內可能會有50單以上，在這種情況下，要求人工調度員每1-2秒鐘做出一次合理的調度決策，顯然是不可能的。

另一方面，由于即時配送過程的復雜性，要做出合理的匹配決策，要求調度員對配送范圍內各商家的出餐速度、各用戶地址的配送難度（例如有的寫字樓午高峰要等很長時間的電梯）、各騎手自身的配送工具/熟悉的商家和用戶范圍/工作習慣等等要有非常深入的了解，在此基礎上具備統籌優化能力，考慮未來進單量、減少空駛等因素，做出全局近優的選擇，這對人工調度員而言，又是一項極其艱巨的任務。

另外，美團外賣有數千個配送區域，如果采用人工調度方式則每個區域均需要配置調度員，會消耗非常高的人力成本。

該問題雖然復雜，但仍具備一定的規律性。尤其是移動互聯網高度發達的今天，我們擁有騎手配送訂單過程中的各類大量歷史數據（e.g. 騎手的位置、訂單狀態、天氣數據、LBS數據），利用這些數據輔以相關數學工具使得實現計算機系統的自動派單成為可能。

系統派單具備如下優勢：

• 系統可以在全局層面上掌握和配送有關的騎手、商家、用戶、訂單等各類信息，在此基礎上，可以做出全局較優的方案，從而提升配送效率和配送體驗，減少配送成本；
• 顯著減輕人工調度員的工作，從而降低人工成本，人工調度員只需要在一些意外場景（如配送員出現緊急情況無法繼續配送等）發生的時候進行干預即可。

所以，隨著數據采集的不斷完善和人工智能技術的不斷成熟，通過人工智能的方法來進行訂單的指派，具有巨大的收益，成為各個配送平臺研究的熱點之一。

三、訂單智能分配系統的基本架構

美團外賣每天產生巨量的訂單配送日志、行駛軌跡數據。通過對配送大數據進行分析、挖掘，會得到每個用戶、樓宇、商家、騎手、地理區域的個性化信息，以及有關各地理區塊騎行路徑的有效數據，那么訂單智能分配系統的目標就是基于大數據平臺，根據訂單的配送需求、地理環境以及每名騎手的個性化特點，實現訂單與騎手的高效動態最優匹配，從而為每個用戶和商家提供最佳的配送服務，并降低配送成本。

即時配送大數據平臺實現對騎手軌跡數據、配送業務數據、特征數據、指標數據的全面管理和監控，并通過模型平臺、特征平臺支持相關算法策略的快速迭代和優化。

機器學習模塊負責從數據中尋求規律和知識，例如對商家的出餐時間、到用戶所在樓宇上下樓的時間、未來的訂單、騎行速度、紅綠燈耗時、騎行導航路徑等因素進行準確預估，為調度決策提供準確的基礎信息；而運籌優化模塊則在即時配送大數據平臺以及機器學習的預測數據基礎上，采用最優化理論、強化學習等優化策略進行計算，做出全局最優的分配決策，并和騎手高效互動，處理執行過程中的問題，實現動態最優化。

1. 問題分析和建模：高效求解問題的第一步

學術研究領域有很多經典的優化問題（如旅行商問題TSP、裝箱問題BP、車輛路徑問題VRP等），它們的決策變量、優化目標和約束條件往往非常明確、簡單。這在學術研究中是很必要的，因為它簡化了問題，讓研究者把精力放在如何設計高效算法上。

然而，由于實際工業場景的復雜性，絕大部分實際場景的決策優化問題很難描述的如此簡單，此時，如果不仔細分析實際業務過程特點而錯誤地建立了和實際場景不符的模型，自然會造成我們獲得的所謂“最優解”應用于實際后也會“水土不服”，最后被大量抱怨甚至拋棄。

所以我們說，準確建模是實際決策優化項目的第一步，也是最關鍵的一步。

準確建模，包括兩個方面的問題：

1. 我們正確理解了實際業務場景的優化問題，并且通過某種形式化語言進行了準確描述；
2. 我們建立的模型中，涉及的各類參數和數據，能夠準確得獲取。

在上述兩個前提下，采用相應的高效優化算法求解模型所得到的最優解，就是符合實際場景需求的最優決策方案。第一個問題，一般是通過業務調研、分析并結合建模工具來得到；而解決第二個問題，則更多地需要依賴數據分析、機器學習、數據挖掘技術結合領域知識，對模型進行精確的量化表達。

一個決策優化問題的數學模型，一般包括三個要素：

1. 決策變量
2. 優化目標
3. 約束條件

其中，決策變量說明了我們希望算法來幫助我們做哪些決策；優化目標則是指我們通過調整決策變量，使得哪些指標得到優化；而約束條件則是在優化決策的過程中所考慮的各類限制性因素。

為了說明即時配送場景下的訂單分配問題，我們先引入若干符號定義：

在即時配送調度場景下，決策變量包括各個訂單需要分配的騎手，以及騎手的建議行駛路線。

即時配送訂單分配問題的優化目標一般包括希望用戶的單均配送時長盡量短、騎手付出的勞動盡量少、超時率盡量低，等等。一般可表達為：

針對實際場景下的配送訂單分配問題，設置哪些指標作為目標函數是一個較為復雜的問題。

原因在于兩個方面：

1. 該優化問題是多目標的，且各個目標在不同時段、不同環境下會有差別。舉個例子，經驗豐富的調度員希望在負載較低的空閑時段，將訂單派給那些不熟悉區域地形的騎手，以鍛煉騎手能力；在天氣惡劣的情況下，希望能夠容忍一定的超時率更多地派順路單，以提高訂單消化速度等。這些考量有其合理性，需要在優化目標中予以體現。
2. 缺乏有助于量化優化目標的數據。如果帶標簽數據足夠多，同時假設調度員的能力足夠好，那么可以通過數據挖掘的手段獲取優化目標的量化表達。不幸的是，這兩個前提都不成立。我們針對該難題，首先通過深入調研明確業務痛點和目標，在此基礎上，采用機理和數據相結合的辦法，由人工設定目標函數的結構，通過仿真系統（下文介紹）和實際數據去設定目標函數的參數，來確定最終采用的目標函數形態。

即時配送調度問題的約束條件至少涵蓋如下幾種類型：

除了以上約束外，有時還需要考慮部分訂單只能由具備某些特點的騎手來配送（例如火鍋訂單只能交給攜帶專門裝備的騎手等）、載具的容量限制等。

以上只是針對給定的一批訂單進行匹配決策的優化問題在建模時所需考慮的部分因素。

事實上，在外賣配送場景中，我們希望的不是單次決策的最優，而是策略在一段時間應用后的累積收益最大。

換句話說，我們不追求某一個訂單的指派是最優的，而是希望一天下來，所有的訂單指派結果整體上是全局最優的。

這進一步加大了問題建模的難度，原因在于算法在做訂單指派決策的時候，未來的訂單信息是不確定的，如下圖所示，在t時刻進行決策的時候，既需要考慮已確定的訂單，還需要考慮未來的尚未確定的訂單。

運籌優化領域中的馬爾可夫決策過程描述的就是這樣的一類在不確定、信息不完備環境下的序貫決策優化問題。

2. 問題建模中的機器學習

過去，在信息化水平較低的環境下，很多工業運籌優化類的項目不成功，重要原因之一就是缺少足夠完備的數據采集基礎工具，大量數據由人工根據經驗設定，其準確性難以保證，且難以隨著環境變化而自適應調整，從而造成模型的優化結果漸漸變得不符合實際。

機器學習領域有個諺語“Garbage in，garbage out”， 說明了精準的基礎數據對于人工智能類項目的重要性。

即時配送訂單分配場景下的數據包括兩類：

1. 直接通過業務系統采集可獲取的數據，例如訂單數據、騎手負載數據、騎手狀態數據等。
2. 無法直接采集得到，需要預測或統計才能獲取的數據，如商戶出餐時間、用戶駐留時間（騎手到達用戶處將訂單交付給用戶的時間）、騎手配送能力等。

第一類數據的獲取一般由業務系統、騎手端App直接給出，其精度通過提升工程質量或操作規范可有效保證；而第二類數據的獲取是即時配送調度的關鍵難點之一。

在訂單的配送過程中，騎手在商家、用戶處的取餐和交付時間會占到整個訂單配送時長的一半以上。準確估計出餐和交付時間，可以減少騎手的額外等待，也能避免“餐等人”的現象。

商家出餐時間的長短，跟品類、時段、天氣等因素都有關，而交付時間更為復雜，用戶在幾樓，是否處于午高峰時段，有沒有電梯等等，都會影響騎手（到了用戶所在地之后）交付訂單給用戶的時間。對這兩類數據，無法單純通過機理來進行預測，因為相關數據無法采集到（如商家今天有幾個廚師值班、用戶寫字樓的電梯是否開放，等等）。

為解決這些問題，我們利用機器學習工具，利用歷史的騎手到店、等餐、取餐的數據，并充分考慮天氣等外部因素的影響，建立了全面反映出餐能力的預測模型，并通過實時維度的特征進行修正，得到準確的出餐/交付時間估計。

進一步，我們建立了調度模型的自學習機制，借鑒多變量控制理論的思想，不斷根據預估偏差調整預估模型中的相關參數。通過以上工作，我們通過調度模型來預估騎手的配送行為（取餐時間和送達時間），平均偏差小于4分鐘，10分鐘置信度達到90%以上，有效地提升了派單效果和用戶滿意度。

3. 訂單——騎手的匹配優化

如果說上述建模過程的目標是構建和實際業務吻合的解空間，優化算法的作用則是在我們構建的解空間里找到最優的策略。配送調度問題屬于典型的NP-Hard類離散系統優化問題，解空間巨大。

以一段時間內產生50個訂單，一個區域有200騎手，每個騎手身上有5個訂單為例，那么對應的調度問題解空間規模將達到pow(200,50)*10（部分為不可行解），這是一個天文數字！

所以，如何設計好的優化算法，從龐大的解空間中搜索得到一個滿意解（由于問題的 NP-Hard特性，得到最優解幾乎是不可能的），是一個很大的挑戰。即時配送對于優化算法的另一個要求是高實時性，算法只允許運行2~3秒鐘的時間必須給出最終決策，這和傳統物流場景的優化完全不同。

針對此難題，我們采用了兩個關鍵思路。一是問題特征分析。運籌優化領域有個說法叫“No Free Lunch Theory”，沒有免費的午餐，含義是說如果沒有對問題的抽象分析并在算法中加以利用，那么沒有算法會比一個隨機算法好。

換句話說，就是我們必須對問題特點和結構進行深入分析，才能設計出性能優越的算法。

在運籌優化領域中的各類基礎性算法也是這樣的更多思路，如單純形、梯度下降、遺傳算法、模擬退火、動態規劃等，它們的本質其實是假定了問題具備某些特征（如動態規劃的貝爾曼方程假設，遺傳算法的Building Blocks假設等），并利用這些假設進行算法設計。

那么，針對配送調度的場景，這個問題可以被分解為兩個層次：騎手路徑優化和訂單分配方案的優化。

騎手路徑優化問題要解決的問題是：在新訂單分配至騎手后，確定騎手的最佳配送線路；而訂單分配優化問題要解決的問題是：把一批訂單分配至相應的騎手，使得我們關注的指標（如配送時長、準時率、騎手的行駛距離等）達到最優。

這兩個問題的關系是：通過訂單分配優化算法進行初始的訂單分配，然后通過騎手路徑優化算法獲取各騎手的最佳行駛路線，進而，訂單分配優化算法根據騎手路徑優化結果調整分配方案。

這兩個層次不斷反復迭代，最終獲得比較滿意的解。

第二個思路是跨學科結合。

訂單分配問題在業內有兩類方法，第一類方法是把訂單分配問題轉換成圖論中的二分圖匹配問題來解決。

但是由于標準的二分圖匹配問題中，一個人只能被分配一項任務，所以常用的一個方法是先對訂單進行打包，將可以由一個人完成的多個訂單組成一個任務，再使用二分圖匹配算法（匈牙利算法、KM 算法）來解決。這種做法是一個不錯的近似方案，優點是實現簡單計算速度快，但它的缺點是會損失一部分滿意解。

第二類方法是直接采用個性化的算法進行訂單分配方案的優化，優點是不損失獲得滿意解的可能性，但實際做起來難度較大。

我們結合領域知識、優化算法、機器學習策略以及相關圖論算法，基于分解協調思想，設計了騎手路徑優化算法和訂單分配優化算法。進一步，我們利用強化學習的思想，引入了離線學習和在線優化相結合的機制，離線學習得到策略模型，在線通過策略迭代，不斷尋求更優解。通過不斷地改進算法，在耗時下降的同時，算法的優化效果提升50%以上。

我們在大量的實際數據集上進行評估驗證，99%以上的情況下，騎手路徑優化算法能夠在30ms內給出最優解。

為了有效降低算法運行時間，我們對優化算法進行并行化，并利用并行計算集群進行快速處理。

一個區域的調度計算會在數百臺計算機上同步執行，在2~3秒內返回滿意結果，每天的路徑規劃次數超過50億次。

4. 應對強隨機性

即時配送過程的一個突出特點是線下的突發因素多、影響大，例如商家出餐異常慢、聯系不上用戶、車壞了、臨時交通管制等等。

這些突發事件造成的一個惡劣結果是：雖然在指派訂單的時刻，所指派的騎手是合理的，然而過了一段時間之后，由于騎手、訂單等狀態發生了變化，會變得不夠合理。訂單交給不合適的騎手來完成，會造成訂單超時，以及騎手需要額外的等待時間來完成訂單，影響了配送效率和用戶體驗的提升。

在出現上述不確定因素造成派單方案變得不合理的情況時，現有方法主要通過人工來完成，即：配送站長/調度員在配送信息系統里，查看各個騎手的位置、手中訂單的狀態及商戶/用戶的位置/期望送達時間等等信息，同時接聽騎手的電話改派請求，在此基礎上，分析哪些訂單應該改派，以及應該改派給哪位騎手，并執行操作。

我們針對即時配送的強不確定性特點，提出了兩點創新：

一是延遲調度策略，即在某些場景訂單可以不被指派出去，在不影響訂單超時的情況下，延遲做出決策；

二是系統自動改派策略，即訂單即便已經派給了騎手，后臺的智能算法仍然會實時評估各個騎手的位置、訂單情況，并幫助騎手進行分析，判斷是否存在超時風險。如果存在，則系統會評估是否有更優的騎手來配送。

延遲調度的好處一方面是在動態多變的不確定環境下，尋求最佳的訂單指派時機，以提高效率；另一方面是在訂單高峰時段存在大量堆積時，減輕騎手的配送壓力。有了這兩項策略，訂單的調度過程更加立體、全面，覆蓋了訂單履行過程全生命周期中的主要優化環節，實現訂單和騎手的動態最優化匹配。

5. 仿真系統

工業系統非?？粗乇O控和評估，“No measurement, No improvement”。在工業優化場景中，如何準確評估算法的好壞，其重要性不亞于設計一個好的算法。

然而，由于多個訂單在線下可能會由同一名騎手來配送，訂單與訂單之間存在耦合關系，導致無法做訂單維度的A/B測試。而區域維度指標受天氣、訂單結構、騎手水平等外在隨機因素影響波動比較大，算法效果容易被隨機因素湮沒從而無法準確評估。

為此，我們針對即時配送場景，建立了相應的仿真模型，開發了配送仿真系統。系統能夠模擬真實的配送過程和線上調度邏輯，并給出按照某種配送策略下的最終結果。該模擬過程和線下的實際導航、地理數據完全一致，系統同時能夠根據實際配送數據進行模型自學習，不斷提升仿真精度。

一個高精度的配送仿真系統，除了能夠對配送調度算法進行準確評估和優化，從而實現高效的策略準入控制外，另一個巨大的價值在于能夠對配送相關的上下游策略進行輔助優化，包括配送范圍優化、訂單結構優化、運力配置優化、配送成本評估等等，其應用的想象空間非常大。

四、結語

美團配送智能調度系統在應用之后，取得了非常不錯的應用效果。下圖說明了在訂單結構比較類似的兩個白領區域上的A/B測試結果。

中關村配送站在5月6日切換了派單模式和相應的算法，大望路配送站的調度策略維持不變。

可以看出，在切換后，中關村的平均配送時長有了2.9分鐘的下降，嚴重超時率下降了4.7個百分點（相比較對比區域）。

同時，在更廣泛的區域上進行了測試，結果表明，在體驗指標不變的前提下，新策略能夠降低19%的運力消耗。

換言之，原來5個人干的活，現在4個人就能干好，所以說，智能調度在降低成本上價值是很大的。

美團配送的目標之一是做本地化的物流配送平臺，那么，效率、體驗和成本將成為平臺追求的核心指標。人工智能技術在美團配送的成功應用有很多，通過大數據、人工智能手段打造一個高效、智能化、動態協同優化的本地智慧物流平臺，能顯著提高本地、同城范圍內的物流配送效率，持續提升配送體驗，降低配送成本。

作者：井華

來源：美團點評技術團隊