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

《车辆路径问题的禁忌搜索算法研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、车辆路径问题的禁忌搜索算法研究郎茂祥，胡思继（北方交通大学交通运输学院，北京100044）摘要：论文在对车辆路径问题进行简单描述的基础上，通过设计一种新的解的表示方法构造了求解该问题的一种新的禁忌搜索算法，并进行了实验计算。计算结果表明，用本文设计的禁忌搜索算法求解车辆路径问题，不仅可以取得很好的计算结果，而且算法的计算效率较高，收敛速度较快，计算结果也较稳定。关键词：车辆路径问题；禁忌搜索算法；优化StudyontheTabuSearchAlgorithmforVehicleRoutingProblemLANGMao-xiang，HUSi-ji（Schoolof

2、TrafficandTransportation，NorthernJiaotongUniversity，Beijing100044，China）Abstract：Onthebasisofdescribingthevehicleroutingproblembriefly,thispaperpresentsanewsolutionindicatingmethodthenbuildsanewtabusearchalgorithmfortheproblemandmakesomeexperimentalcomputations.Thecomputationalresults

3、demonstratesthatthehighqualitysolutionstothevehicleroutingproblemcanbeobtainedbyusingthenewtabusearchalgorithm,andthenewalgorithmisalsoefficientandrobust.Keywords：vehicleroutingproblem;tabusearchalgorithm;optimal1引言车辆路径问题（VRP，VehicleRoutingProblem）是由Dantzig和Ramser于1959年提出的[1]。该问题一直是运筹

4、学与组合优化领域的前沿与热点问题。在现实生产和生活中，邮政投递问题、飞机、铁路列车、水运船舶及公共汽车的调度问题、电力调度问题、管道铺设问题、计算机网络拓扑设计问题等都可以抽象为车辆路径问题。研究车辆路径问题具有重要的理论和现实意义。车辆路径问题作为一个NP难题，随着客户数量的增加，可选的车辆路径方案数量将以指数速度急剧增长。因此，用启发式算法求解该问题就成为人们研究的一个重要方向。求解车辆路径问题的方法很多，常用的有旅行商法、动态规划法、节约法、扫描法[2]、分区配送算法[3]、方案评价法等。禁忌搜索算法的出现，为求解车辆路径问题提供了新的工具。Gendreau

5、、Jiefeng、Barbarosoglu、蔡延光等都曾利用禁忌搜索算法求解车辆路径问题[4-8]，并取得了一些研究成果。但现有研究成果多将车辆路径问题描述为一个网络图问题，因此在设计其禁忌搜索算法时多采用有向边排列的解的表示方法，基于这种解的表示方法所构造的禁忌搜索算法具有以下缺点：（1）由于解的表示不太直观，使得算法策略不仅较为复杂，而且不易理解；（2）解中的元素较多，不仅占用的计算机存储量较大，而且求解时计算时间较长，搜索效率较低；（3）算法迭代过程中产生的解中不可行解很多，从而大大影响了算法的收敛速度。为了克服现有禁忌搜索算法的缺点，本文在对车辆路径问题进

6、行简单描述的基础上，提出了一种新的解的表示方法——客户直接排列的解的表示方法，并基于这种解的表示方法构造了求解车辆路径问题的一种新的禁忌搜索算法，并通过实验计算证明了这种新的禁忌搜索算法的良好寻优性能。52车辆路径问题的禁忌搜索算法的设计2.1车辆路径问题的描述为了使问题易于理解，本文用一个配送车辆调度问题描述车辆路径问题。该问题可以描述为：从某物流中心用多台配送车辆向多个客户送货，每个客户的位置和需求量一定，每台配送车辆的载重量一定，其一次配送的最大行驶距离一定，要求合理安排车辆配送路线，使配送总里程最短，并满足以下约束条件：（1）每条配送路径上各客户的需求量之

7、和不超过配送车辆的载重量；（2）每条配送路径的长度不超过配送车辆一次配送的最大行驶距离；（3）每个客户的需求必须满足，且只能由一台配送车辆送货。2.2禁忌搜索算法的原理和实现步骤利用禁忌搜索算法求解组合优化问题时，首先按照随机方法产生一个初始解作为当前解，然后在当前解的邻域中搜索若干个解，取其中的最好解作为新的当前解。为了避免对已搜索过的局部最优解的重复，禁忌搜索算法使用禁忌表记录已搜索的局部最优解的历史信息，这使得算法可在一定程度上避开局部最优点，从而开辟新的搜索区域。用禁忌搜索算法求解组合优化问题时，其实现步骤为（以目标函数求最小为例）：第一步：选定一个初始解

8、xnow；