【51CTO.com原創(chuàng)稿件】2017年7月21日-22日，由51CTO主辦的以人工智能為主題的WOTI2017全球創(chuàng)新技術峰會在北京富力萬麗酒店隆重舉行。峰會期間，30+AI明星，數十場圍繞人工智能主題的精彩演講與圓桌論壇緩緩揭開面紗。除了場內的精彩演講，場外還有專門為AI愛好者搭建的動手實驗室和科技體驗區(qū)，這一切都讓本次大會亮點十足。

7月21日下午WOTI2017主會場，餓了么副總裁張浩進行了主題為《AI派來的外賣送餐員》的精彩演講。以下是演講實錄，讓我們先睹為快！

[[197646]]
餓了么副總裁張浩

大家下午好！很高興有機會和大家分享，也感謝WOTI給的這個分享平臺。同行業(yè)者已經從最早的外賣走向本地生活，我下面開始我的演講。我今天的分享分三個階段：第一，簡單介紹一下餓了么。第二，講一講AI在餓了么的應用。第三是我的主題，四個案例，給大家分享一下運籌優(yōu)化與機器學習應用實例。

當你把APP打開以后，首先看到的是交易平臺，就像咱們在淘寶和京東看到的是一樣的，只不過搜的不是衣服，主要是以交易為主，搜索、推薦、菜品挖掘等等這些。今天，我要給大家講的更多的是第二部分，本地的物流網絡。物流到現在很多年了，而且這個行業(yè)應用從運籌學到統(tǒng)計優(yōu)化，一直到機器學習，這三個合起來對我們現代物流體系有很大幫助。我們的用戶現在已經到2.6億，B端商家全國已經是130萬，更重要的是我們的配送員，在我們平臺注冊的配送員已經達到300萬，覆蓋全國兩千家城市地區(qū)。

互聯網行業(yè)，衣、食、住、行，淘寶、攜程、滴滴、餓了么分別代表四個方向，我想做個鋪墊，因為這個行業(yè)特點，和其他三家有什么不同的地方和獨特的挑戰(zhàn)。首先是淘寶，淘寶純粹是以用戶和商戶為主，線下當你下了單以后，線下走開放平臺，時效性通常是以天計算，所以它的挑戰(zhàn)更多的是能夠把轉化率提到最高，很短時間內找到自己想要的東西。而攜程也是一個純粹以線上用戶和商戶為主的交易平臺，基本上沒有線下訂單，不管是訂酒店還是別的都是線上完成，相對而言，滴滴和餓了么都是O2O的兩個比較大的方面，這里有不同之處在于，滴滴推薦搜索不是特別重要，不會上去搜這個車不喜歡搜另外的車，更多是通過系統(tǒng)最優(yōu)結果推薦給你，這是比較大的區(qū)別。另外一個比較大的區(qū)別是在時間上的要求，一般我們要求幾分鐘車到達，但上了車以后就是司機和乘客的問題了，平臺不會為此負責任。最后是餓了么，線上以用戶和商戶為主，但不同的是線下更為復雜，更重要的是時效性比如準時達、30分鐘、40分鐘，一旦超過這個時間，平臺將為用戶進行賠償，這對我有很大的挑戰(zhàn)。

在本地物流行業(yè)，或者即時配送，說即時配送更好一些，因為物流太大了。我們希望當你下了單以后30分鐘，整個交易不僅是菜出來送到你手里，整個完成過程我們希望控制在30分鐘。所以這里有幾個大的不同的地方，純粹線上交易，首先就是運籌優(yōu)化，第二才是學習，更重要的是大數據，我們通過離線計算，然后實時算法。

這是一個比較粗略的一覽圖，我們的業(yè)務里邊算法分三個部分。第一個是基于LBS，我們根據你的定位搜到本地配送范圍，所以LBS是我們最重要的服務。其次就是machine learning和optimization。對我們來說，站點網格配送范圍是最重要的，有了這些后面配送才有了最合理的結果。第二個是選址，除了餐廳以外，很多同行業(yè)也在做自主餐廳，加盟商在我們廚房里做品牌，選址就非常關鍵了。

后面的就簡單了，推薦搜索，我們是交易平臺。緊接著是供需預測、訂單運單預測，最后我們的物品是通過人，不管是走動還是騎電動車，給你送到手里，我們需要提前一個季度甚至半年做好規(guī)劃，我們需要根據歷史數據依據算法推測出，比如夏天北京經常下雨，大概需要多少運力和運單，所以供需預測和運單預測非常重要。用戶商戶分層，這個精細化運營要做到。后面智能補貼、路徑規(guī)劃，這都是實際物流當中非常重要的，動態(tài)定價指的是我們在配單的時候，必須根據當時的運力情況調整和控制流量，同時對路徑進行規(guī)劃。出餐時間、送餐時間的預估，這幾個是我下面在算法模塊里詳細講到的重點，我先跳過。我分兩個部分，第一個是講機器學習在餓了么業(yè)務的應用。第二個是在機器學習基礎之，上運籌優(yōu)化和機器學習在餓了么中的應用。

第一個是出餐時間預估，當你訂了一個餐以后，我們希望30分鐘能夠送到，這當中包括餐廳出餐時間，所以對餐廳的出餐時間預估是我們配送環(huán)節(jié)最難的一個，因為我們對它完全沒有控制，我們不知道它什么時候能出完。這點和滴滴的出發(fā)時間預估差別就在這個地方，滴滴場景大家可以看到左邊的圖，你在那個地方，通常希望一到兩公里之內就有車到達，這個平臺不用管。

右邊是餓了么場景，餐廳配餐時間受很多因素影響，首先是堂食的因素，餐品的品類，烹飪方式，訂單大小，實際情況當中餐廳備完以后他不會告訴你ready，必須通過機器學習方法預測。我們怎么做呢？我們從開始到現在大概經歷了三個版本，當然，任何做機器學習的最開始都會做線性模型，毫無疑問，沒什么特別講的。

誤差方面，我們當時調了很多特征，最后平均是6分鐘左右，后來我們用了非線性模型，誤差240秒左右。最簡單的統(tǒng)計特征，這個餐廳過去的出餐時間，他大概有多少人吃飯，今天是周五還是星期天，包括這個餐廳的菜品品類，比如做云南菜，他的菜品一定會花的時間更長，如果是麥當勞，30秒肯定能出來，這些特點都在里面。另外一個特點，我們會用到天氣，尤其天氣這個比較多。這些都會對誤差進行影響。我們做到240秒以后很長一段時間都難以再提高。

最后一個，我們今年開始用深度學習的辦法，因為我們可以把出餐方法當作時間序列進行處理，采用RNN、LSTN模型來做，現在誤差是3分鐘，平均時長不代表什么，因為餐廳爆單的情況下，或者特殊情況下，誤差會比較大一點。這是我們用的模型，實際當中會有不一樣。我們用的是兩層RNN模型，每層大概是1500個（英文），用了65%的dropout，右上角的圖是我們的公式，會隨機根據當時的概率來抓取。

第二個是行程時間預估，行程時間預估相對好一些，當騎手取到這個餐以后，開始從餐廳出來一直到客戶手里，整段時間是行程時間預估，因為我們有GPS采樣，所以我們知道他在過程當中花多長時間，這里的挑戰(zhàn)在哪里？這里的挑戰(zhàn)在于數據是非常難收集的。因為我們和其他的出行行業(yè)不一樣，我們整個過程有三分之一到一半時間，尤其大城市，都是在大廈里邊，高峰時間，上班時間，我們的白領也在大廈里邊，大廈里邊GPS定位是非常不準確的。

所以我們和別的公司合作，用WiFi來提高精確的定位。還有出餐時間方面，比較困難的是走的方式，不像滴滴Uber這樣開到公路上，有的時候步行等電梯上下樓等多種方式，而且樓宇里邊交通非常復雜。左邊這個圖是一個聚類算法的圖，大家可以看到這些點，這些點是我們收到的GPS位點，這里誤差非常大，如果全部用GPS位點來做，O點和D點，交通行業(yè)O點是起點，D是終點。

我們首先有一個聚類，把那些誤差比較大的先去掉，然后通過聚類以后把GPS位點弄到POI上，match到一個點上。我們做同樣的事情，去掉絕大多數噪音。第二個是軌跡聚類，當你知道行程起點和終點以后必須要知道軌跡，右邊的圖剛好是一條河，這個很討厭，我們很多時候不知道，也無法預測騎手怎么走，有的可能走小路，有的不知道走大路，所以預測的時候比較困難。軌跡聚類也有一些心得體會。

其中我們把GPS位點噪音點去掉，讓軌跡更加精準一些。下一個是講開單場景，組合優(yōu)化的問題，你不會從一個點只拿一個單，是很多的單，當你決定把這個單配給誰的時候，你要靠服務。還有行程時間預估，惡劣天氣，各種活動，還有節(jié)假日，如果是周末或者節(jié)假日，這些也是有影響的。

第二個，機器學習與運籌優(yōu)化算法組合在餓了么應用場景，最重要的是智能分單，什么叫智能分單？在沒有智能分單以前，分單是人來做的，整個分單過程是基于當地一個網絡，所以這個單不會全程分，以前都是人來做的，當你每天可能只有幾十單、幾百單的時候，有一個地圖，能看到誰和誰離單比較近，很快來解決問題。但是當量上來以后人是不可靠的，也做不到最優(yōu)，體量比較大的時候這是非常困難的。和其他推薦系統(tǒng)比，它的角色會更多，除了商家還有騎手，騎手還有用戶和團隊的區(qū)別，復雜度也更高。

大家可以看看右邊這個圖，一個騎手通常同時送五到十個餐，所以分單的時候是指數級的問題，我們需要知道他身上已有三到五單，是不是再給他另外五單，在時效性和準確性上要求比較高。這是我們做的第一個版本，當我們拿到這個問題的時候很自然就想到這是很經典的路徑規(guī)劃問題，因為你從這個點出發(fā)要經歷這么多訂單，最后還要回到起點，因為通常大家會聚集在一個地方，這是很傳統(tǒng)的車輛路徑規(guī)劃問題，這里輸入是訂單、騎手、騎手容量、成本，輸出是訂單和騎手間的匹配以及行走路線。優(yōu)化目標是最小化時間或者行駛距離，約束條件，比如騎手背單數，騎手數量，最晚到達時間等，當你下一個單的時候，我們說40分鐘到，這是最晚到達時間，我們希望99%都能在40分鐘到。

VRP問題，你到了目的地之后還需要把你的東西拉回來，左邊TSPB的問題，還有TSPTW的問題，當你有多個車的時候是MTSP，在此基礎上演進一下VRP的變種，比如最遠不超過多少，這些都是這個問題的變種，對我們完全不是新的東西。

我們使用的一種方法是模擬退火算法，大家看看左邊的圖，稍微講下背景。這是一種很傳統(tǒng)的運籌優(yōu)化問題，方法有很多，當我們量大的時候，比如動態(tài)優(yōu)化，大家都知道VRP問題，或者通常組合問題，是很難找到最優(yōu)的解，所以更多的是用（英文）。這是隨機迭代算法，還有別的算法，這里文獻就特別多了，大家如果搜的話有上千篇文章，書有很多本，有興趣大家可以看看。我們采用的一種算法是模擬退火算法，是隨機的最優(yōu)算法。

看看右邊的圖，首先是隨機產生一些解，我們定義下來目標函數，這里最關鍵的是隨機的對當前的解，跟物理退火一樣，找到最優(yōu)解，沒有最優(yōu)解沒關系，數量有一個上限。這是概率算法，不一定找到最優(yōu)，所以下面的判斷是是否達到迭代次數，因為我們可能無限次解下去，達到以后就終止。這是整個算法的過程，現在這個模擬算法已經成熟了，更多挑戰(zhàn)是規(guī)模比較大的時候，分布式計算怎么更有效一些，這個也有很多文獻可以看。用的方案也比較多，比如大型模擬，生產調度，控制工程，機器學習，神經網絡，信號控制等等。

現在我們的方案用的是2.0，基于代價函數的優(yōu)化問題。VRP方案遇到的挑戰(zhàn)在哪里？剛才講到計算復雜度問題，這只是一個方面，更重要的是我們對每個（英文），整個結果就完全的不符合邏輯，這是我們遇到的最大困難。時間預估的不準確性，造成從A點到B點預估時間是不準確的，這個時候做出的結果往往很差，尤其小城鎮(zhèn)，大城市還好，因為有足夠的樣本量，比如北京，可以大概估計一下時間。但小城市很難，很多時候POI都到了鎮(zhèn)政府，而不是餐廳，所以這種情況下我們的VRP完全沒有用。除此之外，還有基礎的送餐習慣，很多時候騎手不會按照你推薦的送，他會這個先送那個后送，影響比較大。

所以我們現在的方案是這樣的。簡單講，這是一個代價矩陣，我們有N個訂單包，N個騎手，這么一個二維的矩陣，我們希望能夠把每個訂單包都分到一個人身上，中間的就是代價矩陣，希望輸出的是訂單包和騎手之間最優(yōu)匹配。這里的代價定義和計算方法也經過幾版的迭代，最開始毫無疑問的，當你決定把一個單分給騎手的時候，代價是其他單不會因此受影響，也不希望他距離跑太長，因為電動車跑兩公里送一單肯定是最壞的選擇。所以我們最開始用規(guī)則的方法，通過大量的離線分析，比如大概20個特征，這些特征每個權重多少，算出來以后，后面是優(yōu)化問題，最后的結果是得到右邊的矩陣。一個訂單分給了這個騎手，匹配用的什么算法？我們用的是比較成熟的最優(yōu)匹配KM算法，KM算法求的是完備匹配下最大權匹配，KM算法也有很多流程，和開始的VRP解決方案比較接近，不斷優(yōu)化。最開始算法流程初始化可行頂標的值，用匈牙利算法尋找完備匹配。

當然，我們還有很多的不足，我們大概解決了基本的問題，但后來我們意識到，分單如果有一個訂單來了，馬上分給一個騎手去接，這往往不是最優(yōu)選擇，如果你再等兩分鐘，同樣餐廳同樣路線上會出現更多的單，所以就出現了蓄水，也許等兩分鐘，等更多的單。蓄水之后我們通過兩個單打包出來，這是2.1版本。打包的時候還有很多不足之處，任何做機器學習都要用規(guī)則來，什么樣的包可以打在一起，同取同送，GPS不準的情況下同取同送帶來的結果就是訂單完成不了，比如這棟樓A座和這棟樓B座。所以2.2版本，去掉了打包規(guī)則，我們用機器學習方法學習，人工調度的時候，什么樣的單人工分成什么樣的包和模型，用訂單相似度模型，但是這還不夠。

因為我們推廣過程當中發(fā)現，在不同的地方有不同的習慣，而這個習慣會造成對騎手滿意度和推廣難度很大的影響。所以我們又出了一個新的叫訂單與騎手匹配模型，我們來定什么樣的是好的，剛才講的更多是我們通過離線算出來的，用一個公式去match全國幾千個站點分單邏輯，這是做不到的，用這種規(guī)則一定做不好。所以我們做了訂單與騎手匹配模型，把數據按照當地站點取出來，我們進行學習，學到人工調度習慣，我們機器學習抓住這個特征，真正做到當地化、本地化，這是我們2.3標準。每個站每個地區(qū)都是獨特的模型。我們正在做的是3.0版本，增強學習，大家對這個也比較熟悉。

2.3的時候在模型上就很難再提高了，但不管怎么說，模型更新一定是離線過程，可能一個星期，可能一天，我們希望變得更快，怎么更快？現在比較流行的增強學習，我們通過在線反饋，騎手喜不喜歡，如果不喜歡會換單，這個信號我們曾經抓到了，但是通過離線進行補償，通過增強學習在線上自動學習，還在開發(fā)過程中。

整個算法過程是這樣的，但最大的問題是我們的基礎數據，剛才我反復提到POI點，不管算法怎么分，它看到的是我們告訴它從這個點到那個點，POI的準確性一直以來是最大的挑戰(zhàn)，所有以LBS為服務的任何公司，POI相當于地址庫，就像Google map為什么值錢，因為它的POI做的好，導航算法是你優(yōu)化的，光有算法沒用，重點在POI的準確性，當然，Google不僅僅在美國，他在全世界做的都比較好，這是他的財富，就是數據。我們自己也在不斷積累POI。ETA、出餐時間預測、騎手模型、餐廳畫像，這些都需要長期提升。騎手模型講的是這個騎手他的習慣、他的能力，對路線的熟悉程度，包括比如給他五個單他能不能準時送到，什么時候單可以分給某個人，他比較靠譜。餐廳畫像也很重要。

最后一個是最優(yōu)餐廳選址問題，這個跟菜鳥搞倉儲的不同，但意思是一樣的，比如菜鳥決定在全國建主站網，倉庫負責哪個區(qū)域，從A倉庫到B倉庫怎么設計路線，這是比較經典的FACILITY LOCATION PROBLEM。在城市里面我們希望餐廳有交錯，能夠囊括最大的用戶。左邊的公式，從兩個點之間他們的代價也最小，這個是我們現在還在經營的業(yè)務，叫未來餐廳，我們希望自己能夠在最便宜地點選到最大化潛在的最多GMV增長。

最后是總結。很多朋友不太清楚，實際上本地生活場景算法非常大，可能送外賣比較多，但想象它不是外賣，而是運籌優(yōu)化，尤其因為是本地生活圈問題導致很多不規(guī)則的東西，所以挑戰(zhàn)非常非常多，不比任何一家互聯網公司小。第一個問題，基礎數據的完整性和準確性，這點沒有人幫到我們，因為行業(yè)特點是靠自己，長期通過人來收集這些數據，餐廳、騎手，甚至電梯難易程度對我們的算法都有影響。

還有對人的行為理解，人的行為理解，在我們分單的時候覺得這樣是最好的，但實際運營當中我們受到很多阻力，別人不喜歡這樣做。比如追單，在五樓接了一個單，剛剛到樓下同樣分一個餐廳的單，騎手不喜歡，好不容易下來的不想再取單了，我們發(fā)現你這個時候再回去總的時間會更少，但騎手不喜歡，他覺得跑上去麻煩，很多時候要等電梯，或者有各種他不喜歡的行為。這都是我們后來意識到，很多時候需要和業(yè)務結合才能有一個完整的解決方案。最后一個，優(yōu)化算法與機器學習的結合，在物流場景更多的是成本優(yōu)化，機器學習更多是對因素的學習。所以優(yōu)化算法和機器學習只有結合起來才能完美解決我們的這些問題。我的內容就分享到此，謝謝大家！

51CTO記者將持續(xù)為您帶來WOTI2017全球創(chuàng)新技術峰會前方精彩報道，敬請期待！

【51CTO原創(chuàng)稿件，合作站點轉載請注明原文作者和出處為51CTO.com】