Article Details

---

Completion Time: 30 min
Difficulty: Beginner
Subject: Optimization Methods and Algorithms

---

---

This article is about the Travelling Salesman Problem. We will first learn what is the Travelling Salesman Problem. we will see a little history of the Travelling Salesman Problem , some application and finally how to solve it.

---

1. What is the Travelling Salesman Problem ?

There are many ways to define the Travelling Salesman Problem. First we can say that the Travelling Salesman Problem is a Combinatorial optimization problem. A simple defintion can be:

given a set of cities and the distance between each possible pair, find the shortest possible route visiting all the cities exactly once and returning to the starting point.

A more tecnical definition could be:

Find the hamiltonian cycle of minimum weight in a graph.

the Travelling Salesman Problem is NP-hard and have two version:

1. Standard or simmetric: In this version of the problem, travelling from city X to city Y is the same distance as travelling from city Y to city X
2. Asimmetric: In this version of the problem, routes may not exist in the two directions between two cities X and Y or the distances can be different.

Some facts about the Travelling Salesman Problem:

1. It can be resolved by exact methods or heuristic methods
2. For n cities, the number of possible routes is ^(n-1)!⁄₂.
3. A 600 MHz processor to evaluate all possible routes for 20 cities will take about 3 years.

---

2. Brief history of the Travelling Salesman Problem

The Travelling Salesman Problem was invented in the 1800 by the mathematicians W.T. Hamilton(Irish) and Thomas Kirkman(british).
The first mathematical formulation of Travelling Salesman Problem was made in 1930 by the American mathematician Karl Menger.
The name Travelling Salesman Problem was introduced by the American mathematician Hassler Whitney

---

3. Application of the Travelling Salesman Problem

Where the Travelling Salesman Problem is used in the real life ? In sectors who have something to do with Scheduling, transportation, planning, logistics and manufacture of microchips.
Here is the lis of some practical example in which the Travelling Salesman Problem is used:

1. overhaul of gas turbine engine
2. x ray crystallography
3. Computer wiring
4. Order-picking problem in Warehouse

---

4. How to solve Travelling Salesman Problem ?

Like said at the begining of the article, to solve the Travelling Salesman Problem we can use heuristics algorithms or exacts algorithms.

Exacts algorithms

1. Direct MethodHere we compute all the possible routes, and then we find the shortest among them.
2. Dynamic Programming
3. Branch and Bound

Heuristics algorithms

1. Nearest Neigbour Algorithm
2. Genetic Algorithm
3. Simulated AnnealingA randomized local searched Algorithm.
4. Tabu Search

---

5. Links and Literature

1. Wikipedia article
2. Wikipedia article on the studentroom.co.uk
3. Report: Travelling Salesman Problem: An Overview of Applications, Formulations, and Solution Approaches. By Rajesh Matai, Surya Prakash Singh and Murari Lal Mittal

---

6. photo and image credits

1. My study challenge
2. www.answers.com
3. www.masaoodjohnbrown.com
4. www.coyoteblog.com
5. www.cipherlab.com

---

7. Thank you

Support my challenge, support my blog. Please Share this article if you found it useful. Thank you.

---