Urban Bus Route Planning Based On GPS Trajectory Data And Trajectory Indexing

In recent years,research on data mining based on GPS trajectory data has attracted the attention of many researchers,especially in the field of taxi operation.However,the research on bus route planning based on GPS trajectory data is still relatively rare,and the breadth and depth of the research are still lacking.There is no multivariate and accurate evaluation system in those existing methods which don't combine with the reality and lack constraints.Therefore,the focus of this thesis is to use GPS trajectory data to design bus stops and bus routes.In view of the actual situation and the deficiencies of the existing works,this thesis mainly does the following works:(1)A clustering algorithm based on center point distance is proposed for the selection of bus stops.Then we optimize the clusters.The stops are selected based on the optimized clusters.After that we use the entropy weight method and the TOPSIS method to comprehensively evaluate the bus station system from multiple indices.(2)Given the bus route origin,destination,candidate bus stops as well as bus capacity constraints,we build the search tree to generate candidate bus routes,and then we select the best route which expects the maximum number of passengers under the given conditions.The best route is selected based on the formula of the number of passengers on a single route.(3)After the above works,we propose an algorithm based on R-tree for trajectory indexing,which takes into account the time factor and the repetition rate between nodes to achieve the purpose of efficient indexing of trajectory points.