论文标题
任何不精确的TSP求解器的行为和自动化算法选择的观点
Anytime Behavior of Inexact TSP Solvers and Perspectives for Automated Algorithm Selection
论文作者
论文摘要
旅行范围 - 问题（TSP）可以说是最著名的NP-HARD组合优化问题之一。两个复杂的启发式求解器LKH和EAX以及各自的（重新启动）变体设法计算近距离甚至最佳的解决方案，同样在合理时间内具有数千个节点的大型实例。在这项工作中，我们通过基于经验运行时分布的任何时间行为来解决现有的基准研究研究，从而增加了对求解器行为的理解以及对问题硬度的各个关系的了解。事实证明，求解器的性能排名高度取决于集中的近似质量。关于表演交点点的见解为构建杂交求解器的巨大潜力取决于实例功能。此外，通过包含有关求解器质量的全面信息，适用于任何时间性能和相应性能指标量身定制的实例功能将极大地改善自动化算法选择模型。
The Traveling-Salesperson-Problem (TSP) is arguably one of the best-known NP-hard combinatorial optimization problems. The two sophisticated heuristic solvers LKH and EAX and respective (restart) variants manage to calculate close-to optimal or even optimal solutions, also for large instances with several thousand nodes in reasonable time. In this work we extend existing benchmarking studies by addressing anytime behaviour of inexact TSP solvers based on empirical runtime distributions leading to an increased understanding of solver behaviour and the respective relation to problem hardness. It turns out that performance ranking of solvers is highly dependent on the focused approximation quality. Insights on intersection points of performances offer huge potential for the construction of hybridized solvers depending on instance features. Moreover, instance features tailored to anytime performance and corresponding performance indicators will highly improve automated algorithm selection models by including comprehensive information on solver quality.
