论文标题
AILS-II：针对大规模电容的车辆路由问题的自适应迭代启发式启发式启发式
AILS-II: An Adaptive Iterated Local Search Heuristic for the Large-scale Capacitated Vehicle Routing Problem
论文作者
论文摘要
一项关于经典电容车辆路由问题（CVRP）的最新研究引入了广泛使用的迭代局部搜索（ILS）范式的自适应版本，并与路径链接策略（PR）杂交。在基准实例上，称为AILS-PR的解决方案方法（称为AILS-PR）优于CVRP的现有元映射。但是，对CVRP大规模实例的测试表明，PR太慢了，在这种情况下，AILS-PR的优势降低了。为了克服这一挑战，本文在其搜索过程中提出了一个自适应迭代的本地搜索（AIL）。这两个阶段都包括IL的扰动和本地搜索步骤。它们之间的主要区别在于，第一阶段中的参考解决方案是通过接受标准找到的，而在第二阶段中，它是从搜索过程中最佳解决方案的池中选择的，即所谓的精英集。该算法称为AILS-II，在较小的实例上具有非常有竞争力，在平均差距到最知名的解决方案方面，文献中的其他方法表现优于文献中的其他方法。此外，AILS-II在更大的实例上始终优于最高30,000个顶点的最新情况。
A recent study on the classical Capacitated Vehicle Routing Problem (CVRP) introduced an adaptive version of the widely used Iterated Local Search (ILS) paradigm, hybridized with a path-relinking strategy (PR). The solution method, called AILS-PR, outperformed existing meta-heuristics for the CVRP on benchmark instances. However, tests on large-scale instances of the CVRP suggested that PR was too slow, making AILS-PR less advantageous in this case. To overcome this challenge, this paper presents an Adaptive Iterated Local Search (AILS) with two phases in its search process. Both phases include the perturbation and local search steps of ILS. The main difference between them is that the reference solution in the first phase is found by the acceptance criterion, while in the second phase it is selected from a pool of the best solutions found in the search process, the so-called elite set. This algorithm, called AILS-II, is very competitive on smaller instances, outperforming the other methods from the literature with respect to the average gap to the best known solutions. Moreover, AILS-II consistently outperformed the state of the art on larger instances with up to 30,000 vertices.
