An Adaptive Large Neighborhood Search for the Pickup and Delivery Problem with Transfers

Renaud Masson (), Fabien Lehuédé () and Olivier Péton ()
Additional contact information
Renaud Masson: LUNAM Université, École des Mines de Nantes, IRCCyN UMR CNRS 6597, F-44307 Nantes cedex 3, France
Fabien Lehuédé: LUNAM Université, École des Mines de Nantes, IRCCyN UMR CNRS 6597, F-44307 Nantes cedex 3, France
Olivier Péton: LUNAM Université, École des Mines de Nantes, IRCCyN UMR CNRS 6597, F-44307 Nantes cedex 3, France

Transportation Science, 2013, vol. 47, issue 3, 344-355

Abstract: The pickup and delivery problem (PDP) consists in defining a set of routes that satisfy transportation requests between a set of pickup points and a set of delivery points. This paper addresses a variant of the PDP where requests can change vehicle during their trip. The transfer is made at specific locations called “transfer points.” The corresponding problem is called the pickup and delivery problem with transfers (PDPT). Solving the PDPT leads to new modeling and algorithmic difficulties. We propose new heuristics capable of efficiently inserting requests through transfer points. These heuristics are embedded into an adaptive large neighborhood search. We evaluate the method on generated instances and apply it to the transportation of people with disabilities. On these real-life instances we show that the introduction of transfer points can bring significant improvements (up to 9%) to the value of the objective function.

Keywords: pickup and delivery problem; transfers; adaptive large neighborhood search (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (45)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1120.0432 (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:47:y:2013:i:3:p:344-355

Access Statistics for this article

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