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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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