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

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

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

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

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

系統(tǒng)首先通過優(yōu)化設(shè)定配送費(fèi)以及預(yù)計(jì)送達(dá)時(shí)間來調(diào)整訂單結(jié)構(gòu)；

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

在騎手送完訂單后，系統(tǒng)根據(jù)訂單需求預(yù)測(cè)和運(yùn)力分布情況，告知騎手不同商圈的運(yùn)力需求情況，實(shí)現(xiàn)閑時(shí)的運(yùn)力調(diào)度。

通過上述技術(shù)和模式的引入，持續(xù)改善了用戶體驗(yàn)和配送成本：

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

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

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

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

這類問題一般可表述為：

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

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

二、即時(shí)配送訂單分配模式的演進(jìn)

在O2O領(lǐng)域，訂單和服務(wù)提供方的匹配問題是一個(gè)非常關(guān)鍵的問題。

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

搶單模式的優(yōu)勢(shì)是開發(fā)難度低，服務(wù)提供者（如司機(jī)、騎手）的自由度較高，可以按照自身的需要進(jìn)行搶單，但其缺點(diǎn)也很明顯：騎手/司機(jī)只考慮自身的場(chǎng)景需求，做出一個(gè)局部近優(yōu)的選擇。

然而由于每個(gè)騎手掌握的信息有限又只從自身利益出發(fā)來決策，導(dǎo)致配送整體效率低下，從用戶端來看，還存在大量訂單無人搶或者搶了之后造成服務(wù)質(zhì)量無法保證（因?yàn)椴糠烛T手無法準(zhǔn)確預(yù)判自己的配送服務(wù)能力）的場(chǎng)景，用戶體驗(yàn)比較差。

人工派單的方式，從訂單分配的結(jié)果上來看，一般優(yōu)于搶單模式。

在訂單量、騎手?jǐn)?shù)相對(duì)比較少的情形下，有經(jīng)驗(yàn)的調(diào)度員可以根據(jù)訂單的屬性特點(diǎn)、騎手的能力、騎手已接單情況、環(huán)境因素等，在騎手中逐個(gè)比對(duì)，根據(jù)若干經(jīng)驗(yàn)規(guī)則挑選一個(gè)比較合適的騎手來配送。一般而言，人工調(diào)度一個(gè)訂單往往至少需要半分鐘左右的時(shí)間才能完成。

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

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

另外，美團(tuán)外賣有數(shù)千個(gè)配送區(qū)域，如果采用人工調(diào)度方式則每個(gè)區(qū)域均需要配置調(diào)度員，會(huì)消耗非常高的人力成本。

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

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

• 系統(tǒng)可以在全局層面上掌握和配送有關(guān)的騎手、商家、用戶、訂單等各類信息，在此基礎(chǔ)上，可以做出全局較優(yōu)的方案，從而提升配送效率和配送體驗(yàn)，減少配送成本；
• 顯著減輕人工調(diào)度員的工作，從而降低人工成本，人工調(diào)度員只需要在一些意外場(chǎng)景（如配送員出現(xiàn)緊急情況無法繼續(xù)配送等）發(fā)生的時(shí)候進(jìn)行干預(yù)即可。

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

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

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

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

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

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

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

然而，由于實(shí)際工業(yè)場(chǎng)景的復(fù)雜性，絕大部分實(shí)際場(chǎng)景的決策優(yōu)化問題很難描述的如此簡單，此時(shí)，如果不仔細(xì)分析實(shí)際業(yè)務(wù)過程特點(diǎn)而錯(cuò)誤地建立了和實(shí)際場(chǎng)景不符的模型，自然會(huì)造成我們獲得的所謂“最優(yōu)解”應(yīng)用于實(shí)際后也會(huì)“水土不服”，最后被大量抱怨甚至拋棄。

所以我們說，準(zhǔn)確建模是實(shí)際決策優(yōu)化項(xiàng)目的第一步，也是最關(guān)鍵的一步。

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

1. 我們正確理解了實(shí)際業(yè)務(wù)場(chǎng)景的優(yōu)化問題，并且通過某種形式化語言進(jìn)行了準(zhǔn)確描述；
2. 我們建立的模型中，涉及的各類參數(shù)和數(shù)據(jù)，能夠準(zhǔn)確得獲取。

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

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

1. 決策變量
2. 優(yōu)化目標(biāo)
3. 約束條件

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

為了說明即時(shí)配送場(chǎng)景下的訂單分配問題，我們先引入若干符號(hào)定義：

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

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

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

原因在于兩個(gè)方面：

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

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

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

以上只是針對(duì)給定的一批訂單進(jìn)行匹配決策的優(yōu)化問題在建模時(shí)所需考慮的部分因素。

事實(shí)上，在外賣配送場(chǎng)景中，我們希望的不是單次決策的最優(yōu)，而是策略在一段時(shí)間應(yīng)用后的累積收益最大。

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

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

運(yùn)籌優(yōu)化領(lǐng)域中的馬爾可夫決策過程描述的就是這樣的一類在不確定、信息不完備環(huán)境下的序貫決策優(yōu)化問題。

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

過去，在信息化水平較低的環(huán)境下，很多工業(yè)運(yùn)籌優(yōu)化類的項(xiàng)目不成功，重要原因之一就是缺少足夠完備的數(shù)據(jù)采集基礎(chǔ)工具，大量數(shù)據(jù)由人工根據(jù)經(jīng)驗(yàn)設(shè)定，其準(zhǔn)確性難以保證，且難以隨著環(huán)境變化而自適應(yīng)調(diào)整，從而造成模型的優(yōu)化結(jié)果漸漸變得不符合實(shí)際。

機(jī)器學(xué)習(xí)領(lǐng)域有個(gè)諺語“Garbage in，garbage out”， 說明了精準(zhǔn)的基礎(chǔ)數(shù)據(jù)對(duì)于人工智能類項(xiàng)目的重要性。

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

1. 直接通過業(yè)務(wù)系統(tǒng)采集可獲取的數(shù)據(jù)，例如訂單數(shù)據(jù)、騎手負(fù)載數(shù)據(jù)、騎手狀態(tài)數(shù)據(jù)等。
2. 無法直接采集得到，需要預(yù)測(cè)或統(tǒng)計(jì)才能獲取的數(shù)據(jù)，如商戶出餐時(shí)間、用戶駐留時(shí)間（騎手到達(dá)用戶處將訂單交付給用戶的時(shí)間）、騎手配送能力等。

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

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

商家出餐時(shí)間的長短，跟品類、時(shí)段、天氣等因素都有關(guān)，而交付時(shí)間更為復(fù)雜，用戶在幾樓，是否處于午高峰時(shí)段，有沒有電梯等等，都會(huì)影響騎手（到了用戶所在地之后）交付訂單給用戶的時(shí)間。對(duì)這兩類數(shù)據(jù)，無法單純通過機(jī)理來進(jìn)行預(yù)測(cè)，因?yàn)橄嚓P(guān)數(shù)據(jù)無法采集到（如商家今天有幾個(gè)廚師值班、用戶寫字樓的電梯是否開放，等等）。

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

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

3. 訂單——騎手的匹配優(yōu)化

如果說上述建模過程的目標(biāo)是構(gòu)建和實(shí)際業(yè)務(wù)吻合的解空間，優(yōu)化算法的作用則是在我們構(gòu)建的解空間里找到最優(yōu)的策略。配送調(diào)度問題屬于典型的NP-Hard類離散系統(tǒng)優(yōu)化問題，解空間巨大。

以一段時(shí)間內(nèi)產(chǎn)生50個(gè)訂單，一個(gè)區(qū)域有200騎手，每個(gè)騎手身上有5個(gè)訂單為例，那么對(duì)應(yīng)的調(diào)度問題解空間規(guī)模將達(dá)到pow(200,50)*10（部分為不可行解），這是一個(gè)天文數(shù)字！

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

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

換句話說，就是我們必須對(duì)問題特點(diǎn)和結(jié)構(gòu)進(jìn)行深入分析，才能設(shè)計(jì)出性能優(yōu)越的算法。

在運(yùn)籌優(yōu)化領(lǐng)域中的各類基礎(chǔ)性算法也是這樣的更多思路，如單純形、梯度下降、遺傳算法、模擬退火、動(dòng)態(tài)規(guī)劃等，它們的本質(zhì)其實(shí)是假定了問題具備某些特征（如動(dòng)態(tài)規(guī)劃的貝爾曼方程假設(shè)，遺傳算法的Building Blocks假設(shè)等），并利用這些假設(shè)進(jìn)行算法設(shè)計(jì)。

那么，針對(duì)配送調(diào)度的場(chǎng)景，這個(gè)問題可以被分解為兩個(gè)層次：騎手路徑優(yōu)化和訂單分配方案的優(yōu)化。

騎手路徑優(yōu)化問題要解決的問題是：在新訂單分配至騎手后，確定騎手的最佳配送線路；而訂單分配優(yōu)化問題要解決的問題是：把一批訂單分配至相應(yīng)的騎手，使得我們關(guān)注的指標(biāo)（如配送時(shí)長、準(zhǔn)時(shí)率、騎手的行駛距離等）達(dá)到最優(yōu)。

這兩個(gè)問題的關(guān)系是：通過訂單分配優(yōu)化算法進(jìn)行初始的訂單分配，然后通過騎手路徑優(yōu)化算法獲取各騎手的最佳行駛路線，進(jìn)而，訂單分配優(yōu)化算法根據(jù)騎手路徑優(yōu)化結(jié)果調(diào)整分配方案。

這兩個(gè)層次不斷反復(fù)迭代，最終獲得比較滿意的解。

第二個(gè)思路是跨學(xué)科結(jié)合。

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

但是由于標(biāo)準(zhǔn)的二分圖匹配問題中，一個(gè)人只能被分配一項(xiàng)任務(wù)，所以常用的一個(gè)方法是先對(duì)訂單進(jìn)行打包，將可以由一個(gè)人完成的多個(gè)訂單組成一個(gè)任務(wù)，再使用二分圖匹配算法（匈牙利算法、KM 算法）來解決。這種做法是一個(gè)不錯(cuò)的近似方案，優(yōu)點(diǎn)是實(shí)現(xiàn)簡單計(jì)算速度快，但它的缺點(diǎn)是會(huì)損失一部分滿意解。

第二類方法是直接采用個(gè)性化的算法進(jìn)行訂單分配方案的優(yōu)化，優(yōu)點(diǎn)是不損失獲得滿意解的可能性，但實(shí)際做起來難度較大。

我們結(jié)合領(lǐng)域知識(shí)、優(yōu)化算法、機(jī)器學(xué)習(xí)策略以及相關(guān)圖論算法，基于分解協(xié)調(diào)思想，設(shè)計(jì)了騎手路徑優(yōu)化算法和訂單分配優(yōu)化算法。進(jìn)一步，我們利用強(qiáng)化學(xué)習(xí)的思想，引入了離線學(xué)習(xí)和在線優(yōu)化相結(jié)合的機(jī)制，離線學(xué)習(xí)得到策略模型，在線通過策略迭代，不斷尋求更優(yōu)解。通過不斷地改進(jìn)算法，在耗時(shí)下降的同時(shí)，算法的優(yōu)化效果提升50%以上。

我們?cè)诖罅康膶?shí)際數(shù)據(jù)集上進(jìn)行評(píng)估驗(yàn)證，99%以上的情況下，騎手路徑優(yōu)化算法能夠在30ms內(nèi)給出最優(yōu)解。

為了有效降低算法運(yùn)行時(shí)間，我們對(duì)優(yōu)化算法進(jìn)行并行化，并利用并行計(jì)算集群進(jìn)行快速處理。

一個(gè)區(qū)域的調(diào)度計(jì)算會(huì)在數(shù)百臺(tái)計(jì)算機(jī)上同步執(zhí)行，在2~3秒內(nèi)返回滿意結(jié)果，每天的路徑規(guī)劃次數(shù)超過50億次。

4. 應(yīng)對(duì)強(qiáng)隨機(jī)性

即時(shí)配送過程的一個(gè)突出特點(diǎn)是線下的突發(fā)因素多、影響大，例如商家出餐異常慢、聯(lián)系不上用戶、車壞了、臨時(shí)交通管制等等。

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

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

我們針對(duì)即時(shí)配送的強(qiáng)不確定性特點(diǎn)，提出了兩點(diǎn)創(chuàng)新：

一是延遲調(diào)度策略，即在某些場(chǎng)景訂單可以不被指派出去，在不影響訂單超時(shí)的情況下，延遲做出決策；

二是系統(tǒng)自動(dòng)改派策略，即訂單即便已經(jīng)派給了騎手，后臺(tái)的智能算法仍然會(huì)實(shí)時(shí)評(píng)估各個(gè)騎手的位置、訂單情況，并幫助騎手進(jìn)行分析，判斷是否存在超時(shí)風(fēng)險(xiǎn)。如果存在，則系統(tǒng)會(huì)評(píng)估是否有更優(yōu)的騎手來配送。

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

5. 仿真系統(tǒng)

工業(yè)系統(tǒng)非?？粗乇O(jiān)控和評(píng)估，“No measurement, No improvement”。在工業(yè)優(yōu)化場(chǎng)景中，如何準(zhǔn)確評(píng)估算法的好壞，其重要性不亞于設(shè)計(jì)一個(gè)好的算法。

然而，由于多個(gè)訂單在線下可能會(huì)由同一名騎手來配送，訂單與訂單之間存在耦合關(guān)系，導(dǎo)致無法做訂單維度的A/B測(cè)試。而區(qū)域維度指標(biāo)受天氣、訂單結(jié)構(gòu)、騎手水平等外在隨機(jī)因素影響波動(dòng)比較大，算法效果容易被隨機(jī)因素湮沒從而無法準(zhǔn)確評(píng)估。

為此，我們針對(duì)即時(shí)配送場(chǎng)景，建立了相應(yīng)的仿真模型，開發(fā)了配送仿真系統(tǒng)。系統(tǒng)能夠模擬真實(shí)的配送過程和線上調(diào)度邏輯，并給出按照某種配送策略下的最終結(jié)果。該模擬過程和線下的實(shí)際導(dǎo)航、地理數(shù)據(jù)完全一致，系統(tǒng)同時(shí)能夠根據(jù)實(shí)際配送數(shù)據(jù)進(jìn)行模型自學(xué)習(xí)，不斷提升仿真精度。

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

四、結(jié)語

美團(tuán)配送智能調(diào)度系統(tǒng)在應(yīng)用之后，取得了非常不錯(cuò)的應(yīng)用效果。下圖說明了在訂單結(jié)構(gòu)比較類似的兩個(gè)白領(lǐng)區(qū)域上的A/B測(cè)試結(jié)果。

中關(guān)村配送站在5月6日切換了派單模式和相應(yīng)的算法，大望路配送站的調(diào)度策略維持不變。

可以看出，在切換后，中關(guān)村的平均配送時(shí)長有了2.9分鐘的下降，嚴(yán)重超時(shí)率下降了4.7個(gè)百分點(diǎn)（相比較對(duì)比區(qū)域）。

同時(shí)，在更廣泛的區(qū)域上進(jìn)行了測(cè)試，結(jié)果表明，在體驗(yàn)指標(biāo)不變的前提下，新策略能夠降低19%的運(yùn)力消耗。

換言之，原來5個(gè)人干的活，現(xiàn)在4個(gè)人就能干好，所以說，智能調(diào)度在降低成本上價(jià)值是很大的。

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

作者：井華

來源：美團(tuán)點(diǎn)評(píng)技術(shù)團(tuán)隊(duì)