Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 200, Issue 3, Pages 711-724Publisher
ELSEVIER
DOI: 10.1016/j.ejor.2009.01.022
Keywords
Pickup and delivery; Dial-a-ride; Branch-and-bound; Branch-and-cut; Benders decomposition; Mixed-integer programming
Ask authors/readers for more resources
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. (C) 2009 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available