导引式局部搜索在一类过度约束VRP中的应用  

Application of the guided local search method to a class of over-constrained vehicle routing problems

作　　者：李菊芳[1] 谭跃进[1] 

机构地区：[1]国防科技大学系统工程研究所,湖南长沙410073

出　　处：《系统工程与电子技术》2004年第11期1612-1615,共4页Systems Engineering and Electronics

摘　　要：针对一类带时间窗口和容量约束的车辆路线问题(VRP),给出了在过度约束即不存在满足所有约束的可行解的情况下,能够最小化约束违反成本的一种新颖的导引式局部搜索(GLS)算法。该算法通过不断动态修改原问题的目标函数,既保留了局部搜索算法的高效率,又有效克服了局部极小解的局限性,因而能够较快地返回一个满意解。求解示例表明,该算法在求解此类问题时,性能要优于常用的禁忌搜索算法。To solve the vehicle routing problem (VRP) with time windows, where over-constrained situation may exist that no feasible solution satisfying all constraints is found, a novel algorithm, guided local search (GLS), is provided to minimize the total cost of violated constraints. By dynamically modifying the original objective function, the algorithm can both keep the high efficiency of local search and overcome the limitation of local minimum, thus quickly returning a satisfactory solution. An example is also provided which shows that GLS is better than broadly used Tabu search for such kind of problems.

关 键 词：度约束 局部搜索算法 禁忌搜索算法 动态修改 VRP 局部极小解 最小化 求解 可行解 时间窗口 

分 类 号：TN919.8[电子电信—通信与信息系统] TP393[电子电信—信息与通信工程]