Heuristic Methods
INDEX function
problem #6, p. 333 [1] [2]
a.
Data |
|
|
Amsterdam |
Athens |
Berlin |
Copenhagen |
Dublin |
Lisbon |
London |
Luxembourg |
Madrid |
Paris |
Rome |
Brussels |
|
From/To |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
Amsterdam |
1 |
0 |
2166 |
577 |
622 |
712 |
1889 |
339 |
319 |
1462 |
430 |
1297 |
175 |
|
Athens |
2 |
2166 |
0 |
1806 |
2132 |
2817 |
2899 |
2377 |
1905 |
2313 |
2100 |
1053 |
2092 |
|
Berlin |
3 |
577 |
1806 |
0 |
348 |
1273 |
2345 |
912 |
598 |
1836 |
878 |
1184 |
653 |
|
Copenhagen |
4 |
622 |
2132 |
348 |
0 |
1203 |
2505 |
942 |
797 |
2046 |
1027 |
1527 |
768 |
|
Dublin |
5 |
712 |
2817 |
1273 |
1203 |
0 |
1656 |
440 |
914 |
1452 |
743 |
1849 |
732 |
|
Lisbon |
6 |
1889 |
2899 |
2345 |
2505 |
1656 |
0 |
1616 |
1747 |
600 |
1482 |
1907 |
1738 |
|
London |
7 |
339 |
2377 |
912 |
942 |
440 |
1616 |
0 |
475 |
1259 |
331 |
1419 |
300 |
|
Luxembourg |
8 |
319 |
1905 |
598 |
797 |
914 |
1747 |
475 |
0 |
1254 |
293 |
987 |
190 |
|
Madrid |
9 |
1462 |
2313 |
1836 |
2046 |
1452 |
600 |
1259 |
1254 |
0 |
1033 |
1308 |
1293 |
|
Paris |
10 |
430 |
2100 |
878 |
1027 |
743 |
1482 |
331 |
293 |
1033 |
0 |
1108 |
262 |
|
Rome |
11 |
1297 |
1053 |
1184 |
1527 |
1849 |
1907 |
1419 |
987 |
1308 |
1108 |
0 |
1173 |
|
Brussels |
12 |
175 |
2092 |
653 |
768 |
732 |
1738 |
300 |
190 |
1293 |
262 |
1173 |
0 |
Order |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
1 |
City |
12 |
1 |
4 |
3 |
2 |
11 |
9 |
6 |
5 |
7 |
10 |
8 |
12 |
Distaance |
175 |
622 |
348 |
1806 |
1053 |
1308 |
600 |
1656 |
440 |
331 |
293 |
190 |
|
Minimum-distance = 8822
The
sequence is Brussels, Amsterdan, Copenhagen, Berlin, Athens, Rome, Madrid, Lisbon, Dublin, London,
Paris, Luxembourg, and then Brussels. The
length of the minimum-distance tour is 8822.
b.
Data |
|
|
Amsterdam |
Athens |
Berlin |
Copenhagen |
Dublin |
Lisbon |
London |
Luxembourg |
Madrid |
Paris |
Rome |
Brussels |
|
From/To |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
Amsterdam |
1 |
0 |
2166 |
577 |
622 |
712 |
1889 |
339 |
319 |
1462 |
430 |
1297 |
175 |
|
Athens |
2 |
2166 |
0 |
1806 |
2132 |
2817 |
2899 |
2377 |
1905 |
2313 |
2100 |
1053 |
2092 |
|
Berlin |
3 |
577 |
1806 |
0 |
348 |
1273 |
2345 |
912 |
598 |
1836 |
878 |
1184 |
653 |
|
Copenhagen |
4 |
622 |
2132 |
348 |
0 |
1203 |
2505 |
942 |
797 |
2046 |
1027 |
1527 |
768 |
|
Dublin |
5 |
712 |
2817 |
1273 |
1203 |
0 |
1656 |
440 |
914 |
1452 |
743 |
1849 |
732 |
|
Lisbon |
6 |
1889 |
2899 |
2345 |
2505 |
1656 |
0 |
1616 |
1747 |
600 |
1482 |
1907 |
1738 |
|
London |
7 |
339 |
2377 |
912 |
942 |
440 |
1616 |
0 |
475 |
1259 |
331 |
1419 |
300 |
|
Luxembourg |
8 |
319 |
1905 |
598 |
797 |
914 |
1747 |
475 |
0 |
1254 |
293 |
987 |
190 |
|
Madrid |
9 |
1462 |
2313 |
1836 |
2046 |
1452 |
600 |
1259 |
1254 |
0 |
1033 |
1308 |
1293 |
|
Paris |
10 |
430 |
2100 |
878 |
1027 |
743 |
1482 |
331 |
293 |
1033 |
0 |
1108 |
262 |
|
Rome |
11 |
1297 |
1053 |
1184 |
1527 |
1849 |
1907 |
1419 |
987 |
1308 |
1108 |
0 |
1173 |
|
Brussels |
12 |
175 |
2092 |
653 |
768 |
732 |
1738 |
300 |
190 |
1293 |
262 |
1173 |
0 |
Order |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
City |
12 |
1 |
4 |
3 |
8 |
10 |
7 |
5 |
6 |
9 |
11 |
2 |
Distaance |
175 |
622 |
348 |
598 |
293 |
331 |
440 |
1656 |
600 |
1308 |
1053 |
|
Minimum-distance = 7424
The
sequence is Brussels, Amsterdan, Copenhagen, Berlin, Luxembourg, Paris, London, Dublin,
Lisbon, Madrid, Rome, and Athens.
Additional questions to answer for Part
B:
|
|
Amsterdam |
Athens |
Berlin |
Copenhagen |
Dublin |
Lisbon |
London |
Luxembourg |
Madrid |
Paris |
Rome |
Brussels |
From/To |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
Amsterdam |
1 |
0 |
2166 |
577 |
622 |
712 |
1889 |
339 |
319 |
1462 |
430 |
1297 |
175 |
Athens |
2 |
2166 |
0 |
1806 |
2132 |
2817 |
2899 |
2377 |
1905 |
2313 |
2100 |
1053 |
2092 |
Berlin |
3 |
577 |
1806 |
0 |
348 |
1273 |
2345 |
912 |
598 |
1836 |
878 |
1184 |
653 |
Copenhagen |
4 |
622 |
2132 |
348 |
0 |
1203 |
2505 |
942 |
797 |
2046 |
1027 |
1527 |
768 |
Dublin |
5 |
712 |
2817 |
1273 |
1203 |
0 |
1656 |
440 |
914 |
1452 |
743 |
1849 |
732 |
Lisbon |
6 |
1889 |
2899 |
2345 |
2505 |
1656 |
0 |
1616 |
1747 |
600 |
1482 |
1907 |
1738 |
London |
7 |
339 |
2377 |
912 |
942 |
440 |
1616 |
0 |
475 |
1259 |
331 |
1419 |
300 |
Luxembourg |
8 |
319 |
1905 |
598 |
797 |
914 |
1747 |
475 |
0 |
1254 |
293 |
987 |
190 |
Madrid |
9 |
1462 |
2313 |
1836 |
2046 |
1452 |
600 |
1259 |
1254 |
0 |
1033 |
1308 |
1293 |
Paris |
10 |
430 |
2100 |
878 |
1027 |
743 |
1482 |
331 |
293 |
1033 |
0 |
1108 |
262 |
Rome |
11 |
1297 |
1053 |
1184 |
1527 |
1849 |
1907 |
1419 |
987 |
1308 |
1108 |
0 |
1173 |
Brussels |
12 |
175 |
2092 |
653 |
768 |
732 |
1738 |
300 |
190 |
1293 |
262 |
1173 |
0 |
Order |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
City |
6 |
9 |
5 |
7 |
10 |
8 |
12 |
1 |
4 |
3 |
11 |
2 |
Distaance |
600 |
1452 |
440 |
331 |
293 |
190 |
175 |
622 |
348 |
1184 |
1053 |
|
Minimum-distance = 6688
If
the sequence is Athens, Rome, Madrid, Lisbon,
Dublin, London, Paris, Luxembourg, Berlin, Copenhagen, Amsterdan, and Brussels,
the solution will have same
objective value as answer b.
Because
the route is same, the distance is same.
In
this sheet, I calculate the
length of the minimum-distance tour. If the trip start from Lisbon, the length of the minimum-distance tour
is shortest. Therefore, I should tell my decision-maker these solutions are not
truely optimal.
If the trip don't need to go back to
Brussels, the order will change and
reduce distance 1398. The solution of answer b is fewer than answer a..
Reference:[1] Powell, Stephen G. Management Science: The Art Of Modeling With Spreadsheets, 4Th Edition. 1st ed. John Wiley & Sons, 2013. Print.
[2] "Solving Travelling Salesman Problem(TSP) using Excel Solver", YouTube, 2017. [Online]. Available: https://www.youtube.com/watch?v=-E3rSoClgMI. [Accessed: 08- Jun- 2017].