Dynamic courier routing for a food delivery service

摘要

Services like Grubhub and UberEats have revolutionized the way that diners can find and order from restaurants. The standard business model for such services, however, allows diners to order from only one restaurant at a time. Inspired by a food delivery service in the southeastern United States, this paper proposes the framework for a more flexible business model in which multiple restaurants may be included in a single customer's order. We formally define this new problem, the virtual food court delivery problem (VFCDP), and provide a mixed integer linear programming formulation. For implementation in a dynamic setting, an auction-based heuristic has also been developed. This so-called "proactive" heuristic anticipates future system states, and seeks solutions which are effective at both serving customers in the present and preparing couriers to handle future demand. This is facilitated through the calculation of metrics describing equity and dispersion. Furthermore, this heuristic is capable of handling both split and non-split delivery policies. An extensive numerical study is conducted in a simulation environment to examine characteristics of this new business model. This study reveals that the proactive heuristic is effective at improving system performance (over an entirely myopic heuristic) according to several customer experience-based metrics (e.g. freshness, earliness, etc.). Furthermore, a non-split delivery policy is shown to deliver all of a customer's items no later than the last item would have arrived in the split delivery case, on average. It does this while also avoiding any waiting time for the customer between deliveries, and while reducing the number of miles traveled by a courier fleet throughout the day. Additional managerial policies, such as the type of delivery window offered to customers, are also discussed. (C) 2019 Elsevier Ltd. All rights reserved.