文档介绍：车辆路径问题的禁忌搜索算法研究
郎茂祥，胡思继
(北方交通大学交通运输学院，北京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, Beij ing 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 experimental computations. The computational 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 年提 出的⑴。该问题一直是运筹学与组合优化领域的前沿与热点问题。在现实生产和生活中，邮 政投递问题、飞机、铁路列车、水运船舶及公共汽车的调度问题、电力调度问题、管道铺设 问题、计算机网络拓扑设计问题等都可以抽象为车辆路径问题。研究车辆路径问题具有重要 的理论和现实意义。
车辆路径问题作为一个NP难题，随着客户数量的增加，可选的车辆路径方案数量将以 指数速度急剧增长。因此，用启发式算法求解该问题就成为人们研究的一个重要方向。求解 车辆路径问题的方法很多，常用的有旅行商法、动态规划法、节约法、扫描法⑵、分区配送 算法⑶、方案评价法等。
禁忌搜索算法的出现，为求解车辆路径问题提供了新的工具。Gendreau> Jiefeng、 Barbarosoglu,蔡延光等都曾利用禁忌搜索算法求解车辆路径问题问，并取得了一些研究成 果。但现有研究成果多将车辆路径问题描述为一个网络图问题，因此在设计其禁忌搜索算法 时多采用有向边排列的解的表示方法，基于这种解的表示