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

作     者：Cortes, Cristian E. Matamala, Martin Contardo, Claudio 

作者机构：Univ Chile Dept Engn Math Santiago Chile Univ Chile Dept Civil Engn Santiago Chile 

出 版 物：《EUROPEAN JOURNAL OF OPERATIONAL RESEARCH》 (欧洲运筹学杂志)

年 卷 期：2010年第200卷第3期

页      面：711-724页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：Millenium Institute in Complex Engineering Systems and Millenium Nucleus in Information and Randomness Fondo Nacional de Desarrollo Científico y Tecnológico, FONDECYT, (1030700) 

主　　题：Pickup and delivery Dial-a-ride Branch-and-bound Branch-and-cut Benders decomposition Mixed-integer programming 

摘      要：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.