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

DOI10.1016/j.cor.2019.01.016zbMath1458.90561arXiv1803.03681OpenAlexW2922057699MaRDI QIDQ2003422

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

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

combinatorial optimizationmatheuristicsinteger programming modelsangular-metric traveling salesman problem

Mathematics Subject Classification ID

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

Related Items

SDP-Based Bounds for the Quadratic Cycle Cover Problem via Cutting-Plane Augmented Lagrangian Methods and Reinforcement Learning, The quadratic cycle cover problem: special cases and efficient bounds, Accelerating the calculation of makespan used in scheduling improvement heuristics, A tabu search with geometry‐based sparsification methods for angular traveling salesman problems, Unnamed Item

Uses Software

• Concorde

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounding procedure for the asymmetric quadratic traveling salesman problem
• An extended approach for lifting clique tree inequalities
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• The traveling salesman. Computational solutions for RSP applications
• A linear time algorithm for the \(3\)-neighbour travelling salesman problem on a Halin graph and extensions
• Generating subtour elimination constraints for the TSP from pure integer solutions
• The traveling salesman problem and its variations.
• The symmetric quadratic traveling salesman problem
• Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics
• The pilot method: A strategy for heuristic repetition with application to the Steiner problem in graphs
• Discrete optimization methods to determine trajectories for Dubins' vehicles
• The Design of Approximation Algorithms
• Handbook of Approximation Algorithms and Metaheuristics
• The Angular-Metric Traveling Salesman Problem
• Traveling Salesperson Problems for the Dubins Vehicle
• An Analysis of the Asymmetric Quadratic Traveling Salesman Polytope
• Minimization and maximization versions of the quadratic travelling salesman problem
• Solution of a Large-Scale Traveling-Salesman Problem
• Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order