Novel concave hull-based heuristic algorithm for TSP

DOI10.1007/S43069-022-00137-9zbMATH Open1492.90150OpenAlexW4223922607MaRDI QIDQ2139346FDOQ2139346

Authors: Kemal Ihsan Kilic, Leonardo Mostarda 

Publication date: 17 May 2022

Published in: SN Operations Research Forum (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s43069-022-00137-9

Recommendations

• Worst-case analysis of some convex hull heuristics for the Euclidean travelling salesman problem
• scientific article; zbMATH DE number 3950233
• Good triangulations yield good tours
• Continuous reformulations and heuristics for the Euclidean travelling salesperson problem
• New TSP construction heuristics and their relationships to the 2-Opt

zbMATH Keywords

computational geometryDelaunay triangulationcombinatorial optimization heuristicsconcave hullTSP approximation algorithmsTSP heuristic algorithms

Mathematics Subject Classification ID

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

Cites Work

• Reducibility among combinatorial problems
• A method for solving traveling-salesman problems
• The multiobjective traveling salesman problem: A survey and a new approach
• Worst-case analysis of a new heuristic for the travelling salesman problem
• Traveling salesman problem, theory and applications.
• The convex-hull-and-line traveling salesman problem: A solvable case
• Spacefilling curves and the planar travelling salesman problem
• Title not available (Why is that?)
• The traveling-salesman problem
• The traveling salesman problem and its variations.
• Title not available (Why is that?)
• Efficient generation of simple polygons for characterizing the shape of a set of points in the plane
• Heuristics Based on Spacefilling Curves for Combinatorial Problems in Euclidean Space
• On the convex layers of a planar set
• TSP heuristics: domination analysis and complexity
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
• Good triangulations yield good tours
• Traveling salesman cycles are not always subgraphs of Voronoi duals
• Traveling salesman cycles are not always subgraphs of Delaunay triangulations or of minimum weight triangulations
• Finding Hamiltonian cycles in Delaunay triangulations is NP-complete
• Hard to solve instances of the Euclidean traveling salesman problem
• The Convex-hull-and-k-line Travelling Salesman Problem
• A simple method for resolving degeneracies in Delaunay triangulations
• Minimax estimation of the volume of a set under the rolling ball condition
• Fundamental Problems in Computing
• Engineering an approximation scheme for traveling salesman in planar graphs

Uses Software

• spatstat
• alphahull
• fitdistrplus
• tictoc
• concaveman

This page was built for publication: Novel concave hull-based heuristic algorithm for TSP

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