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

DOI10.1016/J.COR.2019.01.016MaRDI QIDQ2003422zbMATH OpenOpenAlexFDO

Authors Rostislav Staněk, Peter Greistorfer, Klaus Ladner, Ulrich Pferschy

Publication date 8 July 2019

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.03681

zbMATH Keywords

angular-metric traveling salesman problemcombinatorial optimizationinteger programming modelsmatheuristics

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: A generalization of the classical TSP is the so-called quadratic travelling salesman problem (QTSP), in which a cost coefficient is associated with the transition in every vertex, i.e. with every pair of edges traversed in succession. In this paper we consider two geometrically motivated special cases of the QTSP known from the literature, namely the angular-metric TSP, where transition costs correspond to turning angles in every vertex, and the angular-distance-metric TSP, where a linear combination of turning angles and Euclidean distances is considered. At first we introduce a wide range of heuristic approaches, motivated by the typical geometric structure of optimal solutions. In particular, we exploit lens-shaped neighborhoods of edges and a decomposition of the graph into layers of convex hulls, which are then merged into a tour by a greedy-type procedure or by utilizing an ILP model. Secondly, we consider an ILP model for a standard linearization of QTSP and compute fractional solutions of a relaxation. By rounding we obtain a collection of subtours, paths and isolated points, which are 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. Extensive computational experiments for benchmark instances from the literature and extensions thereof illustrate the Pareto-efficient frontier of algorithms in a (running time, objective value)-space. It turns out that our new methods clearly dominate the previously published heuristics.

Recommendations

• The Angular-Metric Traveling Salesman Problem
• Heuristics and bounds for the travelling salesman location problem on the plane
• Fast Heuristics for Large Geometric Traveling Salesman Problems
• scientific article; zbMATH DE number 5823729
• On two geometric problems related to the travelling salesman problem
• scientific article; zbMATH DE number 1222815
• scientific article; zbMATH DE number 4087452
• The geometric traveling salesman problem in the Heisenberg group
• scientific article; zbMATH DE number 1145369
• scientific article; zbMATH DE number 4199979

Cites work

• A linear time algorithm for the \(3\)-neighbour travelling salesman problem on a Halin graph and extensions
• Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order
• An analysis of the asymmetric quadratic traveling salesman polytope
• An extended approach for lifting clique tree inequalities
• Discrete optimization methods to determine trajectories for Dubins' vehicles
• Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics
• Generating subtour elimination constraints for the TSP from pure integer solutions
• Handbook of Approximation Algorithms and Metaheuristics
• scientific article; zbMATH DE number 1488569 (Why is no real title available?)
• scientific article; zbMATH DE number 3895002 (Why is no real title available?)
• Lower bounding procedure for the asymmetric quadratic traveling salesman problem
• Minimization and maximization versions of the quadratic travelling salesman problem
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Solution of a Large-Scale Traveling-Salesman Problem
• The Angular-Metric Traveling Salesman Problem
• The design of approximation algorithms
• The pilot method: a strategy for heuristic repetition with application to the Steiner problem in graphs
• The symmetric quadratic traveling salesman problem
• The traveling salesman problem and its variations.
• The traveling salesman problem. A computational study.
• The traveling salesman. Computational solutions for RSP applications
• Traveling Salesperson Problems for the Dubins Vehicle

Cited in

(10)

• Angular bisector insertion algorithm for solving small-scale symmetric and asymmetric traveling salesman problem
• The quadratic cycle cover problem: special cases and efficient bounds
• Angle-restricted tours in the plane.
• Accelerating the calculation of makespan used in scheduling improvement heuristics
• The Angular-Metric Traveling Salesman Problem
• SDP-Based Bounds for the Quadratic Cycle Cover Problem via Cutting-Plane Augmented Lagrangian Methods and Reinforcement Learning
• Minimization and maximization versions of the quadratic travelling salesman problem
• Edge sparsification for geometric tour problems
• A tabu search with geometry‐based sparsification methods for angular traveling salesman problems
• The Chvátal-Gomory procedure for integer SDPs with applications in combinatorial optimization

Describes a project that uses

Uses Software

• Concorde

This page was built for publication: Geometric and LP-based heuristics for angular travelling salesman problems in the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2003422)