中国公路学报060423

	中国公路学报 CHINA JOURNAL OF HIGHWAY AND TRANSPORT 2006 Vol.19 No.4 P.123-126

车辆路径问题的模拟退火算法

胡大伟　朱志强　胡勇　

摘　要：在构造车辆路径问题(Vehicle Routing Problem,VRP)数学模型后,采用路径间调整和路径内优化方法,结合模拟退火算法策略对该问题进行求解.重点阐述了VRP模拟退火算法的设计思路,详细分析和编制了求解程序框图,并实现了计算机求解.仿真测试结果表明:采用模拟退火算法求解VRP效果显著,计算速度较快,与有关算法对比显示了较强的实用性和可操作性,为解决大规模VRP提供了一种有效算法.
关键词：物流;车辆路径问题;模拟退火算法;2-opt法;插入法
分类号：U492.22　文献标识码：A
文章编号：1001-7372(2006)04-0123-04

Simulated Annealing Algorithm for Vehicle Routing Problem

HU Da-wei　 ZHU Zhi-qiang　 HU Yong　

基金项目：甘肃省交通科技项目(2171-2004854)
作者简介：胡大伟(1963-),男,北京市人,教授,工学博士研究生,E-mail:dwhu2008cn@yahoo.com.cn.
作者单位：胡大伟（长安大学,汽车学院,陕西,西安,710064）　
　　　　　朱志强（长安大学,汽车学院,陕西,西安,710064）　
　　　　　胡勇（长安大学,汽车学院,陕西,西安,710064）　

参考文献：

[1]PAOLO T,DANIELE V.The Vehicle Routing Problem[M].Philadephia:Society for Industrial and Applied Mathematics,2002.
[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.
[3]刑文训,谢金星.现代优化计算方法[M].北京:清华大出版社,2003.XING Wen-xun,XIE Jin-xing.Modern Optimization Algorithm[M].Beijing:Tsinghua University Press,2003.
[4]POTVIN J Y,ROUSSEAU J M.An Exchange Heu-ristic for Routing Problems with Time Windows[J].Journal of the Operational Research Society,1995,46(12):1 433-1 446.
[5]WU T H,LOW C Y,BAI J W.Heuristics Solutions to Multi-depot Location-Routing Problems[J].Computer& Operation Research,2002,29(2):1 393-1 415.
[6]杨瑞臣,周永付,云庆夏.寻找车辆最优化路径的混合算法[J].交通运输工程学报,2005,5(1):102-105.YANG Rui-chen,ZHOU Yong-fu,YUN Qing-xia.Hybrid Algorithm of Vehicle's Optimal Route[J].Journal of Traffic and Transportation Engineering,2005,5 (1):102-105.
[7]张波,叶家玮,胡郁葱.模拟退火算法在路径优化问题中的应用[J].中国公路学报,2004,17(1):79-81.ZHANG Bo,YE Jia-wei,HU Yu-cong.Application of Optimizing the Path by Simulated Annealing[J].China Journal of Highway and Transport,2004,17 (1):79-81.

收稿日期：2005年10月12日

出版日期：2006年7月31日

请看PDF全文