2
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 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$
    – Yuval Filmus
    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

0

Reset to default

Your Answer

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