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

发布时间：2018-05-02 02:14

本文选题：动态拼车 + 实时路况　；参考：《广西师范大学》2017年硕士论文

【摘要】：出租车在城市公共交通中扮演非常重要的角色,如何降低出租车空载率,解决乘客打车难问题是城市生活中面临的重大课题。出租车拼车系统能够根据乘客需求自动匹配出租车,实现出租车一次行程搭载多个乘客,提高出租车资源利用率。这不仅有效降低公众出行费用,而且有助于提倡人们减少自驾出行,从而缓解交通拥堵和减轻环境污染,具有重要的现实意义。目前,针对出租车拼车问题的研究中,出租车是根据时间约束和载客量限制筛选的,忽略了实时交通状况对车辆的影响。这种算法有两方面问题:一方面,系统可能将拥堵路段的出租车分配给乘客,导致出租车不能按时到达预定地点,从而降低拼车服务的准确性。另一方面,拥堵路段上的出租车基本上是不可能为乘客提供所要求的服务,但系统仍然对拥堵路段的出租车进行搜索和调度,影响系统应答速度。因此,如何过滤掉拥堵路段的出租车,提高出租车拼车的准确性和应答速度是一个值得研究的重要问题。为了解决上述问题,本文提出了基于城市实时路况的动态拼车算法(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最快调度策略可以快速应答。
[Abstract]:Taxi plays a very important role in urban public transportation. How to reduce the taxi ride rate and solve the problem is a major problem in urban life. Taxi system can automatically match taxis according to the needs of passengers, carry out a number of passengers on one trip and improve the utilization of taxi resources. This not only effectively reduces the public travel costs, but also helps to promote people to reduce self driving travel, thus alleviating traffic congestion and mitigating environmental pollution, which is of great practical significance. At present, taxis are screened according to time constraints and passenger volume restrictions, ignoring real-time traffic conditions. There are two problems in this algorithm. On the one hand, the system may distribute the taxi to the passengers, causing the taxi to not arrive at the scheduled place on time, thus reducing the accuracy of the carpool service. On the other hand, the taxi on the congested section is basically impossible to provide the required service for the passengers, but the system is not available. The taxis of the congested sections are still searched and scheduled, which affects the response speed of the system. Therefore, how to filter the taxi and improve the accuracy and response speed of the taxis is an important problem to be studied. In order to solve the above problems, a dynamic carpool algorithm based on urban real-time road conditions (D) is proposed. Ynamic Carpooling algorithm Based on Urban Real-time Traffic Conditions DC-RTTC), DC-RTTC carpool algorithm includes: DC-RTTC candidate taxi search algorithm and scheduling strategy. In order to verify the proposed algorithm, 10355 taxis produced in February 2008 in Beijing are used for trajectory data set and experimental platform The experimental results show that the DC-RTTC carpool algorithm improves the accuracy and response speed of the carpool service. The main research work of this paper is as follows: (1) the characteristics of the existing taxi carpool problems are introduced, and the related research is systematically summarized and analyzed. Based on the definition of the taxi carpool problem, the taxis are introduced. The current research status of the carpool problem, the problems and challenges facing the dynamic carpool, such as the uncertainty of the human and car position, the real-time and accurate response, the accurate driving time, etc. several carpool systems are summarized, and the framework and work flow of these kinds of carpool systems are analyzed, and the advantages and disadvantages of these kinds of carpool systems are pointed out. (2) design the dynamic carpool system framework (Dynamic Carpooling Framework Based on Urban Real-time Traffic Conditions RTC) and data model based on urban real time road conditions. The data model includes: Passenger request, taxi status, road condition information and grid index. The system frame contains 4 modules: data interaction module, RTTC module, search model Block and scheduling module. The data interaction module receives the bus request and taxi status, and sends these data to the search module; the RTTC module sends the real-time traffic information to the search module; the search module selects the car by the maximum passenger volume constraint and road condition information according to the time constraints, and sets the selected candidate taxis to send. Send the scheduling module, the scheduling module inserts the feasibility check for each taxi in the candidate set, and calculates a "suitable" taxi recommendation to the passengers. (3) the candidate taxi search algorithm.DC-RTTC based on the city real time road condition is proposed, and the RTC system framework is used to consider the road congestion. The influence of the condition on the speed of the vehicle, the road congestion coefficient is introduced, the road conditions are divided into different grades, and the work flow of the.DC-RTTC candidate taxi search algorithm based on the congestion coefficient is roughly as follows: first, the grid of the hair and the destination is screened according to the time constraint and the road condition information; secondly, according to the time. Constraints, maximum passenger traffic constraints and traffic information screening taxis within the target grid; finally, get a taxi candidate set. (4) a scheduling strategy based on the urban real-time traffic scheduling strategy.DC-RTTC scheduling strategy includes the DC-RTTC optimal scheduling strategy and the DC-RTTC fastest scheduling strategy, and the DC-RTTC scheduling policy needs to check the insert feasibility to ensure the new When the departure and destination are inserted into the taxi schedule, it does not violate the time constraints that arrive at the other points of the original schedule. At the same time, the taxi will bypass the original schedule more than the original schedule. In order to reduce the fuel cost of the taxi, the DC-RTTC optimal scheduling strategy recommends the least bypass taxi to the taxi. The fastest.DC-RTTC passenger scheduling strategy recommends the first taxi that meets the requirements. The DC-RTTC's fastest scheduling strategy can respond quickly when dealing with large scale requests.

【学位授予单位】：广西师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：U491

【参考文献】