Combining multiple delivery systems for urban logistics by ALNS-based route planning

Abstract Diesel-powered delivery vans still dominate the parcel delivery sector. However, due to their negative environmental impact, delivery service providers are urged to switch to more innovative and eco-friendly delivery vehicles like cargo bikes, delivery robots, or drones. Unfortunately, relying on only one type of delivery system is not always feasible, either because the customer’s site lacks the requirements or because the parcel size is too large. A possible solution is to combine multiple such delivery systems. In this context, this paper focuses on a problem in city logistics based on the two-echelon vehicle routing problem. To accommodate a diverse range of delivery vehicles, it involves deploying various vehicle types in the second echelon, direct delivery by first-echelon vehicles, transfer of second-echelon vehicles and parcels at satellite locations, and preference constraints for customers and vehicle types. To solve the problem, we propose an Adaptive Large Neighborhood Search (ALNS) heuristic that features problem-specific local search and destroy operators. Experiments are conducted for an urban delivery area in Hamburg, Germany. They show that the ALNS can handle various fleet compositions and instance sizes. Our findings indicate that the combination of delivery systems can lead to significant cost savings compared to traditional van delivery and that customer preferences heavily influence the optimal fleet composition.