Research On Dynamic Carpool Scheduling Algorithm Based On Big Traffic Data

With the number of urban cars showing an explosive growth trend,it has caused serious traffic congestion and environmental pollution problems.An efficient carpooling scheduling system is an effective solution.It can benefit passengers,improve the income of taxi drivers,and at the same time,reduce the pollution of the environment and energy consumption.With the continuous development of smart phone GPS Technology,based on the smart phone GPS data to achieve an efficient carpooling scheduling system has become urgent needs of the construction of the modern city.However,it is challenging to design an efficient carpooling algorithm.Compared with the no-ridesharing schedule,ridesharing schedule has more complex scheduling strategy.In practical application system,ridesharing is a process of dynamic change,while doing scheduling optimization,it also need to ensure the real-time performance.Another challenging reason for carpooling is that the passenger's inquiries and the location information of the taxi are highly dynamic and difficult to predict.To address these challenges,in this paper,we through the study of the data mining and analysis of traffic data to build a taxi carpooling scheduling system based on the hot spot,it can effectively provide real-time taxi service to the passenger taxi request,and generate the corresponding scheduling program to meet the needs of passengers.At the same time,the system can significantly reduce the total travel distance of the taxi.In our scheduling method,mainly divided into two stages,search and scheduling phase.In the search phase,a binary search strategy based on time is proposed to quickly and efficiently retrieve candidate sets of taxis that may meet the needs of the trip request.In the scheduling phase,according to the restrictions in the trip request to check the every taxi in the taxi candidate set,and select the taxi which satisfies the request with the maximum average satisfaction to provide services for passengers.In order to reduce the no-load rate,a hot spot based scheduling strategy is then proposed for empty vehicle scheduling,and the optimization of map data access is set up.Among them,the selection of hot spots,the demand forecast of taking a taxi and the scope of the empty car scheduling parameters are through the analysis of real trip data with reasonable setting.After that,we consider the big data application scenarios,given the carpooling scheduling system implementation of Spark,considering the real-time demand we use Spark Streaming and Kafka message queue technology on the platform of data receiving,data processing and data feedback modules for the reasonable design.Finally,we evaluated our system using a large scale taxi dataset containing 101,952 trips in Beijing Chaoyang District over one day generated by a taxi request simulator.The result shows that our proposed method can achieve a 40% service rate increase and saving 30% travel distance.Compared with the existing method can achieve a 15% service rate increase and saving 17% travel distance.