引言
对于驾车、公交、步行、骑行等出行服务，路径规划技术是用户体验的关键。好吧，那就来扒一扒业界地图大玩家的家底！
骑行路径规划怎么做
对于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）调整无向搜索为有向搜索。
