多等5分鐘，少走半程路：一場演算法和道路資訊之間的鬥智鬥勇 | 先聲探祕
AI的浪潮勢不可擋，在無數大眾最熟悉的生活場景中，其實蘊含著許多未被發現的祕密。
這些“深藏功與名”的AI技術，在最基礎的功能背後，卻演繹著資料和演算法最動人的一面。
地圖導航中，演算法與千變萬化的道路資訊之間“鬥智鬥勇”，對地圖中常規的路線規劃進行改造，讓“未來出行”成為可能。
所謂路線規劃就是“兩點之間直線最短”的簡單明瞭嗎？——天真。
要知地圖產品在為使用者規劃路線時，那可是一場人類與複雜演算法、道路資訊之間的鬥智鬥勇。
各種地圖的演算法工程師們，不僅要面對瞬息萬變的路況資訊，還要應對各種各樣“意料之外情理之中”的干擾。
所以如何綜合利用好各類資訊，快速提供準確有效的出行方案，就成了“路線規劃”要解決的切實問題。
小王是一個在北京西二旗工作的資深“碼農”，雖是地道的北京人但因為多年搖不上號只好暫時上了外地牌照。
由於五環在工作日早晚高峰期禁止外地牌照車輛行駛，小王上下班通常會繞開五環或者早早出發躲避限行。
週一早上，公司組織集體去西五環附近的北京園博園參加活動。早上8點40多，大家都準備從公司出發了，因為此時五環還是限行狀態，不少人憑著習慣繞路上了六環。
小王開啟地圖查路線，導航卻提醒他：再等5分鐘後出發，就可以避開限行時間直接走五環。既能節省時間和油費，還不會違章。
最終小王雖然多等了5分鐘，卻比其他人早到20分鐘，還少走了一半路程。
目前大部分地圖導航還無法結合實際情況推薦出發時間和路線，百度地圖新推出“多等5分鐘少走半程路”，通過預估未來交通狀況並提供躲避擁堵、限行路線。
新功能的背後是一整套路線規劃的複雜流程。演算法為使用者規劃路線時，要經過路線規劃、特徵提取、路線篩選和路線排序四個步驟，百度地圖是如何改造路線規劃的四個步驟，滿足使用者智慧化出行需求的呢？
1 針對時間規劃路線
為了實現根據時間推演進行路線規劃，常用做法是將連續的時間點分散成多個時刻，在每一個時刻都生成一套權值，並在路線搜尋過程中恰當切換不同權值，從而實現針對時間進行路線規劃。
在演算法選擇上，一般要考慮預處理時間、線上計算效能、路線效果等要素。A*演算法和CRP演算法（基於剖分的路線規劃演算法）由於預處理時間較短、資料較小，天然具有快速編譯及生效的優點，是面對此類問題的主流選擇。
2 基於海量資料合理預測
有了完整的路線資料後，可以獲得更加精確的預計到達時間，這也是演算法進行後續決策的基礎。由於預計到達時間與路況息息相關，二者都有著豐富的歷史資料作為參考，在進行未來時間預估時，演算法可以根據歷史資料和當前道路狀態合理預測，從而保障路線規劃的準確和智慧。
3 藉助通行規範篩選路線
結合預計到達時間和使用者車牌號，通過限行、交規、封路等通行規範，演算法篩選出符合車輛需求的合理路線。
百度地圖在路線篩選環節已經做到了秒級生效，而利用精準的預計到達時間，則能為使用者提供更多選擇，例如是否立即出發，還是等一段時間避開限行再出發。
4 “為使用者著想”的路線排序
在向用戶推薦3條最優路線時，需要引入對未來路線狀態的判斷，但隨之也帶來了新的難題，例如上文中提到的“外地牌照如何走五環”和各種突發情況。
面對“即刻出發但要繞行的六環”和“等幾分鐘再出發的五環”該如何選擇？
百度地圖一方面通過“常規路線”，即大部分使用者選擇的路線或使用者自身曾走過的路線，過濾掉沒有意義的繞行。另一方面，通過衡量不同路線的代價綜合篩選。因為每個人對時間代價、距離代價的感受不同，意味著每條路線背後的演算法模型，都在逐漸被“主人”養成個性化推薦，通過使用者以往的駕駛行為和操作偏好，推薦更適合路線。
當路上遇到突發情況導致預計到達時間不準，可能引起使用者違章時，演算法往往會做“最壞的假設”。
舉個例子，早上六點半一輛外地牌照的汽車行駛在北京的五環上時，一場交通事故導致了大面積堵車。這時路線規劃將考慮到這一點，對於那些不能幫使用者在規定時間內駛離五環的路線慎重考慮，排序中可能會放到更靠後的位置。並在導航過程中，不斷檢測前方通行狀況判斷使用者是否有違規風險，並通過語音、影象提醒指引更合理的路線。
在這場演算法跟道路資訊之間的鬥智鬥勇中，百度地圖不僅能處理好紛繁複雜的各類資訊，還能讓它們“為我所用”，以這些資訊為指標提供最優的出行選擇。
當“未來時刻”成為使用者越來越重視的核心要素之一，更智慧化的導航規劃也將成為未來趨勢。