Practical Methods for Computing Large Covering Tours and Cycle Covers with Turn Cost
Sándor P. Fekete, Dominik Krupke · Society for Industrial and Applied Mathematics eBooks · 2019
We study the problem of computing provably optimal and near-optimal solutions for the NP-hard problem of finding covering tours and cycle covers with turn cost, which are of practical importance for a variety of applications, such as pest control and precision farming. Previous work has largely focused on theoretical aspects, such as complexity and approximation. We develop a number of algorithm engineering techniques and refinements to make such theoretical insights practically useful, resulting in a comprehensive study for solving a wide spectrum of large instances. We compute provably optimal solutions for instances with more than 1000 pixels, from the largest previous solved instance size of 76 (de Assis and de Souza 2011). Making use of additional algorithm engineering techniques for handling very large instances, we also compute near-optimal solutions for instances with up to 300 000 pixels, for which we give solutions that are typically within a few percent of our computed lower bounds. We also provide an experimental comparison of a practically refined version of our new theoretical approach with the approximation technique of Arkin et al. that dates back to 2001; we show that our new LP/IP-based approximation method closes 70% of the remaining optimality gap to the lower bound.