Global Optimal Routing for Traffic Systems with Multiple ODs using Genetic Algorithm

摘要

The multiple origins multiple destinations routing (MOMDR) problem becomes extremely complicated when considering the traffic volumes on road sections. When solving this kind of problem, only heuristic algorithms have practical values because it is a typical NP-Hard problem. This paper applies Genetic Algorithm (GA) to enhance Sorting- Randomizing-Adjusting-Updating (SRAU) algorithm [1]. The former paper shows that different processing orders of the origin-destinations (ODs) result in different solutions with different performances. Therefore, a heuristic algorithm for finding the best processing order of ODs can optimize SRAU algorithm. In this paper, every processing order of ODs is transformed into a gene/chromosome of the individuals of GA; then the best gene can be found during the evolution of GA; finally, the best gene is transformed back to find the optimal solution of the problem. Sufficient simulations show that the proposed algorithm is more efficient than original SRAU algorithm. Also the consideration of the traffic volumes on the road sections enables the proposed method to apply to real traffic systems.