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

草帽路飞UU

　仿真模型


仿真模型是对物理世界行为或规则的模拟，主要会涉及到两部分。一是自然流转，指车辆在物理世界自然流动的情况，我们需要把它模拟出来。二是模型输入，指仿真世界里的一些实时数据，我们需要提供给


调度算法去作为输入数据，如供需上需要预测的数据或运力的模拟数据。




接下来介绍车辆自然流转的仿真实现，车辆自然流转指在某一时刻某一有限空间下，车辆在不同站点之间流动的情况。如图是某一时刻，车辆在不同站点之间流动的轨迹。我们进行公式提炼，假设某个站点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%。


因此我们得出，真实流出跟仿真流出的数据具有高度的相似性。