# Travelling salesman problem with detours

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?

• You define it, it exists. However, I wonder why the formal definition of your question does not relate to $d$ at all. Commented Feb 15, 2013 at 11:04
• 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. Commented Feb 15, 2013 at 16:55
• 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. Commented Feb 15, 2013 at 16:59
• What would be an application of or a motivation for this problem? Commented Feb 18, 2013 at 5:53
• To say d implies shortest length is wrong, wouldn't d make the number of length.
– user29838
Commented Mar 18, 2015 at 18:13