Research On Shortest Path Algorithm Of Regional Traffic Network Based On Ga

Bus system is a important component of city’s public traffic, so, the bus transit route design is necessary. The research of the bus transit route design problem are focus primary on promoting the transport capacity of the bus system which based on the city’s net of road in existence through making rational transit route layout and plan, it’s good for improving urban traffic conditions and urban public transit service quality."Bus Transit Route Network Design Problem"(BTRNDP) was a multi objective decision making problem of a class of combinatorial optimization problems which have been put forward to account for it since the early60’s, there have been a great development and come into a fairly systematic theory which are already used in "The Intelligent Transportation System(ITS)" more and more. In early90’s, foreign scholars Baaj and Mahamassani have provided a solution of artificial intelligence. Then, more and more scholars make the research of the bus transit route network design problem with genetic algorithm (GA, like standard genetic algorithm, the parallel genetic algorithm and so on), and make a series of achievements, because of the difference of the transit route network design, the method that use GA has its own limits.This thesis includes several parts:the context of the study, the current research status at homeland and abroad and some theory support to thesis, the research of BTRNDP’s mathematical model, the research of genetic algorithm, system designed and tested.This thesis create BTYRNDP’s mathematical model from following aspects:the selection of starting and ending point in a public transit network and the formation and adjustment of routes, and the analysis of transit network constraint conditions(like direct traffic,the cost travel time and the public transit vehicle economic benefits and so on). In the Second chapter of this thesis, we make research about the shortest path algorithm like Yen algorithm and A star algorithm which was used to generate candidate routes set that defined to be the feasible solution space.In the third chapter of this thesis, we make analysis of the defects of genetic algorithm like premature convergence partial convergence. In the chapter, we make improvements based on SGA in following aspects:genetic codes, selecting operator, crossover operator and mutation operator, and a improved genetic algorithm(IGA) which was used to solve the bus transit route network design problem would be proposed.At the last section of this thesis, we summarize disadvantage and analyze some techniques having study value in this thesis.