12

I have a solver that solves normal symmetric TSP problems. The solution means the shortest path via all the nodes with no restriction on which nodes are the first and the last ones in the path.

Is there a way to transform the problem so that a specific node can be ensured as the start node, and another node as the end node?

One way would be to add an I - a very large distance - to all distances between these start/end nodes and all the others (adding I twice to the distance between start and end node), so the solver is tempted to visit them only once (thus making them as the start and the end of the path).

Are there any big disadvantages of this approach, or is there a better way to do this?

Cœur
  • 37,241
  • 25
  • 195
  • 267
Jānis Elmeris
  • 1,975
  • 1
  • 25
  • 43
  • Are you saying that you don't want the solution to return to the start (i.e. you want a normal TSP solution less the edge between start and end points)? – hatchet - done with SOverflow Jan 25 '13 at 18:19
  • @nhahtdh Do you mean to change the solver, so it solves other types of problems than it does now? I cannot do it, unfortunately. The solver solves a normal TSP where a node being the first or the last one in the route depends on what the shortest route is. If the first or the last node is specified, the found path wouldn't be the shortest, so that's another type of problem. – Jānis Elmeris Jan 25 '13 at 18:21
  • @hatchet Yes, I don't want the solution to return to the start. And I also want to specify which node should be the first one and which one should be the last one. – Jānis Elmeris Jan 25 '13 at 18:24
  • 2
    A problem with picking a large distance is that you must ensure it is sufficiently large to force the start and end nodes to be connected in all good solutions. It might be better to give a distance of 0 between start and end. – hatchet - done with SOverflow Jan 25 '13 at 18:30
  • @hatchet: That is a good solution if there is no negative edge. Another way is to add a dummy node that connects the start and end nodes with edge 0. The cycle must contain the dummy node, so it will connects start-dummy-end (this will work whether the graph has negative edge or not). – nhahtdh Jan 25 '13 at 18:36
  • Thank you for the replies! I have only now realised that the solver actually gives me a cycle (not a path with the start to end edge excluded from the total length), so I really can choose the starting point freely. My graph won't have negative edges, so I'll just set the distance from start to end node to 0. – Jānis Elmeris Jan 28 '13 at 11:11
  • @nhahtdh What happens if there are negative edges and I've set distance 0 between start and end, not using the dummy? Does the problem persist if I add the absolute value of the most negative distance I have to all distances (thus making all positive)? – Jānis Elmeris Jan 30 '13 at 12:19
  • 1
    @Janis: Consider a 4 nodes graph with 4 negative edges: S <-> 1 <-> E <-> 2, and another negative edge from 1 <-> 2 that is more than the edge 1 <-> E. Distance 0 between start and end does nothing here. – nhahtdh Jan 30 '13 at 12:37
  • 1
    @Janis: If you add some value to all edges of **original graph**, the shortest path stays the same (since all Hamilton path has same number of edges, you can add/minus any amount and the result will not change) – nhahtdh Jan 30 '13 at 12:42
  • OK, so, the distance between S and E just needs to be smaller than any other distance in the graph, is that the idea of hatchet's solution? If I have negative edges, I just need the S-E distance to be smaller than the smallest negative? Somehow, intuitively, it seems to me that there will be cases that it won't suffice and I'll have to use the dummy node anyway (making all its distances to nodes other than S and E infeasibly big ones). I already have many fake cheap distances due to a ATSP->TSP transformation. – Jānis Elmeris Jan 30 '13 at 13:26

2 Answers2

20

You can add a dummy node, which connects to start and end node with edges with weight 0. Since the TSP must contain the dummy node, the final result must contain the sequence start - dummy node - end (there is no other way to reach the dummy node). Therefore, you can get the shortest Hamilton path with specified start and end node. This solution should work even if the edges in the graph are negative.

nhahtdh
  • 55,989
  • 15
  • 126
  • 162
  • @nmfzone: Not really, it's more of a reduction of "Finding a solution to TSP problem with specific start and end node" to "Finding a solution to TSP problem". – nhahtdh Aug 27 '17 at 05:52
4

Below is a visualization of the "dummy node" concept. On the left is a normal TSP with the same start and end node, A, and the optimal solution [A, B, E, D, C, A]. On the right is the same TSP but where the start node is A and the end node is E. Its optimal solution [A, B, C, D, E] clearly has nothing to do with the one in the normal case. The way we can find that solution is by "hacking" the distance matrix of the TSP graph. At the bottom of the distance matrix the dummy node is inserted and its distances to node A and E are set to 0 and its distances to all other nodes are set to inf. When the solver then tries to search through the distance matrix to find the optimal sequence of nodes A, DUMMY, E will stay together, e.g. [A, B, C, D, E, DUMMY, A] and this can then be cleaned up to give [A, B, C, D, E].

enter image description here

PS. note that this type of hack can have a severe impact on an exact solver's performance. Exact TSP solvers are set up with various geometric heuristics and putting in zero and inf distances clearly messes with that. I e.g. tried this for Concorde and it was not very happy about it and needed much more time to find optimal solutions sometimes. Didn't find any documentation for it to deal with this specific case but maybe there are other exact solvers that have capability to handle this specific condition.

Johan
  • 863
  • 3
  • 13
  • 28
  • Thank you for your input! So, you're offering basically the same as nhahtdh only adding that "no other way to reach the dummy node" could be achieved by setting the other distances to infinity. (This was long time ago, I don't remember, maybe I did exactly that in my specific implementation.) Tell me if I'm missing something here. (The image on the left is exactly what I would get normally, and the image on the right is what I needed instead. If adding the dummy node produces that, it's what I need.) – Jānis Elmeris Dec 16 '19 at 14:02
  • Yes, it's similar but @nhahtdh's answer didn't specify where in the data or code that the dummy is supposed to be added. I showed one way to do it, by changing the distance matrix. This is good if you download some solver which takes a distance matrix as input and you don't want or can't change code in it. This way you only change the input to the solver, but then you have to make sure that the matrix still adheres to specifications i.e. every node needs to have a distance between itself and the dummy. Maybe it's sometimes better to not use 0 and inf, but there needs to be something there. – Johan Dec 16 '19 at 16:53
  • I'm trying to use it and it's doesn't work. i catch an error "The distance between each pair of nodes must be greater than 0". I'm using the same length of array as you but numbered to check that all items looks the same. points: pts = [[0, 0], [1, 1], [2, 2], [3, 3], [4, 4], [np.Inf, np.Inf]] and distances: [[0, 1, 1.4], [0, 2, 2.8], [0, 3, 4.2], [0, 4, 5.6], [0, 5, 0], [1, 2, 1.4], [1, 3, 2.8], [1, 4, 4.2], [1, 5, inf], [2, 3, 1.4], [2, 4, 2.8], [2, 5, inf], [3, 4, 1.4], [3, 5, inf], [4, 5, 0]] – Massimo Dec 16 '21 at 19:39
  • Problem as i see with zero length path's. I'm trying to change zero to very small value like 0.000001 - and i received wrong results of best state: [1, 0, 5, 4, 3, 2] where number 5 - is Infinity (Dummy node). I don't know how to trust the algorithm if results looks random. With the real data (400 points) i received very random results. Im thinking Dummy mode should be first or last in the final path, but i don't get any results with dummy node on the edge of list – Massimo Dec 16 '21 at 19:39
  • @MaxKu Depending on the software small/large values instead of 0/inf might be necessary as you pointed out. The dummy node thing only makes sure that the origin and destination nodes stay connected in the solution cycle and you have to write some code to translate that into [origin, ..., destination]. I know it works but I also remember getting some weird behavior before things started working. – Johan Jan 05 '22 at 18:00