Courier Route With Time Windows
A courier starts at the depot at 08:30 and must visit three customers, P, Q and R. Service at each customer takes 10 minutes. Travel times are: depot to P 20 minutes, depot to Q 35 minutes, depot to R 25 minutes, P to Q 15 minutes, P to R 30 minutes, Q to R 20 minutes. Delivery windows are: P 09:00–10:00, Q 10:30–12:00, R 09:30–11:00. A customer must be arrived at within the window, and service may run past the closing time. The courier may wait at a customer if arriving early. A colleague claims that, because R's window is the tightest, R should always be visited first.
1. Give a feasible visiting order with arrival times.
Read the worked answer
Depot → P → R → Q works. Leave 08:30, arrive P 08:50. P opens at 09:00, so wait 10 minutes and serve 09:00–09:10. Travel P→R 30 minutes, arriving R 09:40, inside 09:30–11:00; serve to 09:50. Travel R→Q 20 minutes, arriving Q 10:10; Q opens at 10:30, so wait and serve 10:30–10:40. All three windows are met. P must come before R because R→P takes 30 minutes and would land after P's 10:00 close, so the colleague's 'tightest window first' rule is wrong.
2. What is the latest depot departure that still completes all three deliveries? Show the binding constraint.
Read the worked answer
P must be first, because any route reaching P after serving R or Q misses P's 10:00 close. With P first, the latest arrival at P is 10:00, and depot→P takes 20 minutes, so the latest departure is 09:40. Check the knock-on: P is served 10:00–10:10, R is reached at 10:40 (closes 11:00), and R→Q arrives at 11:10 (Q closes 12:00). So 09:40 is feasible and any later departure breaches P. P's closing time, not R's, is the binding constraint.
3. Suppose R's window changes to 09:30–09:35. Does any order still work? Explain.
Read the worked answer
No order works. With P first, service at P ends at 09:10 and R is reached at 09:40, five minutes after R's window closes, so even with service allowed to overrun, arrival fails. With R first: leave 08:30, arrive R 08:55, wait until 09:30, serve 09:30–09:40, then R→P takes 30 minutes and arrives 10:10, after P's 10:00 close. Putting Q first is worse because Q opens at 10:30, making P unreachable. The tightened R window therefore makes the round infeasible, not merely slower.