交通运输工程学报
JOURNAL OF TRAFFIC AND TRANSPORTATION ENGINEERING
2003 Vol.3 No.4 P.112-115


带时间窗的车辆路径混合遗传算法

Hybrid genetic algorithm of vehicle routing with time windows

宋厚冰  蔡远利 

摘 要:基于标准遗传算法,将每一个染色体与分组信息相结合,使染色体结构包含有更多信息,辅以λ-交换局部搜索技术,构造了一种新的混合遗传算法,对带时间窗约束的车辆路径问题进行了求解,并与标准遗传算法的求解结果进行了对比研究,发现使用混合遗传算法,总行驶里程为162 km,而使用标准遗传算法,总行驶里程为182 km.结果表明混合遗传算法的求解结果比标准遗传算法更加接近最优解,所需的行驶里程缩短,有效降低运输企业的车辆运行成本.
关键词:智能交通系统;时间窗;车辆路径问题;混合遗传算法;λ-交换局部搜索
分类号:U491 文献标识码:A

文章编号:1671-1637(2003)04-0112-04

基金项目:教育部"面向21世纪教育振兴行动计划"资助项目(A3.16-DX)
作者简介:宋厚冰(1979-),男,山东平阴人,硕士研究生,从事智能交通系统研究.
作者单位:宋厚冰(西安交通大学,电子与信息工程学院,陕西,西安,710049) 
     蔡远利(西安交通大学,电子与信息工程学院,陕西,西安,710049) 

参考文献:

[1]Dantzig G B,Ramser J H.The truck dispatching problem[J].Management Science,1959,10(6):80-91.
[2]祝崇隽,刘民,吴澄.供应链中车辆路径问题的研究进展及前景[J].计算机集成制造系统,2001,7(11):1-6.ZHU Chong-jun,LIU Min,WU Cheng.Review of vehicle routing problem in supply chain[J].Computer Integrated Manufacturing Systems,2001,7(11):1-6.(in Chinese)
[3]Thangiah S R.A hybrid genetic algorithm,simulated annealing and tabu search heuristics for the vehicle routing problem with time windows[J].Complex Coding Systems,1999,3(1):253-277.
[4]肖雁,符卓,李育安.带软时间窗的车辆路径问题及其应用前景探讨[A].中国运筹学会第六届学术交流会论文集[C].长沙:Global-Link出版社,2000.
[5]张丽萍,柴跃廷,曹瑞.有时间窗车辆路径问题的改进遗传算法[J].计算机集成制造系统,2002,8(6):452-454.ZHANG Li-ping,CHAI Yue-ting,CAO Rui.Improved genetic algorithm for vehicle routing problem with time windows[J].Computer Integrated Manufacturing Systems,2002,8(6):452-454.(in Chinese)
[6]孙增圻.智能控制理论与技术[M].北京:清华大学出版社,2000.
[7]Tan K C, Lee L H, Ou K. Artificial intelligence heuristics in solving vehicle routing problems with time window constraints[J].Engineering Applications of Artificial Intelligence,2001,14(1):825-837.
[8]Osman I H,Christofides N.Capacitated clustering problem by hybrid simulated annealing and tabu search[J].International Transaction in Operation Research,1994,1(3):317-336.
[9]姜大立,杨西龙,杜文,等.车辆路径问题的遗传算法研究[J].系统工程理论与实践,1999,19(6):40-45.JIANG Da-li,YANG Xi-long,DU Wen,et al.A study on the genetic algorithm for vehicle routing problem[J].Systems Engineering-Theory & Practice,1999,19(6):40-45.(in Chinese)


收稿日期:2003年4月30日

出版日期:2003年12月1日