A single vehicle routing problem with fixed delivery and optional collections

被引:16
作者
Gutierrez-Jarpa, G. [2 ,3 ]
Marianov, V. [1 ]
Obreque, C. [4 ]
机构
[1] Pontificia Univ Catolica Chile, Dept Elect Engn, Santiago, Chile
[2] Pontificia Univ Catolica Chile, Grad Program, Santiago, Chile
[3] Unversidad Catolica Santisima Concepcion, Dept Ind Engn, Concepcion, Chile
[4] Univ Bio Bio, Dept Ind Engn, Concepcion, Chile
关键词
Routing; delivery and collection; branch and cut; TRAVELING SALESMAN PROBLEM; TEAM ORIENTEERING PROBLEM; EXACT ALGORITHM; CUT ALGORITHM; PICK-UP; BACKHAULS;
D O I
10.1080/07408170903113771
中图分类号
T [工业技术];
学科分类号
08 ;
摘要
The Single-Vehicle Routing Problem with Fixed Delivery and Optional Collections considers a set of delivery customers receiving goods from a depot and a set of collection customers sending goods to the same depot. All delivery customers must be visited by the vehicle, while a collection customer is visited only if the capacity of the vehicle is large enough to fit the collected load and the visit reduces collection costs that would be otherwise incurred. The goal is to minimize the transportation and collection costs. A model is proposed and solved utilizing a branch-and-cut method. Efficient new cuts are proposed. Computational experience is offered on two sets of test problems. It is proved possible to solve instances that previous methods were unable to solve. The method was tested on larger instances.
引用
收藏
页码:1067 / 1079
页数:13
相关论文
共 31 条
[1]   An exact algorithm for the traveling salesman problem with deliveries and collections [J].
Baldacci, R ;
Hadjiconstantinou, E ;
Mingozzi, A .
NETWORKS, 2003, 42 (01) :26-41
[2]  
BERUBE JF, 2008, EUR J OPER RES, V194, P39
[3]   Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery [J].
Bianchessi, Nicola ;
Righini, Giovanni .
COMPUTERS & OPERATIONS RESEARCH, 2007, 34 (02) :578-594
[4]   A new tabu search algorithm for the vehicle routing problem with backhauls [J].
Brandao, J .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2006, 173 (02) :540-555
[5]  
Cohon J.L., 1978, Multiobjective programming and planning
[6]   A branch-and-cut algorithm for the dial-a-ride problem [J].
Cordeau, Jean-Francois .
OPERATIONS RESEARCH, 2006, 54 (03) :573-586
[7]  
DROR M, 1987, NAV RES LOG, V34, P891, DOI 10.1002/1520-6750(198712)34:6<891::AID-NAV3220340613>3.0.CO
[8]  
2-J
[9]   Traveling salesman problems with profits [J].
Feillet, D ;
Dejax, P ;
Gendreau, M .
TRANSPORTATION SCIENCE, 2005, 39 (02) :188-205
[10]  
Fischetti M., 1998, INFORMS Journal on Computing, V10, P133, DOI 10.1287/ijoc.10.2.133