记一次大厂的调度算法评测与仿真系统

草帽路飞UU

　哈啰两轮车调度算法介绍


调度是将稀缺资源分配到一定时间内的不同任务上的决策过程，目的是优化一个或多个目标。两轮车调度场景是指通过预测未来用户的骑行需求，决定各站点车辆的调配任务，并将这些任务分配给合适的运维人员来执行，从而满足用户的骑行需求。在这个调度场景里会涉及三个对象，一是车辆，目标是用户需求满足率高，移车成本低，车辆翻台高。二是运维，目标是运维效率高，运维人员体验好。三是用户，目标是用户体验好。



我们将两轮车调度和外卖/网约车调度做对比，调度涉及到任务生成、任务派发和履约管控三个环节。在任务生成环节，两轮车调度的复杂度比外卖/网约车调度高，原因在于调度涉及到三个要素，调度算法触发的时机需要依托算法来决策，同时需要兼顾线下各种复杂的情况，如天气季节因素，竞对或城管干预等。在任务派发环节，两轮车调度的复杂度比外卖/网约车调度低，原因在于需要匹配的对象少，实时性要求低。在履约管控环节，两轮车调度的复杂度比外卖/网约车调度高，原因在于司机运维执行结果难以监管，而外卖/网约车有用户评价体系，监管便捷。



两轮车调度的难度是多维且立体的，一是定位不准，不同车辆型号定位的精准度是有差异的；二是车辆分散，司机需要去收集散落在各地的车辆；三是需求波动，如季节性的波动、早晚高峰的波动；四是供需失衡，实际投放的车辆数量与用户日益增长的需求匹配不上；五是城市差异，由于城市发展阶段和管控政策不同，会导致车辆投放与用户需求的差异；六是算法黑盒，会导致算法效果评估比较模糊；七是信息孤岛，如司机的载具在某个时刻可能会发生变化，但这些信息并不能及时同步到上层用于算法决策；八是计算复杂，一系列复杂的场景会导致算法的计算复杂度大增。



两轮车调度算法的目标总结下来是多快好省。一是多，我们希望算法调度占比高，覆盖的场景多，支持个性化。二是快，能够实时生成、实时派发、实时执行、实时反馈。三是好，我们希望让业务叫好，让司机叫好。四是省，既能省人工成本，又能省机器成本。



为了达成目标，我们制定了解决方案，左侧是我们解决方案的架构分层图。我们根据多快好省四个分类，推出了对应的解决措施。一是多，我们提供了站点组的调度策略，千城千策，调度场景覆盖广。二是快，我们将需求预测、任务派发与任务决策实时化，并通过路径规划找出最优路线。三是好，我们通过全局匹配来实现最优化，任务聚合来实现效果好，收益预估来提高收益，精益管理来提高管理效率。四是省，我们利用弹性计算、MR调度框架和调度波动预警，提高机器整体的资源利用率。


调度算法在效果评测上的挑战


调度算法效果评测上有五个挑战，一是效率低，一个迭代平均效果评估回收时间需要两周左右。二是不受控，我们无法控制线下运维的执行情况。三是干扰多，线下执行受到的干扰因素多，效果回收准确度低，导致收益和算法归因模糊。四是质量差，模型上线试验后，效果回收正向率低。五是公信力弱，由于线上效果差，合作方对模型效果信任度低。


调度算法仿真系统介绍



为了解决这个挑战，我们提出了仿真系统，通过对物理世界的仿真，达成调度算法离线验证和预测推演的能力。仿真逻辑如图所示，我们可以通过感知建模，对物理世界里的场景属性及行为，转换成特征和模型，其中特征是用来表达物理世界场景属性的数字化信息，而行为、规则用模型来表达。有了特征和模型后，我们可以使用工程[url=]技术[/url]手段把它演化成仿真世界里的场景、属性、行为和规则。如何做到仿真世界的实现，我们提出了三个层面，分别是特征数据、仿真模型和工程支撑。

特征数据



在物理世界中会存在各种各样的信息，如站点信息、车辆信息、用户骑行事件、调度事件、日期天气特征，订单、收益等。我们将其归纳成五个维度，站点数据、车辆数据、运力数据、外部数据和评估指标。

　　一是站点数据特征，包括站点基础信息、站点间流转订单、站点实时停驻车辆数、站点历史需求量和站点间骑行时间。二是车辆数据，包括车辆基础信息、车辆实时标签状态、车辆实时电量、车辆健康度和用户骑行收益。三是运力数据，包括司机画像、载具画像、载具实时数据、司机实时排班和运力成本。四是外部数据特征，包括节假日数据、天气特征、竞对实时数据、地图数据和城管干预。五是评估指标，如缺车数据、订单数据、调度量、翻台数据和车辆收益。