講師簡介

郝井華，美團點評技術(shù)專家，負責(zé)配送優(yōu)化策略研發(fā)工作。加入美團前，在清華大學(xué)從事復(fù)雜工業(yè)過程的智能控制、智能調(diào)度與優(yōu)化技術(shù)的學(xué)術(shù)研究和產(chǎn)品研發(fā)工作，主持設(shè)計了多個行業(yè)的智能物流調(diào)度系統(tǒng)并取得成功應(yīng)用，在該領(lǐng)域發(fā)表學(xué)術(shù)論文20多篇。

分享內(nèi)容

外賣從2013、2014年開始到現(xiàn)在，最近兩到三年發(fā)展速度非?？欤诳焖侔l(fā)展過程里邊涌現(xiàn)了很多很有難度很新的問題，這個里邊訂單的調(diào)度是比較有難度，也是比較有代表性的一個問題，希望通過今天的分享能讓大家對外賣的訂單調(diào)度問題以及我們的工作有一個比較深入的認識。

美團外賣從2015年初開始決定做配送，從最開始的一到兩萬單，已經(jīng)發(fā)展到現(xiàn)在的將近300萬單，目前需要十萬以上的騎手，這個規(guī)模相當(dāng)大。隨之而來的一個問題成本相對比較高，占到整個配送運營80%以上的成本，怎么樣讓我們的騎手工作效率高，是我們配送調(diào)度面臨的問題。

接下來我來具體介紹一下我們的配送業(yè)務(wù)怎么組織的。

這個上面有一些黃色的小圖釘，代表商家，藍色的區(qū)域是商家的配送范圍。也就是只有消費者在商戶的配送范圍以內(nèi)，打開外賣客戶端的時候才能看到這個商家，這個是商戶跟配送范圍的關(guān)系。

調(diào)度最大的挑戰(zhàn)是實時配送，我們希望三四十分鐘，中午一個小時內(nèi)給我們送達，難度體現(xiàn)在兩個方面，第一個是系統(tǒng)的穩(wěn)定性，第二個是線上的調(diào)度算法。我們實際上面臨的，從我們內(nèi)部系統(tǒng)截的一個屏，也是中關(guān)村，有二百多個騎手，一個紅色黃色的小原點代表一個騎手，每個騎手在高峰的時候有七八個甚至更多訂單，如果來了一批新的訂單，我們分配哪些配送員送能使得我們的效率高？這是我們所謂的訂單調(diào)度問題。

對訂單調(diào)度問題這個問題本身是可以分解的，也是目前外賣配送業(yè)界最主流的分解方法，一個是騎手路徑規(guī)劃，一個是訂單分配。騎手路徑規(guī)劃，針對騎手身上的訂單，規(guī)劃一個合理的路徑，以及這個路徑對應(yīng)的總的距離，總的耗時，每一單是否按時完成，這是騎手完成這一單對應(yīng)的指標。訂單分配，提供一個最佳路徑，這個最佳路徑作為一個訂單分配最基礎(chǔ)的信息。我需要做這種嘗試，如果按照這種分配它的結(jié)果會怎么樣，換一種方式它的結(jié)果會怎么樣。從分配方式是相互耦合，相互迭代的一個過程。

為了提高騎手效率，我們做了智能派單系統(tǒng)。對此，我們做了四個方面的主要工作：

第一個是針對大數(shù)據(jù)的分析與挖掘。因為我們積累了很多數(shù)據(jù)，每個騎手每天有幾億次的數(shù)據(jù)，還有相應(yīng)的物流數(shù)據(jù)，這些數(shù)據(jù)是我們建立比較準確的模型基礎(chǔ)。

第二個問題是大規(guī)模實時優(yōu)化，怎么樣去作一個快速的優(yōu)化，得到一個比較好的訂單分配方案。

第二個問題是分布式并行計算，解決當(dāng)計算量比較大的時候，單機上做多核的計算，滿足不了需求。

最后一個是場景回訪和仿真平臺。場景回訪是案例追溯，我們希望回溯當(dāng)時的場景，發(fā)現(xiàn)一些問題和錯誤，并能夠發(fā)現(xiàn)原因解決這個問題。另外一個是仿真，是O2O這個場景比較特殊的問題。普通的線上場景，我們通過應(yīng)用分析不同策略，哪一個策略更好。因為這個場景線下獨立，你這個策略應(yīng)用在這個配送區(qū)，它們之間的可比性成問題，每個配送區(qū)上千個訂單、幾百個騎手，這個仿真平臺有一個策略分析數(shù)據(jù)。

我們下一個就是大規(guī)模實時優(yōu)化，由于時間關(guān)系很難詳細展開，本質(zhì)上任何一個好的優(yōu)化方法，應(yīng)該兼顧兩個方面，我們要分析掌握這個問題所具備的特征，第二個選擇一個好的搜索機制，這兩個方面的結(jié)合才能選擇出一個真正好的優(yōu)化算法。針對這個外賣配送場景，我們是不是可以合單，這個訂單是不是快超時了，可以拿到很多跟問題相關(guān)的特征。

分布式并行計算主要在兩個環(huán)節(jié)，一個是計算本身，算法的計算本身，再一個是為算法準備數(shù)據(jù)。這個過程都實現(xiàn)了并行的過程，還有一個是拆借也是比較難的問題，在一個集群三到五秒鐘就跑完了，我們也是下了很多工夫，后來的時間只有原來的5%之內(nèi)。

對于這個仿真來說我們做的工作就是它本身能實現(xiàn)的工作，我們給它的實例數(shù)據(jù)，在仿真引擎下得到一個策略評估，我通過這個無論一個仿真集群短時間內(nèi)跑很多仿真集群，這個時候我不需要做線下，就可以得到很滿意的結(jié)果。

最后說一下未來的展望，主要是在兩個方面：一個是精益求精，算法本身的完善是沒有止境的，因為很龐大的搜索空間，怎么樣能夠盡量好地提升這個算法的效率，這個是一個非常關(guān)鍵的環(huán)節(jié)。第二個從算法本身，離線在線相結(jié)合的優(yōu)化在最近 AI的領(lǐng)域是比較受關(guān)注的，這也是我們研究推進的一個大的方向。

再一個是上下游協(xié)同優(yōu)化，我們配送調(diào)度的目標是希望提高運營效率、降低運營成本、提升用戶體驗，調(diào)度只是其中的一個環(huán)節(jié)。怎么樣合理指派這個訂單，事實上在美團外賣的整個物流配置、調(diào)度過程中，還有一些其他環(huán)節(jié)比如說像運力配置，是比較重要的。另外就是預(yù)計送達時間，你怎么樣更好設(shè)定管理我們用戶的預(yù)期，對提升效率、提升用戶滿意度是比較重要的。再一個就是價格引導(dǎo)，因為現(xiàn)在這種外賣的業(yè)務(wù)尖峰特點比較明顯，通過合理的價格引導(dǎo)，我們可以讓高峰時期效率更加平衡，在效率跟成本之間帶來一個更好的平衡。