桔妹导读：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 算法。
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 点后，对于场站线路，咱们会在换向工夫过后判断车辆从上行方向驶出；对于循环线路，会让车辆从上行方向驶出的同时，持续模仿前行。
应用 / 离线挖掘出车辆的发车时刻表。
3. 将来瞻望
随着公交数据的一直积攒，咱们将在以下两个方向继续深耕：
一方面，通过用户应用公交服务的数据，进一步优化门路布局服务和实时公交服务，如：
- 联合用户的历史行为，对用户历史行为建模，实现个性化和场景化排序
- 应用深度时序模型优化实时地位弥补，晋升预测的准确率，强化对全国不同城市，各种不同天文特色的泛化能力。
- 利用用户轨迹弥补实时公交信息和步行路网信息
另一方面，能够联合整个滴滴各种出行形式积攒下的大数据，能够赋能给传统公共交通行业，优化线路抉择，智能排班调度等，真正助力智慧交通和智慧城市早日到来。
本文作者
团队招聘
滴滴地图与公交事业部信息公交团队，依靠滴滴海量出行数据和多种共享出行形式的劣势，应用人工智能和大数据等技术，致力于为用户提供多模、高效、智能的公共出行解决方案。
团队长期招聘研发工程师，包含 C ++/go 引擎和业务开发、数据挖掘，机器学习等方向，欢送有趣味的小伙伴退出，可投递简历至 diditech@didiglobal.com，邮件请邮件主题请命名为「姓名 - 应聘部门 - 应聘方向」。
延长浏览
内容编辑 | Charlotte
分割咱们 | DiDiTech@didiglobal.com
滴滴技术 出品