摘要
采用遗传算法来求解不满足先进先出原则的动态网络中的最短路径问题,并采用所提出的随机A*算法解决了利用遗传算法求解最短路径问题时的最大障碍——初始种群的产生.最后以广州市电子地图为基础随机产生了一个不满足先进先出原则的动态网络(包括20000个节点,40000条边和144个时间间隔),来对所提出的算法进行验证.试验结果表明,遗传算法适合求解非常态且不满足先进先出原则的动态网络中的路径诱导问题.
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.
出处
《华南理工大学学报(自然科学版)》
EI
CAS
CSCD
北大核心
2008年第2期13-16,28,共5页
Journal of South China University of Technology(Natural Science Edition)
基金
国家自然科学基金资助项目(50578064)~~
关键词
智能交通系统
动态交通诱导系统
动态网络
最短路径
遗传算法
intelligent transportation system
dynamic transportation guidance system
dynamic network
the shortest path
genetic algorithm