基于遗传算法的离散时间动态网络最短路径求解

华南理工大学学报（自然科学版） ›› 2008, Vol. 36 ›› Issue (2): 13-16,28.

基于遗传算法的离散时间动态网络最短路径求解

温惠英¹ 徐建闽¹ 邹亮²

1. 华南理工大学交通学院, 广东广州 510640; 2. 深圳大学土木工程学院, 广东深圳 518060

收稿日期:2007-03-01 出版日期:2008-02-25 发布日期:2008-02-25
通信作者: 温惠英（1965-），女，副教授，主要从事ITS与现代物流技术、交通运输规划与管理研究． E-mail:hywen@scut.edu.cn
作者简介:温惠英（1965-），女，副教授，主要从事ITS与现代物流技术、交通运输规划与管理研究．
基金资助:
国家自然科学基金资助项目（50578064）

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

Wen Hui-ying¹ Xu Jian-min¹ Zou Liang²

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）

摘要/Abstract

摘要： 采用遗传算法来求解不满足先进先出原则的动态网络中的最短路径问题,并采用所提出的随机A^＊算法解决了利用遗传算法求解最短路径问题时的最大障碍——初始种群的产生.最后以广州市电子地图为基础随机产生了一个不满足先进先出原则的动态网络（包括20000个节点,40000条边和144个时间间隔）,来对所提出的算法进行验证.试验结果表明,遗传算法适合求解非常态且不满足先进先出原则的动态网络中的路径诱导问题.

关键词: 智能交通系统, 动态交通诱导系统, 动态网络, 最短路径, 遗传算法

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

温惠英徐建闽邹亮 . 基于遗传算法的离散时间动态网络最短路径求解[J]. 华南理工大学学报（自然科学版）, 2008, 36(2): 13-16,28.

Wen Hui-ying Xu Jian-min Zou Liang. Genetic Algorithm-Based Computation of the Shortest Path in Discrete-Time Dynamic Networks[J]. Journal of South China University of Technology (Natural Science Edition), 2008, 36(2): 13-16,28.

[1]	邱宇东, 王湛, 谢志燊. 基于混合算法的半刚性连接钢框架结构优化[J]. 华南理工大学学报(自然科学版), 2023, 51(6): 72-77.
[2]	翁剑成, 王茂林, 林鹏飞, 等. 基于客流特征鉴别的公交跨线组合调度优化方法[J]. 华南理工大学学报(自然科学版), 2022, 50(9): 39-48.
[3]	秦雅琴, 钱正富, 谢济铭, 等. 基于社会力的交织区突发瓶颈段协同换道决策模型[J]. 华南理工大学学报(自然科学版), 2022, 50(7): 66-75.
[4]	郑亚晶, 李耀辉, 靳文舟. 考虑换乘客流的城市轨道交通网络末班车衔接优化研究[J]. 华南理工大学学报(自然科学版), 2022, 50(5): 32-39,72.
[5]	夏琴香, 李凯, 马骏, 等. 基于遗传算法的模具电极调度问题求解[J]. 华南理工大学学报(自然科学版), 2022, 50(3): 80-87.
[6]	周中, 邓卓湘, 陈云, 等. 基于GA-BP神经网络的泡沫轻质土强度预测[J]. 华南理工大学学报(自然科学版), 2022, 50(11): 125-132.
[7]	刘璇, 王子航, 张桐瑞, 等. 港口重载AGV横向稳定的优化控制策略[J]. 华南理工大学学报(自然科学版), 2021, 49(8): 113-121.
[8]	李静王晨张家旭. 基于UniTire轮胎模型的汽车行驶速度估计[J]. 华南理工大学学报（自然科学版）, 2021, 49(5): 47-55.
[9]	罗玉涛, 周天阳, 许晓通. 基于遗传算法的四轮转向－驱动汽车时变 LQR 控制[J]. 华南理工大学学报（自然科学版）, 2021, 49(3): 114-122.
[10]	晋刚何志豪王英俊. 基于遗传算法的5G频率选择表面形状优化方法[J]. 华南理工大学学报（自然科学版）, 2021, 49(11): 95-105.
[11]	李家乐刘真伯王雪菲. 智能电网下支持充放电策略的电动汽车配送路径优化[J]. 华南理工大学学报（自然科学版）, 2021, 49(10): 31-40.
[12]	靳文舟胡为洋邓嘉怡, 等. 基于混合算法的需求响应公交灵活调度模型 [J]. 华南理工大学学报（自然科学版）, 2021, 49(1): 123-133.
[13]	刘刚, 郭德明, 郑文成, 等. 基于轴向热路模型的架空地线与预绞丝接触端面接触电阻的计算[J]. 华南理工大学学报（自然科学版）, 2020, 48(7): 9-19.
[14]	马宏伟陈丰收. 基于粗粒度并行遗传算法的阻尼器优化布置[J]. 华南理工大学学报（自然科学版）, 2019, 47(11): 104-112.
[15]	卢凯林茂伟邓兴栋徐广辉徐建闽. 停车总成本最小的区域停车位动态分配与诱导模型[J]. 华南理工大学学报(自然科学版), 2018, 46(9): 82-91,98.