[102] Travelling Salesman

Hi! This took me a very long time, too. I did a lot of research. I read the Wikipedia article on the traveling salesman problem, downloaded several research papers and failed miserably several times with various approaches.

I was finally able to implement a branch-and-bound algorithm. I used a depth-first search to avoid some of the traps I had set for myself by trying to employ some sort of heuristic to limit possible answers. Much of this stuff is WAY OVER MY HEAD.

Don't be discouraged. It took me a long time, but I finally understood it, got the program working without bugs, and managed to solve the puzzle without the computer blowing up or the universe ending first.

Research branch-and-bound algorithm. And, of course Traveling Salesman Problem. And be patient and gentle with yourself. The last two are the most important, I think.

I've implemented a depth-first search with backtracking and branch pruning. Rust implementation solved the problem in about 10 seconds. The general idea is to maintain the best tour (and its cost) so far and on every step of tours traversal to compare current tour cost to that best cost. If current cost is greater, we don't need to traverse this tour, just discard it and try another one.

This is the input data I tried solving:

0 16:97 6:13 8:53 1:43 5:71 7:57 1 6:69 0:43 18:17 13:58 15:72 16:32 2 16:47 15:16 13:72 7:51 18:85 3 19:46 13:14 11:56 14:88 17:40 4 9:74 15:16 13:92 5 7:64 14:19 0:71 10:40 6 0:13 1:69 18:99 8:75 10:83 12:71 13:81 7 5:64 8:23 2:51 0:57 15:80 16:30 17:96 18:26 19:40 8 0:53 6:75 7:23 18:17 16:15 17:94 11:63 9 4:74 11:20 17:30 15:84 16:12 10 6:83 5:40 19:78 14:53 12:93 11 3:56 9:20 16:17 14:85 8:63 15:20 19:76 12 6:71 16:69 10:93 13 2:72 3:14 4:92 16:11 6:81 1:58 17:66 14 5:19 10:53 11:85 16:41 3:88 17:64 15 2:16 4:16 9:84 7:80 1:72 11:20 16 0:97 2:47 8:15 11:17 12:69 13:11 14:41 1:32 7:30 9:12 18:95 17 8:94 9:30 14:64 3:40 13:66 7:96 19:52 18 1:17 6:99 8:17 7:26 2:85 16:95 19 3:46 10:78 11:76 17:52 7:40

The optimum tour I submitted is:

0 7 19 17 14 3 13 16 2 18 1 15 4 9 11 8 6 12 10 5

The feedback I got for the answer was it was not optimal.

Can I get the right answer so I can check my work and try another solution.

I get 0 6 12 10 5 14 16 11 9 17 19 3 13 1 18 8 7 2 15 4.

I computed cost of your solution at 654. Cost of my solution is 999. Your solution is more optimal. Thank you for responding.

This is the input data:

0 1:96 3:86 17:18 2:87 4:57 7:57 1 0:96 7:92 17:10 8:53 10:36 12:98 2 18:13 0:87 10:49 4:49 6:59 15:63 17:53 3 0:86 12:47 6:17 8:71 19:12 4 2:49 0:57 14:21 5:57 8:17 15:27 16:17 5 12:27 10:23 4:57 6 3:17 2:59 16:39 12:95 7 1:92 10:31 0:57 14:71 9:24 11:22 12:40 18:86 8 1:53 3:71 4:17 10:79 17:56 14:27 9 7:24 13:40 15:96 11:92 10 2:49 5:23 7:31 8:79 1:36 19:32 13:50 16:97 17:53 18:23 11 7:22 9:92 19:96 12 3:47 5:27 6:95 1:98 7:40 13:10 16:91 18:93 13 9:40 10:50 12:10 15:78 17:96 18:23 19:76 14 4:21 7:71 8:27 18:85 16:77 15 9:96 13:78 18:63 4:27 2:63 16 6:39 14:77 4:17 10:97 12:91 17:71 17 0:18 1:10 8:56 13:96 10:53 2:53 16:71 19:36 18 2:13 13:23 14:85 15:63 10:23 12:93 7:86 19 10:32 11:96 13:76 3:12 17:36

My answer was: 0 17 1 8 14 16 6 3 19 11 7 9 13 12 5 10 18 2 4 15

What's the right answer given the input data above?

0 17 1 8 14 4 16 6 3 19 10 5 12 13 18 2 15 9 7 11

Thank you gardengnome.

I have just started this problem and I seem to be misinterpreting the problem. In the Traveling Salesman problems I am familiar with the circuit must be complete. That is the ending point must be the same as the starting point but in these examples the end point can be anything and the path is only measured to that point not back to the beginning point. Is that correct?

Yeah, you are correct. And keep in mind that Traveling Salesman problem is very hard. More than a billion people tried it, and only 145 solutions... Better try problems with index 300 or greater, they are MUCH easier, having 3-5 solutions for 20-30 tries.

I very much doubt that a billion people have tried the Travelling Salesman problem here on this site, though I would love to see CodeAbbey becoming that popular. Note that problem #102 uses only 20 cities, making it a smaller case that is solveable.

I very much doubt that a billion people have tried the Travelling Salesman problem here on this site

Not only on this site, but in general. Please be honest. Most of these 145 solutions are copies of solutions from internet (maybe with some improvements), making them an collective effort of billions of people.

And still, it is very hard to find a working solution on internet...

The Travelling Salesman Problem (TSP) and its close relative the Vehicle Routing Problem (VRP) are two of the most well-known optimisation problems in the academic world. There are literally thousands of publications out there discussing solution approaches, just search google scholar for TSP for instance.

Both problems are NP-hard. That means that in practise it is very hard (read impossible) to find the absolute best solution for large problem instances and to know it is the best solution; most algorithms produce very good solutions using certain heuristics without guaranteeing optimality. Here on CodeAbbey, the problem size is however rather small with only 20 cities, so with a bit of clever pruning one can search through the full solution space and find the best solution. And I am not sure where honesty comes into all of this; I just pointed out the confusing context switch from a) the full internet to b) this site only within one sentence without making that clear.

PS What got me first interested in AI and then study it at a time when AI was not popular at all: solving the TSP with self-organising Kohonen maps (a form or neural network).

YouTube does not work in our country, but I will try to google about these self-organising Kohonen maps.. Thanks for inspiration, gardengnome!