Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

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

Ghilas, Veaceslav, Cordeau, Jean-Francois, Demir, Emrah ORCID: and Van Woensel, Tom 2018. Branch-and-price for the pickup and delivery problem with time windows and scheduled lines. Transportation Science 52 (5) , pp. 1191-1210. 10.1287/trsc.2017.0798

[thumbnail of Final_ORCA.pdf]
PDF - Accepted Post-Print Version
Download (675kB) | Preview


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.

Item Type: Article
Date Type: Publication
Status: Published
Schools: Biosciences
Business (Including Economics)
Publisher: INFORMS (Institute for Operations Research and Management Sciences)
ISSN: 0041-1655
Date of First Compliant Deposit: 12 September 2017
Date of Acceptance: 21 July 2017
Last Modified: 09 Nov 2023 09:27

Citation Data

Cited 35 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics