I am interested if there exists a following version of the travelling salesman problem:

INSTANCE: A finite set $C = \{1,2,\dots,k\}$ of cities, a positive integer distance $\delta(i,j)$ for each pair of cities, and two positive integers $d$ and $B$.

QUESTION: Is there a tour that visits every city in $C$, includes exactly $d$ detours, and has total length no more then $B$? In other words, suppose $OPT$ is the optimal permutation of the cities; that is, $OPT(i)$ is the next city after city $i$ in an optimal traveling salesman tour. Is there an ordering $x(0), \dots, x(k-1)$ of the cities such that $$\sum_{i=1}^{k} \delta(x(i), x((i+1) \bmod k)) \leq B$$ and there are exactly $d$ indices $i$ where $x((i+1) \bmod k) \ne OPT(x(i))$?

The $d$ implies that if my shortest tour is $a\rightarrow b \rightarrow c\rightarrow a$ but $d=1$ then what would be the shortest path if I had to first go to $c$, $ a \rightarrow c \rightarrow ...$. So $d$ tells me that I have to make $d$ number of wrong choices but I can choose these choices in any way I want to to minimize the length of the path.

Is this a problem worthwhile describing? Or if it has been described where could I see an example?

  • 1
    $\begingroup$ You define it, it exists. However, I wonder why the formal definition of your question does not relate to $d$ at all. $\endgroup$
    – Raphael
    Feb 15, 2013 at 11:04
  • 3
    $\begingroup$ I revised the formal statement to incorporate $d$, but please verify that I haven't changed the intent of the question. A major issue with this formulation is that the optimal TSO tour is not unique; the reversal of any optimal TSP tour is another optimal TSP tour. $\endgroup$
    – JeffE
    Feb 15, 2013 at 16:55
  • $\begingroup$ Maybe you can circumvent the issue raised by JeffE by asking for a tour which differs in exactly $d$ places from some optimal tour $OPT$. In other words, there is atleast one optimal tour, from which the desired tour differs in $d$ places. $\endgroup$
    – Paresh
    Feb 15, 2013 at 16:59
  • 3
    $\begingroup$ What would be an application of or a motivation for this problem? $\endgroup$ Feb 18, 2013 at 5:53
  • $\begingroup$ To say d implies shortest length is wrong, wouldn't d make the number of length. $\endgroup$
    – user29838
    Mar 18, 2015 at 18:13


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.