Bus Network Design Problem And Its Genetic Algorithm

Bus network design problem is a optimization decision problem of traffic net-work extension in order to cope with the increasing traffic demand, it is a classical optimization problem in operational research.Genetic algorithm is a search algorithm by simulating natural biological evo-lution. Because of strongly global search capacity and better robustness, it is an effective method to solve the bus network design problem. This paper introduces the basic theory of genetic algorithms. To apply the feasible paths of any two bus stations flexibly, a shortest path method to get all the feasible paths is given.Combined the genetic algorithm and the bus network design problem together, this paper established a mathematical model based on minimum cost. According to the structure of feasible solution, put forward the corresponding genetic algorithm, this algorithm adopts the priority coding and get feasible solution by decoding. Crossover and mutation methods are improved, so that we can get better results. Finally, empirical analysis verify the feasibility and validity of the improved genetic algorithm by solving feeder bus network design problem and trunk bus network design problem.The thesis consists of five chapters:The first chapter introduces the development course of public transport, the background, significance, and research status of the feeder bus network and the trunk bus network design problems, and introduces the theory of genetic algorithm.The second chapter, the shortest path method based on feasible path is es-tablished, and its detailed process is given. Compared to the traditional Dijkstra algorithm and Floyd algorithm, this method can not only provide the shortest path between any two points and their distance, but also provide all the feasible paths be-tween any two points and their distances. Thus, it is of more significance in solving practical traffic problems such as road breakdowns.In third chapter, two kinds of partition cluster methods (perpendicular bisector method and shortest path method) are drawn into the feeder bus network design problem, which effectively dispose of the disadvantages of network, such as over-lay routes and cross service. By using the shortest path partition cluster method, and take the minimal total cost including passengers, bus company and rail transit operator as objective, through improve the encoding approach of chromosome and operating strategy of genetic operators, the many-to-one feeder bus network design problem is resolved successfully. The sensitivity of the constraints of route length and bus capacity to the network performance index, such as quantity of route, bus frequency and total cost of the feeder bus network is discussed. The numerical sim-ulation results show that the feeder bus network based on partition cluster approach can not only fully cover service district, but also dispose of redundancy routes and cut down the total cost of the network.The fourth chapter studies the trunk bus network design problem for a suburban residential area. The problem aims to improve the bus services by reducing the number of transfers and the total travel time of the users. This has been achieved by the proposed route path algorithm and hybrid genetic algorithm which can solve the route design and frequency setting problems simultaneously. The example is designed to verify the feasibility and effectiveness of the algorithm.The fifth chapter is simple conclusion of this paper.