A new local search algorithm providing high quality solutions to vehicle routing problems
A new local search algorithm providing high quality solutions to vehicle routing problems
复制标题
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
Paul Shaw
中科院分区：
文献类型：
--
作者：
Paul Shaw
本文描述了一种新的局部搜索算法，它为车辆路径问题提供了非常高质量的解。该方法使用贪婪的局部搜索，但通过使用约束编程技术对选定的客户访问进行重新调度来使用大邻域来避免局部极小值。所采用的移动算子是完全通用的，因为几乎任何边约束都可以被有效地合并到搜索过程中。(fi)计算结果表明，该方法的朴素实现产生了比使用最小转义方法的竞争技术产生的最好结果更好的结果。
This paper describes a new local search algorithm that provides very high quality solutions to vehicle routing problems. The method uses greedy local search, but avoids local minima by using a large neighbourhood based upon rescheduling selected customer visits using constraint programming techniques. The move operator adopted is completely generic, in that virtually any side constraint can be efficiently incorporated into the search process. Computational results show that a naive implementation of the method produces results bettering the best produced by competing techniques using minima-escaping methods.