Design an On-Demand Shuttle Service

Problem Statement: On-Demand Shuttle

An on-demand shuttle service pools many riders into shared vehicles whose routes are computed live as requests arrive. It sits between two familiar systems and is harder than either: a fixed bus runs a static route on a timetable, and a ride-hail sends one car to one rider, but a shuttle must continuously decide which riders share which vehicle and in what order it visits their stops.

The core job is the dynamic dial-a-ride problem: a rider asks to go from A to B; the system finds an in-service shuttle whose current route can absorb a stop at A and a stop at B without breaking the promises already made to the riders on board — their detour stays within budget, the vehicle never exceeds capacity, and everyone's pickup and drop-off time windows hold. If no vehicle can take the rider within budget, we add capacity to the decision (a different shuttle, a short wait) rather than degrade an existing trip.

Two levers make pooling efficient. Virtual stops: instead of door-to-door, the rider walks a short distance (say ≤ 200 m) to a corner that many riders can share, which straightens routes and cuts detours dramatically. Batch matching: rather than assigning each request the instant it arrives (greedy, locally optimal), we collect requests over a short window (~30 s) and match the batch together, which finds better pairings.

The scale that matters is not raw QPS but matching quality under a latency budget. A zone runs ~300 shuttles serving ~80,000 requests/day; each match must evaluate candidate insertions across many live routes in a few seconds. Get matching wrong and either vehicles run empty (no pooling, no economics) or riders suffer wild detours (no retention). The whole design is about computing good shared routes, fast, as the world changes.