2
$\begingroup$

I’m curious whether there is any work on the variant of the Travelling Salesman Problem where a subset of the nodes must be visited in a particular order. I haven’t found anything with searches or in survey articles, but that may just mean I haven’t found the right search terms or the right surveys.

If there are $n$ nodes in the graph, and a list $a_1, \dots, a_k$ of nodes that must be visited in that order, I can transform the problem to an instance of ATSP with $2k(n-k)+k$ nodes. The result is asymmetric even if the original edge-weights were symmetric, so we lose another factor of $2$ if we want to reduce it to a symmetric instance. I would be interested to know if there is a more efficient reduction.

Edited to add: On further reflection I think I can improve the reduction to $k(n-k)+k$ nodes.

Improve this question
$\endgroup$
2
  • $\begingroup$ In the ATSP Path setting we considered such a generalization. See paper theoryofcomputing.org/articles/v003a010/index.html. I had forgotten but the paper also points to a result for the metric case (undirected graphs) where a 3-approximation is feasible. $\endgroup$ – Chandra Chekuri Nov 6 '16 at 4:00
  • $\begingroup$ @ChandraChekuri Thanks! That link isn't working for me right now (server not responding) but I'll check it out when I can. $\endgroup$ – Robin Houston Nov 6 '16 at 12:49
4
$\begingroup$

This is a special case of the precedence-constrained TSP which has been studied quite a lot. For instance, there are a polyhedral analysis by Balas, Fischetti and Pulleyblank, and a branch-and-cut algorithm by Ascheuer, Jünger and Reinelt.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Great, thanks! It looks indeed as though “precedence-constrained TSP” is a key search term I was missing. $\endgroup$ – Robin Houston Nov 6 '16 at 13:01

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.