Crowdsourced on-demand food delivery: An order batching and assignment algorithm

摘要

Since the early 2010s, the meal delivery business went through a veritable revolution due to online food delivery platforms. By allowing customers to quickly order from a wide range of restaurants and outsourcing currently available couriers using their vehicles (crowdsourcing), this typology of service dynamically bridges demand and supply. The main goal of online food delivery platforms consists of matching couriers to meal orders within short time intervals to provide an efficient, reliable, and sustainable service. A way to increase efficiency consists of consolidating orders into batches, such that the same courier can serve several orders in multiple pickup and drop-off routes. Since such an assignment-batching problem becomes computationally prohibitively costly in real-world scenarios characterized by a large number of customer orders as well as uncertain demand and supply, heuristic solution methods come into play. This study proposes an order batching and assignment algorithm that leverages a graph-based approach after decomposing the original problem into more tractable sub-problems employing clustering. The solution is improved by local search moves and re-optimization procedures and integrated with advanced policies to improve solutions over time. An 'Insertion policy' aimed at increasing batch size, and a 'Swap policy' aimed at identifying more efficient assignments, are implemented and compared to a 'Myopic policy' that does not involve any re-optimization over time. An agent-based simulation framework is developed to implement dynamic policies where couriers' operations and movements are realistically reproduced. The performance of the developed solution approach is tested through experiments based on a real-world case study. Results show that the algorithm allows for high-quality solutions in several configurations characterized by different demand and supply patterns (e.g., density levels, couriers availability) and problem sizes.In particular, the two advanced policies investigated considerably improve the solutions.