The two-echelon truck-unmanned ground vehicle routing problem with time-dependent travel times

With the rapid expansion of e-commerce and the resulting surge in parcel delivery demands, the integration of trucks and unmanned ground vehicles (UGVs) in last-mile package delivery provides a more efficient and sustainable venue for a logistics system. However, coordinating trucks and UGVs in the context of fluctuating traffic conditions, especially with varying travel times, continues to be a significant challenge. This study addresses this issue by proposing and solving a two-echelon truck-UGV routing problem with time-dependent travel times. The first echelon encompasses transporting goods from the warehouse to satellites using trucks, considering time-dependent travel times. The second echelon involves distributing goods from satellites to customers using UGVs. Initially, a continuous-time time-dependent travel model is proposed based on the fluid queueing model to estimate vehicle travel times under varying traffic conditions. We then develop a multiobjective mixed integer linear programming model that aims to minimize total operating costs and the number of UGVs used. Subsequently, a novel hybrid algorithm combining an improved three dimension k-nearest neighbor clustering algorithm with an improved multiobjective adaptive large neighborhood search method is developed to solve the model. This algorithm incorporates the adaptive score adjustment and Pareto solution selection strategies to enhance algorithm convergence and evaluate solution quality. The acceptance criterion for new solutions is redesigned based on multiobjective function values to explore the search space more thoroughly. Additionally, the algorithm’s computational performance is verified by comparing it with the CPLEX solver for small-scale problems and with multiobjective ant colony optimization, multiobjective evolutionary algorithms, multiobjective particle swarm optimization, multiobjective monarch butterfly optimization, and multiobjective harmony search algorithms for medium-to-large problems. The results demonstrate the superior convergence, uniformity, and spread of the proposed algorithm. Furthermore, a real-world case study employing traffic information of Dalian city, China, supports that the proposed method enhances the efficiency of delivery. Four different time-dependent travel times model are proposed to analyze the outperformance of the time-dependent travel model in this study. Finally, the sensitivity analysis considers different road congestion states and UGV capacities, aiming to reduce transportation costs, and overcome high coordination and congestion costs in the network. This study offers robust methodologies for theoretically and practically addressing the two-echelon truck-UGV routing problem with time-dependent travel times, providing essential insights for promoting development, enhancing smart city integration, and boosting operational efficiency.