講師簡(jiǎn)介

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

分享內(nèi)容

外賣從2013、2014年開(kāi)始到現(xiàn)在，最近兩到三年發(fā)展速度非常快，在快速發(fā)展過(guò)程里邊涌現(xiàn)了很多很有難度很新的問(wèn)題，這個(gè)里邊訂單的調(diào)度是比較有難度，也是比較有代表性的一個(gè)問(wèn)題，希望通過(guò)今天的分享能讓大家對(duì)外賣的訂單調(diào)度問(wèn)題以及我們的工作有一個(gè)比較深入的認(rèn)識(shí)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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