The pickup and delivery problem with transfers: Formulation and a branch-and-cut solution method

Cristián E. Cortés, Martín Matamala and Claudio Contardo

European Journal of Operational Research, 2010, vol. 200, issue 3, pages 711-724

Abstract: In this paper, a strict formulation of a generalization of the classical pickup and delivery problem is presented. Here, we add the flexibility of providing the option for passengers to transfer from one vehicle to another at specific locations. As part of the mathematical formulation, we include transfer nodes where vehicles may interact interchanging passengers. Additional variables to keep track of customers along their route are considered. The formulation has been proven to work correctly, and by means of a simple example instance, we conclude that there exist some configurations in which a scheme allowing transfers results in better quality optimal solutions. Finally, a solution method based on Benders decomposition is addressed. We compare the computational effort of this application with a straight branch and bound strategy; we also provide insights to develop more efficient set partitioning formulations and associated algorithms for solving real-size problems.

Keywords: Pickup; and; delivery; Dial-a-ride; Branch-and-bound; Branch-and-cut; Benders; decomposition; Mixed-integer; programming (search for similar items in EconPapers)
Date: 2010

Downloads: (external link)
http://www.sciencedirect.com/science/article/B6VCT ... 7d03bf9a2e806e2ef6b3
Full text for ScienceDirect subscribers only

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: http://EconPapers.repec.org/RePEc:eee:ejores:v:200:y:2010:i:3:p:711-724

Access Statistics for this article

European Journal of Operational Research is edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Series data maintained by Heidi Boesdal ().