The single vehicle routing problem with deliveries and selective pickups

被引:76
作者
Gribkovskaia, Irina [1 ]
Laporte, Gilbert [2 ]
Shyshou, Aliaksandr [1 ]
机构
[1] Molde Univ Coll, N-6402 Molde, Norway
[2] HEC Montreal, Canada Res Chair Distribut Management, Montreal, PQ H3T 2A7, Canada
基金
加拿大自然科学与工程研究理事会;
关键词
pickup and delivery problems; selective pickups; tabu search; reverse logistics;
D O I
10.1016/j.cor.2007.01.007
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
The single vehicle routing problem with deliveries and selective pickups (SVRPDSP) is defined on a graph in which pickup and delivery demands are associated with customer vertices. The difference between this problem and the single vehicle routing problem with pickups and deliveries (SVRPPD) lies in the fact that it is no longer necessary to satisfy all pickup demands. In the SVPPDSP a pickup revenue is associated with each vertex, and the pickup demand at that vertex will be collected only if it is profitable to do so. The net cost of a route is equal to the sum of routing costs, minus the total collected revenue. The aim is to design a vehicle route of minimum net cost, visiting each customer, performing all deliveries, and a subset of the pickups. A mixed integer linear programming formulation is proposed for the SVRPDSP. Classical construction and improvement heuristics, as well as a tabu search heuristic (TS), are developed and tested on a number of instances derived from VRPLIB. Computational results show that the solutions produced by the proposed heuristics are near-optimal. There is also some evidence that the best solutions identified by the heuristics are frequently non-Hamiltonian and may contain one or two customers visited twice. (c) 2007 Elsevier Ltd. All rights reserved.
引用
收藏
页码:2908 / 2924
页数:17
相关论文
共 29 条
[1]  
AAS B, 2007, IN PRESS INT J PHYS
[2]  
Angelelli E., 2002, Quantitative Approaches to Distribution Logistics and Supply Chain Management, P249
[3]   A unified tabu search heuristic for vehicle routing problems with time windows [J].
Cordeau, JF ;
Laporte, G ;
Mercier, A .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2001, 52 (08) :928-936
[4]  
Cordeau JF, 1997, NETWORKS, V30, P105, DOI 10.1002/(SICI)1097-0037(199709)30:2<105::AID-NET5>3.0.CO
[5]  
2-G
[6]  
Dantzig GB, 1954, OPER RES, V2, P393, DOI DOI 10.1287/OPRE.2.4.393
[7]  
Dethloff J, 2002, J OPER RES SOC, V53, P115, DOI 10.1057/palgrave/jors/2601263
[9]   The traveling salesman problem with backhauls [J].
Gendreau, M ;
Hertz, A ;
Laporte, G .
COMPUTERS & OPERATIONS RESEARCH, 1996, 23 (05) :501-508
[10]   FUTURE PATHS FOR INTEGER PROGRAMMING AND LINKS TO ARTIFICIAL-INTELLIGENCE [J].
GLOVER, F .
COMPUTERS & OPERATIONS RESEARCH, 1986, 13 (05) :533-549