Traveling Salesman Visualization

Personal motivation

I wanted to do a challenge project, a demonstration of my skills solving combinatorial optimization problems, and most importantly satisfy the desire of learning new skills. Interactive Traveling Salesman Problem demonstration seemed to be perfect fit, as it is classic benchmark for optimization algorithms, and I haven’t had any experience writing JavaScript which is needed to make this program run in a browser.

Problem

Traveling Salesman Problem (TSP) is a NP-hard combinatorial optimization problem that asks a question: what is the shortest route connecting all cities and return to the origin city. In this interactive demonstration you can drop any number of cities by clicking in a box above. Each pair of cities has a distance defined by Cartesian coordinate system, in other words straight line distance connecting those cities. The goal of a problem is to find shortest possible path (or very close to shortest) that connects all cities in the box, and obtain this solution in real time with minimal delay.

Method

To solve this optimization problem, I have chosen Ant Colony Optimization algorithm due my experience using this algorithm solving other combinatorial optimization problems. Ant Colony Optimization is nature inspired meta heuristic optimization algorithm that uses pheromone based communication. Artificial ants are laying down pheromone on each path they visit while doing a tour similarly how real ant laying down pheromone on resources and environment they explore. Increased level of pheromone on a track attracts more ants to visit the track, therefore overtime ants get attracted more to the track while continuing the exploration.

Program

Ant Colony Optimization algorithm starts with search space preparation. Then iterative search is applied. Multiple ants within an iteration build each build entire route. They share local pheromone and best ant on an iteration lays down pheromone on global pheromone. Once iterative search is over, best route is selected for display.

For search space preparation, every city gets a direct connection to every other city (edge), pheromone and heuristic value is associated to each edge of a search space. Iterative search is relatively simple because TSP does not have complex constraints that limit solution feasibility in the optimization problem. While building solution Ants are stochastically choosing next unvisited destination, using pheromone heuristic information and some randomness. Finished routes have tour length evaluated and best ant solution is taken to lay down pheromone for further iterations. When all iterations are finished, overall best solution route is displayed.

Future work

I am planning to do a user interface upgrade where allow option for user place the cities in the box and attempt to draw the route then press a button and let program solve it and compare the distances of user and computer generated paths. Moreover, I plan to add genetic algorithm optimization engine too and compare performance of both algorithms in terms solution quality and time to achieve solution.