I am trying to solve a modified version of the TSP. In my version, multiple visits to a city are allowed, as long as the path is the shortest, and also, only subset of the cities are compulsory to visit, as in, you can go through other cities to visit all the subset cities if path is shorter, but if not, the other cities can be ignored. For simplicity, starting city is fixed. Also, all cities are not connected to others directly. I know approx. solutions for the traditional TSP, but, I have trouble solving this one. A naive approach can be to find all possible combinations of the subset cities and check which has the shortest total path length, but that solution will have a n^2 complexity for trying each combination, plus the complexity for finding shortest path for each two cities. So, what should I use to solve this problem?

  • 1
    $\begingroup$ You can just restrict to the "interesting'" cities by computing shortest paths between them. Allowing multiple visits just lengthens the tour, at least if the triangle inquality is satisfied. $\endgroup$ – vonbrand Mar 1 at 19:28
  • $\begingroup$ @vonbrand but there can be case that the path across another city is shorter than the direct path $\endgroup$ – Shantanu Shinde Mar 1 at 23:46

As mentioned in the comments, you can compute APSP (All-Pairs Shortest Paths) at first and build the matrix $$D:=\left(d_{ij}\right)_{i,j\in[n]}$$, where $d_{ij}$ is the length of a shortest path from the vertex $i$ to the vertex $j$. By solving the usual travelling sales man on the graph $G'$ where $D$ is the adjacency matrix, you get a solution for your version of the problem. Try to see why this works as an exercise.

Your case is actually mentioned in the Wikipedia page under metrics.

Note that $D$ defines a metric and metric TSP admits a polynomial time 1.5-approximation. The same Wikipedia article contains more information about this algorithm under the section "Constructive heuristics".

| cite | improve this answer | |
  • 1
    $\begingroup$ Christofides's algorithm actually guarantees a 3/2-approximation. $\endgroup$ – Antti Röyskö Mar 1 at 23:35
  • $\begingroup$ what is APSP? also, all the cities are not directly connected, so, revisiting can be needed. also, there is case of direct path being longer than path via non compulsory city $\endgroup$ – Shantanu Shinde Mar 1 at 23:48
  • $\begingroup$ APSP is all pairs shortest paths. In short for each pair of vertices $u$ and $v$ set the length of the edge $\{u, v\}$ to be $d_{u,v}$, the length of the shortest path from $u$ to $v$. Solving TSP on the resulting graph would solve your special version of the problem on the input graph. $\endgroup$ – narek Bojikian Mar 1 at 23:59
  • $\begingroup$ @AnttiRöyskö Thanks I will update accordingly $\endgroup$ – narek Bojikian Mar 2 at 0:00

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.