哈罗单车:调度算法评测与仿真系统(中)

发表于:2022-9-27 09:42

字体: | 上一篇 | 下一篇 | 我要投稿

 作者:陈震    来源:掘金

  仿真模型
  仿真模型是对物理世界行为或规则的模拟,主要会涉及到两部分。一是自然流转,指车辆在物理世界自然流动的情况,我们需要把它模拟出来。二是模型输入,指仿真世界里的一些实时数据,我们需要提供给调度算法去作为输入数据,如供需上需要预测的数据或运力的模拟数据。
  接下来介绍车辆自然流转的仿真实现,车辆自然流转指在某一时刻某一有限空间下,车辆在不同站点之间流动的情况。如图是某一时刻,车辆在不同站点之间流动的轨迹。我们进行公式提炼,假设某个站点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%。因此我们得出,真实流出跟仿真流出的数据具有高度的相似性。
  本文内容不用于商业目的,如涉及知识产权问题,请权利人联系51Testing小编(021-64471599-8017),我们将立即处理
《2023软件测试行业现状调查报告》独家发布~

关注51Testing

联系我们

快捷面板 站点地图 联系我们 广告服务 关于我们 站长统计 发展历程

法律顾问:上海兰迪律师事务所 项棋律师
版权所有 上海博为峰软件技术股份有限公司 Copyright©51testing.com 2003-2024
投诉及意见反馈:webmaster@51testing.com; 业务联系:service@51testing.com 021-64471599-8017

沪ICP备05003035号

沪公网安备 31010102002173号