The two-tier multi-depot vehicle routing problem with robot stations and time windows

Abstract

The deployment of sidewalk robots or automated guided vehicles (AGVs) offers significant potential to reduce traffic congestion and operational costs in last-mile logistics. Delivery systems using a two-layer structure, with trucks in the first layer and sidewalk robots at stations in the second, are modeled as Two-Tier Vehicle Routing Problems with Robot Stations (2T-VRP-RS). In this paper, we extend the 2T-VRP-RS to introduce the Two-Tier Multi-Depot Vehicle Routing Problem with Robot Stations and Time Windows (2T-MDVRP-RS-TW). We propose a Mixed-Integer Linear Programming (MILP) formulation and a Multi-Start Iterated Local Search metaheuristic with Crossover and Repair (MS-ILS-CR) operators. The MS-ILS-CR combines three strategies: a Multi-Start mechanism, a Crossover operator, and a Repair operator adapted from Variable Neighborhood Search, Genetic Algorithms, and Adaptive Large Neighborhood Search, respectively. We introduce new instance sets to study the 2T-MDVRP-RS-TW. Results showed that the MILP formulation is competitive for small instances of 10 customers. However, the metaheuristic consistently achieved better solution quality and lower computational times, with improvements of over 20% in the average objective values for instances of up to 30 customers. The MS-ILS-CR outperformed similar metaheuristic methods, improving its initial solutions by 66%. Furthermore, a sensitivity analysis showed a limited impact of time-window variations on the objective values. Nevertheless, a significant sensitivity was found to the depot configurations. Hence, increasing the number of depots from 1 to 3 improved the average objective values by 56%. Additionally, the MS-ILS-CR performance was further enhanced with more crossover iterations, but at the cost of higher computational times.