Optimizing autonomous multimodal last-mile delivery systems with time windows: Analyzing trade-offs between drones, robots, and trucks

Abstract

• New extension of the Drone-Assisted VRP with Robot Stations (VRPD-RS). • Includes a Three-Phased Granular Multi-Start Iterated Local Search metaheuristic. • Comparative insights on delivery systems using makespan and operational cost objectives. • Insights provided on the advantages of multimodality. • New benchmark instance set designed based on Amsterdam. This paper studies multi-modal last-mile delivery systems. More specifically, it introduces the Drone-Assisted Vehicle Routing Problem with Robot Stations and Time Windows (VRPD-RS-TW) to face exigent delivery schedules in last-mile logistics. The VRPD-RS-TW applies to highly populated city centers, where due to infrastructural issues, customers might be hard to reach by conventional trucks. This problem is characterized by utilizing three transportation modes: trucks, drones, and robots collaborating to deliver parcels and meet time window requirements. To solve this problem, we develop a Mixed Integer Linear Programming (MILP) formulation, valid inequalities to strengthen the linear relaxation, and a Three-Phased Granular Multi-Start Iterated Local Search (3P-GMS-ILS) metaheuristic algorithm. A computational study on instances of Amsterdam (the Netherlands) demonstrates that the 3P-GMS-ILS outperforms the MILP formulation and state-of-the-art metaheuristic approaches in terms of both objective function values and computational times. Furthermore, we provide insights into the effectiveness of the VRPD-RS-TW, showing that, under various cost scenarios, the combination of trucks, drones, and robots outperforms scenarios with fewer transportation modes. Across the studied cost scenarios, the VRPD-RS-TW simultaneously coordinates a higher volume of delivery operations, with 48.75 % performed by drones and robots, resulting in better objective function values than the related transportation systems. In scenarios where truck routing costs are lower than those of drones and robots, the VRPD-RS-TW still achieves better objective function values compared to the related transportation systems, although the share of drone and robot deliveries drops to 14.78 %. This shows that adding drones is not necessarily beneficial when trucks carry drones, as trucks should wait for drones, which might result in higher costs related to drone routing and drivers’ wages.