3. Travelling salesman problem using branch and bound (penalty) method
1. A travelling salesman has to visit five cities. He wishes to start from a particular city, visit each city only once and then return to his starting point. The travelling cost of each city from a particular city is given below.
To city
A
B
C
D
E
From city
A
x
2
5
7
1
B
6
x
3
8
2
C
8
7
x
4
7
D
12
4
6
x
5
E
1
3
2
8
x
How should the jobs be allocated, one per employee, so as to minimize the total man-hours?
2. A travelling salesman, named Magan Shah plans to visit five cities 1, 2, 3, 4 and 5. The travel time (in hours) between these cities is shown below.
To city
1
2
3
4
5
From city
1
x
5
8
4
5
2
5
x
7
4
5
3
8
7
x
8
6
4
4
4
8
x
8
5
5
5
6
8
x
How should he schedule his touring plan in order to minimize the total travel time, if he visits each city once a week?