Journal of South China University of Technology (Natural Science Edition) ›› 2008, Vol. 36 ›› Issue (2): 13-16,28.

• Traffic & Transportation Engineering • Previous Articles     Next Articles

Genetic Algorithm-Based Computation of the Shortest Path in Discrete-Time Dynamic Networks

Wen Hui-ying1  Xu Jian-min1  Zou Liang2   

  1. 1. School of Traffic and Communications, South China University of Technology, Guangzhou 510640, Guangdong, China;2. College of Civil Engineering, Shenzhen University, Shenzhen 518060, Guangdong, China
  • Received:2007-03-01 Online:2008-02-25 Published:2008-02-25
  • Contact: 温惠英（1965-），女，副教授，主要从事ITS与现代物流技术、交通运输规划与管理研究． E-mail:hywen@scut.edu.cn
  • About author:温惠英（1965-），女，副教授，主要从事ITS与现代物流技术、交通运输规划与管理研究．
  • Supported by:

    国家自然科学基金资助项目（50578064）

PDF

569

Abstract:

In this paper, the genetic algorithm is adopted to compute the shortest path in the dynamic networks unsatisfying the first-in-first-out （FIFO） principle, and a random A*algorithm is proposed to overcome the difficulty in obtaining the initial generation of the genetic algorithm. Then, based on the electronic map of Guangzhou city, a dynamic network containing 20000 nodes, 40000 links and 144 time intervals, which does not satisfy the FIFO principle, is proposed to test the proposed algorithm. Experimental results indicate that the genetic algorithm is suitable for the solving of transportation guidance problem in the dynamic networks unsatisfying the FIFO principle and possessing unstable states.

Key words: intelligent transportation system, dynamic transportation guidance system, dynamic network, the shortest path, genetic algorithm