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 C is 42, and from A to E is 48, and so on.
| A | C: 42 | E: 48 | D: 56 | F: 66 | B: 82 |
|---|---|---|---|---|---|
| B | F: 36 | C: 42 | E: 56 | D: 72 | A: 82 |
| C | D: 40 | A: 42 | B: 42 | E: 44 | F: 44 |
| D | C: 40 | A: 56 | B: 72 | E: 82 | F: 84 |
| E | F: 26 | C: 44 | A: 48 | B: 56 | D: 82 |
| F | E: 26 | B: 36 | C: 44 | A: 66 | D: 84 |
Solve the given 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