?桔妹導讀：IT技術的不斷更新推動著公共交通的概念不斷在深度和廣度上擴展，深度上，精準的公交ETA和實時到站等資訊可以幫助用戶更好的規劃行程時間；廣度上，配合單車，網約車等共享出行方式可以幫助用戶更好的決策出行方式，

1. 資訊公交服務簡介

公交，在傳統意義上主要指城市內的公交巴士和地鐵通行方式，因此傳統的互聯網資訊公交服務的核心功能便是路徑規劃服務，即：根據用戶給出起點O和終點D，給出通過公交地鐵可以到達的方案，在進入移動互聯網和物聯網時代后，一方面，快車、單車等共享出行方式滲透率大大提升，成為公交的重要補充方式；另一方面，隨著物聯網和大資料的應用帶來的實時資訊可以更好的輔助用戶出行決策，在公交服務中的應用愈加重要，因此查詢公交實時位置相關的服務成為又一個公交服務的核心功能，下面將對路徑規劃和實時公交這兩個服務在滴滴的實作進行介紹，

2. 公交服務中的技術挑戰

▍2.1 路徑規劃服務

整體架構如下：

總體來說，路徑規劃分為算路和排序兩個階段，在算路階段召回能到達用戶指定OD的線路，分為離線和在線兩個階段；排序階段綜合步行距離，到達時間，換乘次數，乘車價格等不同的用戶偏好給出最匹配用戶的N條結果，

2.1.1. 離線算路與在線算路

路徑規劃問題的基本思路是首先將城市的公交和地鐵線路資料，以站點集合為頂點集合V，每條公交或地鐵線路上相鄰的兩站用邊連接起來得到有向圖，同時，由于站點之間換乘需要一段步行是常見情況，因此還需要將距離較近的兩個站用步行路網也用邊連接起來（圖中的藍色虛線），最后，以每段路徑的預估消耗時間作為每條邊的權重，就得到了一張有向帶權圖，有了這樣一張有向帶權圖后，當用戶輸入起點和重點請求換乘路線資訊的時候，問題就轉換為：已知有向帶權圖中的起始節點O和終止節點D，搜索找到O和D之間的K條較優通路，

這類問題常規的解法有BFS，Dijkstra，Floyd等，但在實際應用中，基于性能考慮，都不會在線實時的用這張圖去計算，而是將一部分預處理的作業轉移到離線階段，

2.1.1.1. 離線算路

盡管離線計算對性能的要求比在線低很多，但由于加入了步行之后的公交地鐵有向圖網路每個頂點的分叉非常多，直接使用BFS，Dijkstra這類演算法依然會難以忍受，因此滴滴根據自身的實際的資料情況進行了以下幾種優化：

路網分層
在現實中，我們往往會有一些大家熟知的大區之間的聯絡線路，如地鐵4號線可以從中關村區域到大興區域，當我們從海淀其他區域自己規劃乘車去大興的時候也會先想到坐到地鐵4號線的某站到大興區域的某站，然后再看從這一站怎么到達最終目的地，這當中大區之間為人熟知的聯絡線路其實就是一種先驗資訊，借鑒這種思路，我們在離線階段抽象出若干較大片的區域，提前計算好這些區域之間幾條主干通路，在線時，將起終點轉換為區域，取出事先已算好的區域通路路徑，可以大幅降低計算成本，

雙向搜索(Bidirectional Search)
正如他的名稱一樣，借鑒大家實際應用中找路線的想法，同時從起點和終點掃描各自經過相向的線路，尋找其中有沒有共同的車站（或步行可達的車站），雙向是一種非常有效的提效手段，BFS，Dijkstra都有雙向的變種，
使用估值函式剪枝
在搜索中一個常見提升性能的最重要的策略就是剪枝，通過一些耗時小的估算，提前結束一些明顯會比當前路徑更差的，我們采用的是AStar演算法，

2.1.1.2. 在線算路模塊

在線算路模塊，需要根據用戶輸入的起終點在上一步離線算路模塊中選出最佳方案，并根據實時車輛情況，計算單車拼乘和網約車拼乘方案，

多模實時換乘
在離線算路階段產出的方案，根據用戶輸入的起終點選擇最佳上下車站點，再根據實時單車/網約車資訊，生成步行/騎行/網約車前往站點來接駁公交/地鐵的方案，
在線剪枝
多模接駁階段會產生大量方案，為了提高線上服務性能，需要將方案進行剪枝，包括將不在運營時間的方案、價格明顯偏高，網約車排隊時間過長，或單車數量較少區域的方案去除，同時，將多個路線一致的方案合并成一個，
粗排計算
經過前面處理后，得到了所有可行方案，下面需要對這些方案進行排序，選擇最優的方案，粗排計算階段需要根據每條方案的基礎特征（例如耗時、路程等），對上千條可行方案快速計算評分，根據分數選出候選方案集送給后續排序模塊，

2.1.1.3. 排序模塊

ETA
ETA是用戶選擇時最主要的參考資訊，為了更精準地得到方案的耗時，推薦出實時最佳方案，滴滴利用路況資訊、歷史通行耗時等資訊，借鑒網約車的經驗，建立了公交車專用ETA模型用來估計車輛當前位置到達站點和到達目的站點的時間，更精確地預計了用戶的等車時間和到達目的地時間，

網約車模型收益

精排
多模換乘推薦引擎中需要比較眾多包含多種交通工具的候選方案，而將包含多種不同交通工具公平地進行比較，并推薦出若干個符合大眾心目中最優的方案是一個較為復雜的問題，除了基礎特征外，還需要從方案中挖掘出更多資訊，增強模型的表征能力，我們設計了包含預計通行時間、換乘次數、步行距離、綜合距離、地鐵距離、單車距離、價格、發班時間、備選車次數量、交通工具型別、是否在主干道行駛、是否公交專用道、各種交通工具占比等若干高級特征，在線計算出特征后，提供給后續排序模型使用，
Rerank和多樣性
為了兼顧用戶的個性化訴求，最終展示給用戶的N條方案時，通過rerank來保證整體方案的多樣性，一般用戶的個性化因素包括價格是否敏感，地鐵偏好，步行長短，換乘偏好等等，以點擊率作為整個公交方案的線上觀察指標，

▍2.2 實時公交服務

隨著傳統行業的線上數字化改造，已有200多個城市公交巴士都配置了智能硬體設備，可以實時上報公交的位置，以此為基礎，向用戶提供實時公交位置，預估等待時間等相關資訊成為公交服務的又一基礎功能，整體架構如下：

2.2.1. 資料接入

實時公交的資料來自公交公司和交委，然而由于沒有統一的標準，上報的格式，各欄位的含義都不一樣，因此滴滴制定了一套自己的資料規范來適配各地資料，從而對應用層提供統一格式的資料，除了格式的統一之外，由于公交站點和線路的名稱，ID編碼規則各地也都會不定期發生變化，因此，為了保障應用層使用的繼承性，滴滴對所有資料也定義了自己的ID編碼規則，在資料接入階段，還有一個重要的作業就是對資料物體進行映射，

2.2.2. GPS位置補償

位置的正確性和時效性是實時公交服務的核心能力，如果用戶在線下看到車的位置和APP上的位置有比較大的差別，就會失去信任感，流失到競品，

然而各地上報的GPS都有一定的延遲，且延遲有不可預知性，如果完全依賴上報的位置資料呈現給用戶，在極端情況下（如隧道等網路不好的地方），可能會出現用戶真實看見了一輛車但是在APP上未出現的情況，因此必須通過AI的方式對實際的位置進行估算才能給到用戶準確的資訊展示，在這里，源資料上報的時效性是位置預測時最大的困擾，如下圖一所示，對于不同的延遲時間，誤差和延遲的比例正相關，

延遲時間統計圖利用滴滴大資料的優勢，首先會根據實時的路況資料（該路段的平均行駛速度，紅綠燈等待時間等）對公交的實時速度進行預估，對沒有實時路況和特殊路段，會根據歷史上同時間同路段的速度對路況進行預估，最后會使用公交靜態平均速度進行兜底，完成對延遲時間內位置移動的補償，

另外，由于各地上報GPS的規范性不一致，還需要處理一些邊界問題，如：GPS的延遲上報如果處理不好，在前兩站給用戶的傷害更為明顯：車輛可能在已經駛過第二站后才上報了第一個GPS點，這意味著，如果我們不對車輛的發出時間做預估，而完全依賴上報的資料的話，第二站用戶看到的永遠是車輛等待發車，而在前兩站會比較容易出現的特殊情況是：