3
$\begingroup$

I'm currently working on a project discussing applications of the Delaunay Triangulation, and the primary use-case is applications to TSP (or relaxations of the problem).

See: http://www.lancaster.ac.uk/staff/letchfoa/articles/triangulations.pdf for context.

One snag in the approach is that it occasionally produces non-Hamiltonian graphs (no Hamiltonian cycles). This forces us to consider relaxations of TSP where revists are allowed. In particular, given a Delaunay graph $G = (V,E)$, where the edges $E$ are weighted, I wish to find the minimum weight circuit when revisits are allowed.

I'm sure the usual heuristics apply here (nearest-neighbor, simulated annealing, ant colony, etc.) but I'm looking for any major research in this direction. I had difficulty finding anything substantial after a few hours research. This is perhaps because I'm having difficulty putting the problem into words, which brings me to my next question: is there a common name for this problem, so that I can search the literature more efficiently?

Thanks, Jon

PS: Attached is one such non-Hamiltonian triangulation. I had initially hoped these cases would be very uncommon, but unfortunately this one arose from a data set representing city locations (see: http://www.math.uwaterloo.ca/tsp/world/countries.html).

Non-Hamiltonian Graph Resulting from Delaunay Triangulation

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.