![]()
![]()
桔妹导读：IT技术的不断更新推动着公共交通的概念不断在深度和广度上扩展。深度上，精准的公交ETA和实时到站等信息可以帮助用户更好的规划行程时间；广度上，配合单车，网约车等共享出行方式可以帮助用户更好的决策出行方式。
公交，在传统意义上主要指城市内的公交巴士和地铁通行方式。 因此传统的互联网信息公交服务的核心功能便是路径规划服务，即： 根据用户给出起点O和终点D，给出通过公交地铁可以到达的方案。 在进入移动互联网和物联网时代后，一方面，快车、单车等共享出行方式渗透率大大提升，成为公交的重要补充方式； 另一方面，随着物联网和大数据的应用带来的实时信息可以更好的辅助用户出行决策，在公交服务中的应用愈加重要，因此查询公交实时位置相关的服务成为又一个公交服务的核心功能。 下面将对路径规划和实时公交这两个服务在滴滴的实现进行介绍。
总体来说，路径规划分为算路和排序两个阶段，在算路阶段召回能到达用户指定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算法。
2.1.1.2. 在线算路模块
在线算路模块，需要根据用户输入的起终点在上一步离线算路模块中选出最佳方案，并根据实时车辆情况，计算单车拼乘和网约车拼乘方案。
多模实时换乘
在离线算路阶段产出的方案，根据用户输入的起终点选择最佳上下车站点。再根据实时单车/网约车信息，生成步行/骑行/网约车前往站点来接驳公交/地铁的方案。
在线剪枝
多模接驳阶段会产生大量方案，为了提高线上服务性能，需要将方案进行剪枝。包括将不在运营时间的方案、价格明显偏高，网约车排队时间过长，或单车数量较少区域的方案去除。同时，将多个路线一致的方案合并成一个。
粗排计算
经过前面处理后，得到了所有可行方案，下面需要对这些方案进行排序，选择最优的方案。粗排计算阶段需要根据每条方案的基础特征（例如耗时、路程等），对上千条可行方案快速计算评分，根据分数选出候选方案集送给后续排序模块。
2.1.1.3. 排序模块
ETA
ETA是用户选择时最主要的参考信息。为了更精准地得到方案的耗时，推荐出实时最佳方案。滴滴利用路况信息、历史通行耗时等信息，借鉴网约车的经验，建立了公交车专用ETA模型用来估计车辆当前位置到达站点和到达目的站点的时间。更精确地预计了用户的等车时间和到达目的地时间。
![]()
网约车模型收益
精排
多模换乘推荐引擎中需要比较众多包含多种交通工具的候选方案。而将包含多种不同交通工具公平地进行比较，并推荐出若干个符合大众心目中最优的方案是一个较为复杂的问题。除了基础特征外，还需要从方案中挖掘出更多信息，增强模型的表征能力。我们设计了包含预计通行时间、换乘次数、步行距离、综合距离、地铁距离、单车距离、价格、发班时间、备选车次数量、交通工具类型、是否在主干道行驶、是否公交专用道、各种交通工具占比等若干高级特征。在线计算出特征后，提供给后续排序模型使用。
Rerank和多样性
为了兼顾用户的个性化诉求，最终展示给用户的N条方案时，通过rerank来保证整体方案的多样性。一般用户的个性化因素包括价格是否敏感，地铁偏好，步行长短，换乘偏好等等。以点击率作为整个公交方案的线上观察指标。
▍2.2 实时公交服务
随着传统行业的线上数字化改造，已有200多个城市公交巴士都配置了智能硬件设备，可以实时上报公交的位置。以此为基础，向用户提供实时公交位置，预估等待时间等相关信息成为公交服务的又一基础功能。整体架构如下：
2.2.1. 数据接入
实时公交的数据来自公交公司和交委，然而由于没有统一的标准。上报的格式，各字段的含义都不一样，因此滴滴制定了一套自己的数据规范来适配各地数据，从而对应用层提供统一格式的数据。除了格式的统一之外，由于公交站点和线路的名称，ID编码规则各地也都会不定期发生变化，因此，为了保障应用层使用的继承性，滴滴对所有数据也定义了自己的ID编码规则。在数据接入阶段，还有一个重要的工作就是对数据实体进行映射。
2.2.2. GPS位置补偿
位置的正确性和时效性是实时公交服务的核心能力，如果用户在线下看到车的位置和APP上的位置有比较大的差别，就会失去信任感，流失到竞品。
然而各地上报的GPS都有一定的延迟，且延迟有不可预知性，如果完全依赖上报的位置数据呈现给用户，在极端情况下（如隧道等网络不好的地方），可能会出现用户真实看见了一辆车但是在APP上未出现的情况。因此必须通过AI的方式对实际的位置进行估算才能给到用户准确的信息展示。在这里，源数据上报的时效性是位置预测时最大的困扰，如下图一所示，对于不同的延迟时间，误差和延迟的比例正相关。
图一
利用滴滴大数据的优势，首先会根据实时的路况数据（该路段的平均行驶速度，红 绿灯等待时间等）对公交的实时速度进行预估，对没有实时路况和特殊路段，会根据历史上同时间同路 段的速度对路况进行预估，最后会使用公交静态平均速度进行兜底，完成对延迟时间内位置移动的补偿。
另外，由于各地上报GPS的规范性不一致。还需要处理一些边界问题。如：GPS的延迟上报如果处理不好，在前两站给用户的伤害更为明显：车辆可能在已经驶过第二站后才上报了第一个GPS点，这意味着，如果我们不对车辆的发出时间做预估，而完全依赖上报的数据的话，第二站用户看到的永远是车辆等待发车。而在前两站会比较容易出现的特殊情况是：
场站线路
即车辆在到达上一方向的终点站后，会回到场站，停留一段时间后发出；
循环线路
即车辆在到达上一方向的终点站后，直接驶向下一方向的起点。
我们目前的解决方案是：
根据历史数据，离线统计出车辆的上下行换向时间，即当车辆到达上行方向的终点站后，停留在场站（或继续行驶）多长时间后会出现在下行方向的起点位置。
线上使用时，当收到车辆上行方向上报的最后一个GPS点后，对于场站线路，我们会在换向时间过后判断车辆从下行方向驶出；对于循环线路，会让车辆从下行方向驶出的同时，继续模拟前行。
使用/离线挖掘出车辆的发车时刻表。
随着公交数据的不断积累，我们将在以下两个方向持续深耕：
一方面，通过用户使用公交服务的数据，进一步优化路径规划服务和实时公交服务，如：
结合用户的历史行为，对用户历史行为建模，实现个性化和场景化排序
使用深度时序模型优化实时位置补偿，提升预测的准确率，强化对全国不同城市，各种不同地理特征的泛化能力。
利用用户轨迹补偿实时公交信息和步行路网信息
另一方面，可以结合整个滴滴各种出行方式积累下的大数据，可以赋能给传统公共交通行业，优化线路选择，智能排班调度等，真正助力智慧交通和智慧城市早日到来。
本文作者
团队招聘
▬
滴滴地图与公交事业部信息公交团队，依托滴滴海量出行数据和多种共享出行方式的优势，使用人工智能和大数据等技术，致力于为用户提供多模、高效、智能的公共出行解决方案。
团队长期招聘研发工程师，包括C++/go引擎和业务开发、数据挖掘，机器学习等方向，欢迎有兴趣的小伙伴加入，可投递简历至 diditech@didiglobal.com，邮件请邮件主题请命名为「姓名-应聘部门-应聘方向」。
扫描了解更多岗位
联系我们 | DiDiTech@didiglobal.com
