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.
Traveling salesman problem:
a) Just consider how a postman delivers the post to the addressee. He arranges all the letters in an order and starts from the post office and goes from addressee to addressee and finally back to his post office. If he does not arrange the posts in an order he may have to travel a long distance to clear all the posts.
b) Similarly, a traveling sales man has to plan his visits. Let us say, he starts from his head office and go round the branch offices and come back to his head office. While traveling he will not visit the branch already visited and he will not come back until he visits all the branches.
c) There are different types of traveling salesman's problems.
d) One is cyclic problem. In this problem, he starts from his headquarters and after visiting all the branches, he will be back to his headquarters.
e) 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.
f) The first type ofthe problem is solved by Hungarian method or Assignment technique.
g) 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 to 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.
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 I 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:
