A GRASP × Evolutionary Local Search Hybrid for the Vehicle Routing Problem
A GRASP × Evolutionary Local Search Hybrid for the Vehicle Routing Problem
复制标题
DOI：
10.1007/978-3-540-85152-3_2
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
C. Prins
中科院分区：
文献类型：
--
作者：
C. Prins
本章提出了基于迭代局部搜索（ILS）的新VRP算法：纯ILS，每代有几个后代解的版本，称为进化局部搜索或ELS，以及混合形式GRASP×ILS和GRASP×ELS。这些变体共享三个主要特征：简单的结构，编码为巨型图尔斯和VRP解决方案的解决方案之间的交替，以及基于移动顺序分解的快速局部搜索。在Christofides et al.（1979）和Golden et al.（1998）的实例上对所提出的方法进行了测试。我们最好的算法是GRASP×ELS混合算法。在第一组中，如果只允许使用相同参数运行一次，则它优于除Mester和Bräysy（2007）的AGES算法之外的所有最近的算法。只有AGES和Tarantilis（2005）的SEPAS方法在第二组上做得更好，但GRASP×ELS改进了两个最著名的解决方案。我们的算法也比大多数VRP元算法更快。
This chapter proposes new VRP heuristics based on Iterated Local Search (ILS): a pure ILS, a version with several offspring solutions per generation, called Evolutionary Local Search or ELS, and hybrid forms GRASP×ILS and GRASP×ELS. These variants share three main features: a simple structure, an alternation between solutions encoded as giant tours and VRP solutions, and a fast local search based on a sequential decomposition of moves. The proposed methods are tested on the Christofides et al. (1979) and Golden et al. (1998) instances. Our best algorithm is the GRASP×ELS hybrid. On the first set, if only one run with the same parameters is allowed, it outperforms all recent heuristics except the AGES algorithm of Mester and Bräysy (2007). Only AGES and the SEPAS method of Tarantilis (2005) do better on the second set, but GRASP×ELS improves two best-known solutions. Our algorithm is also faster than most VRP metaheuristics.