The Research Of Urban Transit Routing Problem Based On Genetic Algorithm

Without considering setting bus stops, the urban transit network design problem (UTNDP) can be mainly divided into two problems which are the urban transit routing problem (UTRP) and the urban transit scheduling problem (UTSP). The former involves constructing efficient transit routes on an existing transit network, with predefined bus stops. On the other hand, the latter is charged with assigning the schedules for the passenger carrying vehicles.This thesis only focuses on the urban transit routing problem. To generate efficient transit routes we need to ensure the quality of the chosen representation, the effectiveness of the initialization procedures and feasibility check procedures and the suitability of the chosen neighborhood moves. Last but not least we need effective optimization algorithm. Due to the generality and efficiency for solving optimization problems, this thesis has proposed a solution for the urban transit routing problem based on genetic algorithm. And all the implementation details are listed. At the same time the constraints of the urban transit routing problem have also been discussed.Mandl's Swiss transit network seems to be the only benchmark problem. In order to compare solution generated by this thesis with solutions generated by other researchers, this thesis will also use that benchmark data. At the same time, this thesis also proposed a data set generation algorithm to generate initial data according to user's needs and actually generated some data by that algorithm to test the method proposed in this thesis on a larger scale.