Abstract
Food delivery, today, is a multi-billion dollar industry. Minimizing food delivery time is a key contributor towards building positive customer experiences. More precisely, given a stream of food orders and available delivery vehicles, how should orders be assigned to vehicles so the delivery time is minimized? Several decisions have to be made: (1) assignment of orders to vehicles, (2) grouping orders into batches to cope with limited vehicle availability, (3) adapting to dynamic positions of delivery vehicles, and (4) ensuring scalability to the demands of real-world workloads. We show that the minimization problem is not only NP-hard but inapproximable in polynomial time. To mitigate this computational bottleneck, we develop an algorithm called FoodMatch, which maps the vehicle assignment problem to that of minimum weight perfect matching on a bipartite graph. To further reduce the quadratic construction cost of the bipartite graph, we deploy best-first search to only compute a subgraph that is highly likely to contain the minimum matching. The solution quality is further enhanced by reducing batching to a graph batching problem and anticipating dynamic positions of vehicles through angular distance. We perform extensive experiments on real food-delivery data from large metropolitan cities. Our results establish that FoodMatch imparts substantial improvements over baseline strategies across a host of metrics such as food delivery time, waiting time at restaurants, and orders delivered per kilometer. Furthermore, FoodMatch is efficient enough to handle real-world workloads.
Introduction
The food delivery process is a race against the clock involving four critical steps: assignment, the "first mile" (driving to the restaurant), food preparation, and the "last mile" (delivery to the customer). Unlike ride-sharing, where the goal is simply to get the nearest car to a person, food delivery is complicated by preparation time. If a driver arrives too early, they waste time waiting; if they arrive too late, the food gets cold.
The authors tackle the "Food Delivery Problem" (FDP): how to assign a stream of incoming orders to a fleet of moving vehicles to minimize the total delivery time. This is computationally brutal—the authors prove it is not only NP-hard but also inapproximable in polynomial time. Existing solutions often rely on oversimplified assumptions, like using straight-line distance instead of actual road networks, or ignoring the fact that vehicles are constantly moving while assignments are being calculated.
The FoodMatch Framework
The authors break the problem down into a pipeline called FOODMATCH, which optimizes assignments through several key innovations:
- Iterative Batching: Instead of looking at orders individually, the algorithm groups them into batches using an "Order Graph." It uses iterative clustering to merge orders that can be delivered together efficiently, stopping only when the "marginal cost" of adding more orders to a batch becomes too high.
- Bipartite Matching (FOODGRAPH): The problem is framed as finding a minimum weight perfect matching between batches of orders and available vehicles.
- Best-First Sparsification: Constructing a full bipartite graph for thousands of orders and drivers is too slow (quadratic cost). The authors use a best-first search to only compute edges for the most likely candidates, drastically speeding up computation.
- Angular Distance: To handle the "moving target" problem, they introduce a "vehicle-sensitive edge weight." This uses the bearing (direction) of a vehicle. If a vehicle is already moving toward a restaurant, its "angular distance" is low, making it a better candidate than a vehicle that is physically closer but heading in the opposite direction.
- Reshuffling: The system allows orders to be re-assigned to different drivers as long as the original driver hasn't picked up the food yet, allowing the system to adapt to new, better opportunities as they arrive.
Experimental Evaluation
The study utilizes two primary sources: a publicly available Grubhub Dataset and a massive, newly released Swiggy Dataset containing 6 days of data from three large Indian cities. This includes road network data from OpenStreetMap and map-matched GPS trajectories of delivery riders.
Key Results
- 30% Reduction in Extra Delivery Time: Compared to the standard greedy baseline, FOODMATCH significantly reduced the time customers waited beyond the theoretical minimum.
- Efficiency Gains: The algorithm increased "Orders per Kilometer" (O/Km) by 20% and reduced driver waiting time at restaurants by approximately 40%.
- Scalability: During peak lunch and dinner rushes, FOODMATCH maintained a 0% "overflow" rate, meaning it always finished calculations before the next batch of orders arrived.
Conclusion
FOODMATCH demonstrates that the "aha moment" in food delivery is realizing that food preparation time can happen in parallel with the driver's journey. The goal isn't to find the closest driver, but the driver who will arrive exactly when the food is ready. By accounting for vehicle directionality through angular distance and pruning the search space via sparsification, the framework achieves the efficiency needed for real-world metropolitan workloads. Future work may explore treating vehicle capacity and delivery time limits as dynamic variables to further enhance performance.
Summary updated