Question 9
TSP
The distance matrix for 6 cities are provided below. For each city the distances to other cities are listed in ascending order. For example, the distance from A to D is 38, and from A to E is 46, and so on.
| A | D:38 | E:46 | F:64 | B:66 | C:68 |
|---|---|---|---|---|---|
| B | E:40 | F:42 | C:58 | A:66 | D:74 |
| C | F:18 | E:26 | D:42 | B:58 | A:68 |
| D | E:36 | A:38 | C:42 | F:48 | B:74 |
| E | F:18 | C:26 | D:36 | B:40 | A:46 |
| F | C:18 | E:18 | B:42 | D:48 | A:64 |
Solve the sub-questions using the TSP Branch-and-Bound algorithm.
Attention: Infer as much as possible (and as early as possible) about the permanent segments in the partial solutions. A segment is a two-way edge between two cities.
What is the lower bound on the cost of the tours (S0) as per the TSP BnB algorithm discussed in class?
Enter a natural number.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 17