Night Bus Route Planning Over Large-scale Taxi Trajectories

With the acceleration of urbanization and urban population boom,more and more people have to travel for life or commute at night,which leads to the public transportation facing with the contradiction between the rapid growth of demands and the supply of services.Therefore,how to design an optimized bus route to meet the needs of the majority of people who travel at night become the key to solve this problem.The traditional methods of designing bus routes mainly depend on the form surveys to investigate the travel patterns of citizens.But this method is timeconsuming and with low efficiency.They can not adapt to frequent changes of road networks and traffic demands.To solve this problem,this paper analyzes large-scale real taxi trajectories to understand the rules of dynamic traffics and crowds by using big data analysis technologies.Then we present a solution to plan urban night bus stations and routes.Our major work in this paper are listed as follows:(1)By investigating the existing bus line planning work,we summarizes the pros and cons of related work on travel demand prediction and bus station layout.Then we propose a method to extract mobility patterns of citizens by large-scale taxi GPS trajectories and transactions in order to design more reasonable bus lines.(2)The related technologies involved in this work are studied in detail.We further describe the differences among existing clustering algorithms.We discuss the main features for each category in detail.The blind search algorithm and heuristic search algorithm are introduced in detail.Examples are given to compare these two algorithms.(3)An improved density-based clustering algorithm(DC-DBSCAN)is proposed to determine the locations of night bus stations.Firstly,we preprocess transaction and GPS trajectories data generated by about 15,000 taxis at Shenzhen in a month.An improved density-based clustering algorithm is proposed to explore the hot spots of traffic in the city at night.Candidate bus stations are selected based on these hot spots.Experimental results show the validity of the proposed algorithm.(4)A heuristic algorithm(BR)is proposed for the planning of night bus routes.First of all,reasonable rules are established to construct a candidate bus route graph,which can be pruned according to some specific conditions to reduce the size of the graph.Then we use the BR algorithm to generate a night bus line from Shenzhen Huanggang station to Dexing Garden station.Experiments show the convergence of the BR algorithm.And the generated candidate bus lines are analysised.We compare the performance between the BR algorithm and the Top-K algorithm in terms of the algorithm efficiency and bus line results.Experimental results show that the BR algorithm not only can find a satisfactory bus line,but also is about 12 times higher efficiency than that of the Top-K algorithm.Finally,we compares the rationality and feasibility of the bus lines generated by our method with the newly opened night bus line.