4 Joe, a courier, is required to deliver parcels to six different locations, \(A , B , C , D , E\) and \(F\).
Joe needs to start and finish his journey at the depot.
The distances, in miles, between the depot and the six different locations are shown in the table below.
| Depot | \(\boldsymbol { A }\) | \(\boldsymbol { B }\) | C | \(\boldsymbol { D }\) | \(E\) | \(F\) |
| Depot | - | 18 | 17 | 15 | 16 | 19 | 30 |
| \(\boldsymbol { A }\) | 18 | - | 29 | 20 | 25 | 35 | 21 |
| B | 17 | 29 | - | 26 | 30 | 16 | 14 |
| C | 15 | 20 | 26 | - | 28 | 31 | 27 |
| D | 16 | 25 | 30 | 28 | - | 34 | 24 |
| E | 19 | 35 | 16 | 31 | 34 | - | 28 |
| F | 30 | 21 | 14 | 27 | 24 | 28 | - |
The minimum total distance that Joe can travel in order to make all six deliveries, starting and finishing at the depot, is \(L\) miles.
4
- Using the nearest neighbour algorithm starting from the depot, find an upper bound for \(L\).
4 - By deleting the depot, find a lower bound for \(L\).
4 - Joe starts from the depot, delivers parcels to all six different locations and arrives back at the depot, covering 134 miles in the process.
Joe claims that this is the minimum total distance that is possible for the journey. Comment on Joe's claim.