淺談滴滴派單算法

淺談滴滴派單算法導(dǎo)讀：說到滴滴的派單算法，大家可能感覺到既神秘又好奇，從出租車揚召到司機在滴滴平臺搶單最后到平臺派單，大家今天的出行體驗已經(jīng)發(fā)生了翻天覆地的變化，面對著每天數(shù)千萬的呼叫，滴滴的派單算法一直在持續(xù)努力讓更多人打到車，本篇文章會著重介紹我們是如何分析和建模這個問題，并且這其中面臨了怎樣的算法挑戰(zhàn)，以及介紹一些我們常用的派單算法，這些算法能夠讓我們不斷的提升用戶的打車確定性。1.為什么我們需要更好的派單算法說到滴滴的派單算法，大家可能感覺到既神秘又好奇，從揚召到搶單到派單，我們又是如何演進到今天大家的打車體驗的呢，我們首先來看一看，好的派單算法為什么是出行行業(yè)不可或缺的能力？回想幾年前，當我們還沒有滴滴的時候，只能在寒風(fēng)或者酷暑中等待可能有、可能沒有的揚招出租車，到后來可以從滴滴上呼叫一輛出租車，乘客可以在室內(nèi)相對舒適的等待車輛的到達，從線上到線下，乘客的確定性得到第一次的提升，然而這還不夠，搶單的模式注定我們的應(yīng)答率天花板不會太高，在15年，滴滴上線快車業(yè)務(wù)，我們從搶單演進到了派單模式，乘客的應(yīng)答率有了20個點以上的提升，很多時候能夠全天能夠高達90+（高峰&局部供需緊張應(yīng)答率會相對吃緊），乘客確定性再一次得到大幅的提升，由此可見，派單模式為滴滴創(chuàng)造了巨大用戶價值。再看近年來不斷興起的O2O業(yè)務(wù)，從國內(nèi)外的網(wǎng)約車公司，包括我們的友商Uber、Lyft都基于派單的產(chǎn)品形態(tài)進行司機和乘客之間的交易撮合，Uber上市的時候把派單引擎也作為核心技術(shù)能力放在了招股書中；再看我們的國內(nèi)的外賣平臺，核心派單系統(tǒng)的優(yōu)劣也決定了整個平臺的交易效率（單均配送成本）和用戶體驗（配送時長）；最后，整個大物流行業(yè)近年來也不斷在進行線上化的改造，如何撮合貨物和司機，以及更好的拼單能力也是整個交易環(huán)節(jié)的關(guān)鍵和商業(yè)模式是否成立的前提。從運人到運物，派單引擎目前越來越多的被應(yīng)用在現(xiàn)實的商業(yè)和生活中。2.派單問題初探言歸正傳，這里我們也來看一下，滴滴網(wǎng)約車平臺到底是怎么派單的。首先，我們來看下我們面對的是什么樣的問題？“訂單分配即是在派單系統(tǒng)中將乘客發(fā)出的訂單分配給在線司機的過程”這是一個看似簡單的，但實際上非常復(fù)雜的問題。說到這，可能有很多人就會問，能否就把我的訂單分配給離我最近的司機就好了？的確啊，實際上目前滴滴的派單算法最大的原則就是“就近分配”（70%~80%的訂單就是分配給了最近的司機），據(jù)我所知，目前世界上其他的競品公司（包括Uber），也均是基于這個原則分單的。我們進一步來看這個問題，如果我們只按照就近分配，先到先得的貪心策略，是不是能最好的滿足平臺所有乘客和司機的訴求呢？答案是否定的，原因就在于，如果我們只基于當前時刻和當前局部的訂單來進行決策，忽視了未來新的訂單&司機的變化，還忽視了和你相鄰的其他區(qū)域甚至整個城市的需求（注：在時序上來看，新的司機&訂單的出現(xiàn)會導(dǎo)致，貪心策略反而違背了就近分配的目標）。這就是為什么這個問題依然是非常復(fù)雜的原因。這里稍微有點抽象了，不過沒關(guān)系，我們再來一步一步的拆解一下訂單分配的問題，讓大家有個更好的理解：簡單看，在我們的平臺上，每一個時刻，都有N個訂單在被乘客創(chuàng)建，同時有M個司機可以被我們用來進行分配，我們強大的平臺能夠為派單算法給出司機的實時的地理位置坐標，以及所有訂單的起終點位置，并且告訴我們每一個司機接到訂單的實時導(dǎo)航距離。▍如果是1個訂單、1個司機看上去似乎就非常簡單了，我們直接把這個訂單指派給這個司機就好了嘛?！澳敲礊槭裁从袝r候附近有輛空車卻不能指派給你呢？”實際線上的系統(tǒng)會比這里稍微復(fù)雜一點，原因一方面有可能是司機正好網(wǎng)絡(luò)出現(xiàn)故障，或者正在和客服溝通等等導(dǎo)致司機無法聽單，另一方面的原因是并不是所有的車都能夠符合服務(wù)你訂單的要求，最基本的策略其實是人工設(shè)定的規(guī)則過濾。舉幾個最基礎(chǔ)的例子：規(guī)則A：快車司機不能接專車訂單

規(guī)則B：保證司機接單后不會通過限行限號區(qū)域

規(guī)則C：為設(shè)定實時目的地的司機過濾不順路區(qū)域

規(guī)則D：為只聽預(yù)約單司機過濾實時訂單

規(guī)則E：同一個訂單只會發(fā)給一個司機一次

……必須澄清的一點是這里的規(guī)則并不會造成分單時不公平的效果，而完全是為了業(yè)務(wù)能正常運行而設(shè)立的，這些策略承擔著保證業(yè)務(wù)正確性的重要職責。▍如果是1個訂單和2個司機假設(shè)這兩個司機都能夠分配給這個訂單，那么我們來看系統(tǒng)應(yīng)該是如何分配的。首先第一種情況是，同一時刻下，這兩個司機和訂單的距離都完全一樣的情況下，系統(tǒng)應(yīng)該如何分配？剛才也說到，我們平臺訂單分配最大的原則是就近分配，當距離完全一樣的情況下，當前我們系統(tǒng)上會主要考慮司機的服務(wù)分的優(yōu)劣，服務(wù)分較高的司機會獲取到這個訂單（注：服務(wù)分對分單的影響，簡單的理解可以換算為多少分可以換成多少米距離的優(yōu)勢，這塊不是今天的重點就不展開介紹），再說明一下，系統(tǒng)用到的是地圖的導(dǎo)航距離，而非人直觀看到的直線距離，有時候差一個路口就會因為需要掉頭導(dǎo)致距離差異很大；并且如果司機的定位出現(xiàn)問題，也會出現(xiàn)分單過遠的情況。那么我們來看第二種情況，如果A司機離的近，B司機離的遠，系統(tǒng)怎么派？這就簡單了，根據(jù)就近分配的原則，我們會把A司機分配給這個訂單。嘿嘿~~，假設(shè)我們再把問題設(shè)置的更加實際一點，當訂單發(fā)出時，B司機已經(jīng)在線并空閑，但是A司機還沒有出現(xiàn)（沒有上線，或者還在送乘客），但再過1s，離得更近的A司機突然出現(xiàn)可被分單了，假設(shè)我們使用先到先得的貪心策略，那么B司機就會被分給這個訂單，那就違背我們希望就近分單的目標了：（。所以看上去簡單，但實際情況下，算法還需要變的更好一些，這個問題我們把它叫做派單中的時序問題，我們后面再來看怎么解決。▍如果有N個乘客、M個司機最后我們來考慮最復(fù)雜的多對多的情況，這也是線上系統(tǒng)每天高峰期都需要面對的挑戰(zhàn)，我們一般把這種情況會形式化為一個二部圖的匹配問題，在運籌領(lǐng)域也叫做matching的問題，如圖所示：我們再把這個問題具象一點，假設(shè)這個時候我們有20個乘客，有20個司機，這些乘客都可以被這20個司機中的一個接駕，我們的系統(tǒng)需要把這20個乘客都分配出去，并且讓大家的總體接駕的時長最短。聽上去是不是有點復(fù)雜？我們套用下組合數(shù)學(xué)的知識，這其中可能的解法存在20的階乘那么多，20的階乘是什么概念呢？20

1918

…1=2432902008176640000，這個數(shù)巨大無比，想要完全的暴力搜索是絕對不可能的。這里需要更聰明的辦法。▍如果有N個乘客、M個司機，一會再來幾個乘客和司機？這就是派單問題最大的挑戰(zhàn)，我們不僅僅需要當前這個時刻的最優(yōu)，我們要考慮未來一段時間整體的最優(yōu)，新來的司機和乘客會在整個分配的網(wǎng)絡(luò)中實時插入新的節(jié)點，如何更好的進行分配也就發(fā)生了新的變化，所以如何考慮時序?qū)ξ覀兎浅Ｖ匾@個問題在業(yè)內(nèi)也被稱為DynamicVRP問題，這個Dynamic也就是隨時間時序變化的意思，這也就是為什么，滴滴的派單問題遠復(fù)雜于物流行業(yè)的相對靜態(tài)的貨物和路線的規(guī)劃問題。假設(shè)我們知道了未來供需的完全真實的變化，仿真告訴我們，我們的系統(tǒng)有可能可以利用同樣的運力完成1.2~1.5倍的需求量，這也是派單算法的同學(xué)持續(xù)為之努力的方向。想起前段時間的吐槽大會，大家提到文嵩曾說我們的派單問題比alphago還要難，其實這兩個問題還確實有點相似，都是在超大的搜索空間中找到一個近似最優(yōu)的解，而alphago則會在一個更加明確的游戲規(guī)則和環(huán)境中進行求解，它的難點在于博弈，而我們的派單問題難點在于未來供需不確定性&用戶行為的不確定性。近年來在學(xué)界，已經(jīng)有不少嘗試在利用類似alphago的技術(shù)進行VRP&TSP等方向的探索，強化學(xué)習(xí)結(jié)合運籌理論是未來運籌界非常前沿的方向之一（非技術(shù)同學(xué)可以跳過此處：））3.派單算法簡介上面我們已經(jīng)描述了什么是訂單分配問題，并且它所面臨的各種挑戰(zhàn)，那么在這里我們來聊一聊我們線上的派單策略是如何解決其中一部分問題的。在介紹具體策略之前，首先我們來說一下派單算法大的原則，目前派單策略主要的原則是：站在全局視角，盡量去滿足盡可能多的出行需求，保證乘客的每一個叫車需求都可以更快更確定的被滿足，并同時盡力去提升每一個司機的接單效率，讓總的接駕距離和時間最短。如何理解這個原則呢？我們說策略會站在全局的角度去達成全局最優(yōu)，這樣對于每一個獨立的需求來看，派單可能就不是“局部最優(yōu)”，不過可以告訴大家的是，就算在這個策略下，仍然有70%~80%的需求也是符合當前距離最近的貪心派單結(jié)果的。接下來，這里會拿兩個重要的派單策略的來進行介紹。（這里的內(nèi)容主要是講清楚策略的motivation為主哈，細節(jié)不再展開）▍批量匹配（全局最優(yōu)）派單策略中最為基礎(chǔ)的部分，就是為了解決上一節(jié)所提到的時序問題。這個算法幾乎是所有類似派單系統(tǒng)為了解決這個問題的最基礎(chǔ)模型，在Uber叫做BatchingMatching，我們內(nèi)部也叫做“全局最優(yōu)”或者“延遲集中分單”。這個Idea其實也非常直觀，由于用戶訂單的產(chǎn)生和司機的出現(xiàn)往往并不在同一時間點，在時間維度上貪婪的分單方式（即每個訂單出現(xiàn)時即選擇附近最近的司機派單）并不能獲得全局最優(yōu)的效果。一個自然的想法就是先讓乘客和司機稍等一會，待收集了一段時間的訂單和司機信息后，再集中分配。這樣，有了相對較多、較密集的訂單、司機后，派單策略即可找到更近更合理的派單方式了。找尋司機和訂單分配的全局最優(yōu)是一個二分圖匹配問題(bipartitegraphmatching)，一邊是乘客、一邊是司機，可用運籌優(yōu)化中各種解決Matching問題的方法進行求解。和再大家澄清一下，我們所采用的批量匹配的模式和大家所希望的，“把離我最近的司機派給我”的「就近派單模式」并不矛盾,我們也是尋求“乘客接駕時長最短”的最優(yōu)解，大多數(shù)情況下也是指派離你最近的司機，但充分滿足每一個乘客的“把離我最近的司機派給我”的個體需求,有些時候反而會導(dǎo)致部分乘客的需求無法得到滿足，比如說下面這種情況：當編號1和2兩個乘客同時叫車,如果完全按照“就近派單”的模式,雖然可以讓1號乘客先被接單,但是2號乘客會因為接駕距離較遠,導(dǎo)致等待時間變長,甚至因為最近的司機超出平臺派單距離,導(dǎo)致2號乘客叫不到車。1、2號乘客總等待時長15分鐘,平均等待時長7.5分鐘。我們采取的做法是,把距離較遠的2號車派給1號乘客。把1號車派給2號乘客,這樣一來,1號乘客和2號乘客,平均等待時長縮短為5分鐘,比就近派單,縮短了2.5分鐘,總等待時長縮短為10分鐘,比就近派單,縮短了足足5分鐘。通過提升全局的效率,才能轉(zhuǎn)化為讓更多乘客的需求得到滿足。▍基于供需預(yù)測的分單“如果有先知告訴我們未來每一個訂單的生成時間&地點，每一個司機的上線時間&地點，派單就會變成非常輕松的一件事”剛才所說的批量匹配的方法，理論上能夠保證那一個批次的匹配是最優(yōu)的。但是這樣就夠了嗎？很遺憾，以上所述的延遲集中分單的策略只能解決部分的問題，仍不是一個完全的方案。其最大的問題，在于用戶對系統(tǒng)派單的響應(yīng)時間容忍度有限，很多情況下短短的幾秒鐘即會使用戶對平臺喪失信心，從而取消訂單。故實際線上我們只累積了幾秒鐘的訂單和司機信息進行集中分單，而這在大局上來說仍可近似看做時間維度上的貪婪策略。若想即時的獲得最優(yōu)派單結(jié)果，唯一的方法是利用對未來的預(yù)測，即進行基于供需預(yù)測的分單。這種想法說來玄妙，其實核心內(nèi)容也很簡單：如果我們預(yù)測出未來一個區(qū)域更有可能有更多的訂單/司機，那么匹配的時候就讓這個區(qū)域的司機/訂單更多去等待匹配這同一個區(qū)域的訂單/司機。▍連環(huán)派單基于供需預(yù)測的分單有很大意義，但由于預(yù)測的不確定性，其實際效果很難得到保證。為此，我們使用了一種更有確定性的預(yù)測方式來進行派單，即連環(huán)派單?！斑B環(huán)派單，即將訂單指派給即將結(jié)束服務(wù)的司機，條件為如果司機的終點與訂單位置很相近”與預(yù)測訂單的分布相反，連環(huán)派單預(yù)測的是下一時刻空閑司機的所在位置。由于高峰期空閑司機多為司機完成訂單后轉(zhuǎn)換而來，預(yù)測司機的位置就變成了一個相對確定性的問題，即監(jiān)測司機到目的地的距離和時間。當服務(wù)中的司機距終點很近，且終點離乘客新產(chǎn)生的訂單也很近時，便會命中連環(huán)派單邏輯。司機在結(jié)束上一單服務(wù)后，會立刻進入新訂單的接單過程中，有效地壓縮了訂單的應(yīng)答時間、以及司機的接單距離。▍如何做的更好整個派單算法核心克服的是未來供需的不確定性，動態(tài)的時空結(jié)構(gòu)的建模，以及用戶行為的不確定性，對于這些不確定性我們現(xiàn)在更多采用深度學(xué)習(xí)方法對我們的時空數(shù)據(jù)&用戶行為進行建模預(yù)測。另外，我們的問題相對于傳統(tǒng)推薦搜索領(lǐng)域，多了一層匹配決策，我們到底積攢多久的訂單進行分配，對于每一個分配來說我們都面臨著分或者不分，現(xiàn)在分還是未來分配，并且分給誰的問題，這個問題天生就可以建模為強化學(xué)習(xí)問題，目前在我們的系統(tǒng)中也引入了強化學(xué)習(xí)方法來優(yōu)化更長期的收益。除了不斷去優(yōu)化之前說到的派單問題，整個派單系統(tǒng)還面臨著大量其他的挑戰(zhàn)，包括如何利用快車優(yōu)享等多個品類的運力進行跨層的最優(yōu)分配，如何同時對用戶&司機&平臺短期長期等多個目標進行優(yōu)化，如何同時優(yōu)化預(yù)約&實時訂單，如何在具備網(wǎng)絡(luò)效應(yīng)的場景下對算法進行評估，如果建立一個較為精準的仿真系統(tǒng)等等，這里既是挑戰(zhàn)，也是AIForTransportation中大量新的重新定義問題和創(chuàng)新