Feasibility of the Pickup and Delivery Problem with Fixed Partial Routes: A Complexity Analysis

Gerardo Berbeglia (), Gilles Pesant () and Louis-Martin Rousseau ()
Additional contact information
Gerardo Berbeglia: Melbourne Business School, Carlton, 3053, Australia
Gilles Pesant: Département de génie informatique et génie logiciel, École Polytechnique de Montréal, Montréal H3T 2A7, Canada
Louis-Martin Rousseau: Département de mathématiques et de génie industriel, École Polytechnique de Montréal, Montréal H3T 2A7, Canada

Transportation Science, 2012, vol. 46, issue 3, 359-373

Abstract: In the pickup and delivery problem (PDP) a fleet of vehicles must serve customers' requests, which consist of transporting objects from their origins to their destinations. We introduce the PDP with fixed partial routes (PDP-FPR), in which some partial routes are given, and the problem consists in obtaining a solution (a set of routes) that includes those partial routes. We have analyzed the complexity of determining whether or not a feasible solution exists for this problem as well as for some relaxations of it. Checking the feasibility of the PDP-FPR and some of its relaxations is shown to be NP-complete, whereas for other relaxations, the problem was proved to be polynomial-time solvable.

Keywords: pickup and delivery; complexity; partial routes; scheduling; dial-a-ride (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1110.0394 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:46:y:2012:i:3:p:359-373

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().