作者：井華，本文由美團點評技術(shù)團隊微信公眾號授權(quán)轉(zhuǎn)發(fā)

編者按

美團點評日前完成最新一輪融資，估值達到300億美元。此輪融資后將會在人工智能、無人配送等前沿技術(shù)研發(fā)上加大投入。但美團并不是為技術(shù)而技術(shù)，事實上，人工智能技術(shù)已經(jīng)在支撐著美團眾多業(yè)務(wù)場景。

以日訂單量剛剛突破1600萬的外賣業(yè)務(wù)為例，智能調(diào)度系統(tǒng)就是整個平臺的“超級大腦”，發(fā)揮了至關(guān)重要的作用。我們將通過一系列的文章來為大家揭開這背后的技術(shù)秘密。今天是系列的第一篇，講解外賣調(diào)度中關(guān)鍵難點之一訂單分配。

序言

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

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

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

在過去一年多時間里，美團配送團隊在機器學(xué)習(xí)、運籌優(yōu)化、仿真技術(shù)等方面，持續(xù)發(fā)力，深入研究，并針對即時配送場景特點將上述技術(shù)綜合運用，推出了用于即時配送的“超級大腦”O(jiān)2O即時配送智能調(diào)度系統(tǒng)。

系統(tǒng)首先通過優(yōu)化設(shè)定配送費以及預(yù)計送達時間來調(diào)整訂單結(jié)構(gòu)；在接收訂單之后，考慮騎手位置、在途訂單情況、騎手能力、商家出餐、交付難度、天氣、地理路況、未來單量等因素，在正確的時間將訂單分配給最合適的騎手，并在騎手執(zhí)行過程中隨時預(yù)判訂單超時情況并動態(tài)觸發(fā)改派操作，實現(xiàn)訂單和騎手的動態(tài)最優(yōu)匹配。

同時，系統(tǒng)派單后，為騎手提示該商家的預(yù)計出餐時間和合理的配送線路，并通過語音方式和騎手實現(xiàn)高效交互；在騎手送完訂單后，系統(tǒng)根據(jù)訂單需求預(yù)測和運力分布情況，告知騎手不同商圈的運力需求情況，實現(xiàn)閑時的運力調(diào)度。

通過上述技術(shù)和模式的引入，持續(xù)改善了用戶體驗和配送成本：訂單的平均配送時長從2015年的41分鐘，下降到32分鐘，進一步縮短至28分鐘，另一方面，在騎手薪資穩(wěn)步提升的前提下，單均配送成本也有了20%以上的縮減。

本文將以外賣場景下上述調(diào)度流程中的關(guān)鍵問題之一訂單分配問題為例，闡述該問題的本質(zhì)特點、模式變遷、方案架構(gòu)和關(guān)鍵要點，為大家在解決業(yè)務(wù)優(yōu)化問題上提供一個案例參考。

外賣訂單分配問題描述

外賣訂單的分配問題一般可建模為帶有若干復(fù)雜約束的DVRP（Dynamic Vehicle Routing Problem）問題。這類問題一般可表述為：有一定數(shù)量的騎手，每名騎手身上有若干訂單正在配送過程中，在過去一段時間（如1分鐘）內(nèi)產(chǎn)生了一批新訂單，已知騎手的行駛速度、任意兩點間的行駛距離、每個訂單的出餐時間和交付時間（騎手到達用戶所在地之后將訂單交付至用戶所需的時間），那么如何將這批新訂單在正確的時間分配至正確的騎手，使得用戶體驗得到保證的同時，騎手的配送效率最高。

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

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

在O2O領(lǐng)域，訂單和服務(wù)提供方的匹配問題是一個非常關(guān)鍵的問題。在外賣行業(yè)發(fā)展初期主要依賴騎手搶單模式和人工派單模式。

搶單模式的優(yōu)勢是開發(fā)難度低，服務(wù)提供者（如司機、騎手）的自由度較高，可以按照自身的需要進行搶單，但其缺點也很明顯：騎手/司機只考慮自身的場景需求，做出一個局部近優(yōu)的選擇，然而由于每個騎手掌握的信息有限又只從自身利益出發(fā)來決策，導(dǎo)致配送整體效率低下，從用戶端來看，還存在大量訂單無人搶或者搶了之后造成服務(wù)質(zhì)量無法保證（因為部分騎手無法準(zhǔn)確預(yù)判自己的配送服務(wù)能力）的場景，用戶體驗比較差。

人工派單的方式，從訂單分配的結(jié)果上來看，一般優(yōu)于搶單模式。在訂單量、騎手數(shù)相對比較少的情形下，有經(jīng)驗的調(diào)度員可以根據(jù)訂單的屬性特點、騎手的能力、騎手已接單情況、環(huán)境因素等，在騎手中逐個比對，根據(jù)若干經(jīng)驗規(guī)則挑選一個比較合適的騎手來配送。一般而言，人工調(diào)度一個訂單往往至少需要半分鐘左右的時間才能完成。

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

另一方面，由于即時配送過程的復(fù)雜性，要做出合理的匹配決策，要求調(diào)度員對配送范圍內(nèi)各商家的出餐速度、各用戶地址的配送難度（例如有的寫字樓午高峰要等很長時間的電梯）、各騎手自身的配送工具/熟悉的商家和用戶范圍/工作習(xí)慣等等要有非常深入的了解，在此基礎(chǔ)上具備統(tǒng)籌優(yōu)化能力，考慮未來進單量、減少空駛等因素，做出全局近優(yōu)的選擇，這對人工調(diào)度員而言，又是一項極其艱巨的任務(wù)。另外，美團外賣有數(shù)千個配送區(qū)域，如果采用人工調(diào)度方式則每個區(qū)域均需要配置調(diào)度員，會消耗非常高的人力成本。

該問題雖然復(fù)雜，但仍具備一定的規(guī)律性。尤其是移動互聯(lián)網(wǎng)高度發(fā)達的今天，美團擁有騎手配送訂單過程中的各類大量歷史數(shù)據(jù)，e.g. 騎手的位置、訂單狀態(tài)、天氣數(shù)據(jù)、LBS數(shù)據(jù)，利用這些數(shù)據(jù)輔以相關(guān)數(shù)學(xué)工具使得實現(xiàn)計算機系統(tǒng)的自動派單成為可能。

系統(tǒng)派單具備如下優(yōu)勢：

• 系統(tǒng)可以在全局層面上掌握和配送有關(guān)的騎手、商家、用戶、訂單等各類信息，在此基礎(chǔ)上，可以做出全局較優(yōu)的方案，從而提升配送效率和配送體驗，減少配送成本；

• 顯著減輕人工調(diào)度員的工作，從而降低人工成本，人工調(diào)度員只需要在一些意外場景（如配送員出現(xiàn)緊急情況無法繼續(xù)配送等）發(fā)生的時候進行干預(yù)即可。

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

訂單智能分配系統(tǒng)的基本架構(gòu)

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

即時配送大數(shù)據(jù)平臺實現(xiàn)對騎手軌跡數(shù)據(jù)、配送業(yè)務(wù)數(shù)據(jù)、特征數(shù)據(jù)、指標(biāo)數(shù)據(jù)的全面管理和監(jiān)控，并通過模型平臺、特征平臺支持相關(guān)算法策略的快速迭代和優(yōu)化。

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

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

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

然而，由于實際工業(yè)場景的復(fù)雜性，絕大部分實際場景的決策優(yōu)化問題很難描述的如此簡單，此時，如果不仔細分析實際業(yè)務(wù)過程特點而錯誤地建立了和實際場景不符的模型，自然會造成我們獲得的所謂“最優(yōu)解”應(yīng)用于實際后也會“水土不服”，最后被大量抱怨甚至拋棄。所以說，準(zhǔn)確建模是實際決策優(yōu)化項目的第一步，也是最關(guān)鍵的一步。

準(zhǔn)確建模，包括兩個方面的問題：

• 我們正確理解了實際業(yè)務(wù)場景的優(yōu)化問題，并且通過某種形式化語言進行了準(zhǔn)確描述；

• 我們建立的模型中，涉及的各類參數(shù)和數(shù)據(jù)，能夠準(zhǔn)確得獲取。

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

一個決策優(yōu)化問題的數(shù)學(xué)模型，一般包括三個要素：

• 決策變量

• 優(yōu)化目標(biāo)

• 約束條件

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

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

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

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

針對實際場景下的配送訂單分配問題，設(shè)置哪些指標(biāo)作為目標(biāo)函數(shù)是一個較為復(fù)雜的問題。

原因在于兩個方面：

1）該優(yōu)化問題是多目標(biāo)的，且各個目標(biāo)在不同時段、不同環(huán)境下會有差別。舉個例子，經(jīng)驗豐富的調(diào)度員希望在負載較低的空閑時段，將訂單派給那些不熟悉區(qū)域地形的騎手，以鍛煉騎手能力；在天氣惡劣的情況下，希望能夠容忍一定的超時率更多地派順路單，以提高訂單消化速度等。這些考量有其合理性，需要在優(yōu)化目標(biāo)中予以體現(xiàn)。

2）缺乏有助于量化優(yōu)化目標(biāo)的數(shù)據(jù)。如果帶標(biāo)簽數(shù)據(jù)足夠多，同時假設(shè)調(diào)度員的能力足夠好，那么可以通過數(shù)據(jù)挖掘的手段獲取優(yōu)化目標(biāo)的量化表達。不幸的是，這兩個前提都不成立。美團針對該難題，首先通過深入調(diào)研明確業(yè)務(wù)痛點和目標(biāo)，在此基礎(chǔ)上，采用機理和數(shù)據(jù)相結(jié)合的辦法，由人工設(shè)定目標(biāo)函數(shù)的結(jié)構(gòu)，通過仿真系統(tǒng)（下文介紹）和實際數(shù)據(jù)去設(shè)定目標(biāo)函數(shù)的參數(shù)，來確定最終采用的目標(biāo)函數(shù)形態(tài)。

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

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

以上只是針對給定的一批訂單進行匹配決策的優(yōu)化問題在建模時所需考慮的部分因素。事實上，在外賣配送場景中，我們希望的不是單次決策的最優(yōu)，而是策略在一段時間應(yīng)用后的累積收益最大。

換句話說，不追求某一個訂單的指派是最優(yōu)的，而是希望一天下來，所有的訂單指派結(jié)果整體上是全局最優(yōu)的。這進一步加大了問題建模的難度，原因在于算法在做訂單指派決策的時候，未來的訂單信息是不確定的，如下圖所示，在t時刻進行決策的時候，既需要考慮已確定的訂單，還需要考慮未來的尚未確定的訂單。運籌優(yōu)化領(lǐng)域中的馬爾可夫決策過程描述的就是這樣的一類在不確定、信息不完備環(huán)境下的序貫決策優(yōu)化問題。

問題建模中的機器學(xué)習(xí)

過去，在信息化水平較低的環(huán)境下，很多工業(yè)運籌優(yōu)化類的項目不成功，重要原因之一就是缺少足夠完備的數(shù)據(jù)采集基礎(chǔ)工具，大量數(shù)據(jù)由人工根據(jù)經(jīng)驗設(shè)定，其準(zhǔn)確性難以保證，且難以隨著環(huán)境變化而自適應(yīng)調(diào)整，從而造成模型的優(yōu)化結(jié)果漸漸變得不符合實際。機器學(xué)習(xí)領(lǐng)域有個諺語“Garbage in，garbage out”， 說明了精準(zhǔn)的基礎(chǔ)數(shù)據(jù)對于人工智能類項目的重要性。

即時配送訂單分配場景下的數(shù)據(jù)包括兩類：

• 直接通過業(yè)務(wù)系統(tǒng)采集可獲取的數(shù)據(jù)，例如訂單數(shù)據(jù)、騎手負載數(shù)據(jù)、騎手狀態(tài)數(shù)據(jù)等。

• 無法直接采集得到，需要預(yù)測或統(tǒng)計才能獲取的數(shù)據(jù)，如商戶出餐時間、用戶駐留時間（騎手到達用戶處將訂單交付給用戶的時間）、騎手配送能力等。

第一類數(shù)據(jù)的獲取一般由業(yè)務(wù)系統(tǒng)、騎手端App直接給出，其精度通過提升工程質(zhì)量或操作規(guī)范可有效保證；而第二類數(shù)據(jù)的獲取是即時配送調(diào)度的關(guān)鍵難點之一。

在訂單的配送過程中，騎手在商家、用戶處的取餐和交付時間會占到整個訂單配送時長的一半以上。準(zhǔn)確估計出餐和交付時間，可以減少騎手的額外等待，也能避免“餐等人”的現(xiàn)象。商家出餐時間的長短，跟品類、時段、天氣等因素都有關(guān)，而交付時間更為復(fù)雜，用戶在幾樓，是否處于午高峰時段，有沒有電梯等等，都會影響騎手（到了用戶所在地之后）交付訂單給用戶的時間。

對這兩類數(shù)據(jù)，無法單純通過機理來進行預(yù)測，因為相關(guān)數(shù)據(jù)無法采集到（如商家今天有幾個廚師值班、用戶寫字樓的電梯是否開放，等等）。為解決這些問題，美團利用機器學(xué)習(xí)工具，利用歷史的騎手到店、等餐、取餐的數(shù)據(jù)，并充分考慮天氣等外部因素的影響，建立了全面反映出餐能力的預(yù)測模型，并通過實時維度的特征進行修正，得到準(zhǔn)確的出餐/交付時間估計。

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

訂單-騎手的匹配優(yōu)化

如果說上述建模過程的目標(biāo)是構(gòu)建和實際業(yè)務(wù)吻合的解空間，優(yōu)化算法的作用則是在我們構(gòu)建的解空間里找到最優(yōu)的策略。配送調(diào)度問題屬于典型的NP-Hard類離散系統(tǒng)優(yōu)化問題，解空間巨大。以一段時間內(nèi)產(chǎn)生50個訂單， 一個區(qū)域有200騎手，每個騎手身上有5個訂單為例，那么對應(yīng)的調(diào)度問題解空間規(guī)模將達到pow(200,50)*10（部分為不可行解），這是一個天文數(shù)字！

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

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

換句話說，就是必須對問題特點和結(jié)構(gòu)進行深入分析，才能設(shè)計出性能優(yōu)越的算法。在運籌優(yōu)化領(lǐng)域中的各類基礎(chǔ)性算法也是這樣的更多思路，如單純形、梯度下降、遺傳算法、模擬退火、動態(tài)規(guī)劃等，它們的本質(zhì)其實是假定了問題具備某些特征（如動態(tài)規(guī)劃的貝爾曼方程假設(shè)，遺傳算法的Building Blocks假設(shè)等），并利用這些假設(shè)進行算法設(shè)計。那么，針對配送調(diào)度的場景，這個問題可以被分解為兩個層次：騎手路徑優(yōu)化和訂單分配方案的優(yōu)化。

騎手路徑優(yōu)化問題要解決的問題是：在新訂單分配至騎手后，確定騎手的最佳配送線路；而訂單分配優(yōu)化問題要解決的問題是：把一批訂單分配至相應(yīng)的騎手，使得我們關(guān)注的指標(biāo)（如配送時長、準(zhǔn)時率、騎手的行駛距離等）達到最優(yōu)。這兩個問題的關(guān)系是：通過訂單分配優(yōu)化算法進行初始的訂單分配，然后通過騎手路徑優(yōu)化算法獲取各騎手的最佳行駛路線，進而，訂單分配優(yōu)化算法根據(jù)騎手路徑優(yōu)化結(jié)果調(diào)整分配方案。這兩個層次不斷反復(fù)迭代，最終獲得比較滿意的解。

第二個思路是跨學(xué)科結(jié)合。訂單分配問題在業(yè)內(nèi)有兩類方法，第一類方法是把訂單分配問題轉(zhuǎn)換成圖論中的二分圖匹配問題來解決。但是由于標(biāo)準(zhǔn)的二分圖匹配問題中，一個人只能被分配一項任務(wù)，所以常用的一個方法是先對訂單進行打包，將可以由一個人完成的多個訂單組成一個任務(wù)，再使用二分圖匹配算法（匈牙利算法、KM 算法）來解決。

這種做法是一個不錯的近似方案，優(yōu)點是實現(xiàn)簡單計算速度快，但它的缺點是會損失一部分滿意解。第二類方法是直接采用個性化的算法進行訂單分配方案的優(yōu)化，優(yōu)點是不損失獲得滿意解的可能性，但實際做起來難度較大。美團結(jié)合領(lǐng)域知識、優(yōu)化算法、機器學(xué)習(xí)策略以及相關(guān)圖論算法，基于分解協(xié)調(diào)思想，設(shè)計了騎手路徑優(yōu)化算法和訂單分配優(yōu)化算法。

進一步，美團利用強化學(xué)習(xí)的思想，引入了離線學(xué)習(xí)和在線優(yōu)化相結(jié)合的機制，離線學(xué)習(xí)得到策略模型，在線通過策略迭代，不斷尋求更優(yōu)解。通過不斷地改進算法，在耗時下降的同時，算法的優(yōu)化效果提升50%以上。

美團在大量的實際數(shù)據(jù)集上進行評估驗證，99%以上的情況下，騎手路徑優(yōu)化算法能夠在30ms內(nèi)給出最優(yōu)解。為了有效降低算法運行時間，美團對優(yōu)化算法進行并行化，并利用并行計算集群進行快速處理。一個區(qū)域的調(diào)度計算會在數(shù)百臺計算機上同步執(zhí)行，在2~3秒內(nèi)返回滿意結(jié)果，每天的路徑規(guī)劃次數(shù)超過50億次。

應(yīng)對強隨機性

即時配送過程的一個突出特點是線下的突發(fā)因素多、影響大，例如商家出餐異常慢、聯(lián)系不上用戶、車壞了、臨時交通管制等等。這些突發(fā)事件造成的一個惡劣結(jié)果是， 雖然在指派訂單的時刻，所指派的騎手是合理的，然而過了一段時間之后，由于騎手、訂單等狀態(tài)發(fā)生了變化，會變得不夠合理。訂單交給不合適的騎手來完成，會造成訂單超時，以及騎手需要額外的等待時間來完成訂單，影響了配送效率和用戶體驗的提升。 

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

美團針對即時配送的強不確定性特點，提出了兩點創(chuàng)新：一是延遲調(diào)度策略，即在某些場景訂單可以不被指派出去，在不影響訂單超時的情況下，延遲做出決策；二是系統(tǒng)自動改派策略，即訂單即便已經(jīng)派給了騎手，后臺的智能算法仍然會實時評估各個騎手的位置、訂單情況，并幫助騎手進行分析，判斷是否存在超時風(fēng)險。如果存在，則系統(tǒng)會評估是否有更優(yōu)的騎手來配送。

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

仿真系統(tǒng)

工業(yè)系統(tǒng)非?？粗乇O(jiān)控和評估，“No measurement, No improvement”。在工業(yè)優(yōu)化場景中，如何準(zhǔn)確評估算法的好壞，其重要性不亞于設(shè)計一個好的算法。然而，由于多個訂單在線下可能會由同一名騎手來配送，訂單與訂單之間存在耦合關(guān)系，導(dǎo)致無法做訂單維度的A/B測試。

而區(qū)域維度指標(biāo)受天氣、訂單結(jié)構(gòu)、騎手水平等外在隨機因素影響波動比較大，算法效果容易被隨機因素湮沒從而無法準(zhǔn)確評估。為此，美團針對即時配送場景，建立了相應(yīng)的仿真模型，開發(fā)了配送仿真系統(tǒng)。

系統(tǒng)能夠模擬真實的配送過程和線上調(diào)度邏輯，并給出按照某種配送策略下的最終結(jié)果。該模擬過程和線下的實際導(dǎo)航、地理數(shù)據(jù)完全一致，系統(tǒng)同時能夠根據(jù)實際配送數(shù)據(jù)進行模型自學(xué)習(xí)，不斷提升仿真精度。

一個高精度的配送仿真系統(tǒng)，除了能夠?qū)ε渌驼{(diào)度算法進行準(zhǔn)確評估和優(yōu)化，從而實現(xiàn)高效的策略準(zhǔn)入控制外，另一個巨大的價值在于能夠?qū)ε渌拖嚓P(guān)的上下游策略進行輔助優(yōu)化，包括配送范圍優(yōu)化、訂單結(jié)構(gòu)優(yōu)化、運力配置優(yōu)化、配送成本評估等等，其應(yīng)用的想象空間非常大。

結(jié)語

美團配送智能調(diào)度系統(tǒng)在應(yīng)用之后，取得了非常不錯的應(yīng)用效果。下圖說明了在訂單結(jié)構(gòu)比較類似的兩個白領(lǐng)區(qū)域上的A/B測試結(jié)果。中關(guān)村配送站在5月6日切換了派單模式和相應(yīng)的算法，大望路配送站的調(diào)度策略維持不變?？梢钥闯?，在切換后，中關(guān)村的平均配送時長有了2.9分鐘的下降，嚴重超時率下降了4.7個百分點（相比較對比區(qū)域）。

同時，在更廣泛的區(qū)域上進行了測試，結(jié)果表明，在體驗指標(biāo)不變的前提下，新策略能夠降低19%的運力消耗。換言之，原來5個人干的活，現(xiàn)在4個人就能干好，所以說，智能調(diào)度在降低成本上價值是很大的。

美團配送的目標(biāo)之一是做本地化的物流配送平臺，那么，效率、體驗和成本將成為平臺追求的核心指標(biāo)。人工智能技術(shù)在美團配送的成功應(yīng)用有很多，通過大數(shù)據(jù)、人工智能手段打造一個高效、智能化、動態(tài)協(xié)同優(yōu)化的本地智慧物流平臺，能顯著提高本地、同城范圍內(nèi)的物流配送效率，持續(xù)提升配送體驗，降低配送成本。

此文系作者個人觀點，不代表物流沙龍立場

 END