Vehicle routing problem with simultaneous deliveries and pickups

被引:97
作者
Chen, JF
Wu, TH
机构
[1] Feng Chia Univ, Dept Ind Engn & Syst Management, Taichung 40724, Taiwan
[2] Da Yeh Univ, Changhua, Taiwan
关键词
delivery; pickup; record-to-record travel; vehicle routing problem;
D O I
10.1057/palgrave.jors.2602028
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
The vehicle routing problem with backhauls involves the delivery and pickup of goods at different customer locations. In many practical situations, however, the same customer may require both a delivery of goods from the distribution centre and a pickup of recycled items simultaneously. In this paper, an insertion-based procedure to generate good initial solutions and a heuristic based on the record-to-record travel, tabu lists, and route improvement procedures are proposed to resolve the vehicle routing problems with simultaneous deliveries and pickups. Computational characteristics of the insertion-based procedure and the hybrid heuristic are evaluated through computational experiments. Computational results show that the insertion-based procedure obtained better solutions than those found in the literature. Computational experiments also show that the proposed hybrid heuristic is able to reduce the gap between initial solutions and optimal solutions effectively and is capable of obtaining optimal solutions very efficiently for small-sized problems.
引用
收藏
页码:579 / 587
页数:9
相关论文
共 26 条
[1]   ONE WAREHOUSE MULTIPLE RETAILER SYSTEMS WITH VEHICLE-ROUTING COSTS [J].
ANILY, S ;
FEDERGRUEN, A .
MANAGEMENT SCIENCE, 1990, 36 (01) :92-114
[2]  
Anily S, 1996, NAV RES LOG, V43, P415, DOI 10.1002/(SICI)1520-6750(199604)43:3<415::AID-NAV7>3.0.CO
[3]  
2-C
[4]  
Casco DO, 1988, Vehicle Routing: Methods and Studies, V16, P127
[5]  
Christofides N., 1979, Combinatorial optimization, P315
[6]  
Deif I., 1984, P BABS C SOFTW US TR, P75
[8]   NEW OPTIMIZATION HEURISTICS - THE GREAT DELUGE ALGORITHM AND THE RECORD-TO-RECORD TRAVEL [J].
DUECK, G .
JOURNAL OF COMPUTATIONAL PHYSICS, 1993, 104 (01) :86-92
[9]   A tabu search heuristic for the vehicle routing problem with backhauls and time windows [J].
Duhamel, C ;
Potvin, JY ;
Rousseau, JM .
TRANSPORTATION SCIENCE, 1997, 31 (01) :49-59
[10]  
Glover F., 1990, ORSA Journal on Computing, V2, P4, DOI [10.1287/ijoc.1.3.190, 10.1287/ijoc.2.1.4]