Overview
In the Traveling Salesman Problem (TSP), you are generally given a list of cities and the distances between each pair of cities. The goal is to find the shortest possible route that visits each city exactly once and returns to the original city. The TSP has a wide range of applications in many different industries, including (but not limited to) optimizing mail and shipping routes, guiding industrial machines, reducing flight times, and mapping genomes. The problem has been studied informally for centuries, and more formally for decades. The TSP has become one of the most popular problems in the fields of mathematics and computer science. Numerous approximation techniques have been studied, ranging from linear programming methods to nature-inspired models. Here, we present a novel N-body approach to the TSP.
- Being an N-body simulation, we let each pair of cities interact with each other through an attractive-repulsive force.
- Surround the cities with a bounding circle whose center is the centroid of the cities.
- Insert an additional circle at the centroid of the cities, with an initial radius of zero.
- Increase the inner circle's radius over time until it reaches the outer circle.
- The circles act as walls pushing on the cities, so that by the time the inner circle has reached the outer circle, the cities have been pushed into a 1-dimensional ring.
- Obtain the path from the resulting ring.
Check out some runs, either below or from the sidebar menu!
In the future, I'd like to perform some hyperparameter optimization in order to find ideal parameters for our simulations. Additionally, I'd like to be able to run multiple simulations simulataneously in parallel on the GPU. In general, I'd like to improve code efficiency. I'd also like to investigate other force functions and moving into higher dimensional spaces.
Runs
Click on the images below to view runs for that dataset.
att48
The capitals of the lower 48 contiguous states.
bayg29
29 cities in Bavaria, Germany.
ch150
150 random points.