本文作者：陈震
哈啰两轮车调度算法介绍
调度是将稀缺资源分配到必定时刻内的不同使命上的决议计划进程，目的是优化一个或多个方针。两轮车调度场景是指经过预测未来用户的骑行需求，决定各站点车辆的分配使命，并将这些使命分配给适宜的运维人员来履行，从而满意用户的骑行需求。在这个调度场景里会涉及三个方针，一是车辆，方针是用户需求满意率高，移车本钱低，车辆翻台高。二是运维，方针是运维功率高，运维人员体验好。三是用户，方针是用户体验好。
咱们将两轮车调度和外卖/网约车调度做比照，调度涉及到使命生成、使命派发和履约管控三个环节。在使命生成环节，两轮车调度的杂乱度比外卖/网约车调度高，原因在于调度涉及到三个要素，调度算法触发的时机需求依托算法来决议计划，一起需求兼顾线下各种杂乱的状况，如气候季节要素，竞对或城管干涉等。在使命派发环节，两轮车调度的杂乱度比外卖/网约车调度低，原因在于需求匹配的方针少，实时性要求低。在履约管控环节，两轮车调度的杂乱度比外卖/网约车调度高，原因在于司机运维履行成果难以监管，而外卖/网约车有用户点评体系，监管快捷。
两轮车调度的难度是多维且立体的，一是定位禁绝，不同车辆类型定位的精准度是有差异的；二是车辆涣散，司机需求去搜集散落在各地的车辆；三是需求动摇，如季节性的动摇、迟早高峰的动摇；四是供需失衡，实际投进的车辆数量与用户日益增长的需求匹配不上；五是城市差异，由于城市发展阶段和管控政策不同，会导致车辆投进与用户需求的差异；六是算法黑盒，会导致算法作用评价比较含糊；七是信息孤岛，如司机的载具在某个时刻或许会发生变化，但这些信息并不能及时同步到上层用于算法决议计划；八是核算杂乱，一系列杂乱的场景会导致算法的核算杂乱度大增。
两轮车调度算法的方针总结下来是多快好省。一是多，咱们期望算法调度占比高，掩盖的场景多，支持个性化。二是快，可以实时生成、实时派发、实时履行、实时反馈。三是好，咱们期望让事务叫好，让司机叫好。四是省，既能省人工本钱，又能省机器本钱。
为了到达方针，咱们制定了处理方案，左边是咱们处理方案的架构分层图。咱们依据多快好省四个分类，推出了对应的处理措施。一是多，咱们供给了站点组的调度战略，千城千策，调度场景掩盖广。二是快，咱们将需求预测、使命派发与使命决议计划实时化，并经过途径规划找出最优路线。三是好，咱们经过大局匹配来完成最优化，使命聚合来完成作用好，收益预估来进步收益，精益办理来进步办理功率。四是省，咱们运用弹性核算、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多个城市的恣意选择。二是评价功率，原先评价功率是周级别，仿真体系评价功率是小时级别。三是线上质量，原先线上收回正向率低，仿真体系线上收回正向率预计进步两倍。四是评价目标，原先评价目标比较简单，收回也相对麻烦，仿真体系可以定制多维度的目标。五是搅扰要素，原先有许多不可控要素，仿真体系搅扰项都是可感知可操控的。六是进程剖析，原先进程变化是看不到的，仿真体系进程可回放、可剖析。
当前咱们是在渠道化阶段，依托仿真渠道化建造，完成车辆调度类算法评测赋能，带来六大收益。后边咱们期望可以完成场景化，借助场景化建模，完成事务场景无感接入，灵敏扩展。第三个阶段是智能化仿真国际，咱们期望可以完成智能感知特征数据、自主学习规矩模型、智能剖析评测作用。最后是事务赋能，咱们期望可以赋能更多的事务场景，去完成线下的推演和可行性的验证，助力事务的高速增长。
重视公众号「哈啰技术」，第一时刻收到最新技术推文。
