Research On Dynamic Carpooling Algorithm Based On Urban Real-time Traffic Conditions

Taxi in the urban public transport plays a very important role,how to reduce the taxi no-load rate and passengers take the taxi difficult is a major problem that the urban life is facing.Taxi carpooling system can automatically match the taxi according to the needs of passengers,achieve a taxi trip with multiple passengers,improve the utilization of taxi resources.This is not only effective in reducing public travel costs,but also help to promote people to reduce travel by car,thus easing traffic congestion and reduce environmental pollution,has important practical significance.At present,in the study of taxi carpooling problems,the taxi is screened according to the time constraints and the capacity limit,ignoring the real-time traffic conditions on the impact of the vehicle.There are two problems with this algorithm:On the one hand,the system maybe assign a taxi which in the congested road to the passenger,causing the taxi fail to reach the intended location on time,reduce the accuracy of the carpool service.On the other hand,the taxi on the congested road is basically impossible for the passengers to provide the requested service,but the system still searches and dispatches the taxi which is on the congested road,that is affect the speed of the system.Therefore,how to filter out the taxi which on the congestion road,improve the accuracy of taxi and the system speed of response is an important issue worthy of study.In order to solve the above problems,this paper presents a Dynamic Carpooling algorithm Based on Urban Real-time Traffic Conditions.DC-RTTC carpooling algorithm includes:DC-RTTC candidate taxi searching algorithm and DC-RTTC dispatching strategy.In order to verify the proposed carpooling algorithm,this paper uses the GPS trajectory data set generated by 10355 taxis in Beijing in February 2008 and the experimental platform TaxiQueryGenerator to carry out the experiment.The experimental results show that the DC-RTTC carpooling algorithm improves the accuracy and response speed of taxi carpooling.The main work in this paper is as follows:(1)Introduce the characteristics of the existing taxi carpool problem,and makes a systematic summary and analysis of the related research.On the basis of defining the taxi carpooling problem,this paper introduces the research status of taxi carpooling problem,summarize the problems and challenges of dynamic carpooling,such as:the uncertainty of person and vehicle' location,real-time and accurate response,calculate the exact travel time and so on.Several carpooling systems are reviewed,also analyzes the framework and working flow of these carpooling systems.Points out the advantages and shortcomings of these carpooling systems.(2)Dynamic Carpooling Framework and data model based on Urban Real-Time Traffic Conditions(RTC)is designed.The data model includes:ride request,taxi status,traffic condition information and grid index.The system framework consists of four modules:the data interaction module,the RTTC module,the search module and the dispatching module.The data interaction module receives the ride request and the taxi status,also sends the data to the search module;The RTTC module sends the real-time traffic condition information to the search module;The search module filters the taxi according to the time constraint,the maximum passenger volume constraint and the traffic condition information,and the selected candidate taxi collection is sent to the dispatching module;The dispatching module performs a feasibility check on each taxi in the candidate set and recommends a "fit" taxi to the passenger.(3)The Candidate Taxi Search algorithm based on Urban Real-time Traffic Conditions is Proposed.DC-RTTC Candidate Taxi Search algorithm uses the RTC system framework considering the impact of road congestion on the speed of vehicle,the road congestion coefficient is introduced,and the traffic conditions are divided into different grades,the travel time is calculated according to the congestion coefficient.The work flow of the DC-RTTC Candidate Taxi Search algorithm is as follows:Firstly,the grid on both sides of the origin and destination is selected according to the time constraint and traffic condition information;Secondly,search the taxi within the target grid according to the time constraint,the maximum capacity constraint and the traffic condition information;Finally,get a taxi candidate set.(4)The dispatching strategy based on Urban Real-time Traffic Conditions is proposed.DC-RTTC dispatching strategy contains DC-RTTC optimal dispatching strategy and DC-RTTC fastest dispatching strategy.DC-RTTC dispatching strategy needs to check the insertion feasibility to ensure that the new departure and destination are inserted into the taxi dispatch does not violate the time constraints to reach the rest of the original itinerary dispatch.At the same time,the taxi in order to pick up new passengers than the original itinerary plan to bypass a certain distance,in order to reduce the fuel costs of the taxi,the DC-RTTC optimal dispatching strategy,recommends a taxi which has the smallest bypass distance to the passengers.DC-RTTC fastest dispatching strategy recommends the first taxi which meets the conditions,in dealing with large-scale travel requests,DC-RTTC fastest dispatching strategy can quickly respond.