Georgia Tech × Grubhub’s 70-Page Landmark Paper: Defining the Meal Delivery Routing Problem (MDRP)
In academia, some papers don’t solve problems — they define them. This 70-page paper by Georgia Tech’s Alan Erera, Damian Reyes, and Martin Savelsbergh, co-authored with Grubhub’s decision engineering team (Sagar Sahasrabudhe and Ryan O’Neil), is precisely such a work. It formally introduces the Meal Delivery Routing Problem (MDRP) — elevating meal delivery from a vague engineering practice into a rigorously defined operations research object.
Before this paper, optimization research for meal delivery was scattered across Vehicle Routing Problem (VRP), Pickup and Delivery Problem (PDP), and Dynamic Fleet Management literature, lacking a unified problem definition and standardized experimental methodology. MDRP established the common language and evaluation standards for the entire field.
Why Meal Delivery Is “The Ultimate Challenge in Last Mile Logistics”
The paper opens with a bold assertion: meal delivery is the ultimate challenge in last mile logistics. This isn’t hyperbole but a precise analysis of meal delivery’s unique characteristics:
Extreme time pressure. Traditional parcel delivery windows are “today” or “within hours.” Meal delivery expectations are 30-60 minutes, ideally less. From food completion to delivery, couriers may have only 15-20 minutes — virtually no room for consolidation optimization. Any algorithm must compute in seconds.
Extreme dynamism. Parcel routes can be pre-planned (packages wait in warehouses). Meal orders arrive in real-time. During Grubhub’s peak hours, dozens of new orders arrive per minute, each potentially changing the optimal global assignment. The system must decide amid continuous change rather than waiting for complete information.
Fundamental supply-side uncertainty. Meal couriers aren’t employees but independent contractors (gig workers). They have autonomous decision rights — choosing when to go online, which orders to accept or reject, even going offline mid-shift. This fundamentally differs from traditional VRP’s assumption of “fleet fully obeys dispatch.” Platforms can only indirectly manage capacity through economic incentives, not direct command.
Extreme spatiotemporal demand fluctuation. Meal demand exhibits extreme peak-valley differences temporally (lunch peak can be 10x the 3 PM lull) and concentrates spatially in commercial districts rather than distributing uniformly. This “pulse-like” demand pattern poses unique capacity scheduling challenges.
Formalizing MDRP: From Chaos to Order
The paper’s most important contribution is abstracting meal delivery’s complex reality into a computable mathematical model. MDRP’s core elements include:
- Orders: Pickup location, delivery location, order time, estimated preparation time, promised delivery time
- Couriers: Current location, online periods, carrying capacity, travel speed
- Two-stage decisions: (1) Dispatching — assigning orders to couriers; (2) Routing — determining pickup and delivery sequences
- Dynamic arrivals: Orders continuously arrive over time with incomplete information
- Multiple objectives: Minimize delivery time, maximize service rate, control costs
Behind this seemingly simple definition lies enormous computational complexity. Even with just 20 orders and 5 couriers, possible assignment combinations are astronomical. Add dynamic arrivals and time constraints, and the online version becomes orders of magnitude harder than offline.
Algorithm Framework: Two-Stage Commitment and Priority Scheduling
The paper’s algorithmic contribution is equally substantial. The researchers propose a “Two-Stage Commitment” framework, a major improvement over traditional single-stage approaches:
Single-stage commitment: Orders are immediately assigned to couriers with routes confirmed upon arrival. Simple but fundamentally flawed — premature assignment lock-in prevents optimization using subsequently arriving information.
Two-stage commitment: Stage one “soft-assigns” orders to couriers (adjustable); stage two “hard-confirms” routes only when couriers are about to depart. This delayed confirmation mechanism creates windows for subsequent order bundling and re-optimization.
Extensive computational experiments demonstrate: two-stage commitment significantly outperforms single-stage in virtually all scenarios. The advantage is most pronounced in low-dynamism (slower order arrival), low-pickup-flexibility (fixed restaurant preparation times), and high order-to-capacity ratio (insufficient couriers) scenarios — where single-stage commitment leads to more undelivered orders and longer delivery times.
Additionally, the paper introduces a priority scheduling scheme: instead of solving all orders’ optimal matching in one pass per optimization cycle, three rounds are executed — first handling urgent near-timeout orders, then regular orders, then newly arrived orders. This prioritization is critical during courier shortages, significantly reducing undelivered order rates.
Capacity Management: Closing the Loop from Algorithms to Shift Scheduling
The paper addresses not only real-time dispatching (online decisions) but also capacity pre-planning (offline decisions) — how to schedule courier shifts in advance to match expected demand. Academically, this is a two-stage stochastic programming problem; industrially, it’s a core operational challenge:
Over-scheduling: Couriers idle, platform bears unnecessary labor costs. Under-scheduling: Peak-hour courier shortage, mass timeouts, user experience collapse. The optimum aligns the capacity curve as closely as possible with the demand curve — but demand itself is uncertain.
The paper proposes demand-forecast-based shift scheduling optimization and demonstrates capacity level’s nonlinear impact on system performance: below a critical threshold, small capacity additions yield massive service improvements; above it, marginal returns diminish sharply. Finding this “optimal capacity waterline” is key to platform operations.
Establishing a Standardized Experimental Framework
The paper’s hidden contribution is establishing standardized experimental methodology for MDRP research. The authors designed a parameterized instance generator controlling:
- Dynamism: Order arrival concentration/dispersion
- Urgency: Time window from order placement to expected delivery
- Geography: Spatial distribution of restaurants and delivery locations
- Scale: Number of orders and couriers
- Supply-demand ratio: Courier capacity relative to order volume
This framework enables subsequent researchers to compare algorithms under standardized conditions — essential infrastructure for a maturing research field. After MDRP, numerous follow-up studies (including work from Meituan, Tsinghua, and others covered in our earlier articles) built upon this foundation.
Strategic Implications for the Logistics Industry
1. “Delayed commitment” is a universal principle for dynamic logistics. Two-stage commitment’s core idea — delay irreversible decisions as long as possible, preserving adjustment room for incoming information — applies beyond meal delivery. Parcel sorting route confirmation, ride-hailing carpooling matches, warehouse picking batch formation all benefit from similar delayed commitment strategies. In dynamic environments with incomplete information, “one step slower” often outperforms “one step faster.”
2. The independent contractor model redefines optimization boundaries. When the “fleet” isn’t under direct control, all traditional VRP assumptions need revision. The platform’s optimization target includes not just routes and assignments but incentive design — how bonuses, surge pricing, and completion-rate rewards guide courier behavior toward system optimum. Incentive design is fundamentally a mechanism design problem, equally important as algorithmic optimization.
3. Capacity planning deserves more investment than real-time algorithms. Experiments clearly show: with severe courier shortage, no real-time algorithm can rescue service quality. Capacity “quantity” determines the system ceiling; algorithm “quality” determines how close you get to that ceiling. For meal delivery and instant logistics companies, capacity forecasting and shift scheduling systems should take higher investment priority than dispatch algorithms.
4. Problem definition often outvalues problem solving. MDRP’s greatest contribution isn’t any specific algorithm but a clear problem definition and evaluation framework. For internal operations research teams, investing time to precisely define “what problem are we actually solving” — including objective functions, constraints, and information structure — often delivers more value than rushing to write optimization code.
Source: Reyes, D., Erera, A., Savelsbergh, M., Sahasrabudhe, S., & O’Neil, R. (2018). “The Meal Delivery Routing Problem.” Georgia Institute of Technology & Grubhub. | H. Milton Stewart School of Industrial Engineering, Georgia Tech | Grubhub Decision Engineering
