AI的浪潮勢(shì)不可擋，在無(wú)數(shù)大眾最熟悉的生活場(chǎng)景中，其實(shí)蘊(yùn)含著許多未被發(fā)現(xiàn)的秘密。

這些“深藏功與名”的AI技術(shù)，在最基礎(chǔ)的功能背后，卻演繹著數(shù)據(jù)和算法最動(dòng)人的一面。

地圖導(dǎo)航中，算法與千變?nèi)f化的道路信息之間“斗智斗勇”，對(duì)地圖中常規(guī)的路線規(guī)劃進(jìn)行改造，讓“未來(lái)出行”成為可能。

全文共1791字，閱讀時(shí)長(zhǎng)約為5分鐘

圖片來(lái)源 |?網(wǎng)絡(luò)

出品 |?先聲會(huì)

所謂路線規(guī)劃就是“兩點(diǎn)之間直線最短”的簡(jiǎn)單明了嗎？——天真。

要知地圖產(chǎn)品在為用戶規(guī)劃路線時(shí)，那可是一場(chǎng)人類與復(fù)雜算法、道路信息之間的斗智斗勇。

各種地圖的算法工程師們，不僅要面對(duì)瞬息萬(wàn)變的路況信息，還要應(yīng)對(duì)各種各樣“意料之外情理之中”的干擾。

所以如何綜合利用好各類信息，快速提供準(zhǔn)確有效的出行方案，就成了“路線規(guī)劃”要解決的切實(shí)問(wèn)題。

小王是一個(gè)在北京西二旗工作的資深“碼農(nóng)”，雖是地道的北京人但因?yàn)槎嗄険u不上號(hào)只好暫時(shí)上了外地牌照。

由于五環(huán)在工作日早晚高峰期禁止外地牌照車輛行駛，小王上下班通常會(huì)繞開(kāi)五環(huán)或者早早出發(fā)躲避限行。

周一早上，公司組織集體去西五環(huán)附近的北京園博園參加活動(dòng)。早上8點(diǎn)40多，大家都準(zhǔn)備從公司出發(fā)了，因?yàn)榇藭r(shí)五環(huán)還是限行狀態(tài)，不少人憑著習(xí)慣繞路上了六環(huán)。

小王打開(kāi)地圖查路線，導(dǎo)航卻提醒他：再等5分鐘后出發(fā)，就可以避開(kāi)限行時(shí)間直接走五環(huán)。既能節(jié)省時(shí)間和油費(fèi)，還不會(huì)違章。

最終小王雖然多等了5分鐘，卻比其他人早到20分鐘，還少走了一半路程。

目前大部分地圖導(dǎo)航還無(wú)法結(jié)合實(shí)際情況推薦出發(fā)時(shí)間和路線，百度地圖新推出“多等5分鐘少走半程路”，通過(guò)預(yù)估未來(lái)交通狀況并提供躲避擁堵、限行路線。

新功能的背后是一整套路線規(guī)劃的復(fù)雜流程。算法為用戶規(guī)劃路線時(shí)，要經(jīng)過(guò)路線規(guī)劃、特征提取、路線篩選和路線排序四個(gè)步驟，百度地圖是如何改造路線規(guī)劃的四個(gè)步驟，滿足用戶智能化出行需求的呢？

1

針對(duì)時(shí)間規(guī)劃路線

為了實(shí)現(xiàn)根據(jù)時(shí)間推演進(jìn)行路線規(guī)劃，常用做法是將連續(xù)的時(shí)間點(diǎn)分散成多個(gè)時(shí)刻，在每一個(gè)時(shí)刻都生成一套權(quán)值，并在路線搜索過(guò)程中恰當(dāng)切換不同權(quán)值，從而實(shí)現(xiàn)針對(duì)時(shí)間進(jìn)行路線規(guī)劃。

在算法選擇上，一般要考慮預(yù)處理時(shí)間、在線計(jì)算性能、路線效果等要素。A*算法和CRP算法（基于剖分的路線規(guī)劃算法）由于預(yù)處理時(shí)間較短、數(shù)據(jù)較小，天然具有快速編譯及生效的優(yōu)點(diǎn)，是面對(duì)此類問(wèn)題的主流選擇。

2

基于海量數(shù)據(jù)合理預(yù)測(cè)

有了完整的路線數(shù)據(jù)后，可以獲得更加精確的預(yù)計(jì)到達(dá)時(shí)間，這也是算法進(jìn)行后續(xù)決策的基礎(chǔ)。由于預(yù)計(jì)到達(dá)時(shí)間與路況息息相關(guān)，二者都有著豐富的歷史數(shù)據(jù)作為參考，在進(jìn)行未來(lái)時(shí)間預(yù)估時(shí)，算法可以根據(jù)歷史數(shù)據(jù)和當(dāng)前道路狀態(tài)合理預(yù)測(cè)，從而保障路線規(guī)劃的準(zhǔn)確和智能。

3

借助通行規(guī)范篩選路線

結(jié)合預(yù)計(jì)到達(dá)時(shí)間和用戶車牌號(hào)，通過(guò)限行、交規(guī)、封路等通行規(guī)范，算法篩選出符合車輛需求的合理路線。

百度地圖在路線篩選環(huán)節(jié)已經(jīng)做到了秒級(jí)生效，而利用精準(zhǔn)的預(yù)計(jì)到達(dá)時(shí)間，則能為用戶提供更多選擇，例如是否立即出發(fā)，還是等一段時(shí)間避開(kāi)限行再出發(fā)。

4

“為用戶著想”的路線排序

在向用戶推薦3條最優(yōu)路線時(shí)，需要引入對(duì)未來(lái)路線狀態(tài)的判斷，但隨之也帶來(lái)了新的難題，例如上文中提到的“外地牌照如何走五環(huán)”和各種突發(fā)情況。

面對(duì)“即刻出發(fā)但要繞行的六環(huán)”和“等幾分鐘再出發(fā)的五環(huán)”該如何選擇？

百度地圖一方面通過(guò)“常規(guī)路線”，即大部分用戶選擇的路線或用戶自身曾走過(guò)的路線，過(guò)濾掉沒(méi)有意義的繞行。另一方面，通過(guò)衡量不同路線的代價(jià)綜合篩選。因?yàn)槊總€(gè)人對(duì)時(shí)間代價(jià)、距離代價(jià)的感受不同，意味著每條路線背后的算法模型，都在逐漸被“主人”養(yǎng)成個(gè)性化推薦，通過(guò)用戶以往的駕駛行為和操作偏好，推薦更適合路線。

當(dāng)路上遇到突發(fā)情況導(dǎo)致預(yù)計(jì)到達(dá)時(shí)間不準(zhǔn)，可能引起用戶違章時(shí)，算法往往會(huì)做“最壞的假設(shè)”。

舉個(gè)例子，早上六點(diǎn)半一輛外地牌照的汽車行駛在北京的五環(huán)上時(shí)，一場(chǎng)交通事故導(dǎo)致了大面積堵車。這時(shí)路線規(guī)劃將考慮到這一點(diǎn)，對(duì)于那些不能幫用戶在規(guī)定時(shí)間內(nèi)駛離五環(huán)的路線慎重考慮，排序中可能會(huì)放到更靠后的位置。并在導(dǎo)航過(guò)程中，不斷檢測(cè)前方通行狀況判斷用戶是否有違規(guī)風(fēng)險(xiǎn)，并通過(guò)語(yǔ)音、圖像提醒指引更合理的路線。

在這場(chǎng)算法跟道路信息之間的斗智斗勇中，百度地圖不僅能處理好紛繁復(fù)雜的各類信息，還能讓它們“為我所用”，以這些信息為指標(biāo)提供最優(yōu)的出行選擇。

當(dāng)“未來(lái)時(shí)刻”成為用戶越來(lái)越重視的核心要素之一，更智能化的導(dǎo)航規(guī)劃也將成為未來(lái)趨勢(shì)。