當我們打開滴滴使用網(wǎng)約車服務(wù)時，出發(fā)前我們往往會關(guān)注要走哪條路，這條路要花多長時間，要花多少錢，有多少個紅綠燈，路況是否擁堵......這些都與路徑規(guī)劃密切相關(guān)。路徑規(guī)劃對滴滴來說十分重要，它是網(wǎng)約車服務(wù)的重要一環(huán)，與用戶體驗直接相關(guān)，一次糟糕的“繞路”可能會引起一次投訴進線，甚至影響用戶留存；而良好的路徑規(guī)劃不僅可以顯著提升司乘雙方的使用體驗，還能讓司機少堵在路上，進一步提升整體出行效率。

1. 

類似于語言任務(wù)中的token，物理世界的道路會被建模成一段一段的link，這些link都具有唯一的id以及對應(yīng)的道路屬性，比如長度，方向，道路等級等。對于路口來說，進入路口的link和出路口的link往往都有多個。拿北京舉例，北京的路網(wǎng)包含大約200W個link，網(wǎng)約車訂單可能會包含數(shù)十甚至上百個路口，在如此龐大且復(fù)雜的路網(wǎng)中和較為苛刻的時間限制下，規(guī)劃出高質(zhì)量的路線絕非易事。

圖中每一個帶箭頭的紅色線段表示一個link，可以看出不同link之間的長度差別是比較大的。

此外，我們知道物理世界的道路是會發(fā)生改變的，這種改變可能是永久的，比如修路，也可能是臨時的，比如交通管制。所以路網(wǎng)數(shù)據(jù)也是動態(tài)的，實際上目前我們地圖的路網(wǎng)數(shù)據(jù)是天級更新的，這也加大了路徑規(guī)劃任務(wù)的復(fù)雜度。

從實際業(yè)務(wù)來看，和自駕推薦走更快，更通暢的路線不同，由于網(wǎng)約車會基于里程、時長計費，我們需要同時考慮時間、距離、價格、安全因素，推薦相對快又相對便宜的路線?？紤]用戶的偏好，讓用戶在安全、快速到達目的地的同時，讓行駛距離盡量短，總花費盡量少，是我們路徑規(guī)劃的核心原則。但很多時候“快”和“近”很難同時滿足。距離更短的路往往是次干路或者支路，紅綠燈多，堵車可能性更大；而繞遠的高速路或者環(huán)路，通行能力更強，只要不極擁堵，車速通常更快，反倒用時更短。

有乘客希望更快，也有乘客希望不繞遠。為了盡量平衡，從去年3月起，我們率先在網(wǎng)約車上線了“選擇路線”功能，充分考慮乘客的出行偏好，提供最多三條路線供乘客選擇(拼車、一口價訂單司機需按照平臺指定路線行駛)；并聯(lián)動司機服務(wù)部鼓勵司機主動詢問乘客是否有常走路線。今年8月，我們還進一步在北京、杭州、深圳、南京、西安、廈門等28個城市試行“行前多路線選擇”功能。乘客實時呼叫網(wǎng)約車，發(fā)單前可以根據(jù)路線標簽、預(yù)估里程、行駛時長等信息選擇最合適的路線，系統(tǒng)自動同步至司機端導航。

綜上，想要做好讓司乘雙方都滿意的路徑規(guī)劃是一件極具挑戰(zhàn)的事情，但是這也為我們進一步提高出行服務(wù)質(zhì)量提供了機遇。

路徑規(guī)劃是指給定起終點的情況下，規(guī)劃出一條或多條由起點到終點的路線。傳統(tǒng)的路徑規(guī)劃是一個圖論問題，當路網(wǎng)中的權(quán)值都是靜態(tài)的時候，使用dijkstra等算法就可以求出權(quán)值之和最小的路線，比如求出兩點之間距離最短的路線是容易的。然而在很多場景需要動態(tài)權(quán)值，調(diào)整權(quán)值大小也需要大量經(jīng)驗，目前線上采用的方式是先使用基于圖論的算法生成一批低權(quán)值的路線，然后再經(jīng)過基于機器學習算法的排序模型的篩選，這個過程涉及到粗排，精排，rerank，最后將排名靠前的路線透出給用戶選擇。這個路線規(guī)劃系統(tǒng)涉及的鏈路還是比較長的，不同于基于圖論算法生成高權(quán)值的路線，我們嘗試探索一種基于AI算法的路線生成方式。

得益于滴滴海量的出行數(shù)據(jù)尤其是高質(zhì)量的軌跡數(shù)據(jù)，我們可以利用深度學習技術(shù)去挖掘和學習司機的駕駛行為以及用戶對路線的偏好，借助訓練出的深度模型在短時間內(nèi)為用戶規(guī)劃出滿意的路線，降低線上的偏航率。

我們這里可以把尋路的過程和AlphaGo下圍棋的場景進行類比，司機在路網(wǎng)中行駛猶如棋手在棋盤上落子，初級棋手往往通過記憶棋譜來獲取暫時的領(lǐng)先，而最終贏棋往往要求棋手有“大局觀”，每一步的落子考慮到之后棋局的演變，關(guān)鍵在于最終贏棋，而不在于一時的得失。尋路過程也是需要往后多看幾步的，因為在某個路口的選擇眼前可能看是最優(yōu)的，放在全局看則不一定是最好的選擇。我們探索路線生成的過程是和AlphaGo“進化”過程是相似的[1]，是一個從監(jiān)督學習到強化學習的過程。

3. 

規(guī)劃最符合司乘習慣的路線：

從監(jiān)督學習到強化學習 

圖中移動的小車展示了beam search在路徑規(guī)劃中的應(yīng)用，在小車前進的過程中，我們可以給不同的路線打分，維護得分最高的topK路線，直到小車抵達終點。紅色的路線表示最終得分最高的路線，也是最符合用戶習慣的路線。

▍3.2 行為克隆的問題

行為克隆實際上屬于監(jiān)督學習的范疇，在AlphaGo中如果讓agent純粹的去學習棋譜中的走法，它很難打敗更加專業(yè)的棋手，所以AlphaGo引入了強化學習并搭配MCTS這一搜索策略，從而大大提升了對弈的勝率。同樣的，純粹的擬合專家軌跡是存在問題的:當尋路agent在某個路口判斷錯誤，那么就會進入到?jīng)]有遇到過的狀態(tài)，在這種狀態(tài)下agent的判斷容易出錯，而錯誤的累積會容易導致尋路過程演變成“一步錯步步錯”的結(jié)果。雖然我們的模型具有一定的泛化能力，尋路agent也可以找到終點，但由于我們沒有顯式的引入偏航后的監(jiān)督信號，尋路agent往往需要更多不必要的“繞路”才能回到理想的路線上來。圖中藍色軌跡是小車偏航后所致，小車既有可能回到demo軌跡（紅色路線）上來，也有可能越來越遠，偏離demo軌跡，因為模型并沒有學習到發(fā)生偏航后該如何快速糾正。

▍3.3 強化學習的應(yīng)用

強化學習是近年來解決行為克隆帶來的問題的熱門方向。在文本生成領(lǐng)域，seqGAN通過判別器（簡稱D）來指導生成器(簡稱G)的訓練，在G生成下一個單詞時，使用MCTS和D來評估這個單詞的好壞，通過reward作為反饋，使用Policy Gradient來更新G的參數(shù)，從而增加reward大的單詞的生成概率。與此方法類似的還有在游戲系列數(shù)據(jù)集上表現(xiàn)優(yōu)秀的GAIL，AIRL，這些方法的主要思想是另外訓練一個能夠指導生成網(wǎng)絡(luò)更新的評估網(wǎng)絡(luò)，缺點在于略顯復(fù)雜，訓練難度和計算量較大。

AlphaGoZero通過“自己與自己對弈”的過程大大增強了棋力，類似的，我們想要通過生成學習的方式來增強路線引擎的能力。這里我們采用Q-learning的方式來學習一個尋路策略，為了加速模型收斂的速度，我們這里先使用前文提到的行為克隆的方式訓練一個能夠容易走到目的地的基礎(chǔ)模型，然后使用該基礎(chǔ)模型在路網(wǎng)上尋路，生成大量的采樣軌跡，如果在某個狀態(tài)，模型采取的動作與用戶一致，則給該狀態(tài)-動作對以+1的reward，相反如果在該狀態(tài)模型采取的動作與用戶不一致，則給該狀態(tài)-動作對的reawrd為0。這種人為設(shè)定reward的方式既沒有引入對抗學習的過程，也不要額外學一個reward函數(shù)，計算量大幅度減小，同時它可以有效克服行為克隆帶來的狀態(tài)分布偏移的問題。

圖中大致展示了我們的訓練流程，通過老模型的self-play獲取新的軌跡數(shù)據(jù)，將采樣得到的新軌跡和真實軌跡融合訓練，更新我們的策略模型，該過程是可以不斷迭代的。經(jīng)過多輪迭代后，路線生成模型的分類準確率雖然沒有明顯提升，但是生成軌跡質(zhì)量更高：與真實軌軌跡的重合率明顯提高，偏航后返回到demo軌跡的速度更快。這是讓人驚喜的結(jié)果。

4. 

滴滴的路線引擎每天需要處理超過400億次的路線規(guī)劃請求，我們致力于為平臺用戶提供安全，快捷的路線服務(wù)。本文介紹的路線生成方式是深度強化學習在路徑規(guī)劃業(yè)務(wù)上落地的一次探索，主要用來降低偏航率?？紤]到路徑規(guī)劃業(yè)務(wù)的復(fù)雜性，我們會從更多的方向（比如躲避擁堵）來打磨我們的路線引擎，讓它變得更加智能。

當然目前路線引擎還有它不完善的地方，還需要持續(xù)的迭代和優(yōu)化，也歡迎大家給我們提供寶貴的意見。我們團隊將會持續(xù)優(yōu)化路線引擎系統(tǒng)的性能，迭代路線規(guī)劃的算法，為司機和乘客創(chuàng)造更大的用戶價值。

引用

1. Mastering the game of Go with deep neural networks and tree search[J]. Nature, 2016, 529(7587):484-489.

本文作者

?