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?
$\begingroup$
$\endgroup$
2
-
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$– vonbrandCommented Mar 1, 2020 at 19:28
-
$\begingroup$ @vonbrand but there can be case that the path across another city is shorter than the direct path $\endgroup$– Shantanu ShindeCommented Mar 1, 2020 at 23:46
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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".
answered Mar 1, 2020 at 20:37
-
1$\begingroup$ Christofides's algorithm actually guarantees a 3/2-approximation. $\endgroup$ Commented Mar 1, 2020 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$ Commented Mar 1, 2020 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$ Commented Mar 1, 2020 at 23:59
-
$\begingroup$ @AnttiRöyskö Thanks I will update accordingly $\endgroup$ Commented Mar 2, 2020 at 0:00