关于测试:调度算法评测与仿真系统

5次阅读

共计 5229 个字符，预计需要花费 14 分钟才能阅读完成。

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

咱们将两轮车调度和外卖 / 网约车调度做比照，调度波及到工作生成、工作派发和履约管控三个环节。在工作生成环节，两轮车调度的复杂度比外卖 / 网约车调度高，起因在于调度波及到三个因素，调度算法触发的机会须要依靠算法来决策，同时须要兼顾线下各种简单的状况，如天气节令因素，竞对或城管干涉等。在工作派发环节，两轮车调度的复杂度比外卖 / 网约车调度低，起因在于须要匹配的对象少，实时性要求低。在履约管控环节，两轮车调度的复杂度比外卖 / 网约车调度高，起因在于司机运维执行后果难以监管，而外卖 / 网约车有用户评估体系，监管便捷。

两轮车调度的难度是多维且平面的，一是定位不准，不同车辆型号定位的精准度是有差别的；二是车辆扩散，司机须要去收集散落在各地的车辆；三是需要稳定，如季节性的稳定、早晚顶峰的稳定；四是供需失衡，理论投放的车辆数量与用户日益增长的需要匹配不上；五是城市差别，因为城市倒退阶段和管控政策不同，会导致车辆投放与用户需要的差别；六是算法黑盒，会导致算法成果评估比拟含糊；七是信息孤岛，如司机的载具在某个时刻可能会发生变化，但这些信息并不能及时同步到下层用于算法决策；八是计算简单，一系列简单的场景会导致算法的计算复杂度大增。

两轮车调度算法的指标总结下来是多快好省。一是多，咱们心愿算法调度占比高，笼罩的场景多，反对个性化。二是快，可能实时生成、实时派发、实时执行、实时反馈。三是好，咱们心愿让业务叫好，让司机叫好。四是省，既能省人工成本，又能省机器老本。

为了达成指标，咱们制订了解决方案，左侧是咱们解决方案的架构分层图。咱们依据多快好省四个分类，推出了对应的解决措施。一是多，咱们提供了站点组的调度策略，千城千策，调度场景笼罩广。二是快，咱们将需求预测、工作派发与工作决策实时化，并通过门路布局找出最优路线。三是好，咱们通过全局匹配来实现最优化，工作聚合来实现成果好，收益预估来进步收益，精益治理来进步管理效率。四是省，咱们利用弹性计算、MR 调度框架和调度稳定预警，进步机器整体的资源利用率。

调度算法成果评测上有五个挑战，一是效率低，一个迭代均匀成果评估回收工夫须要两周左右。二是不受控，咱们无奈控制线下运维的执行状况。三是烦扰多，线下执行受到的烦扰因素多，成果回收准确度低，导致收益和算法归因含糊。四是品质差，模型上线试验后，成果回收正向率低。五是公信力弱，因为线上成果差，合作方对模型成果信任度低。

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

在物理世界中会存在各种各样的信息，如站点信息、车辆信息、用户骑行事件、调度事件、日期天气特色，订单、收益等。咱们将其演绎成五个维度，站点数据、车辆数据、运力数据、内部数据和评估指标。一是站点数据特色，包含站点根底信息、站点间流转订单、站点实时停驻车辆数、站点历史需求量和站点间骑行工夫。二是车辆数据，包含车辆根底信息、车辆实时标签状态、车辆实时电量、车辆衰弱度和用户骑行收益。三是运力数据，包含司机画像、载具画像、载具实时数据、司机实时排班和运力老本。四是内部数据特色，包含节假日数据、天气特色、竞对实时数据、地图数据和城管干涉。五是评估指标，如缺车数据、订单数据、调度量、翻台数据和车辆收益。

仿真模型是对物理世界行为或规定的模仿，次要会波及到两局部。一是天然流转，指车辆在物理世界天然流动的状况，咱们须要把它模仿进去。二是模型输出，指仿真世界里的一些实时数据，咱们须要提供给调度算法去作为输出数据，如供需上须要预测的数据或运力的模仿数据。

接下来介绍车辆天然流转的仿真实现，车辆天然流转指在某一时刻某一无限空间下，车辆在不同站点之间流动的状况。如图是某一时刻，车辆在不同站点之间流动的轨迹。咱们进行公式提炼，假如某个站点 Sa 在某一时刻流出的车辆总数是 O，流向各个站点的概率为（Si，Pi）。咱们就能够晓得站点 Sa 流向站点 Sb 的车辆状况，或者是站点 Sa 流向站点 Sc 的车辆状况，通过这个计算公式就能够得进去。

第一步咱们要计算某一时刻站点流出的车辆数，会用到三个维度的特色数据，一是站点数据，包含站点根底信息、站点实时车辆数、站点历史需要和站点间车辆骑行时长。二是车辆数据，包含车辆实时电量和车辆实时标签。三是内部数据，包含节假日数据和天气特色。咱们的筛选条件有两个，一是可用日期的筛选，咱们取历史一个月内雷同日期特色的数据，如是否节假日、天气因素类似。二是站点内可用车辆的数据，这里须要剔除异样车辆，如故障车和低电车。举个例子，咱们要计算 2 月 28 日 0 点 10 分的站点车辆流出数据，会获取历史一个月内同样是 0 点 10 分的所有站点数据，依据可用日期作为筛选条件，把雷同日期特色的站点数据筛选进去，汇总取平均值。有了均匀站点车辆数后，咱们还要去看站点内的可用车的状况。如果可用车辆数大于计算出来站点的出站数，就取出站数；如果可用车辆数小于出站数，就取站内可用车辆数。

第二步咱们要计算某一时刻站点间转移概率，会用到两个维度的特色数据。一是站点数据，包含站点间流转订单、站点间车辆骑行时长。二是内部数据，包含节假日数据和天气特色。它是一个统计问题，又因为物理世界中会存在某种意外概率的事件，为了可能模仿这些意外概率的事件，咱们退出轮盘赌抉择法，来使咱们仿真的后果更贴近于物理世界。统计形式有些相似，都是取一个月内雷同日期特色，计算不同站点之间流转概率的均匀汇总。

第三步是联合流出车辆数据和站点间流转概率，模仿特定时刻站点间车辆流转状况。如图所示，0 点 10 分站点 A 流出 10 辆车，联合流转概率，咱们能够得出站点 A 会往 B 流出 5 辆车，站点 A 会往 C 流出 3 辆车，站点 A 会往 D 流出 2 辆车，同样其余站点用相似的计算形式会得出流转形式。仿真会带来一些劣势，一是可能修改谬误，特定日期可能会有异样，如某个站点当日流出 5 辆车，并不代表它的实在需要是 5 辆车，可能是因为这个站点内只有 5 辆车，所以只能最多流出 5 辆车。咱们有历史数据作为根据，能够修改异样值。二是升高必然性，如某些站点某一时刻会因为热点事件，如台风天气或演唱会举办等事件带来需要的稳定，并不代表广泛的成果。

介绍完车辆天然流转模仿，这里有个问题，什么后果是好的仿真后果？于是就有了逼真度的概念。逼真度是用来量化仿真零碎的一种路径，在肯定水平上可能体现出仿真零碎的正确性和可信度。而只有保障仿真零碎的正确性和可信度，仿真后果才具备理论利用价值。

第一个维度是数据源和建模，咱们假如数据源选取某城市、某日期，计算每个站点在每个时刻的实在流出，计算每个站点在每个时刻的仿真流出。咱们会做两个维度的建模，站点维度和工夫维度。站点维度建模是指咱们依照实在流出和仿真流出两个指标，汇总出每一个站点在所有时刻的总流出并排序，会失去站点维度的实在排序和站点维度的仿真排序。工夫维度建模是汇总每个小时在这个城市所有站点的总流出并按工夫排序，得出工夫维度的实在排序和工夫维度的仿真排序。

这里咱们评估逼真度，借鉴了伪工夫排序分数 POS 算法，设计仿真流转排序相似性算法。举个例子，如图是工夫维度的排序，咱们看到依照相似性算法，实在流出在 0 - 1 时是递加的，所以咱们用“-”，0- 2 时是递增的，所以咱们用“+”。仿真流出数据也依照这个逻辑。咱们会发现 0 - 2 时实在流出和仿真流出不统一，因而咱们得出排序相似性是 83%。

根据这样的计算形式，咱们对某个城市某一时刻的数据做逼真度的剖析，会得出两个后果。工夫维度上站点每小时的实在流出与仿真流出，在 24 小时的排序类似度达到 93%；站点维度上排序类似度达到 85%。因而咱们得出，实在流出跟仿真流出的数据具备高度的相似性。

工程撑持次要借助工程的能力，交融特色和模型去实现仿真世界的演变。这里会用到很多的技术能力，如地图引擎、服务调度、报表剖析、过程回放和数仓数据计算。咱们将其演绎成三个维度，包含数据计算、调度中台和前端成果。

仿真数据具备三大特点，一是数据量大，哈啰单车和助力车笼罩近千个城市，近百万站点，近千万辆车，有上亿的订单和 IOT 数据上报。二是数据结构简单，数据起源多样性，导致结构化数据、非结构化数据、半结构化数据都混合在一起。三是计算粒度细、周期长，如果在仿真的时候去长期计算，老本会十分高，因而咱们借助了数仓的离线计算能力，提高效率。

如图是试验创立执行流程，以此介绍调度中台的工作过程。首先是用户在前端创立试验，调度中台通过试验创立环节，会把用户创立试验的配置信息、城市、模型信息存储到在线存储里去。如果用户在前端进行试验执行的操作，调度中台通过试验调度的环节，依据之前配置的信息，整合相干的特色数据的汇合，包含试验周期的约束条件，传递给仿真算法，这是异步的过程。数据传递过来后，仿真算法会依据粒度和周期去调用在线和离线数据作为模型入参，执行算法决策。在周期执行过程中，算法会把过程记录通过音讯的形式实时反馈给调度中台，调度中台会把这些数据进行过程指标的计算，并把过程后果和指标后果落库到在线存储里去。前端就能够实时查看试验的过程，对试验的过程进行操作干涉。仿真算法执行实现后，调度中台会对整个试验数据做存储和规格化的解决，可能给前端提供过程回放和试验数据的展示，这是整个的试验流程。

仿真零碎是咱们算法测试平台的一个子服务，平台还涵盖数据品质监控、服务可用性监测、模型性能评测、模型成果评测、语音辨认评测、文本辨认评测和图像识别评测。算法测试平台采纳微服务的设计思路，最外层有 web 服务层，对接所有的上游前端业务，底层可分为四大核心，包含调度核心（负责所有治理行为，如数据调度，工作治理，策略管理，告警治理，计算调度等）、数据计算中心（负责所有计算行为，如实时 & 离线数据计算，数据转换，数据勘误等）、数据分析统计核心（负责指标统计类行为，因为指标计算规定变动频繁且灵活多样，因而在该核心下连贯多个脚本环境容器，如 python，groovy 等，通过平台在线编辑能力，容许用户灵便调整，随时变更指标剖析与统计脚本）和数据中心（负责所有内外部数据拜访收口及三方服务拜访收口，并通过进步该服务的利用等级，保障整个零碎的稳定性），它们各司其职，保障合作的稳定性和迭代开发的效率。

前端成果总览包含试验的治理、仿真过程回放和各项指标评测后果。一是仿真实验室，作为仿真零碎的入口，提供了试验创立、筛选和试验过程管控。二是试验配置，能够去设置试验相干的参数，如仿真区域、工夫区间、工夫粒度等。三是仿真回放，咱们嵌入了地图的渲染引擎，提供观测不同模型的车辆流转成果和数据变动过程的能力。四是实验报告，提供各项评估指标数据、报表化展现、穿插比照验证的能力。

仿真零碎的收益归纳起来有六点，一是城市笼罩，原先城市笼罩的数量无限且老本高，仿真零碎能够反对全国 400 多个城市的任意抉择。二是评估效率，原先评估效率是周级别，仿真零碎评估效率是小时级别。三是线上品质，原先线上回收正向率低，仿真零碎线上回收正向率预计进步两倍。四是评估指标，原先评估指标比较简单，回收也绝对麻烦，仿真零碎能够定制多维度的指标。五是烦扰因素，原先有很多不可控因素，仿真零碎烦扰项都是可感知可管制的。六是过程剖析，原先过程变动是看不到的，仿真零碎过程可回放、可剖析。

以后咱们是在平台化阶段，依靠仿真平台化建设，实现车辆调度类算法评测赋能，带来六大收益。前面咱们心愿可能实现场景化，借助场景化建模，实现业务场景无感接入，灵便扩大。第三个阶段是智能化仿真世界，咱们心愿可能实现智能感知特色数据、自主学习规定模型、智能剖析评测成果。最初是业务赋能，咱们心愿可能赋能更多的业务场景，去实现线下的推演和可行性的验证，助力业务的高速增长。

（本文作者：陈震）