  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.
