车辆路径问题的禁忌搜索算法研究.doc

文档介绍：车辆路径问题的禁忌搜索算法研究
郎茂祥,胡思继
(北方交通大学交通运输学院,北京 100044)
摘要:论文在对车辆路径问题进行简单描述的基础上,通过设计一种新的解的表示方法构造了求解该问题的一种新的禁忌搜索算法,并进行了实验计算。计算结果表明,用本文设计的禁忌搜索算法求解车辆路径问题,不仅可以取得很好的计算结果,而且算法的计算效率较高,收敛速度较快,计算结果也较稳定。
关键词:车辆路径问题;禁忌搜索算法;优化
Study on the Tabu Search Algorithm for Vehicle Routing Problem
LANG Mao-xiang,HU Si-ji
(School of Traffic and Transportation,Northern Jiaotong University,Beijing 100044,China)
Abstract:On the basis of describing the vehicle routing problem briefly, this paper presents a new solution indicating method then builds a new tabu search algorithm for the problem and make some putations. putational results demonstrates that the high quality solutions to the vehicle routing problem can be obtained by using the new tabu search algorithm, and the new algorithm is also efficient and robust.
Keywords:vehicle routing problem; tabu search algorithm; optimal
1 引言
车辆路径问题(VRP,Vehicle Routing Problem)是由Dantzig和Ramser于1959年提出的[1]。该问题一直是运筹学与组合优化领域的前沿与热点问题。在现实生产和生活中,邮政投递问题、飞机、铁路列车、水运船舶及公共汽车的调度问题、电力调度问题、管道铺设问题、计算机网络拓扑设计问题等都可以抽象为车辆路径问题。研究车辆路径问题具有重要的理论和现实意义。
车辆路径问题作为一个NP难题,随着客户数量的增加,可选的车辆路径方案数量将以指数速度急剧增长。因此,用启发式算法求解该问题就成为人们研究的一个重要方向。求解车辆路径问题的方法很多,常用的有旅行商法、动态规划法、节约法、扫描法[2]、分区配送算法[3]、方案评价法等。
禁忌搜索算法的出现,为求解车辆路径问题提供了新的工具。Gendreau、Jiefeng、Barbarosoglu、蔡延光等都曾利用禁忌搜索算法求解车辆路径问题[4-8],并取得了一些研究成果。但现有研究成果多将车辆路径问题描述为一个网络图问题,因此在设计其禁忌搜索算法时多采用有向边排列的解的表示方法,基于这种解的表示方法所构造的禁忌搜索算法具有以下缺点:(1)由于解的表示不太直观,使得算法