TSP Flaming

TSP Flaming

TSP Flaming quickly finds a good solution of the Travelling Salesman Problem using the method of Simulated Annealing.

Problem Statement

Given a map with cities locations, what is the least-cost round-trip route that visits each city exactly once and then returns to the starting city?

Observation

Size of solution space is n!, where n is number of cities. The most direct solution rapidly becomes impractical.

Simulated Annealing

Instead of using exhaustive enumeration a generic probabilistic meta-algorithm is used. In fixed amount of time it finds a good approximation to the global optimum in a large search space.