出租车在城市公共交通中扮演非常重要的角色,如何降低出租车空载率,解决乘客打车难问题是城市生活中面临的重大课题。出租车拼车系统能够根据乘客需求自动匹配出租车,实现出租车一次行程搭载多个乘客,提高出租车资源利用率。这不仅有效降低公众出行费用,而且有助于提倡人们减少自驾出行,从而缓解交通拥堵和减轻环境污染,具有重要的现实意义。目前,针对出租车拼车问题的研究中,出租车是根据时间约束和载客量限制筛选的,忽略了实时交通状况对车辆的影响。这种算法有两方面问题:一方面,系统可能将拥堵路段的出租车分配给乘客,导致出租车不能按时到达预定地点,从而降低拼车服务的准确性。另一方面,拥堵路段上的出租车基本上是不可能为乘客提供所要求的服务,但系统仍然对拥堵路段的出租车进行搜索和调度,影响系统应答速度。因此,如何过滤掉拥堵路段的出租车,提高出租车拼车的准确性和应答速度是一个值得研究的重要问题。为了解决上述问题,本文提出了基于城市实时路况的动态拼车算法(Dynamic Carpooling 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 Based on 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最快调度策略可以快速应答。