The truck-and-robot routing problem with pickups and deliveries

The increasing number of home deliveries paired with various delivery modes and channels require retailers to establish efficient delivery networks. Integrating retailers into delivery networks of third-party logistics service providers (3PLs) is one way to address this challenge. In this regard, the innovative truck-and-robot concept is a promising alternative to standard truck deliveries. The concept relies on autonomous robots carried and released by trucks to serve customers in predefined time windows. We extend this concept by integrating pickup locations and corresponding delivery requests for direct customer supply. This setup combines the first and the last mile, giving rise to a novel concept where different delivery modes are established that provide robots as a service to pick up and deliver goods to customers. The problem is formalized as the Truck-and-Robot Pickup-and-Delivery Problem (TnR-PDP), integrating pickups and introducing four different delivery modes for home deliveries. We solve the problem using a specialized heuristic, the Adaptive Genetic Algorithm (AGA). The AGA is based on a recombination-based search framework but tailored to the problem specifics (e.g., no or multiple visits per location) using specialized recombination operators and an adaptive search strategy for location and operator selection. Our numerical experiments show that our algorithm works efficiently, outperforming a benchmark approach concerning runtime by up to 79 % while improving solution quality. Furthermore, an in-depth analysis shows a savings potential of 81 % when integrating pickups into the concept compared with alternative approaches, highlighting the benefits of the newly introduced delivery modes.