网约车辆在线均衡调度分派算法的研究与实现

发布时间：2020-04-18 20:43

【摘要】：随着GPS、Wi-Fi、RFID以及Bluetooth等无线网络技术与传感器设备的大量普及,出现了越来越多的车辆推荐系统,这些车辆的移动轨迹数据也能够被不断的收集,通过分析与挖掘这些历史轨迹数据,可以更好的改善车辆推荐系统。车辆推荐系统可以更好的在用户与车辆之间进行调度,更准确地进行车辆推荐与路线规划,减少车辆盲目行驶,对于增加车辆的收入,减少用户等待时间,缓解交通阻塞,以及减少环境污染都有着很强的现实意义。传统的车辆推荐系统主要关注于用户的满意程度,即尽可能地减少用户的等待时间,而忽略了车辆之间的公平性,这些系统趋向于推荐离用户最近的空乘车辆。本文通过对真实历史轨迹数据进行统计分析发现,随着推荐次数增加,车辆之间的收入差异变得越来越大。异于传统的车辆推荐系统,本文的目的就是对于不断产生的用户请求,根据一些策略将请求推荐给车辆,使得推荐结果即能保证车辆之间分配的公平性,又能保证较短的用户等待时间。然而,通过分析,我们发现这两者是一个权衡问题,无法同时达到最优。本文首先针对Brute-force算法与Greedy算法在解决该问题存在的不足,提出了一个高效的RRA-LSP算法。Brute-force算法属于暴力算法,对于每一个用户请求,都直接从整个城市中寻找最优的车辆,并为其规划行驶路线。该算法的时间复杂度较高,但结果准确。Greedy算法属于近似算法,每次都是在以用户请求为圆心,半径为3000米的范围内寻找局部最优的车辆。该算法相对较快,但很难得到最优推荐结果。RRA-LSP算法则为一个高效的算法,而且能够得到与Brute-force算法一致的准确解。RRA-LSP算法首先不断地缩小搜索范围,直到达到一定的条件,得到最终的搜索范围。通过严格证明发现,最优车辆一定在该范围内。最后,我们只需要在该范围内寻找到最优车辆,然后推荐给用户。对于多用户请求场景下产生的冲突问题,我们提出了相应的冲突处理规则,并设计了一个均衡调度机制,用于对多用户请求的分配。通过对比在两个真实道路网络数据集上的实验结果表明,本文提出的算法不仅能减少车辆之间的收入差异,而且能保证较短的用户等待时间,并且进一步验证了RRALSP算法的高效性与准确性,相比传统的车辆推荐算法,能够更好地保证车辆之间分配的公平性。
【图文】：

累积分布,出租车,车辆,场景

法的推荐结果来看，都是推荐可以使得用户等待时间尽可能小的车辆给用户，而并没有考虑到车辆之间分配的公平性问题。图2.1 现实场景的在线车辆推荐问题为了更好的引出本文的推荐方法，我们先对真实的出租车历史轨迹数据进行分析。在这里我们统计分析了上海市 2500 多辆网约出租车 5 天的历史轨迹数据，并有了以下的一些统计结论。如图 2.2，是乘客搭乘出租车的时间的分布与累积分布图，从图中可以发现，大概 80%的乘客打车时间少于 20 分钟，，这意味着大部分乘客的目的地

累积分布,累积分布,乘客,出租车

分配的公平性，而且能保证较短的乘客等待时间。（a）（b）图2.2 乘客搭乘出租车的时间的分布于累积分布图（a）（b）图2.3 乘客的等待时间的分布于累积分布图
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：U495

【参考文献】