SKEDSOFT

Introduction:

Traveling salesman problem is the part of operation research which deals the interaction between costumer and salesman. The peculiarities of this type of problem is that one flight / train / bus leaves form a station with some flight number / train number / bus number. After reaching the destination, the same plane / train/bus leave that place (destination) and reach the hometown with different number.

Types of traveling and salesman problem:

•         There are different types of traveling salesman‘s problems.
•          One is cyclic problem. In this problem, starts from his headquarters and after visiting all the branches, he will be back to his headquarters.
•        The second one is Acyclic problem. In this case, the traveling salesman leaves his headquarters and after visiting the intermediate branches, finally reaches the last branch and stays there.
•         The first type of the problem is solved by Hungarian method or Assignment technique.
•         The second one is solved by Dynamic programming method.

Note:

The traveling salesman‘s problem, where we sequence the cities or branches he has to visit is a SEQUENCING PROBLEM. But the solution is got by Assignment technique. Hence basically, the traveling salesman problem is a SEQUENCING PROBLEM; the objective is to minimize the total distance traveled.

The mathematical statement of the problem is: Decide variable xij = 1 or 0 for all values of I and j so as to:

•       This is indeed a statement of assignment problem, which may give two or more disconnected cycles in optimum solution.
•        This is not permitted.
• That is salesman is not permitted to return to the origin of his tour before visiting all other cities in his itinerary.
•        The mathematical formulation above does not take care of this point.
•          A restriction like Xab Xbc Xca ≤ 2 will prevent sub-cycles of cities A, B, C and back to A.
•         It is sufficient to state at this stage that all sub - cycles can be ruled out by particular specifications of linear constraints.
•         This part, it is easy to see that a variable xij = 1, has no meaning.
•         To exclude this from solution, we attribute very large cost to it i.e infinity or big M, which is very larger than all the elements in the matrix.

Example:

A salesman stationed at city A has to decide his tour plan to visit cities B, C, D, E and back to city A in the order of his choice so that total distance traveled is minimum. No sub touring is permitted. He cannot travel from city A to city A itself. The distance between cities in Kilometers is given below: