Batching and Matching for Food Delivery in Dynamic Road Networks

Given a stream of food orders and available delivery vehicles, how should orders be assigned to vehicles so that the delivery time is minimized? For a successful assignment strategy, two key decisions need to be made: (1) assignment of orders to vehicles, (2) grouping orders into batches to cope with limited vehicle availability. 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. The solution quality is further enhanced by reducing batching to a graph clustering problem. Extensive experiments on food-delivery data from large metropolitan cities establish that FOODMATCH is substantially better than baseline strategies on a number of metrics.