Geometric and LP-based heuristics for angular travelling salesman problems in the plane

摘要

The angular-metric travelling salesman problem (AngleTSP) asks for a Hamiltonian cycle for given points in the Euclidean plane mimimizing the sum of all turning angles. Setting as objective the linear combination of these angles with the distances of the classical TSP, gives rise to the angular-distance-metric travelling salesman problem (AngleDistanceTSP).Since both problems are NP-hard, we first introduce a wide range of heuristic approaches, motivated by the typical geometric structure of optimal solutions. In particular, we exploit lens-shaped neighbourhoods of edges and a decomposition of the graph into layers of convex hulls, which are then merged into a tour. Secondly, we consider an ILP model based on the more general quadratic travelling salesman problem (QTSP). By rounding its fractional solutions we obtain a collection of subtours, paths and isolated points, which are then combined into a tour by various strategies, all of them involving auxiliary ILP models. Finally, different improvement heuristics are proposed, most notably a matheuristic which locally reoptimizes the solution for rectangular sectors of the given point set by an ILP approach.Results of extensive computational experiments using benchmark instances from the literature illustrate the Pareto-efficient frontier of algorithms in a (running time, objective value)-space. It turns out that our new methods clearly dominate previously published heuristics. (C) 2019 Elsevier Ltd. All rights reserved.