详情

原文传递基于城市实时路况的动态拼车算法研究

论文题名：	基于城市实时路况的动态拼车算法研究
关键词：	动态拼车算法;城市实时路况;出租车;搜索算法;调度策略
摘要：	出租车在城市公共交通中扮演非常重要的角色，如何降低出租车空载率，解决乘客打车难问题是城市生活中面临的重大课题。出租车拼车系统能够根据乘客需求自动匹配出租车，实现出租车一次行程搭载多个乘客，提高出租车资源利用率。这不仅有效降低公众出行费用，而且有助于提倡人们减少自驾出行，从而缓解交通拥堵和减轻环境污染，具有重要的现实意义。　　目前，针对出租车拼车问题的研究中，出租车是根据时间约束和载客量限制筛选的，忽略了实时交通状况对车辆的影响。这种算法有两方面问题:一方面，系统可能将拥堵路段的出租车分配给乘客，导致出租车不能按时到达预定地点，从而降低拼车服务的准确性。另一方面，拥堵路段上的出租车基本上是不可能为乘客提供所要求的服务，但系统仍然对拥堵路段的出租车进行搜索和调度，影响系统应答速度。因此，如何过滤掉拥堵路段的出租车，提高出租车拼车的准确性和应答速度是一个值得研究的重要问题。　　为了解决上述问题，本文提出了基于城市实时路况的动态拼车算法(DynamicCarpooling algorithm Based on Urban Real-time Traffic Conditions DC-RTTC),DC-RTTC拼车算法包括:DC-RTTC候选出租车搜索算法和DC-RTTC调度策略。为了验证本文提出的拼车算法，采用北京市2008年2月10355辆出租车产生的GPS轨迹数据集和实验平台TaxiQueryGenerator进行实验。实验结果表明，DC-RTTC拼车算法提高了拼车服务的准确性和响应速度。本文主要研究工作如下: 　　(1)介绍现有出租车拼车问题的特点，对相关研究进行了系统的总结和分析。在定义了出租车拼车问题的基础上，介绍了出租车拼车问题的研究现状，归纳动态拼车存在的问题和面临的挑战，如:人和车位置不确定性、实时准确的应答、计算准确的行驶时间等。综述了几种拼车系统，对这几种拼车系统的框架和工作流程进行分析，并指出了这几种拼车系统的优缺点。　　(2)设计基于城市实时路况的动态拼车系统框架（Dynamic Carpooling Framework Basedon Urban Real-time Traffic Conditions RTC）和数据模型。数据模型包含:乘车请求、出租车状态、路况信息和网格索引。系统框架包含4个模块:数据交互模块、RTTC模块、搜索模块和调度模块。数据交互模块接收乘车请求和出租车状态，并将这些数据发送给搜索模块;RTTC模块将实时的路况信息发送给搜索模块;搜索模块根据时间约束、最大载客量约束和路况信息筛选出租车，并将筛选出来的候选出租车集合发送给调度模块;调度模块对候选集合中每一辆出租车进行插入可行性检查，并计算得到一辆“合适”的出租车推荐给乘客。　　(3)提出基于城市实时路况的候选出租车搜索算法。DC-RTTC候选出租车搜索算法采用了RTC系统框架，考虑道路拥堵状况对车辆行驶速度的影响，引入道路拥堵系数，将路况划分为不同的等级，并根据拥堵系数计算行驶时间。DC-RTTC候选出租车搜索算法的工作流程大致为:首先，根据时间约束和路况信息筛选出发地和目的地附近的网格;其次，根据时间约束、最大载客量约束和路况信息筛选目标网格内的出租车;最后，得到出租车候选集。　　(4)提出基于城市实时路况的调度策略。DC-RTTC调度策略包含DC-RTTC最优调度策略和DC-RTTC最快调度策略，DC-RTTC调度策略需要检查插入可行性，确保将新的出发地和目的地插入到出租车行程计划表后，不违反到达原行程计划表其他点的时间约束。同时，出租车为了接送新乘客会比原行程计划多绕行一段距离，为了减少出租车的燃油成本，DC-RTTC最优调度策略，推荐绕行距离最小的出租车给乘客。DC-RTTC最快调度策略推荐首辆满足条件的出租车，在处理大规模乘车请求时，DC-RTTC最快调度策略可以快速应答。
作者：	郝莉萍
专业：	软件工程
导师：	覃少华
授予学位：	硕士
授予学位单位：	广西师范大学
学位年度：	2017
正文语种：	中文