浅谈滴滴需求响应式公交背后的技术

上图是一个简单的示意图，途中，B1,B2车辆已经分配行程任务，正在执行既有行程，有2个未分配行程的车辆B3和B4，实时在线等待派发任务，同时在该时刻我们聚合形成了一个新的行程，后续出现的订单可以继续在行程上聚合拼单，同时告知用户，行程已经拼成，车辆信息稍后告知但是暂时没有合适的车。我们会根据运力规则，路况，预测发单情况去实时更新最合适的车辆，最终指定车辆B4去执行该未分配车辆的行程。

需求响应式公交主要由乘客端、司机端、管理后台和引擎几个部分组成。整个系统从用户呼单为起点开始运转，订单经过分析处理后放入订单池，订单池以某个特定的频率向引擎发起拼单请求，引擎分析请求，适配合适的算法，给订单撮合最优的车辆，并给车辆规划出接送人的顺序，然后将结果返回给后台系统进行缓存。司机端和乘客端接收后台的信息进行展示并对信息进行迭代更新，这样，就构成了一个完整的系统闭环。

整个系统的架构简图如下：

动态公交拼单和规划引擎主要是解决多车、多单在时间和空间上的匹配问题，在满足各种先决条件下，尽可能多的拼成订单，同时确保司乘体验。公交车辆车型多样，有几座的，也有几十座以上的，相比网约车，动态公交在每个车辆怎么分配多个订单、多个订单如何组合不同路线两个维度上多了延伸，而这种维度上的增加带来的是组合上指数级的增长。

如此规模的VRP问题，暴力检索是不可想象的。小规模区域下，可以通过传统运筹学范畴的算法精确求解；当针对区域规模较大时，精确求解是不切实际的，需要寻找合理的智能算法，既要考虑搜索性能，也要合理规避陷入局部最优。为了更好的应对这种NP-难问题，寻找更好的次优解是我们解决问题的关键。

动态公交VRP问题，有它独特的限制要求（车载量限制、用户时间窗限制、站点顺序限制等等），这种情况下一个合理的初始解很重要，能够较大程度上缩减搜索规模，这里我们可以结合拼单逻辑，启发式生成初始解；搜索过程中引入禁忌表避免重复操作；采用变领域搜索避免陷入局部最优等等，在集中性和疏散性之间达到较好的平衡。另外，目标函数决定了搜索的方向，如何设计合理的目标函数，如何平衡拼单率和体验之间的关系，一直是我们探索的方向。目前我们也在布局通过机器学习智能推荐合理站点、引导车辆合理分布等供需自动平衡方案。同时我们也在利用已有的历史订单数据和用户行为数据通过深度学习的方法积极搭建我们的仿真系统，为针对不同运营区域独立建模搭建基础。

出于赋能公交行业的目的， 除支持滴滴主app呼单外，我们还提供一个开放平台合作模式，依靠开放平台客户可以更加自主化的实现自身需求。

公交是一个多方合作的业务，技术平台以开放平台的模式来构建。使用开放api的方式，支持了多种方式的合作可能，运营方可以直接在滴滴app上运营产品，也可以通过我们提供的开放api和sdk接入到自有系统和app产品运营。

目前我们的产品和系统还有很多不完善的地方，也面对着很多的技术难点，欢迎大家对我们提出您宝贵的意见，帮助我们更好的成长，谢谢。

梦在远方，路在脚下，我们致力于为您提供最佳公共出行解决方案！