引言
對(duì)于駕車、公交、步行、騎行等出行服務(wù)，路徑規(guī)劃技術(shù)是用戶體驗(yàn)的關(guān)鍵。好吧，那就來扒一扒業(yè)界地圖大玩家的家底！
騎行路徑規(guī)劃怎么做
對(duì)于LBS行業(yè)，所謂路徑規(guī)劃是指基于某種路網(wǎng)模型（帶權(quán)圖），尋找一條或多條由起點(diǎn)到終點(diǎn)的出行路線（尋路的方法即為搜索算法）。
顧名思義，騎行路徑規(guī)劃就是基于騎行路網(wǎng)模型，尋找由起點(diǎn)到終點(diǎn)的騎行路線。
根據(jù)上面的定義，要想實(shí)現(xiàn)騎行路徑規(guī)劃，充要條件是：
1）適合騎行的路網(wǎng)模型
2）適合騎行的路網(wǎng)數(shù)據(jù)
3）適合騎行的搜索算法
那么，百度地圖的騎行路徑規(guī)劃是怎么做的？
1、騎行的路網(wǎng)模型
根據(jù)《中華人民共和國道路交通安全法》，機(jī)動(dòng)車、非機(jī)動(dòng)車、行人屬于道路交通的參與者，必須各行其道。騎行屬于非機(jī)動(dòng)車范疇，必須遵循的交通法規(guī)如下：
第三十五條 機(jī)動(dòng)車、非機(jī)動(dòng)車實(shí)行右側(cè)通行。
第三十六條 根據(jù)道路條件和通行需要，道路劃分為機(jī)動(dòng)車道、非機(jī)動(dòng)車道和人行道的，機(jī)動(dòng)車、非機(jī)動(dòng)車、行人實(shí)行分道通行。沒有劃分機(jī)動(dòng)車道、非機(jī)動(dòng)車道和人行道的，機(jī)動(dòng)車在道路中間通行，非機(jī)動(dòng)車和行人在道路兩側(cè)通行。
第三十七條 道路劃設(shè)專用車道的，在專用車道內(nèi)，只準(zhǔn)許規(guī)定的車輛通行，其他車輛不得進(jìn)入專用車道內(nèi)行駛。
第五十七條 駕駛非機(jī)動(dòng)車在道路上行駛應(yīng)當(dāng)遵守有關(guān)交通安全的規(guī)定。非機(jī)動(dòng)車應(yīng)當(dāng)在非機(jī)動(dòng)車道內(nèi)行駛；在沒有非機(jī)動(dòng)車道的道路上，應(yīng)當(dāng)靠車行道的右側(cè)行駛。
第六十七條 行人、非機(jī)動(dòng)車、拖拉機(jī)、輪式專用機(jī)械車、鉸接式客車、全掛拖斗車以及其他設(shè)計(jì){zg}時(shí)速低于七十公里的機(jī)動(dòng)車，不得進(jìn)入高速公路。
根據(jù)上述規(guī)定，騎行的路網(wǎng)模型應(yīng)該具有如下特征：
1）通行規(guī)則：在非機(jī)動(dòng)車道上，實(shí)行右側(cè)通行；在沒有非機(jī)動(dòng)車道的道路上，應(yīng)當(dāng)靠車行道的右側(cè)行駛；
2）不可通行的道路：高速公路；明確規(guī)定非機(jī)動(dòng)車禁止駛?cè)氲膶Ｓ玫缆罚?/span>
由上述特征可知，騎行的路網(wǎng)模型為：
1）帶權(quán)有向圖
2）騎行路網(wǎng)屬于道路網(wǎng)絡(luò)的子集（去掉不允許非機(jī)動(dòng)車通行的道路）
2、騎行的數(shù)據(jù)來源
根據(jù)騎行的路網(wǎng)模型可知，理想情況是道路網(wǎng)絡(luò)能夠標(biāo)示出所有允許騎行的道路，但是，全國的道路網(wǎng)絡(luò)屬于海量數(shù)據(jù)，數(shù)據(jù)采集和數(shù)據(jù)制作的成本非常高，很難在短時(shí)間內(nèi)制作理想情況的騎行數(shù)據(jù)。因此，必須利用百度地圖的現(xiàn)有資源，采用折衷方案來生產(chǎn)騎行路網(wǎng)數(shù)據(jù)。
騎行路網(wǎng)數(shù)據(jù)的折衷方案如下：
1）騎行基礎(chǔ)路網(wǎng)：駕車路網(wǎng)+步行設(shè)施
2）駕車路網(wǎng)過濾：根據(jù)道路等級(jí)屬性，去掉不允許非機(jī)動(dòng)通行的道路，包括高速、城市高速、輪渡、行人道路、公交專用道、步行街、全封閉道路等
3）步行設(shè)施過濾：去掉不方便騎行的步行設(shè)施，包括過街天橋、地下通道等；
4）過濾道路召回：對(duì)于被過濾的部分道路，數(shù)據(jù)部門調(diào)查核實(shí)后提取可騎行的道路；
5）道路權(quán)重設(shè)置：根據(jù)道路等級(jí)屬性，設(shè)置不同的道路權(quán)重，提升路線的合理性；
3、騎行的搜索算法
百度地圖自2015年5月推出騎行導(dǎo)航以來，其搜索算法經(jīng)歷了三個(gè)里程碑的發(fā)展：
Sprint 1 : 基于步行A*算法搭建規(guī)劃引擎，確保騎行產(chǎn)品推出；于5月18日上線；
Sprint 2 : 創(chuàng)新實(shí)現(xiàn)HD（High Dijkstra）算法，并成功應(yīng)用于騎行路徑規(guī)劃，從原理上解決了A*算法的技術(shù)瓶頸，取得重大技術(shù)突破；于9月10日上線；
Sprint 3 : 結(jié)合技術(shù)、產(chǎn)品需求，對(duì)HD算法進(jìn)行深度優(yōu)化，算法性能和合理性得到重大提升；于12月16日上線。
羅馬不是{yt}建成的，后續(xù)章節(jié)將詳細(xì)介紹騎行搜索算法的演變歷程。
Sprint 1: A*
經(jīng)過前期調(diào)研，雖然百度地圖提供了步行導(dǎo)航，但是步行路線并不能滿足騎行用戶的真實(shí)訴求（很多步行的道路并不允許騎行；步行不考慮道路通行方向，逆行對(duì)于騎行來說很危險(xiǎn)），用戶期望百度地圖提供專門的騎行導(dǎo)航功能。
我們決定2015年春節(jié)過后，快速搭建騎行導(dǎo)航引擎，計(jì)劃5月份上線產(chǎn)品。
那么，問題來了，如何快速構(gòu)建出騎行引擎，騎行的路徑規(guī)劃如何突破？
復(fù)用？復(fù)用可以提{gx}率，少走彎路
根據(jù)調(diào)研，百度公交的路網(wǎng)規(guī)格不適合騎行；百度導(dǎo)航的技術(shù)復(fù)雜度很高，很難在短時(shí)間進(jìn)行算法重構(gòu)；百度步行的路網(wǎng)規(guī)格基本符合騎行，并且步行和騎行的后端服務(wù)由地圖基礎(chǔ)技術(shù)團(tuán)隊(duì)負(fù)責(zé)，因此，決定復(fù)用步行的搜索算法來實(shí)現(xiàn)騎行路徑規(guī)劃。
步行的搜索算法是基于帶權(quán)無向圖實(shí)現(xiàn)的分層、雙向、A*算法。根據(jù)分析，該算法的性能和合理性存在不足，主要表現(xiàn)為：起終點(diǎn)直線距離小于50km時(shí)，在路網(wǎng)密集的大城市（北上廣深）容易出現(xiàn)搜索超時(shí)（>2S）；超過50km時(shí)會(huì)進(jìn)行分層規(guī)劃，繞路現(xiàn)象嚴(yán)重。
由于騎行的路網(wǎng)模型為帶權(quán)有向圖，并且對(duì)于50km及以上的路線請(qǐng)求為強(qiáng)需求，因此，必須對(duì)步行的搜索算法進(jìn)行復(fù)用，并進(jìn)行策略調(diào)整，包括：
1）調(diào)整分層路網(wǎng)的提取原則；
2）調(diào)整分層搜索的策略；
3）調(diào)整A*算法估計(jì)代價(jià)的計(jì)算方法；
4）調(diào)整無向搜索為有向搜索。
