论文标题
混合遗传搜索CVRP：开源实施和交换*社区
Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood
论文作者
论文摘要
车辆路线问题是研究最多的组合优化主题之一，因为它的实际重要性和方法论上的兴趣。然而，尽管有广泛的方法论进展，但由于有限的简单有效的开源解决方案方法，许多最近的研究受到了阻碍。鉴于当前算法的复杂性，重新实现已成为一项艰巨而耗时的练习，需要广泛的护理才能真正成功。在这种背景下，我们利用这篇简短论文的机会引入了专门针对电容的车辆路由问题（CVRP）的简单的 - 开源 - 混合遗传搜索（HGS）。这种最先进的算法使用与Vidal等人相同的一般方法。 （2012年），但还包括在过去十年中学习的其他方法论改进和经验教训。特别是，它包括一个名为Swap*的附加社区，该社区包括在没有插入的情况下在不同路线之间交换两个客户。正如我们的研究中强调的那样，对掉期*移动的有效探索显着有助于当地搜索的性能。此外，正如在Uchoa等人的经典实例的其他最新方法中所观察到的那样。 （2017年），HGS仍然是有关解决方案质量，收敛速度和概念简单性的领先元疗法。
The vehicle routing problem is one of the most studied combinatorial optimization topics, due to its practical importance and methodological interest. Yet, despite extensive methodological progress, many recent studies are hampered by the limited access to simple and efficient open-source solution methods. Given the sophistication of current algorithms, reimplementation is becoming a difficult and time-consuming exercise that requires extensive care for details to be truly successful. Against this background, we use the opportunity of this short paper to introduce a simple -- open-source -- implementation of the hybrid genetic search (HGS) specialized to the capacitated vehicle routing problem (CVRP). This state-of-the-art algorithm uses the same general methodology as Vidal et al. (2012) but also includes additional methodological improvements and lessons learned over the past decade of research. In particular, it includes an additional neighborhood called SWAP* which consists in exchanging two customers between different routes without an insertion in place. As highlighted in our study, an efficient exploration of SWAP* moves significantly contributes to the performance of local searches. Moreover, as observed in experimental comparisons with other recent approaches on the classical instances of Uchoa et al. (2017), HGS still stands as a leading metaheuristic regarding solution quality, convergence speed, and conceptual simplicity.
