An algorithm for the open travelling salesman problem

by Thomas Delaney   Last Updated June 13, 2019 12:20 PM

I have come up with a dynamic programming approach to the travelling salesman problem, but I don't have the background knowledge of whether this type of program is in use, or programming skills to figure out how good a program it is. These are the steps of my program:

  1. For each city, connect it to the city that is closest to it (unless there is already a connection with that city). This step will result in one or more groups of cities, where a group is a set that is connected. (Marked in the diagram below as A, B, C, D.)

enter image description here

  1. Repeat step 1, now at the level of groups. Each group has 2 active ends - the city at either end of the chain (Blue in the diagram above). To find the distance of a group to another group, take the minimum of the four possible combinations for joining the active ends to each other. Choose a random group. Compare the distance of that group to each other group, choose the one which is closest, and connect them to form a larger group (this means two cities will become inactive. Choose another random group, connect it to the one which is closest. Keep repeating until there is only one group.

enter image description here

This algorithm seems to be quite light on computational power. How good is it in generating close-to optimal solutions?



Related Questions


Updated February 20, 2018 13:20 PM

Updated October 27, 2017 19:20 PM