# Batching and Matching for Food Delivery in Dynamic Road Networks

arXiv: https://arxiv.org/abs/2008.12905 · HTML: https://mlsanity.com/paper/2008.12905/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Aug 2020.

## Built on by (most cited first, 3 of 3)

- [FRIGATE: Frugal Spatio-temporal Forecasting on Road Networks](https://mlsanity.com/paper/2306.08277/) (2023)
- [Gigs with Guarantees: Achieving Fair Wage for Food Delivery Workers](https://mlsanity.com/paper/2205.03530/) (2022)
- [Harvesting Efficient On-Demand Order Pooling from Skilled Couriers: Enhancing Graph Representation Learning for Refining Real-time Many-to-One Assignments](https://mlsanity.com/paper/2406.14635/) (2024)

## Abstract (arXiv)

Given a stream of food orders and available delivery vehicles, how should orders be assigned to vehicles so that 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, and (3) adapting to dynamic positions of delivery vehicles. 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 clustering problem and anticipating dynamic positions of vehicles through angular distance. Extensive experiments on food-delivery data from large metropolitan cities establish that FoodMatch is substantially better than baseline strategies on a number of metrics, while being efficient enough to handle real-world workloads.