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