An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Scheduled Lines

Integrating freight flows with public scheduled transportation creates attractive business opportunities because the same transportation needs can be met with less traveling time and fewer emissions. The Pickup and Delivery Problem with Scheduled Lines (PDP-SL) concerns scheduling a set of vehicles to serve the requests such that a part of the journey can be carried out on a scheduled public transportation line using bus, train, tram, metro, etc. Due to the complexity of the problem, which is NP-hard, we propose an Adaptive Large Neighborhood Search (ALNS) heuristic algorithm to solve the PDP-SL. Complex aspects such as the fixed lines’ schedules and synchronization constraints
are eciently considered in the proposed algorithm. Results of extensive computational experiments show that ALNS is highly eective in finding good-quality solutions on the generated PDP-SL instances with up to 100 freight requests that reasonably represent real life situations.