A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection

被引:133
作者
Dell'Amico, Mauro
Righini, Giovanni
Salani, Matteo
机构
[1] Univ Modena & Reggio Emilia, Dipartimento Sci & Metodi Ingn, I-42100 Reggio Emilia, Italy
[2] Univ Milan, Dipartimento Tecnol Informaz, I-26013 Crema, Italy
关键词
reverse logistics; vehicle routing; branch and price; dynamic programming;
D O I
10.1287/trsc.1050.0118
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
The vehicle routing problem with simultaneous distribution and collection (VRPSDC) is the variation of the capacitated vehicle routing problem that arises when the distribution of goods from a depot to a set of customers and the collection of waste from the customers to the depot must be performed by the same vehicles of limited capacity and the customers can be visited in any order. We study how the branch-and-price technique can be applied to the solution of this problem and in particular we compare two different ways of solving the pricing subproblem: exact dynamic programming and state space relaxation. By applying a bidirectional search we experimentally prove its effectiveness in solving the subproblem. We also devise suitable branching strategies for both the exact and the relaxed approach and we report on an extensive set of computational experiments on benchmark instances with both simple and composite demands.
引用
收藏
页码:235 / 247
页数:13
相关论文
共 28 条
[1]  
Ahuja R.K., 1993, NETWORK FLOWS THEORY
[2]  
Angelelli E., 2002, Quantitative Approaches to Distribution Logistics and Supply Chain Management, P249
[3]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[4]   AN ALGORITHM FOR LARGE ZERO-ONE KNAPSACK-PROBLEMS [J].
BALAS, E ;
ZEMEL, E .
OPERATIONS RESEARCH, 1980, 28 (05) :1130-1154
[5]   AN ALGORITHM FOR THE RESOURCE CONSTRAINED SHORTEST-PATH PROBLEM [J].
BEASLEY, JE ;
CHRISTOFIDES, N .
NETWORKS, 1989, 19 (04) :379-394
[6]  
BIANCHESSI N, 2006, IN PRESS COMPUT OPER
[7]  
Casco DO, 1988, Vehicle Routing: Methods and Studies, V16, P127
[8]   STATE-SPACE RELAXATION PROCEDURES FOR THE COMPUTATION OF BOUNDS TO ROUTING-PROBLEMS [J].
CHRISTOFIDES, N ;
MINGOZZI, A ;
TOTH, P .
NETWORKS, 1981, 11 (02) :145-164
[9]  
Desaulniers G, 1998, FLEET MANAGEMENT AND LOGISTICS, P57
[10]   A NEW OPTIMIZATION ALGORITHM FOR THE VEHICLE-ROUTING PROBLEM WITH TIME WINDOWS [J].
DESROCHERS, M ;
DESROSIERS, J ;
SOLOMON, M .
OPERATIONS RESEARCH, 1992, 40 (02) :342-354