# 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. – Raphael Feb 15 '13 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. – JeffE Feb 15 '13 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. – Paresh Feb 15 '13 at 16:59
• What would be an application of or a motivation for this problem? – Yuval Filmus Feb 18 '13 at 5:53
• To say d implies shortest length is wrong, wouldn't d make the number of length. – user29838 Mar 18 '15 at 18:13
{"ft_lang_label":"__label__en","ft_lang_prob":0.8710183,"math_prob":0.9990708,"size":1189,"snap":"2020-34-2020-40","text_gpt3_token_len":334,"char_repetition_ratio":0.11223628,"word_repetition_ratio":0.0,"special_character_ratio":0.2918419,"punctuation_ratio":0.11153846,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9998857,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-09-21T18:52:17Z\",\"WARC-Record-ID\":\"<urn:uuid:ef52377e-7d6e-467e-9b81-e37d47df1760>\",\"Content-Length\":\"146292\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:727a8e4f-ec64-41d0-99fb-fc5050c5acc1>\",\"WARC-Concurrent-To\":\"<urn:uuid:cf390763-866b-4e81-b7c8-c15e4f48b24b>\",\"WARC-IP-Address\":\"151.101.65.69\",\"WARC-Target-URI\":\"https://cs.stackexchange.com/questions/9802/travelling-salesman-problem-with-detours\",\"WARC-Payload-Digest\":\"sha1:MPPU23OY4WX5DVF7BWF3O2WVXGJMUHNI\",\"WARC-Block-Digest\":\"sha1:5F6R33IJNJN7H7ONPNFVCUXXBHNIQNVE\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-40/CC-MAIN-2020-40_segments_1600400202007.15_warc_CC-MAIN-20200921175057-20200921205057-00112.warc.gz\"}"}