Meals-on-Wheels is a charity service that prepares meals in its central facility for delivery to people who qualify for the service. Ideally, all meals should be delivered within 20 min from the time they leave the kitchen. This means that the return time from the last-meal location to the kitchen is not a factor in determining the sequence of deliveries.

The charity is in the process of determining the delivery route. The first pilot schedule includes seven recipients with the following travel times, ‘tij ‘ (row 1 and column 1 represent the kitchen).

‘tij ‘ = ®

0 10 12 5 17 9 13 7 10 0 9 20 8 11 3 5 12 9 0 14 4 10 1 16 5 20 14 0 20 5 28 10 17 8 4 20 0 21 4 9 9 11 10 5 21 0 2 3 13 3 1 28 4 2 0 2 7 5 16 10 9 3 2 0



(a) Compare the lower bounds on the optimum tour length using both the assignment model and linear programming. Is the assignment model solution optimum for the TSP?

(b) Based on the information in (a), is it possible to deliver the eight meals within the 20-min time window?