An Exact Approach for the Pickup and Delivery Problem with Time Windows and Scheduled Lines

The Pickup and Delivery Problem with Time Windows and Scheduled Lines (PDPTW-SL) concerns routing and scheduling a set of vehicles to serve a set of freight requests such that a part of the journey can be carried out on scheduled public transportation lines. In this study, we propose an exact solution approach for the PDPTW-SL based on a branch and price algorithm. A path-based set partitioning formulation is used as master problem, and a variant of elementary shortest path problem with resource constraints is studied as pricing problem. The results of extensive computational experiments show that the proposed exact algorithm is able to solve small and medium-sized PDPTW-SL instances with up to 40 freight requests.

Registration to Remy Spliet, spliet@ese.eur.nl is required for availability of lunch.