AI的浪潮勢不可擋丙挽，在無數(shù)大眾最熟悉的生活場景中，其實蘊(yùn)含著許多未被發(fā)現(xiàn)的秘密匀借。
這些“深藏功與名”的AI技術(shù)颜阐，在最基礎(chǔ)的功能背后，卻演繹著數(shù)據(jù)和算法最動人的一面吓肋。
地圖導(dǎo)航中凳怨，算法與千變?nèi)f化的道路信息之間“斗智斗勇”，對地圖中常規(guī)的路線規(guī)劃進(jìn)行改造是鬼，讓“未來出行”成為可能肤舞。
全文共1791字，閱讀時長約為5分鐘
圖片來源 |?網(wǎng)絡(luò)
出品 |?先聲會
所謂路線規(guī)劃就是“兩點之間直線最短”的簡單明了嗎均蜜？——天真李剖。
要知地圖產(chǎn)品在為用戶規(guī)劃路線時，那可是一場人類與復(fù)雜算法囤耳、道路信息之間的斗智斗勇杖爽。
各種地圖的算法工程師們，不僅要面對瞬息萬變的路況信息紫皇，還要應(yīng)對各種各樣“意料之外情理之中”的干擾。
所以如何綜合利用好各類信息腋寨，快速提供準(zhǔn)確有效的出行方案聪铺，就成了“路線規(guī)劃”要解決的切實問題。
小王是一個在北京西二旗工作的資深“碼農(nóng)”萄窜，雖是地道的北京人但因為多年搖不上號只好暫時上了外地牌照铃剔。
由于五環(huán)在工作日早晚高峰期禁止外地牌照車輛行駛撒桨，小王上下班通常會繞開五環(huán)或者早早出發(fā)躲避限行。
周一早上键兜，公司組織集體去西五環(huán)附近的北京園博園參加活動凤类。早上8點40多，大家都準(zhǔn)備從公司出發(fā)了普气，因為此時五環(huán)還是限行狀態(tài)谜疤，不少人憑著習(xí)慣繞路上了六環(huán)。
小王打開地圖查路線现诀，導(dǎo)航卻提醒他：再等5分鐘后出發(fā)夷磕，就可以避開限行時間直接走五環(huán)。既能節(jié)省時間和油費仔沿，還不會違章坐桩。
最終小王雖然多等了5分鐘，卻比其他人早到20分鐘封锉，還少走了一半路程绵跷。
目前大部分地圖導(dǎo)航還無法結(jié)合實際情況推薦出發(fā)時間和路線，百度地圖新推出“多等5分鐘少走半程路”成福，通過預(yù)估未來交通狀況并提供躲避擁堵碾局、限行路線。
新功能的背后是一整套路線規(guī)劃的復(fù)雜流程闷叉。算法為用戶規(guī)劃路線時擦俐，要經(jīng)過路線規(guī)劃、特征提取握侧、路線篩選和路線排序四個步驟蚯瞧，百度地圖是如何改造路線規(guī)劃的四個步驟，滿足用戶智能化出行需求的呢品擎？
1
針對時間規(guī)劃路線
為了實現(xiàn)根據(jù)時間推演進(jìn)行路線規(guī)劃埋合，常用做法是將連續(xù)的時間點分散成多個時刻，在每一個時刻都生成一套權(quán)值萄传，并在路線搜索過程中恰當(dāng)切換不同權(quán)值甚颂，從而實現(xiàn)針對時間進(jìn)行路線規(guī)劃。
在算法選擇上秀菱，一般要考慮預(yù)處理時間振诬、在線計算性能、路線效果等要素衍菱。A*算法和CRP算法（基于剖分的路線規(guī)劃算法）由于預(yù)處理時間較短赶么、數(shù)據(jù)較小，天然具有快速編譯及生效的優(yōu)點脊串，是面對此類問題的主流選擇辫呻。
2
基于海量數(shù)據(jù)合理預(yù)測
有了完整的路線數(shù)據(jù)后清钥，可以獲得更加精確的預(yù)計到達(dá)時間，這也是算法進(jìn)行后續(xù)決策的基礎(chǔ)放闺。由于預(yù)計到達(dá)時間與路況息息相關(guān)祟昭，二者都有著豐富的歷史數(shù)據(jù)作為參考，在進(jìn)行未來時間預(yù)估時怖侦，算法可以根據(jù)歷史數(shù)據(jù)和當(dāng)前道路狀態(tài)合理預(yù)測篡悟，從而保障路線規(guī)劃的準(zhǔn)確和智能。
3
借助通行規(guī)范篩選路線
結(jié)合預(yù)計到達(dá)時間和用戶車牌號础钠，通過限行恰力、交規(guī)、封路等通行規(guī)范旗吁，算法篩選出符合車輛需求的合理路線踩萎。
百度地圖在路線篩選環(huán)節(jié)已經(jīng)做到了秒級生效，而利用精準(zhǔn)的預(yù)計到達(dá)時間很钓，則能為用戶提供更多選擇香府，例如是否立即出發(fā)，還是等一段時間避開限行再出發(fā)码倦。
4
“為用戶著想”的路線排序
在向用戶推薦3條最優(yōu)路線時企孩，需要引入對未來路線狀態(tài)的判斷，但隨之也帶來了新的難題袁稽，例如上文中提到的“外地牌照如何走五環(huán)”和各種突發(fā)情況勿璃。
面對“即刻出發(fā)但要繞行的六環(huán)”和“等幾分鐘再出發(fā)的五環(huán)”該如何選擇？
百度地圖一方面通過“常規(guī)路線”推汽，即大部分用戶選擇的路線或用戶自身曾走過的路線补疑，過濾掉沒有意義的繞行。另一方面歹撒，通過衡量不同路線的代價綜合篩選莲组。因為每個人對時間代價、距離代價的感受不同暖夭，意味著每條路線背后的算法模型锹杈，都在逐漸被“主人”養(yǎng)成個性化推薦，通過用戶以往的駕駛行為和操作偏好迈着，推薦更適合路線竭望。
當(dāng)路上遇到突發(fā)情況導(dǎo)致預(yù)計到達(dá)時間不準(zhǔn)，可能引起用戶違章時裕菠，算法往往會做“最壞的假設(shè)”咬清。
舉個例子，早上六點半一輛外地牌照的汽車行駛在北京的五環(huán)上時，一場交通事故導(dǎo)致了大面積堵車枫振。這時路線規(guī)劃將考慮到這一點，對于那些不能幫用戶在規(guī)定時間內(nèi)駛離五環(huán)的路線慎重考慮顶瞳，排序中可能會放到更靠后的位置铺呵。并在導(dǎo)航過程中盛正，不斷檢測前方通行狀況判斷用戶是否有違規(guī)風(fēng)險，并通過語音杖小、圖像提醒指引更合理的路線。
在這場算法跟道路信息之間的斗智斗勇中愚墓，百度地圖不僅能處理好紛繁復(fù)雜的各類信息予权，還能讓它們“為我所用”，以這些信息為指標(biāo)提供最優(yōu)的出行選擇浪册。
當(dāng)“未來時刻”成為用戶越來越重視的核心要素之一扫腺，更智能化的導(dǎo)航規(guī)劃也將成為未來趨勢。
