Mumbai University > MECH > Sem 7 > Operations Research

Marks: 5 M

Year: Dec 2012

Travelling salesman problem

A salesman visits a number of cities to sell his product. He knows the distance between each pair of cities that he’s travelling to. He also knows the associated cost of travelling between the cities. So the logical thing to do would be for him to either choose the shortest possible route, or the cheapest.

Usually, distance and/or cost is independent of the direction that the person is travelling. Such a model is said to be symmetrical. If the direction or cost varies with direction, then it is said to be asymmetrical.

Such a model could be used to find the quickest route in the following cases:

• Postal deliveries
• Inspection
• Assembly lines
• Bus routes