Focus on modelling : Travelling Salesman Problem (TSP)

In addition to well-known technical algorithms, it would also be interesting to, sometimes, discuss most challenging problems of mathematical modelling. The problem, we shall discuss today, is the Travelling Salesman Problem, or TSP for short.

TSP is a well known area of reasearch having many practical applications. It originated in Medieval Times, and, at a first glance, TSP may seem to be a simple problem having the following description : a travelling merchant (salesman) is planning to visit every city exactly once before returning to his home town. Since the distances between the towns are known, the merchant is planning his itinerary to minimize the total distance travelled. The problem is easily solvable by inspection of routes for relatively small number of cities. However, the problem is becoming more difficult to solve the more cities become involved. The difficulty of the problem is n! permutations. The TSP was proven to be NP-hard. Therefore, exhaustive enumeration of routes becomes impossible for large instances.

Some state-of-the-art algorithms based on branch-and-cut approach sucessfully solve relatively large TSP instances having hundreds or thousands of cities. However, due to problem's complexity, heuristics-based methods also appear to be very popular. For example, genetic algorithms prove to be very effective at exploring various parts of the search space by gradually evolving populations of chromosomes towards the optimum. On this way, the challenging questions to think about are how the chromosomes will be represented, and how recombination and mutation will work ...

Meantime, the author will look for the most efficient representations of chromosomes and post same in the forthcomming days ... :)