Meal Delivery Routing Problem with a Hybrid Fleet of Riders and Autonomous Vehicles under Dynamic Environment

Autonomous vehicles (AVs) are considered as next-generation delivery vehicles for logistics systems. This study proposes a dynamic Meal Delivery Routing Problem with a hybrid Rider-AV fleet (MDRP-RA). The hybrid fleet consists of riders and AVs. Each order must be fulfilled by an AV or a rider. Some orders can be delivered by riders or AVs only, while others can be delivered by both. The food of each order is one of three product segments (regular, frozen, and hot food), and each segment has a particular temperature need. An AV has multiple compartments, each of which needs to be cooled (heated) if it contains frozen (hot) food. Thus, AVs can deliver all kinds of food, while riders can deliver regular food only. A mathematical programming model is established for MDRP-RA, with the objective of minimizing the total cost, including the vehicle fixed cost, delivery fee to riders, energy consumption cost, and penalty cost for delay. An Adaptive Large Neighborhood Search based Approach (ALNS-A) is proposed to solve MDRP-RA. It involves a local search procedure with removal and insertion operators, where five operators are specifically devised for the problem. Experiments show that it can effectively solve MDRP-RA and outperforms comparative approaches.