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

作者: 滴滴技术 | 来源:发表于2020-09-29 12:10 被阅读0次

桔妹导读：所谓需求响应式公交，就是根据用户出行需求，提供非固定路线的、能够实时拼单的公交系统。目前滴滴动态公交可通过灵活调配运力、实时规划行驶路线，为用户提供经济、直达、有座、高效的响应式公交服务。

1. 产品背景介绍

传统公交系统以固定路线和时间表的形式给公众提供出行服务。近年来，随着信息技术的快速发展以及与各行业的深度融合，个性化服务逐渐兴起。在公共交通领域，滴滴、Uber、Lyft等科技出行公司通过运用新技术赋能传统出行行业，推出了更加便捷、优质的出行解决方案。

目前，全国每天约有2.5亿人次选择公共出行。滴滴本着让出行更美好的愿景，依靠掌握的高质量的交通大数据的优势，不断思索改进公共出行领域的解决方案，积极配合交管部门等合作伙伴一起用技术力量改善城市交通，普惠大众出行。

在此背景下，滴滴需求响应式公交服务应运而生。其根据用户的个性化出行需求灵活调整运力，针对客流和虚拟站点实时计算最优路径，快速进行公交运力资源动态调配，实现全局效率最优。可有效弥补传统公交在特定区域、特定时段内，运力和需求不匹配的问题，提升公共交通运行效率，有效满足乘客出行的多元需求，有效提升用户公共出行体验，增加公共交通可达性。目前该业务已在青岛、西安等多座城市落地，为用户提供经济、直达、有座、少步行的响应式公交服务。

在ToG、ToB的合作过程中，滴滴创新公交团队主要致力于输出产品技术能力，赋能B端，孵化多场景下多样化的产品解决方案。公共出行的细分场景比较多样化，有通勤、定点疏散、商务、旅游、城际等类枢纽场景，有社区、产业园、大学城等类微循环场景，不同场景下可设计出不同的公交产品模式。同时需要一整套的运营体系来支持产品的运转，若各B端自研，成本高、周期长、风险大。和滴滴需求响应式公交技术平台产品对接，可大大降低合作方成本，加速产品落地。同时助力提升公共出行信息化、网约化水平，让乘客便捷获取实时、准确的出行信息，让运营主体实时监控车辆运营状态、及时了解用户诉求。

2. 公交业务模型

我们说出行问题，本质上是解决时空问题，公交出行同样如此。下面通过对业务模型的抽象，拆解模型图层，如下图所示。第一层是静态区域站点层，站点可以规划设计大、中、虚拟站点；第二层是线路层，刻画站点之间的通达路径；第三层是一体化服务层，通过各种模式来进行人车接送，调度等服务。不同出行场景下，时空分布存在差异，可以通过3层的不同模式来最优化公交服务。图中右上角区域，出行时间、空间都很密集，这种场景下一般规划大中站点、固定路线、投入大车、固定排班的枢纽模式为主；图中左下角区域，出行时间、空间都不密集，这种情况下规划虚拟小站、投入小车、实时聚合、动态的微循环模式为主；时间密集、空间不密集和空间密集、时间不密集两种情况下，可结合枢纽和微循环组合模式去运营比较高效。

3. 产品服务架构

为了落地实现产品价值，基于滴滴基础产研能力，滴滴实现了一整套动态公交产品服务。底层依托弹性云平台、地图、算法、调度引擎等基础能力，构建了人、车、线动态智能匹配的服务。应用端包括乘客端，司机端，还有数据运营管理平台。

4. 产品界面

下面是动态公交产品效果截图。前3张是乘客端，用户选择上下车站点，出发时间等实时呼叫或者预约出行，等待系统响应，响应之后，乘客可以看到车辆车牌号、车辆位置、预计到站时间等信息引导用户乘坐。后1张是司机端，司机接到分配的行程任务后，会按照顺序接送乘客。

5. 多样化场景支持

公交出行的场景本身会比较多样化，有通勤场景，有枢纽疏散场景，有商务，旅游，城际，社区，产业园大学城等各种不同场景，不同场景下可能适合设计不同的公交产品模式来服务。

下图是一个客运站枢纽疏散场景，开通分时段班次动态线路。青岛西站出站乘客呼叫预约，系统根据不同上下车站点，动态聚合，规划动态路线，将乘客疏散到下边的大片区域。

下图是一个大学城区域，投入中小巴运营，固定站点，完全不固定线路。片区內乘客可实时呼叫或者预约，系统实时聚合匹配，实时生成动态路线，司机按照系统派发任务，按顺序接送乘客。

为了支撑实现多样化产品，我们做了对业务模型的统一抽象。对公交服务来说，核心模块设计包括站线模式、成行模式、调车模式、合乘模式、计价支付模式、取消模式等。线站模式包括固定线路、不固定线路、部分约束固定等模式；成行模式包括固定班次成行、拼够人数成行，票款达标等模式；调车模式包括固定排定计划、实时动态最优、轮循等模式；合乘模式包括排班乘坐、效率优先合乘、乘客体验均衡等模式；计价模式包括固定票价、阶梯票价、里程计价等模式；支付模式包括前支付、后支付、不支付等模式；取消模式包括不可取消，免费取消，惩罚取消等。在这个业务模型中每种模式都模版化，运营方可以根据场景实际情况，自由灵活选择组合，快速创造落地运营新产品。

6. 线站模型升维

需求响应式公交集合了网约车的便利和公交的优惠，是传统公交的一种创新，其本质还是一种公共交通形式，强调规划性，需要有线站模型的规划设计。

为了表达多样化的产品运营形态，我们升维了线站模型，从目前行业內以线为主，升级拓展为网状结构，配合站站通达性约束图，打开线路的表达空间，能创造出更多可能的灵活线路形态。

公交的运营主体是各地的公交集团、客运公司、小范围的园区、社区管委会等。不同的运营主体，根据自身的需要，运营特点以及当地交通规则以及实际情况，会设计差异化的线路约束。

比较典型的线路通达性设计约束有:

部分或全部站点可能要求有相对站序，不允许逆站序行驶，通常见于火车站到市区，机场到市区的这种集散地疏散场景。
要求设置一个或多个必经站，通常见于旅游景区、车站、学校等。
允许系统动态微调乘客下单的上车站点，以提升车辆的运营效率，比如将乘客的上车站点修改到马路对面，通常见于园区，或者城区无方向的微循环场景，减少车辆的调头。
特殊情况下，站点之间的路径轨迹要按照运力方实际线下经验规划的路径来设置，而不是按照导航服务的动态推荐线路来规划。

类似的场景还有很多。从功能上看，似乎都是互不相关的定制化需求，但是从技术层面，我们可以把这些需求都统一抽象成一个特殊有向图的表达。如果需要站点相对有序，我们可以通过配置站点的连通性，来达到同样的效果。如果需要换站，我们可以通过训练和挖掘手段，来找出可以换站条件的站点，并通过引擎算法的支撑来实现最终的效果。

通过配置，挖掘，训练等手段，构造出一个特殊有向图结构，并且运用到引擎内，最终转化成不同“定制化”需求，我们称之为需求响应式公交的线网模型。

7. 区域和站线规划

由于是公交的属性，比较强调区域，站线的规划。在规划方面，基于客流大数据，应用聚类等相关算法进行计算分析，并且求解最优闭包区域，建议站点设置，最优途径路线等。

8. 车辆排班和调度

不同的运营商，在不同场景下，运营方式是多种多样的。有在一个范围内车辆不停巡游的场景，也有在多个场站之间定时排班的场景，还有在多个场站之间按需排班的场景。公交运营方通常会有一个线下调度员，专门负责车辆的调度工作，如何使用线上数据和技术手段，替换或者辅助车辆调度，并满足多种不同的场景需求，也是需求响应式公交面临的一个重要问题。

针对实际情况，我们提炼出了静态和动态两种调度模式。

静态调度：根据分时段客流量以及方向分布，还有分时段路况等信息规划运力或者班次投入计划。并且利用智能算法，综合考虑司机工作时长要求、疲劳驾驶、休息周期、驾驶表现，以及车辆续驶里程、加油充电周期、全程用时等相关信息，智能计算推荐排班，然后人工快速选择和校正，高效产生最优排班计划。

动态调度：动态生成合乘路线之后，调度引擎会实时为其寻找最优的车辆进行匹配和分配任务。系统会结合规则、车辆状态、车辆位置等一系列因素去评估和计算，如果通过计算判定路线任务可以被响应，就会对行程路线和车辆进行任务绑定，车辆接到任务按顺序接送乘客。

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

9. 系统核心架构

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

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

10. 拼单和规划引擎

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

假设某个场景下有M辆车、N个订单同时拼单，可能的组合方案（车单无序组合）会有

种；另，某个方案上有K辆车拼成，某辆车上有Q个订单，则该方案下的解会有

种组合；则，理论上，M车N单可能的组合方案数级别为：

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

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