Scribd
Upload
222 views

Example: Travelling Salesman Problem: To From 1 2 3 4 5 1 2 3 4 5

Mr. Rolling Stone plans to visit 5 cities with varying travel times between each city. Using the Hungarian method, the optimal route is determined to be: 1) Start in city 1 and travel to city 4 (4 hours) 2) Travel from city 4 to city 2 (4 hours) 3) Travel from city 2 to city 3 (7 hours) 4) Travel from city 3 to city 5 (6 hours) 5) Travel from city 5 back to city 1 (5 hours) This route minimizes the total travel time at 26 hours.

Uploaded by

Isha Natu
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
222 views

Example: Travelling Salesman Problem: To From 1 2 3 4 5 1 2 3 4 5

Mr. Rolling Stone plans to visit 5 cities with varying travel times between each city. Using the Hungarian method, the optimal route is determined to be: 1) Start in city 1 and travel to city 4 (4 hours) 2) Travel from city 4 to city 2 (4 hours) 3) Travel from city 2 to city 3 (7 hours) 4) Travel from city 3 to city 5 (6 hours) 5) Travel from city 5 back to city 1 (5 hours) This route minimizes the total travel time at 26 hours.

Uploaded by

Isha Natu
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

Example: Travelling Salesman Problem

To

From 1 2 3 4 5

1 ∞ 5 8 4 5

2 5 ∞ 7 4 5

3 8 7 ∞ 8 6

4 4 4 8 ∞ 8

5 5 5 6 8 ∞

A travelling salesman, named Rolling Stone plans to visit five cities 1, 2, 3, 4 & 5. The
travel time (in hours) between these cities is shown below:

How should Mr. Rolling Stone schedule his touring plan in order to minimize the total
travel time, if he visits each city once a week?

Solution

After applying steps 1 to 4of the Hungarian method, we get the following assignments.

To

From 1 2 3 4 5

1 ∞ 1 3 1

2 1 ∞ 2 1

3 2 1 ∞ 2

4 3 ∞ 4

5 3 ∞
Number of lines (4) not equal to order of Matrix (5). So optimal condition not
satisfied.

Select the smallest element from all the uncovered elements (LOE=1). Subtract this
LOE from all the uncovered elements and add it to the elements, which lie at the
intersection of two lines. Thus, we obtain another reduced matrix for fresh assignment.
Repeating step 3 on the reduced matrix, we get the following assignments.

To

From 1 2 3 4 5

1 ∞ 2 1

2 ∞ 1 1

3 1 ∞ 2

4 3 ∞ 5

5 4 ∞

Optimal condition satisfied.

The above solution suggests that the salesman should go from city 1 to city 4, city 4 to
city 2, and then city 2 to 1 (original starting point). The above solution is not a solution to
the travelling salesman problem as he visits city 1 twice.

The next best solution can be obtained by bringing the minimum non-zero element, i.e.,
1 into the solution. Please note that the value 1 occurs at two places. We will consider
all the cases separately until the acceptable solution is obtained. To make the
assignment in the cell (2, 3), delete the row & the column containing this cell so that no
other assignment can be made in the second row and third column.

Now, make the assignments in the usual manner as shown in the following table.
He starts from city 1 and goes to city 4; from city 4 to city 2; from city 2 to city 3; from
city 3 to city 5; from city 5 to city 1.

Substituting values from original table:


4 + 7 + 6+ 4 + 5 = 26 hours.

You might also like