Multi-trip routing of autonomous robots for mixed pickups and deliveries in last-mile logistics

The growing adoption of autonomous ground robots and aerial drones for last-mile logistics underscores the urgent need for efficient routing in daily operations. In this context, we investigate a routing problem for autonomous robots, wherein vehicles equipped with different types of containers perform pickup and delivery services subject to stringent time window constraints. Over the planning horizon, each robot may perform multiple trips, returning to the depot to reload or unload as needed. Depot operations are explicitly modeled, including a fixed preparation time per trip and customer-dependent loading and unloading times. To address this problem, we first propose a Branch-and-Price (BP) algorithm that provides exact solutions for small and medium-sized instances. We further develop an efficient Iterated Local Search (ILS) heuristic for large instances. The algorithm employs labeling algorithms embedded in the BP algorithm to optimally determine depot return decisions for a given customer sequence. Extensive computational experiments demonstrate that the BP algorithm produces tight bounds or optimal solutions for instances with up to 40 customers, achieving an average optimality gap below 2.0% while significantly outperforming a state-of-the-art MILP solver. Furthermore, the proposed ILS obtains all optimal solutions confirmed by the BP algorithm and significantly outperforms both a general-purpose MILP solver and the BP algorithm, especially on instances with 100 customers, where it achieves an average gap of over 14.0% relative to the best solutions from exact algorithms. Finally, we conduct sensitivity analyses to assess the effects of customer time window lengths and robot capacity configurations on the solutions, thereby providing managerial insights for last-mile logistics companies.