Travelling salesman: bounds and practical problems Problem set A Answers

1. (a) LB = 16
2. (b) LB = 19
3. (c) The lower bound 19, from deleting E: it is the larger.

1. (a) BD = 18 (route B-A-D); BE = 23 (route B-A-E); CE = 18 (route C-A-E)
2. (b) UB = 59
3. (c) C-A-D-E-A-B-C, length 59; visited more than once: A

UB = 62: D-C-B-F-A-E-D

1. (a) LB = 17
2. (b) The route is optimal: its length 17 equals the lower bound, so no tour is shorter.

1. (a) AC = 7 (route A-D-C); AE = 8 (route A-F-E); BD = 11 (route B-C-D); BE = 18 (route B-A-F-E); BF = 12 (route B-A-F); CE = 12 (route C-D-F-E); CF = 6 (route C-D-F); DE = 9 (route D-F-E)
2. (b) UB = 42
3. (c) A-F-D-C-B-A-F-E-F-A, length 42; visited more than once: A, F
4. (d) LB = 32; the shortest route is between 32 and 42 km

1. (a) LB = 62
2. (b) LB = 59
3. (c) UB = 66; between 62 and 66; no, the bounds are not equal, so the tour is not shown to be optimal.