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