講師簡介

郝井華，美團點評技術專家，負責配送優化策略研發工作。加入美團前，在清華大學從事復雜工業過程的智能控制、智能調度與優化技術的學術研究和產品研發工作，主持設計了多個行業的智能物流調度系統并取得成功應用，在該領域發表學術論文20多篇。

分享內容

外賣從2013、2014年開始到現在，最近兩到三年發展速度非常快，在快速發展過程里邊涌現了很多很有難度很新的問題，這個里邊訂單的調度是比較有難度，也是比較有代表性的一個問題，希望通過今天的分享能讓大家對外賣的訂單調度問題以及我們的工作有一個比較深入的認識。

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

接下來我來具體介紹一下我們的配送業務怎么組織的。

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

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

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

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

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

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

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

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

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

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

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

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

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