Nearest rider for every order? Everyone loses.

transcript

Three orders. Three free riders. Give each order its nearest rider. Sounds perfect. It's the wrong answer. Here's why.

Order one comes due first. It grabs Rider A, the closest. But Rider A was the only rider near order two. So order two gets a rider four kilometres away. Locally best. Globally worse.

So don't decide one order at a time. Run a round every 20 seconds, per city. Take every due order. Every rider free or finishing soon, within about 3 kilometres. Score every pair. Then solve the whole round at once. Offers go out. Each rider gets 20 seconds to accept.

But here's the clever part. How do you score a pair? In minutes. Minutes the rider stands idle at the counter. Minutes the food waits on the pass. Those count twice. And minutes late against the promise.

Sounds slow? In the largest city, about 10,000 pairs a round. Scored in about 2 seconds, on one model. So it isn't slower. Greedy is just worse.

And if a rider declines, or doesn't answer in 20 seconds? The order joins the next round, with higher priority.

Locally best choices are globally worse. A few seconds of delay buys a much better match.

Full breakdown in the lecture.