Branch-and-price for the pickup and delivery problem with time windows and scheduled lines

V. Ghilas, J.-F. Cordeau, E. Demir, T. van Woensel

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

51 Citaten (Scopus)
153 Downloads (Pure)


The Pickup and Delivery Problem with Time Windows and Scheduled Lines (PDPTW-SL) consists of routing and scheduling a set of vehicles, by integrating them with scheduled public transportation lines, to serve a set of freight requests within their time windows. This paper presents an exact solution approach based on a branch-and-price algorithm. A path-based set partitioning formulation is used as the master problem, and a variant of the elementary shortest path problem with resource constraints is solved as the pricing problem. In addition, the proposed algorithm can also be used to solve the PDPTW with transfers (PDPTW-T) as a special case. Results of extensive computational experiments confirm the efficiency of the algorithm: it is able to solve small- and medium-size instances to optimality within reasonable execution time. More specifically, our algorithm solves the PDPTW-SL with up to 50 requests and the PDPTW-T with up to 40 requests on the considered instances.
Originele taal-2Engels
Pagina's (van-tot)1191-1210
Aantal pagina's20
TijdschriftTransportation Science
Nummer van het tijdschrift5
StatusGepubliceerd - 1 sep. 2018


Duik in de onderzoeksthema's van 'Branch-and-price for the pickup and delivery problem with time windows and scheduled lines'. Samen vormen ze een unieke vingerafdruk.

Citeer dit