桔妹导读：IT技术的不断更新推动着公共交通的概念不断在深度和广度上扩展。深度上，精准的公交ETA和实时到站等信息可以帮助用户更好的规划行程时间；广度上，配合单车，网约车等共享出行方式可以帮助用户更好的决策出行方式。
1. 信息公交服务简介公交，在传统意义上主要指城市内的公交巴士和地铁通行方式。因此传统的互联网信息公交服务的核心功能便是路径规划服务，即：根据用户给出起点O和终点D，给出通过公交地铁可以到达的方案。在进入移动互联网和物联网时代后，一方面，快车、单车等共享出行方式渗透率大大提升，成为公交的重要补充方式；另一方面，随着物联网和大数据的应用带来的实时信息可以更好的辅助用户出行决策，在公交服务中的应用愈加重要，因此查询公交实时位置相关的服务成为又一个公交服务的核心功能。下面将对路径规划和实时公交这两个服务在滴滴的实现进行介绍。
2. 公交服务中的技术挑战 ▍2.1 路径规划服务整体架构如下：
总体来说，路径规划分为算路和排序两个阶段，在算路阶段召回能到达用户指定OD的线路，分为离线和在线两个阶段；排序阶段综合步行距离，到达时间，换乘次数，乘车价格等不同的用户偏好给出最匹配用户的N条结果。
2.1.1. 离线算路与在线算路路径规划问题的基本思路是首先将城市的公交和地铁线路数据，以站点集合为顶点集合V，每条公交或地铁线路上相邻的两站用边连接起来得到有向图。同时，由于站点之间换乘需要一段步行是常见情况，因此还需要将距离较近的两个站用步行路网也用边连接起来（图中的蓝色虚线）。最后，以每段路径的预估消耗时间作为每条边的权重，就得到了一张有向带权图。有了这样一张有向带权图后，当用户输入起点和重点请求换乘路线信息的时候，问题就转换为：已知有向带权图中的起始节点O和终止节点D，搜索找到O和D之间的K条较优通路。
这类问题常规的解法有BFS，Dijkstra，Floyd等，但在实际应用中，基于性能考虑，都不会在线实时的用这张图去计算，而是将一部分预处理的工作转移到离线阶段。
2.1.1.1. 离线算路尽管离线计算对性能的要求比在线低很多，但由于加入了步行之后的公交地铁有向图网络每个顶点的分叉非常多，直接使用BFS，Dijkstra这类算法依然会难以忍受，因此滴滴根据自身的实际的数据情况进行了以下几种优化：
路网分层
在现实中，我们往往会有一些大家熟知的大区之间的联络线路，如地铁4号线可以从中关村区域到大兴区域。当我们从海淀其他区域自己规划乘车去大兴的时候也会先想到坐到地铁4号线的某站到大兴区域的某站，然后再看从这一站怎么到达最终目的地。这当中大区之间为人熟知的联络线路其实就是一种先验信息，借鉴这种思路，我们在离线阶段抽象出若干较大片的区域，提前计算好这些区域之间几条主干通路，在线时，将起终点转换为区域，取出事先已算好的区域通路路径，可以大幅降低计算成本。
双向搜索(Bidirectional Search)
正如他的名称一样，借鉴大家实际应用中找路线的想法，同时从起点和终点扫描各自经过相向的线路，寻找其中有没有共同的车站（或步行可达的车站）。双向是一种非常有效的提效手段，BFS，Dijkstra都有双向的变种。
使用估值函数剪枝
在搜索中一个常见提升性能的最重要的策略就是剪枝，通过一些耗时小的估算，提前结束一些明显会比当前路径更差的。我们采用的是AStar算法。
在线算路模块，需要根据用户输入的起终点在上一步离线算路模块中选出***方案，并根据实时车辆情况，计算单车拼乘和网约车拼乘方案。