即時(shí)配送業(yè)務(wù)是典型的 O2O 業(yè)務(wù)，線上和線下存在大量復(fù)雜的業(yè)務(wù)約束和多種多樣的決策變量。美團(tuán)智能配送系統(tǒng)負(fù)責(zé)訂單和騎手的資源優(yōu)化配置，致力于改善顧客體驗(yàn)、降低配送成本。作為美團(tuán)智能配送系統(tǒng)最核心的技術(shù)之一，運(yùn)籌優(yōu)化是如何在各種業(yè)務(wù)場(chǎng)景落地的？本文整理自王圣堯老師在 ArchSummit 全球架構(gòu)師峰會(huì)上的演講內(nèi)容，以饗廣大技術(shù)讀者。

一、美團(tuán)智能配送系統(tǒng)架構(gòu)

美團(tuán)配送是一個(gè)怎樣的業(yè)務(wù)場(chǎng)景呢？下圖里的這組數(shù)字是 2019 年 5 月份美團(tuán)配送品牌發(fā)布時(shí)候的數(shù)據(jù)。作為服務(wù)三方客戶的平臺(tái)（包括商家、騎手、用戶），目前我們每天完成的單量峰值已經(jīng)遠(yuǎn)不止這個(gè)數(shù)字。

單獨(dú)看這幾個(gè)數(shù)字可能沒(méi)有概念，但是如果告訴大家每年給騎手支付的工資是幾百億的量級(jí)，就知道在這樣大規(guī)模的業(yè)務(wù)場(chǎng)景下，配送的智能化是多么重要。智能配送的核心是做資源的優(yōu)化配置。

外賣(mài)配送是一個(gè)典型的 O2O 場(chǎng)景。既有線上的業(yè)務(wù)，也有線下的復(fù)雜運(yùn)營(yíng)。配送連接訂單需求和運(yùn)力供給。為了達(dá)到需求和供給的最好平衡，不僅要在線下運(yùn)營(yíng)商家、運(yùn)營(yíng)騎手，還要在線上將這些需求和運(yùn)力供給做合理配置，目的是提高效率。配送效率最大化，才能帶來(lái)良好的顧客體驗(yàn)、較低的配送成本。做資源優(yōu)化配置的過(guò)程，實(shí)際上是有分層的。按我們的理解，可以分為三層：

• 基礎(chǔ)層是結(jié)構(gòu)優(yōu)化，它直接決定了配送系統(tǒng)效率的上限。這種基礎(chǔ)結(jié)構(gòu)的優(yōu)化，周期比較長(zhǎng)，頻率比較低，包括配送網(wǎng)絡(luò)規(guī)劃、運(yùn)力結(jié)構(gòu)規(guī)劃等。
• 中間層是市場(chǎng)調(diào)節(jié)，相對(duì)來(lái)說(shuō)是中短期的，主要通過(guò)定價(jià)或者營(yíng)銷(xiāo)手段，使供需達(dá)到一個(gè)相對(duì)理想的平衡狀態(tài)。
• 再上層是實(shí)時(shí)匹配，通過(guò)調(diào)度做實(shí)時(shí)的資源最優(yōu)匹配。實(shí)時(shí)匹配的頻率是最高的，決策的周期也是最短的。

針對(duì)智能配送的三層體系，配送算法團(tuán)隊(duì)也是這樣運(yùn)作的。圖中右邊三個(gè)子系統(tǒng)，對(duì)應(yīng)三層，最底層是規(guī)劃系統(tǒng)，中間層是定價(jià)系統(tǒng)，最上層是調(diào)度系統(tǒng)。同樣非常重要的，還包括圖中另外四個(gè)子系統(tǒng)，在配送過(guò)程中做精準(zhǔn)的數(shù)據(jù)采集、感知、預(yù)估，為優(yōu)化決策提供準(zhǔn)確的參數(shù)輸入，包括機(jī)器學(xué)習(xí)系統(tǒng)、IoT 和感知系統(tǒng)、LBS 系統(tǒng)，都是配送系統(tǒng)非常重要的環(huán)節(jié)，有大量復(fù)雜的機(jī)器學(xué)習(xí)問(wèn)題。

二、實(shí)戰(zhàn)業(yè)務(wù)項(xiàng)目

1. 智能區(qū)域規(guī)劃

為了有助于快速理解配送業(yè)務(wù)的基本背景，首先分享智能區(qū)域規(guī)劃項(xiàng)目中遇到的問(wèn)題和解決方案。

配送連接的是商家、顧客、騎手三方，配送網(wǎng)絡(luò)決定了這三方的連接關(guān)系。打開(kāi) App，哪些商家可以點(diǎn)餐，是由商家配送范圍決定的。每個(gè)商家的配送范圍不一樣，看似是商家粒度的決策，但實(shí)際上直接影響每個(gè) C 端用戶得到的商流供給，這本身還是一個(gè)資源分配或者資源搶奪問(wèn)題。商家配送范圍智能化也是很有意思的組合優(yōu)化問(wèn)題，但是我們這里講的是商家和騎手的連接關(guān)系。

在公司點(diǎn)外賣(mài)，為我服務(wù)的騎手是哪一批呢？又是怎么確定的呢？這些是由配送區(qū)域邊界來(lái)決定的。配送區(qū)域邊界指的是一些商家的集合所對(duì)應(yīng)的范圍。為什么要?jiǎng)澐謪^(qū)域邊界呢？從優(yōu)化的角度來(lái)講，對(duì)于一個(gè)確定問(wèn)題，反而是約束條件越少，目標(biāo)函數(shù)值更優(yōu)的可能性越大。做優(yōu)化的同學(xué)肯定都不喜歡約束條件，但是配送區(qū)域邊界實(shí)際是給配送系統(tǒng)強(qiáng)加的約束。

在傳統(tǒng)物流中，影響末端配送效率最關(guān)鍵的點(diǎn)其實(shí)是配送員對(duì)他所負(fù)責(zé)區(qū)域的熟悉程度。這也是為什么在傳統(tǒng)物流領(lǐng)域，配送站或配送員，都會(huì)固定負(fù)責(zé)某幾個(gè)小區(qū)的原因之一。因?yàn)樵绞煜ぃ渌托试礁摺?/p>

即時(shí)配送場(chǎng)景也類(lèi)似，每個(gè)騎手需要盡量固定去熟悉一片商家或者配送區(qū)域。同時(shí)，對(duì)于管理而言，站點(diǎn)的管理范圍也是比較明確的。另外，如果有新商家上線，也很容易確定由哪個(gè)配送站來(lái)提供服務(wù)。所以，這個(gè)問(wèn)題有很多運(yùn)營(yíng)管理訴求在里面。

區(qū)域規(guī)劃這個(gè)項(xiàng)目的發(fā)起，是因?yàn)閷?shí)際已經(jīng)存在很多問(wèn)題需要解決。有這樣三類(lèi) case：

• 配送區(qū)域里的商家不聚合。這是一個(gè)典型站點(diǎn)，商家主要集中在左下角和右上角，造成騎手在區(qū)域里取餐、送餐時(shí)執(zhí)行任務(wù)的地理位置非常分散，需要不停往返兩個(gè)商圈，無(wú)效跑動(dòng)非常多。
• 區(qū)域奇形怪狀，空駛嚴(yán)重。之前在門(mén)店上線外賣(mài)平臺(tái)的發(fā)展過(guò)程中，很多地方原本沒(méi)有商家，后來(lái)上線的商家多了，就單獨(dú)作為一個(gè)配送區(qū)域。這樣的區(qū)域形狀可能就會(huì)不規(guī)則，導(dǎo)致騎手很多時(shí)候在區(qū)域外面跑。而商家和騎手是有綁定關(guān)系的，騎手只能服務(wù)自己區(qū)域內(nèi)的商家，因此騎手無(wú)法接到配送區(qū)域外的取餐任務(wù)，空駛率非常高。很多時(shí)候騎手出去送完餐之后，只能空著跑回來(lái)才可能接到新任務(wù)。
• 站點(diǎn)的大小不合理。圖三這個(gè)站點(diǎn)，每天的單量只有一二百單。如果從騎手平均單量的角度去配置騎手的話，只能配置 3~4 個(gè)騎手。如果某一兩個(gè)人突然有事要請(qǐng)假，可想而知，站點(diǎn)的配送體驗(yàn)一定會(huì)非常差的，運(yùn)營(yíng)管理很難。反之，如果一個(gè)站點(diǎn)非常大，站長(zhǎng)又不可能管得了那么多騎手。所以，需要給每個(gè)站點(diǎn)規(guī)劃一個(gè)合理的單量規(guī)模。

既然存在這么多的問(wèn)題，那么就很需要做區(qū)域規(guī)劃項(xiàng)目。

優(yōu)化的三要素是，目標(biāo)、約束、決策變量。

第一點(diǎn)，首先要確定優(yōu)化目標(biāo)。 在很多比較穩(wěn)定或者傳統(tǒng)的業(yè)務(wù)場(chǎng)景中，目標(biāo)是非常確定的。在區(qū)域規(guī)劃這個(gè)場(chǎng)景，怎么定義優(yōu)化目標(biāo)呢？首先要思考的是區(qū)域規(guī)劃主要影響的是什么。從剛才幾類(lèi)問(wèn)題的分析發(fā)現(xiàn)，影響的主要是騎手的順路性、空駛率，也就是騎手平均為每一單付出的路程成本。所以，我們將問(wèn)題的業(yè)務(wù)目標(biāo)定為優(yōu)化騎手的單均行駛距離。基于現(xiàn)有的大量區(qū)域和站點(diǎn)積累的數(shù)據(jù)，做大量的統(tǒng)計(jì)分析后，可以定義出這樣幾個(gè)指標(biāo)：商家聚合度、訂單的聚合度、訂單重心和商家重心的偏離程度。 數(shù)據(jù)分析結(jié)果說(shuō)明，這幾個(gè)指標(biāo)和單均行駛距離的相關(guān)性很強(qiáng)。經(jīng)過(guò)這一層的建模轉(zhuǎn)化，問(wèn)題明確為優(yōu)化這三個(gè)指標(biāo)。

第二點(diǎn)，需要梳理業(yè)務(wù)約束。 在這方面，我們花費(fèi)了比較多的時(shí)間和精力。比如：區(qū)域單量是有上限和下限的；區(qū)域之間不能有重合，不能有商家歸多個(gè)區(qū)域負(fù)責(zé)；所有的 AOI 不能有遺漏，都要被某個(gè)區(qū)域覆蓋到，不能出現(xiàn)商家沒(méi)有站點(diǎn)服務(wù)。

最難的一個(gè)問(wèn)題，其實(shí)是要求區(qū)域邊界必須沿路網(wǎng)。起初我們很難理解，因?yàn)楸举|(zhì)上區(qū)域規(guī)劃只是對(duì)商家進(jìn)行分類(lèi)，它只是一個(gè)商家集合的概念，為什么要畫(huà)出邊界，還要求邊界沿路網(wǎng)呢？其實(shí)剛才介紹過(guò)，區(qū)域邊界是為了回答，如果有新商家上線，到底屬于哪個(gè)站點(diǎn)。而且，從一線管理成本來(lái)講，更習(xí)慣于哪條路以東、哪條路以南這樣的表述方式，便于記憶和理解，提高管理效率。所以，就有了這樣的訴求，我們希望區(qū)域邊界是“便于理解”的。

目標(biāo)和約束確定了之后，整體技術(shù)方案分成三部分：

• 首先，根據(jù)三個(gè)目標(biāo)函數(shù)，確定商家最優(yōu)集合。這一步反而比較簡(jiǎn)單，因?yàn)樽鲞\(yùn)籌優(yōu)化的同學(xué)可以很快速解決這樣一個(gè)多目標(biāo)組合優(yōu)化問(wèn)題。
• 后面的步驟比較難，怎么把區(qū)域邊界畫(huà)出來(lái)呢？為了解決這個(gè)問(wèn)題，我們和美團(tuán)地圖團(tuán)隊(duì)合作。先利用路網(wǎng)信息，把城市切成若干互不重疊的多邊形，然后根據(jù)計(jì)算幾何，把一批商家對(duì)應(yīng)的多邊形拼成完整的區(qū)域邊界。
• 最后，用美團(tuán)自主研發(fā)的配送仿真系統(tǒng)，評(píng)測(cè)這樣的區(qū)域規(guī)劃對(duì)應(yīng)的單均行駛距離和體驗(yàn)指標(biāo)是否符合預(yù)期。因?yàn)橐痪€直接變動(dòng)的成本是很高的，這里仿真系統(tǒng)就起到了非常好的作用。

下面是一個(gè)實(shí)際案例，我們用算法把一個(gè)城市做了重新的區(qū)域規(guī)劃。當(dāng)然，這里必須要強(qiáng)調(diào)的是，在這個(gè)過(guò)程中，人工介入還是非常必要的。對(duì)于一些算法很難處理好的邊角場(chǎng)景，需要人工微調(diào)，使整個(gè)規(guī)劃方案更加合理。中間的圖是算法規(guī)劃的結(jié)果。試點(diǎn)后，城市整體的單均行駛距離下降了 5%，平均每一單騎手的行駛距離節(jié)省超過(guò) 100 米。可以想象一下，在這么龐大的單量規(guī)模下，每單平均減少 100 米，總節(jié)省的路程、節(jié)省的電瓶車(chē)電量，都是非常可觀的數(shù)字。更重要的是，可以讓騎手自己明顯感覺(jué)到效率的提升。

2. 智能騎手排班

隨著外賣(mài)配送的營(yíng)業(yè)時(shí)間越來(lái)越長(zhǎng)，衍生出這樣一個(gè)項(xiàng)目。最早，外賣(mài)只服務(wù)午高峰到晚高峰，后來(lái)慢慢可以點(diǎn)夜宵、點(diǎn)早餐，到如今很多配送站點(diǎn)已經(jīng)是 24 小時(shí)服務(wù)了。但是，騎手不可能全天 24 小時(shí)開(kāi)工，勞動(dòng)法對(duì)每天的工作時(shí)長(zhǎng)也有規(guī)定。

另外，外賣(mài)配送場(chǎng)景的訂單峰谷效應(yīng)非常明顯。上圖是一個(gè)實(shí)際的進(jìn)單曲線，全天 24 小時(shí)內(nèi)，午晚高峰兩個(gè)時(shí)段單量非常高，而閑時(shí)和夜宵相對(duì)來(lái)說(shuō)單量又少一些。因此，沒(méi)辦法把一天 24 小時(shí)根據(jù)每個(gè)人的工作時(shí)長(zhǎng)做平均切分，需要進(jìn)行排班。

對(duì)于排班，有這樣兩類(lèi)方案的選型問(wèn)題。很多業(yè)務(wù)的排班是基于人的維度，好處是配置的粒度非常精細(xì)，每個(gè)人的工作時(shí)段都是個(gè)性化的，可以考慮每個(gè)人的訴求。但是，在配送場(chǎng)景的缺點(diǎn)也顯而易見(jiàn)。如果站長(zhǎng)需要為每個(gè)人去規(guī)劃工作時(shí)段，難度可想而知，也很難保證公平性。

我們最終選用的是按組排班的方式，把所有騎手分成幾組，規(guī)定每個(gè)組的開(kāi)工時(shí)段。然后大家可以按組輪崗，每個(gè)人對(duì)于每個(gè)班次都會(huì)輪到。

這個(gè)問(wèn)題最大的挑戰(zhàn)是，我們并不是在做一項(xiàng)業(yè)務(wù)工具，而是在設(shè)計(jì)算法。算法是要有優(yōu)化目標(biāo)的，排班的目標(biāo)是什么呢？我們問(wèn)站長(zhǎng)，覺(jué)得怎么樣的排班是好的，他只是說(shuō)，要讓需要用人的時(shí)候有人。但這不是算法語(yǔ)言，更不能變成模型語(yǔ)言。

我們首先做的是設(shè)計(jì)決策變量，決策變量并沒(méi)有選用班次的起止時(shí)刻和結(jié)束時(shí)刻，那樣做決策空間太大了。我們把時(shí)間做了離散化，以半小時(shí)為粒度。對(duì)于一天來(lái)講，只有 48 個(gè)時(shí)間單元，決策空間大幅縮減。然后，目標(biāo)定為運(yùn)力需求滿足訂單量的時(shí)間單元最多。這是因?yàn)椋⒉荒鼙ＷC站點(diǎn)的人數(shù)在對(duì)應(yīng)的進(jìn)單曲線情況下可以滿足每個(gè)單元的運(yùn)力需求，所以，我們把業(yè)務(wù)約束轉(zhuǎn)化為目標(biāo)函數(shù)的一部分。這樣還有一個(gè)好處，沒(méi)必要知道站點(diǎn)的總?cè)藬?shù)是多少。

在建模層面，標(biāo)準(zhǔn)化和通用的模型才是好的。所以，我們把人數(shù)做了歸一化，算法分配每個(gè)班次的騎手比例，但不分人數(shù)。最終只需要輸入站點(diǎn)的總?cè)藬?shù)，就得到每個(gè)班次的人數(shù)。在算法決策的時(shí)候，不決策人數(shù)、只決策比例，這樣也可以把單量進(jìn)行歸一化。每個(gè)時(shí)間單元的進(jìn)單量除以每天峰值時(shí)間單元的單量，也變成了 0~1 之間的數(shù)字。這樣就可以認(rèn)為，如果某個(gè)時(shí)間單元內(nèi)人數(shù)比例大于單量比例，那么叫作運(yùn)力得到滿足。這樣，通過(guò)各種歸一化，變成了一個(gè)通用的問(wèn)題，而不需要對(duì)每種場(chǎng)景單獨(dú)處理。

另外，這個(gè)問(wèn)題有大量復(fù)雜的強(qiáng)約束，涉及各種管理的訴求、騎手的體驗(yàn)。約束有很多，比如每個(gè)工作時(shí)段盡量連續(xù)、每個(gè)工作時(shí)段持續(xù)的時(shí)間不過(guò)短、不同工作時(shí)段之間休息的時(shí)間不過(guò)短……有很多這樣的業(yè)務(wù)約束，梳理之后我們發(fā)現(xiàn)，這個(gè)問(wèn)題的約束太多了，求最優(yōu)解甚至可行解的難度太大了。另外，站長(zhǎng)在使用排班工具的時(shí)候，希望能馬上給出系統(tǒng)排班方案，再快速做后續(xù)微調(diào)，因此對(duì)算法運(yùn)行時(shí)間要求也很高。

綜合考慮以上，我們最終基于約束條件根據(jù)啟發(fā)式算法構(gòu)造初始方案，再用局部搜索迭代優(yōu)化。這樣的方式，求解速度是毫秒級(jí)的，而且可以給出任意站點(diǎn)的排班方案。優(yōu)化指標(biāo)還不錯(cuò)，當(dāng)然，不保證是最優(yōu)解，只是可以接受的滿意解。

這個(gè)算法也在自營(yíng)場(chǎng)景做了落地應(yīng)用，和那些排班經(jīng)驗(yàn)豐富的站長(zhǎng)相比，效果基本持平，一線的接受程度也比較高。最重要的是帶來(lái)排班時(shí)間的節(jié)省，每次排班幾分鐘就搞定了，這樣可以讓站長(zhǎng)有更多的時(shí)間去做其它管理工作。

3. 騎手路徑規(guī)劃

騎手的路徑規(guī)劃問(wèn)題，不是路線規(guī)劃，不是從 a 到 b 該走哪條路的問(wèn)題。這個(gè)場(chǎng)景是，一個(gè)騎手身上有很多配送任務(wù)，這些配送任務(wù)有各種約束，怎樣選擇最優(yōu)配送順序去完成所有任務(wù)。這是一個(gè) NP 難問(wèn)題，當(dāng)有 5 個(gè)訂單、10 個(gè)任務(wù)點(diǎn)的時(shí)候，就已經(jīng)有 11 萬(wàn)多條可能的順序。而在高峰期的時(shí)候，騎手往往是背負(fù)不止 5 單的，甚至有時(shí)候一個(gè)騎手會(huì)同時(shí)有十幾單，這時(shí)候可行的取送順序就是天文數(shù)字了。

再看算法的應(yīng)用場(chǎng)景，這是智能調(diào)度系統(tǒng)中最重要的一個(gè)環(huán)節(jié)。系統(tǒng)派單、系統(tǒng)改派，都依賴(lài)路徑規(guī)劃算法；在騎手端，給每個(gè)騎手推薦任務(wù)執(zhí)行順序；另外，用戶點(diǎn)了外賣(mài)之后，美團(tuán)會(huì)實(shí)時(shí)展示騎手當(dāng)前任務(wù)還需要執(zhí)行幾分鐘，給用戶提供更多預(yù)估信息。這么多應(yīng)用場(chǎng)景，共同的訴求是時(shí)效要求非常高，算法運(yùn)行時(shí)間越短越好。

但是，算法僅僅是快就可以嗎？并不是。因?yàn)檫@是派單、改派這些環(huán)節(jié)的核心模塊，所以算法的優(yōu)化求解能力也非常重要。如果路徑規(guī)劃算法不能給出較優(yōu)路徑，可想而知，上層的指派和改派很難做出好的決策。

所以，對(duì)這個(gè)問(wèn)題做明確的梳理，核心的訴求是優(yōu)化效果必須是穩(wěn)定的好。不能這次的優(yōu)化結(jié)果好，下次就不好；另外，運(yùn)行時(shí)間一定要短。

在求解路徑規(guī)劃這類(lèi)問(wèn)題上，很多公司的技術(shù)團(tuán)隊(duì)，都經(jīng)歷過(guò)這樣的階段：起初，采用類(lèi)似遺傳算法的迭代搜索算法，但是隨著業(yè)務(wù)的單量變大，發(fā)現(xiàn)算法耗時(shí)太慢，根本不可接受；然后，改為大規(guī)模鄰域搜索算法，但算法依然有很強(qiáng)的隨機(jī)性，因?yàn)闆](méi)有隨機(jī)性在就沒(méi)辦法得到比較好的解。而這種基于隨機(jī)迭代的搜索策略，帶來(lái)很強(qiáng)的不確定性，在問(wèn)題規(guī)模大的場(chǎng)景會(huì)出現(xiàn)非常多的 bad case。另外，迭代搜索耗時(shí)太長(zhǎng)了。主要的原因是，隨機(jī)迭代算法是把組合優(yōu)化問(wèn)題當(dāng)成一個(gè)單純的 permutation 問(wèn)題去求解，很少用到問(wèn)題結(jié)構(gòu)特征。這些算法，求解 TSP 時(shí)這樣操作，求解 VRP 時(shí)也這樣操作，求解 Scheduling 還是這樣操作，這種類(lèi)似“無(wú)腦”的方式很難有出色的優(yōu)化效果。

所以在這個(gè)項(xiàng)目中，基本可以確定這樣的技術(shù)路線。首先，只能做啟發(fā)式定向搜索，不能在算法中加隨機(jī)擾動(dòng)。不能允許同樣的輸入在不同運(yùn)行時(shí)刻給出不一樣的優(yōu)化結(jié)果。然后，不能用普通迭代搜索，必須把這個(gè)問(wèn)題結(jié)構(gòu)特性挖掘出來(lái)，做基于知識(shí)的定制化搜索。

說(shuō)起來(lái)容易，怎么做呢？最重要的，是看待這個(gè)問(wèn)題的視角。這里的路徑規(guī)劃問(wèn)題，對(duì)應(yīng)的經(jīng)典問(wèn)題模型，是開(kāi)環(huán) TSP 問(wèn)題，或是開(kāi)環(huán) VRP 的變種么？可以是，也可以不是。我們做了一個(gè)有意思的建模轉(zhuǎn)換，把它看作流水線調(diào)度問(wèn)題：每個(gè)訂單可以認(rèn)為是 job；一個(gè)訂單的兩個(gè)任務(wù)取餐和送餐，可以認(rèn)為是一個(gè) job 的 operation；任意兩個(gè)任務(wù)點(diǎn)之間的通行時(shí)間，可以認(rèn)為是序列相關(guān)的準(zhǔn)備時(shí)間；每一單承諾的送達(dá)時(shí)間，包括預(yù)訂單和即時(shí)單，可以映射到流水線調(diào)度問(wèn)題中的提前和拖期懲罰上。

做了這樣的建模轉(zhuǎn)換之后，流水線調(diào)度問(wèn)題有大量的啟發(fā)式算法可以借鑒。我們把一個(gè)經(jīng)典的基于問(wèn)題特征的啟發(fā)式算法做了適當(dāng)適配和改進(jìn)，可以得到非常好的效果。相比于之前的算法，耗時(shí)下降 70%，優(yōu)化效果還不錯(cuò)。因?yàn)檫@是一個(gè)確定性算法，所以運(yùn)行多少次的結(jié)果都一樣。但是，我們的算法運(yùn)行一次，和其它算法運(yùn)行 10 次的最優(yōu)結(jié)果相比，優(yōu)化效果是持平的。

4. 訂單智能調(diào)度

配送調(diào)度場(chǎng)景，可以用數(shù)學(xué)語(yǔ)言描述。它不僅是一個(gè)業(yè)務(wù)問(wèn)題，更是一個(gè)標(biāo)準(zhǔn)的組合優(yōu)化問(wèn)題，并且是一個(gè)馬爾可夫決策過(guò)程。

并非對(duì)于某個(gè)時(shí)刻的一批訂單做最優(yōu)分配就夠了，還需要考慮整個(gè)時(shí)間窗維度，每一次指派對(duì)后面的影響。每一次訂單分配，都影響了每個(gè)騎手后續(xù)時(shí)段的位置分布和行進(jìn)方向。如果騎手的分布和方向不適合未來(lái)的訂單結(jié)構(gòu)，相當(dāng)于降低了后續(xù)調(diào)度時(shí)刻的最優(yōu)性的天花板。所以，要考慮長(zhǎng)周期的優(yōu)化，而不是一個(gè)靜態(tài)優(yōu)化問(wèn)題。

為了便于理解，我們還是先看某個(gè)調(diào)度時(shí)刻的靜態(tài)優(yōu)化問(wèn)題。它不僅僅是一個(gè)算法問(wèn)題，還需要我們對(duì)工程架構(gòu)有非常深刻的理解。因?yàn)椋趯?duì)問(wèn)題輸入數(shù)據(jù)進(jìn)行拆解的時(shí)候，會(huì)發(fā)現(xiàn)算法的輸入數(shù)據(jù)太龐大了。比如說(shuō)，我們需要任意兩個(gè)任務(wù)點(diǎn)的導(dǎo)航距離數(shù)據(jù)。

而我們面臨的問(wèn)題規(guī)模，前幾年只是區(qū)域維度的調(diào)度粒度，一個(gè)商圈一分鐘峰值 100 多單，匹配幾百個(gè)騎手，但是這種乘積關(guān)系對(duì)應(yīng)的數(shù)據(jù)已經(jīng)非常大了。現(xiàn)在，由于有更多業(yè)務(wù)場(chǎng)景，比如跑腿和全城送，是會(huì)跨非常多的商圈，甚至跨越半個(gè)城市，所以只能做城市級(jí)的全局優(yōu)化匹配。目前，調(diào)度系統(tǒng)處理的問(wèn)題的峰值規(guī)模，是 1 萬(wàn)多單和幾萬(wàn)名騎手的匹配。而算法允許的運(yùn)行時(shí)間只有幾秒鐘，同時(shí)對(duì)內(nèi)存的消耗也非常大。

另外，配送和網(wǎng)約車(chē)派單場(chǎng)景不太一樣。打車(chē)的調(diào)度是做司機(jī)和乘客的匹配，本質(zhì)是個(gè)二分圖匹配問(wèn)題，有多項(xiàng)式時(shí)間的最優(yōu)算法：KM 算法。打車(chē)場(chǎng)景的難點(diǎn)在于，如何刻畫(huà)每對(duì)匹配的權(quán)重。而配送場(chǎng)景還需要解決，對(duì)于沒(méi)有多項(xiàng)式時(shí)間最優(yōu)算法的情況下，如何在指數(shù)級(jí)的解空間，短時(shí)間得到優(yōu)化解。如果認(rèn)為每一單和每個(gè)騎手的匹配有不同的適應(yīng)度，那么這個(gè)適應(yīng)度并不是可線性疊加的。也就意味著多單對(duì)多人的匹配方案中，任意一種匹配都只能重新運(yùn)算適應(yīng)度，計(jì)算量可想而知。

總結(jié)一下，這個(gè)問(wèn)題有三類(lèi)挑戰(zhàn)：

性能要求極高，要做到萬(wàn)單對(duì)萬(wàn)人的秒級(jí)求解。我們之前做了一些比較有意思的工作，比如基于歷史最優(yōu)指派的結(jié)果，用機(jī)器學(xué)習(xí)模型做剪枝。大量的歷史數(shù)據(jù)，可以幫助我們節(jié)省很多無(wú)用的匹配方案評(píng)價(jià)。

動(dòng)態(tài)性。作為一個(gè) MDP 問(wèn)題，需要考慮動(dòng)態(tài)優(yōu)化場(chǎng)景，這涉及大量的預(yù)估環(huán)節(jié)。在只有當(dāng)前未完成訂單的情況下，騎手如何執(zhí)行、每一單的完成時(shí)刻如何預(yù)估、未來(lái)時(shí)段會(huì)進(jìn)哪些結(jié)構(gòu)的訂單、對(duì)業(yè)務(wù)指標(biāo)和效率指標(biāo)產(chǎn)生怎樣的影響……可能會(huì)覺(jué)得這是一個(gè)典型的強(qiáng)化學(xué)習(xí)場(chǎng)景，但它的難點(diǎn)在于決策空間太大，甚至可以認(rèn)為是無(wú)限大的。目前我們的思路，是通過(guò)其它的建模轉(zhuǎn)換手段解決。

配送業(yè)務(wù)的隨機(jī)因素多。比如商家的出餐時(shí)間，也許是很長(zhǎng)時(shí)間內(nèi)都無(wú)法解決的隨機(jī)性。就連歷史每一個(gè)已完成訂單，商家出餐時(shí)間的真值都很難獲得，因?yàn)槿藶辄c(diǎn)擊的數(shù)據(jù)并不能保證準(zhǔn)確和完整。商家出餐時(shí)刻不確定，這個(gè)隨機(jī)因素是永遠(yuǎn)存在的，并且非常制約配送效率提升。另外，在顧客位置交付的時(shí)間也是不確定的。寫(xiě)字樓工作日的午高峰，上電梯、下電梯的時(shí)間，很難準(zhǔn)確預(yù)估。當(dāng)然，我們不斷努力讓預(yù)估變得更精準(zhǔn)，但隨機(jī)性還是永遠(yuǎn)存在。對(duì)于騎手，平臺(tái)沒(méi)法規(guī)定每個(gè)騎手的任務(wù)執(zhí)行順序。騎手在配送過(guò)程中是自由發(fā)揮的，所以騎手執(zhí)行順序的不確定性也是存在的。為了解決這些問(wèn)題，我們想用魯棒優(yōu)化或是隨機(jī)規(guī)劃的思想。但是，如果基于隨機(jī)場(chǎng)景采樣的方式，運(yùn)算量又會(huì)大幅增長(zhǎng)。所以，需要進(jìn)行基于學(xué)習(xí)的優(yōu)化，優(yōu)化不是單純的機(jī)器學(xué)習(xí)模型，也不是單純的啟發(fā)式規(guī)則，優(yōu)化算法是結(jié)合真實(shí)數(shù)據(jù)和算法設(shè)計(jì)者的經(jīng)驗(yàn)，學(xué)習(xí)和演進(jìn)而得。只有這樣，才能在性能要求極高的業(yè)務(wù)場(chǎng)景下，快速的得到魯棒的優(yōu)化方案。

目前我們團(tuán)隊(duì)的研究方向，不僅包括運(yùn)籌優(yōu)化，還包括機(jī)器學(xué)習(xí)、強(qiáng)化學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域。這里具有很多非常有挑戰(zhàn)的業(yè)務(wù)場(chǎng)景，非常歡迎大家加入我們。

作者介紹

王圣堯博士，美團(tuán)資深算法專(zhuān)家，畢業(yè)于清華大學(xué)自動(dòng)化系，主要研究調(diào)度理論、運(yùn)籌優(yōu)化和系統(tǒng)仿真，中國(guó)仿真學(xué)會(huì)智能仿真優(yōu)化與調(diào)度專(zhuān)委會(huì)委員，出版專(zhuān)著《分布估計(jì)調(diào)度算法》。目前負(fù)責(zé)美團(tuán)配送智能調(diào)度算法團(tuán)隊(duì)的技術(shù)研發(fā)。