Novel concave hull-based heuristic algorithm for TSP

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

Leonardo Mostarda, Kemal Ihsan Kilic

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

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reducibility among Combinatorial Problems
• A Method for Solving Traveling-Salesman Problems
• Approximation algorithms for multi-criteria 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
• The convex-hull-and-line traveling salesman problem: A solvable case
• Spacefilling curves and the planar travelling salesman problem
• The Traveling-Salesman Problem
• The traveling salesman problem and its variations.
• 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)