Ida Bjerga: T H E T R A V E L L I N G S A L E S M A N P R O B L E M

Some of you may think I´m lying around lazy doing nothing els than drinking red wine every day and enjoying my one year holiday. I hereby want to disconfirm this, and tell you that I´ve actually been working on an advanced logistical problem - the Travelling Salesman Problem.

For those of you who do not know the Travelling Salesman Problem this is Wikipedias explanation:

The travelling salesman problem (TSP) is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible route that visits each city exactly once and returns to the origin city.The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. In many applications, additional constraints such as limited resources or time windows make the problem considerably harder.(source: http://en.wikipedia.org/wiki/Travelling_salesman_problem)

The problem can be formulated as follows:
"If there are n cities a salesman must visit, and the distance between each pair of these cities is given, find the shortest tour where each city is visited exactly once and returing to your starting point"."The first thing you'll think is: "Can not be difficult..." That's true. You can easily solve the problem by comparing all possible solutions. However, when you have more than (let's say) 25 cities, it will be soon practically impossible to calculate all the ordered combinations (permutations). This is because the number of combinations is (n-1)!/2. (factorial of n = n * (n-1) * (n-2) * .. * 2 * 1) "
(source: http://travellingsalesmanproblem.com/)
(ps i dont care if the sources are reliable. this is not a bachelor assignement.)

Under you´ll see a map over Argentina. I´ve circled 12 places we would like to visit (with some smaller places close by). There are 19 958 400 possible solutions to this problem (11!/2). We´ve chosen the one under.