Question 21
TSP
The distance matrix for 5 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | - | 42 | 45 | 80 | 64 |
| B | 42 | - | 10 | 23 | 21 |
| C | 45 | 10 | - | 35 | 24 |
| D | 80 | 23 | 35 | - | 86 |
| E | 64 | 21 | 24 | 86 | - |
| BC | 10 |
|---|---|
| BE | 21 |
| BD | 23 |
| CE | 24 |
| CD | 35 |
| AB | 42 |
|---|---|
| AC | 45 |
| AE | 64 |
| AD | 80 |
| DE | 86 |
Based on the above data, answer the given subquestions.
Construct the savings tour using D as the base city. The savings for the pairs AB, AC, BC and BE, respectively, are 61, 70, 48 and 88. Compute the savings for the remaining pairs of cities and then compute the savings tour. Enter the path representation of the savings tour starting from city D. Enter a comma separated list of city names.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: D,X,Y,Z