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