混沌遗传算法优化公路运输路径

摘要/Abstract

摘要：

公路运输路径问题已被证明是高维非线性完全问题，实际中还会增加非流通图约束，使求解更复杂，研究价值较高.鉴于传统遗传算法在求解过程中容易出现早熟收敛、冗余迭代的缺陷，在初始种群生成、交叉变异及搜索操作方面提出改进，设计混沌遗传算法.采用遍历城市顺序的染色体编码，结合随机法与贪心法生成较优初始种群，避免出现大量非可行染色体，提高了后续的遗传效率.接着，执行优先保留交叉和平移变异操作，依次引入局部邻域搜索以及混沌搜索以加快算法收敛，还给出最优解的非连通公路约束满足判据.最后，实验结果验证了新算法的有效性，不但取得了较优解，而且子代种群离散程度较小，收敛性更好.

关键词: 公路运输, 运输路径优化, 混沌遗传算法, 局部邻域搜索

Abstract:

Highway transportation path problem has been proven to be a nondeterministic polynomial complete problem with high research value. It involves some unconnected graph constraints that make the solving process become more complex. In view of the defects of premature convergence and slow convergence of the traditional genetic algorithm, this paper makes the generation of initial population, crossover, mutation and search operation to design a chaos genetic algorithm. The algorithm adopts the chromosome encoding scheme based on sequence of city that highway vehicle passed through. It combines the stochastic method and greedy method to produce the initial populations in order to contain the optimal value, avoid infeasible chromosomes and improve the subsequently genetic efficiency. Then, precedence preservation crossover and shift change mutation operations are operated. Meanwhile, the local neighborhood search and chaos search are successively introduced to accelerate the convergence. Furthermore, the criterion is given to verify whether the optimal solution meets unconnected graph constraints or not. Finally, the computation results prove the effectiveness of the proposed method. The method can generate the optimal solution with less range of offspring population and better convergence.

Key words: highway transportation, transportation path optimization, chaos genetic algorithm, local neighborhood search

中图分类号:

TP18

孔令夷. 混沌遗传算法优化公路运输路径[J]. 交通运输系统工程与信息, 2013, 13(1): 179-.

KONG Ling-yi. Optimizing Highway Transportation Path by Chaos Genetic Algorithm[J]. Journal of Transportation Systems Engineering and Information Technology, 2013, 13(1): 179-.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract18540.shtml

http://www.tseit.org.cn/CN/Y2013/V13/I1/179

参考文献

［1］梁艳春, 吴春国, 时小虎, 等.群智能优化算法理论与应用[M]. 北京: 科学出版社, 2009. [LIANG Y C, WU C G, SHI X H, et al. Group intelligent optimization algorithm theory and application[M]. Beijing: Science press, 2009.]

［2］ ZHAO X C, Gao X S. Affinity genetic algorithm[J]. Journal of Heuristics, 2007, 13(2): 133-150.

［3］ YANG J H, Wu C G, Lee H P et al. Solving traveling salesman problems using generalized chromosome genetic algorithm[J]. Progress in Natural Science, 2008, 18(7): 887-892.

［4］ Bhatia A K, Basu S K. Tackling 0/1 knapsack problem with gene induction[J].Soft Computing, 2003, 8(1): 1-9.

［5］黄永青,梁昌勇,张祥德,等.一种小种群自适应遗传算法研究[J].系统工程理论与实践,2005,25(11):92-97. [HUANG Y Q, LIANG C Y, ZHANG X D, et al. Research on adaptive genetic algorithm with small population[J]. Systems EngineeringTheory & Practice, 2005,25(11):92-97.]

［6］陶林波,沈建京,韩强.一种解决早熟收敛的自适应遗传算法设计[J].微计算机信息,2005,22(12):268-270.[TAO L B, SHEN J J, HAN Q. An algorithm design for solving premature convergence of adaptive genetic algorithm[J]. Microcomputer Information, 2005,22(12):268-270.]

［7］李锋,魏莹. 基于仿真的遗传算法求解动态旅行商问题[J]. 系统管理学报,2009,18(5):591-595. [LI F, WEI Y. A simulationbased genetic algorithm for dynamic traveling salesman problem [J]. Journal of Systems & Management, 2009,18(5):591-595.]

［8］周辉仁,唐万生,牛犇. 基于递阶遗传算法的多旅行商问题优化[J]. 计算机应用研究,2009,26(10):3754-3757. [ZHOU H R, TANG W S, NIU B. Optimization of multiple traveling salesman problem based on hierarchical genetic algorithm[J]. Application Research of Computers, 2009,26(10):3754-3757.]

［9］王美华,田绪红,廖鸿翔. 求解广义旅行商问题的混合染色体遗传算法[J]. 计算机工程与应用,2009,45(27):59-61. [WANG M H, TIAN X H, LIAO H X. Mixed chromosomes genetic algorithm for solving the generalized traveling salesman problem[J]. Computer Engineering and Applications, 2009,45(27):59-61.]

［10］韩丽霞,王宇平. 解旅行商问题的一个新的遗传算法[J]. 系统工程理论与实践,2007,(12):145-150. [HAN L X, WANG Y P. A novel genetic algorithm for traveling salesman problem[J]. Systems EngineeringTheory & Practice, 2007,(12):145-150.]

［11］朱云飞,蔡自兴,袁琦钊,等. 求解多目标旅行商问题的混合遗传算法[J]. 计算机工程与应用,2011,47(7):52-56. [ZHU Y F, CAI Z X, YUAN Q Z, et al. Hybrid genetic algorithm for multipleobjective TSP[J]. Computer Engineering and Applications,2011,47(7):52-56.]

［12］汪民乐,高晓光,刘刚.遗传算法早熟问题的定量分析及其预防策略[J].系统工程与电子技术,2006,28(8):1249-1251. [WANG M L, GAO X G, LIU G. Quantitative analysis and prevention of genetic algorithm premature convergence[J]. Systems Engineering and Electronics, 2006, 28(8): 1249-1251.]

［13］郏宣耀,王芳.一种改进的小生境遗传算法[J].重庆邮电学院学报（自然科学版）,2005,17(16):721-723. [JIA X Y, WANG F. Improved niching genetic algorithm[J]. Journal of Chongqing University of Posts and Telecommunications(Natural Science), 2005, 17(16): 721-723.]

［14］贺毅朝,刘坤起,张翠军,等.求解背包问题的贪心遗传算法及其应用[J].计算机工程与设计, 2007, 28(11): 2655-2657. [HE Y C, LIU K Q, ZHANG C J,et al. Greedy genetic algorithm for solving knapsack problems and its applications[J]. Computer Engineering and Design, 2007, 28(11): 2655-2657.]

［15］田建立,晁学鹏. 求解01背包问题的混沌遗传算法[J].计算机应用研究,2011,28(8):2838-2839. [TIAN J L, CHAO X P. Novel chaos genetic algorithm for solving 01 knapsack problem[J]. Application Research of Computers, 2011,28(8): 2838-2839.]

［16］ Bievwirth C, Mattfeld D, Kopfer H. On permutation representations for scheduling problems[C]//Proceedings of the 4th International Conference on Parallel Problem Solving from Nature.Berlin, Germany:Springer,1996:310-318.

［17］ Murata T, Ishibuchi H, Tanaka H. Genetic algorithms for flowshop scheduling problem[J]. Computers & Industrial Engineering,1996,30(4):1061-1071.

［18］康立山,谢云,尤矢勇,等.模拟退火算法[M].北京:科学出版社,1994:150-151. [KANG L S, XIE Y, YOU S Y et al. Simulated Annealing Algorithm[M]. Beijing: Science Press, 1994:150-151.]

[1]	王宁, 张佳蕊, 赵姣. 城际零担货运平台车辆路径问题研究[J]. 交通运输系统工程与信息, 2022, 22(2): 163-177.
[2]	谭二龙, 李宏海, 钟厚岳, 霍恩泽, 马晓磊. 基于轨迹数据的货车自发编队节油潜力估计[J]. 交通运输系统工程与信息, 2022, 22(1): 74-84.
[3]	贾术艳, 宋雨童, 杨紫都. 基于生长曲线函数的货车运营环节碳达峰研究[J]. 交通运输系统工程与信息, 2021, 21(6): 310-318.
[4]	甘蜜, 卿三东, 刘晓波, 李丹丹. 货车轨迹数据在公路货运系统中应用研究综述[J]. 交通运输系统工程与信息, 2021, 21(5): 91-101.
[5]	李根, 翟伟, 朱兴贝, 杨晟, 邬岚. 侧向碰撞风险对交织区汇合行为的影响[J]. 交通运输系统工程与信息, 2021, 21(4): 204-210.
[6]	李桃迎，王婷，张羽琪. 考虑多特征的高速公路交通流预测模型[J]. 交通运输系统工程与信息, 2021, 21(3): 101-111.
[7]	袁方，杨轸，周雄峰. 双车道公路弯道半径及回旋线长度对转向行为的影响[J]. 交通运输系统工程与信息, 2021, 21(1): 116-123.
[8]	胡立伟，何越人，李耀平，孟玲，殷秀芬. 基于人工免疫机制的营运货车运行风险评价研究[J]. 交通运输系统工程与信息, 2021, 21(1): 149-155.
[9]	戢晓峰，吴亚欣，郝京京，房锐，胡澄宇. 平纵组合路段事故严重程度致因辨识模型[J]. 交通运输系统工程与信息, 2020, 20(6): 197-204.
[10]	程颖，张佳乐，张少君，郭继孚，张达. 大型货运车辆生态驾驶及节油潜力评估[J]. 交通运输系统工程与信息, 2020, 20(6): 253-258.
[11]	段莉珍，栾庆熊，赵鑫. 区域路网货物运输量统计方法改进[J]. 交通运输系统工程与信息, 2020, 20(4): 28-33.
[12]	刘昱，吴志新，李孟良，于晗正男，汪洋，贺可勋，安晓盼. 中国乘用车工况构建[J]. 交通运输系统工程与信息, 2020, 20(3): 233-240.
[13]	何永明，裴玉龙，冉斌. 基于智能路钮的超高速公路虚拟轨道系统研究[J]. 交通运输系统工程与信息, 2020, 20(2): 55-60.
[14]	王海星，王翔宇，王招贤，李学东. 基于数据挖掘的危险货物运输风险驾驶行为聚类分析[J]. 交通运输系统工程与信息, 2020, 20(1): 183-189.
[15]	杨涛，王鹏，朱季萍，赵建东. 多元收费方式下的高速公路收费站车道数优化研究[J]. 交通运输系统工程与信息, 2019, 19(5): 212-218.