基于云计算的城市路网最短路径遗传算法求解

doi:10.3969/j.issn.1000-565X.2014.03.008

华南理工大学学报（自然科学版） ›› 2014, Vol. 42 ›› Issue (3): 47-51,58.doi: 10.3969/j.issn.1000-565X.2014.03.008

基于云计算的城市路网最短路径遗传算法求解

杨庆芳^1,2,3梅朵³郑黎黎^1,2,3†马明辉³王伟³

1．吉林大学汽车仿真与控制国家重点实验室，吉林长春 130022; 2．吉林大学吉林省道路交通重点实验室，吉林长春 130022; 3．吉林大学交通学院，吉林长春 130022

收稿日期:2013-09-03 修回日期:2013-12-22 出版日期:2014-03-25 发布日期:2014-02-19
通信作者: 郑黎黎(1975-)，女，副教授，主要从事智能交通运输系统研究． E-mail:zlldtq024@163.com
作者简介:杨庆芳(1966-)，女，教授，博士生导师，主要从事智能交通运输系统研究．E-mail:yangqf@jlu．edu．cn
基金资助:
国家 “863” 计划项目(2012AA112307)

Cloud Computing- Based Genetic Algorithm to Solve the Shortest Path in Urban Rood Networks

Yang Qing- fang^1,2,3Mei Duo³ Zheng Li- li^1,2,3Ma Ming- hui³ Wang Wei³

1.State Key Laboratory of Automobile Simulation and Control,Jilin University,Changchun 130022,Jilin,China;2.Jilin Province Key Laboratory of Road Traffic,Jilin University, Changchun 130022,Jilin,China;3.College of Transportation,Jilin University,Changchun 130022,Jilin,China

Received:2013-09-03 Revised:2013-12-22 Online:2014-03-25 Published:2014-02-19
Contact: 郑黎黎(1975-)，女，副教授，主要从事智能交通运输系统研究． E-mail:zlldtq024@163.com
About author:杨庆芳(1966-)，女，教授，博士生导师，主要从事智能交通运输系统研究．E-mail:yangqf@jlu．edu．cn
Supported by:
国家 “863” 计划项目(2012AA112307)

摘要/Abstract

摘要： 针对城市路网最短路径求解过程中计算量庞大的问题，在分析遗传算法特征和缺陷的基础上，提出了基于 MapReduce 的并行遗传算法，并以长春市路网特征数据为基础验证了该算法的有效性．实验结果表明:基于 MapReduce 的并行遗传算法较传统遗传算法收敛速度快，运行时间短;随着并行节点数的增加，节点间的通信负荷加重，因此恰当地选择节点数尤为重要，合适的节点数可以提高运行效率．

关键词: 交通运输工程, 最短路径, 云计算, 遗传算法

Abstract:

Aiming at the heavy calculation load existing in the solution to the shortest path in urban road networks,this paper proposes a parallel genetic algorithm based on MapReduce in light of analysis of the features and short-comings of genetic algorithm,and has validated the effectiveness of this algorithm based on Changchun City's dataof road network features.Experimental results show that the proposed algorithm based on MapReduce is of fasterconvergence rate and shorter running time in comparison with the traditional genetic one; and that the inter- nodecommunication load increases as parallel nodes increase,so that proper selection of node number plays a key role inenhancing the operation efficiency.

Key words: traffic and transportation engineering, shortest path, cloud computing, genetic algorithm

杨庆芳梅朵郑黎黎马明辉王伟. 基于云计算的城市路网最短路径遗传算法求解[J]. 华南理工大学学报（自然科学版）, 2014, 42(3): 47-51,58.

Yang Qing- fang Mei Duo Zheng Li- li Ma Ming- hui Wang Wei. Cloud Computing- Based Genetic Algorithm to Solve the Shortest Path in Urban Rood Networks[J]. Journal of South China University of Technology (Natural Science Edition), 2014, 42(3): 47-51,58.

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

基于云计算的城市路网最短路径遗传算法求解

Cloud Computing- Based Genetic Algorithm to Solve the Shortest Path in Urban Rood Networks

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价