面向大规模拼车出行的最优路径规划算法研究

发布时间：2020-03-20 20:32

【摘要】：随着移动智能手机等设备的不断发展和普及,拼车出行已经成为大众接受并选择的出行方式之一。在本文解决的拼车出行场景中,乘客和司机都有自身行程的约束,还可以在拼车请求中提出各自的时间约束和费用约束。当拼车过程中出现多名乘客共同乘车的情况时,则需要满足车上所有乘客和司机的拼车约束。考虑到缓解交通压力、节能减排等因素,本文的目标是为乘客找到一名能够满足双方拼车要求并且绕路距离最小的司机,以及其对应的最优拼车路径。现有的拼车算法在解决上述问题中,普遍存在如下缺陷。(1)拼车设定不够人性化:仅考虑乘客的拼车要求,忽略司机也有拼车时间的约束条件。(2)计费方式不合理:直接给所有拼车乘客予以一定的费率折扣,忽视了拼车对已有乘客影响更大,应该给予更多补偿。(3)拼车路线不够合理:只查找乘客附近司机来提供接送服务,不考虑司机是否顺路。因此,本文需要解决的难点包括以下两项:(1)如何制定合理的拼车计费模型;(2)如何在大规模拼车场景中保证最优路径规划算法的实时性和高效性;为了解决上述挑战,本文首先提出了一种拼车计费模型。该模型同时适用于一名司机接送一名乘客和接送多名乘客的拼车场景。除了考虑到需要平衡司机和乘客的利益之外,还考虑到新乘客拼车后对车上已有乘客产生的行程延误影响,而设计了对已有乘客的补偿机制。随后在该计费模型的基础上,本文设计并实现了相应的最优路径规划算法URoad。该算法首先采用了出发时间筛选和欧氏距离筛选的剪枝技术,在算法前期通过较小的时间代价删除了大量不满足要求的司机。然后在后续的路径规划中采用了贪心策略,加快了算法的整体运行效率。本文最后还设计了相应的实验来验证算法整体和各个阶段的高效性与有效性。实验表明,在10万名司机中,为一名乘客查找满足所有拼车条件并且产生绕路距离最小的司机及其对应的最优路径,耗时不超过0.5秒。
【图文】：

小客车,私人,意见,上海

第1章绪论1.1 研究背景及意义.1.1 研究背景随着经济的发展，城市中私家车的数量也不断地增多[1]，这使得交通压力日趋增大别是早晚高峰时期道路更是拥堵不堪[2]，随之而来的空气污染等环境问题也日益严重。近年来，，作为解决交通问题的有效手段之一，拼车开始受到政府等职能部门的高度[3]。自 2014 年来，各地政府也出台了拼车出行规范和指导意见[4,5]。2016 年 12 月 21 日京上海率先落地拼车新规，与之前出台的《关于规范本市私人小客车合乘出行的实施(征求意见稿)》[6],[7]相比，落地新规在车辆、定价等方面都进行了相应调整，调整之新规显现出更多的对拼车的鼓励。

时空索引,乘客,司机

边动态规划的优化算法和一种精心设计的下线剪接送一名乘客的拼车出行方式在行程体验上会更解交通压力而言，一名司机匹配多名乘客的拼车的现实意义。多名乘客24]提出了一种面向大规模出租车实时拼车的问题。时间约束，动态地为乘客查找满足要求的司机并提服务。[23]提出了一个针对出租车的大规模动态拼车问题机的时空索引，如图 2-2 所示。使用该时空索引从而加快查找最优司机及接送路径的目的来解决
【学位授予单位】：浙江工业大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O221

【相似文献】