Optimizing autonomous multimodal last-mile delivery systems with time windows: Analyzing trade-offs between drones, robots, and trucks
研究卡车、无人机和机器人协同配送的最后一英里系统，提出混合整数线性规划模型和三阶段元启发式算法，在阿姆斯特丹实例中验证了多模式组合优于单一模式，并分析了不同成本场景下的配送效率。
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.