Urban food delivery service optimisation with coordinated delivery riders and drones
Mingzhi Lyu, Wei Liu, Qingying He, Lingxiao Wu
Abstract
Online food delivery platforms like Meituan and Foodpanda are paying increasing attention to integrating drone technology into existing delivery service networks to enhance the efficiency and flexibility of their operations. However, existing drone-assisted delivery models are primarily designed for parcel delivery, which cannot be directly used for the food delivery market with coordinated delivery riders and drones. To address this challenge, we investigate a one-to-one Pickup and Delivery Problem with multi-riders and multi-drones (PDP-mR-mD) for the urban food delivery market. The studied problem involves coordinated riders and drones with package transhipment and synchronisation permitted at docking hubs. Pickup and delivery of a food package can be fulfilled by either a rider or a drone independently or in cooperation while considering constraints of time window, payload capacity, battery endurance, and location accessibility. In particular, an arc-based mixed integer linear programming model is developed for the studied problem. An exact branch-and-price algorithm is developed by decomposing the arc-based model into a path-based master problem with two resource-constrained pricing sub-problems, where synchronised package transhipment at docking hubs is established through the branching scheme. An Adaptive Large Neighbourhood Search (ALNS) algorithm has also been designed to solve large-scale instances. The efficiency and effectiveness of the proposed solution approaches and the potential benefits of coordinated delivery systems are verified and illustrated through small-scale instances and large-scale case studies.