Travelling Sales Person Problem

TSP Problem

The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?"

The problem was first formulated in 1930 and is one of the most intensively studied problems in optimization. It is used as a benchmark for many optimization methods. Even though the problem is computationally difficult, a large number of heuristics and exact algorithms are known, so that some instances with tens of thousands of cities can be solved completely and even problems with millions of cities can be approximated within a small fraction of 1%.

The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments. The TSP also appears in astronomy, as astronomers observing many sources will want to minimize the time spent moving the telescope between the sources. In many applications, additional constraints such as limited resources or time windows may be imposed.

These are some of the algorithms I used

Note the purple route is the best route it's found so far and the thin white lines are the routes it's trying real time.

Random Sort

This canvas sorts through random possiblities. Every frame the program chooses two random points (cities) and swaps them around. eg say the order was London, Paris, Madrid, the program would swap London and Paris so that the new order is: Paris, London, Madrid. The program then compares the distance against the record distance to decide whether the new order is better than the old order. This search method is the most inefficient way, the worst case scenario is never ending, as the point swaping is random the program may never reach the optimum route


Lexicographic Order

This canvas sorts through all possible orders sequentially, so after n! (where n is the number of points) this algorithm is guaranteed to have found the quickest possible route. However it is highly inefficient always taking n! frames to complete and as n increases, time taken increases exponentially.

Click here to learn more about the algorithm

Genetic Algorithm

This canvas is the most efficient at finding the quickest route, it is a mixture of the two methods above. It starts off by creating a population of orders, a fitness is then generated for each order in the population. This fitness decides how likely the order is to be picked and is based on the distance it takes (lower distance is better). When two orders are picked, the algorithm splices the two together at a random term, it's then mutated and compared against the record distance. This takes the least amount of time to find the shortest distance as the algorithm doesn't search through permuations that are obviously longer due to the order.