Unit 6 — windowed global matching (DISCO), pooling, and pricing as control
Advanced Marketplace
Each previous unit optimized one decision in isolation: the fastest route, the nearest drivers, a single dispatch, a zone's surge. Run them all greedily and at launch scale it works. At peak, in a dense city, the seams show — drivers crisscross to pickups, prices oscillate between neighboring zones, and overlapping trips ride with empty seats.
This capstone asks the marketplace question Uber answers with a system called DISCO (Dispatch Optimization): can coordinating decisions across many riders and drivers at once beat the sum of locally optimal choices? You'll implement the core of it — global matching and pooling — and unlock each step with a deterministic checkpoint.
Sub-unit 1 of 16
The problem: coordinate, don't just react
Maximize system-wide outcomes — completed trips, low wait times, high utilization — by coordinating matching and pricing across simultaneous riders and drivers, instead of deciding each request in isolation.
Functional
- Match many riders to many drivers jointly within a time window.
- Pool compatible trips into a shared vehicle within detour bounds.
- Steer supply with pricing as a feedback control loop.
- Compose cleanly with routing, retrieval, dispatch, and pricing (Units 1–5).
Non-functional
- Bounded batching delay (a few seconds) — still feels instant.
- Higher utilization and throughput than greedy at peak.
- Stable under feedback — pricing and matching must not oscillate.
- Tractable at city scale (heuristics, not exact NP-hard solves).
Constraints
- Optimal pooling (VRPTW) is NP-hard.
- Decisions interact: matching affects supply affects price affects demand.
- Every added second of batching is rider-perceptible latency.
Uber's own framing on its marketplace: "Initially, we matched users by asking, who's closest? But we learned that closest doesn't always mean quickest." Traffic, overpasses, and rivers make the nearest car the wrong car. The fix is batched matching — wait a few seconds, then pair a whole batch to minimize everyone's collective wait, not just the closest pair. Uber says this saves riders 10 years of waiting every day.