Return of the Robots: The Truck-and-Robot Routing Problem with Robot Reuse and Reallocation

Retailers and logistics providers must adapt and extend their delivery systems to address the constantly increasing challenges in last-mile delivery. Reverse logistics tasks add to these challenges as about 45% of orders involve product returns. Consequently, efficient integration of delivery solutions with innovative return strategies is becoming a basic requirement for ensuring sustainable and resilient operations. Such delivery systems must enhance customer experience while mitigating delivery costs, congestion, and emissions in urban areas. This study proposes a concept that addresses key challenges in last-mile delivery using the innovative setting of collaborative truck and robot operations. The proposed concept fully leverages the collaborative system’s advantages and enables efficient handling of deliveries and return shipments. It extends existing frameworks by incorporating new features, such as robot reallocations and reuse, while also addressing practical limitations, such as limited robot depot capacities and robot return routing strategies. We formalize the arising routing problem that integrates truck and robot routing, requiring synchronization between both vehicle types while determining stop locations, visit frequencies, and robot movements. We develop a recombination-based matheuristic based on a genetic algorithm and a compact integer program for robot routing referred to as the robot routing problem with autonomous reallocation, reuse, and returns. Numerical experiments demonstrate the algorithm’s efficiency, reducing runtime by up to 93% compared with a benchmark while also improving solution quality. Furthermore, the advanced robot movements ensure feasible operations where previous concepts made simplifying assumptions. Operational costs can be reduced by up to 27% by reallocating and reusing more than half of the robots deployed. The extended and independent robot movements within the collaborative system substantially increase flexibility, constituting a promising alternative for sustainable and efficient last-mile delivery in the future. History: This paper has been accepted for the Transportation Science Special Issue on Climate-Resilient, Smart Transportation of People and Goods. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2025.0523 .