A new saving-based ant algorithm for the Vehicle Routing Problem with Simultaneous Pickup and Delivery

被引:96
作者
Catay, Buelent [1 ]
机构
[1] Sabanci Univ, Fac Engn & Nat Sci, TR-34956 Istanbul, Turkey
关键词
Vehicle routing; Metaheuristics; Ant Colony Optimization; Reverse logistics; TABU SEARCH ALGORITHM; HEURISTIC ALGORITHMS; SYSTEM; SINGLE; DEPOT; COLONY;
D O I
10.1016/j.eswa.2010.03.045
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
The Vehicle Routing Problem with Pickup and Delivery (VRPPD) is a variant of the Vehicle Routing Problem where the vehicles are not only required to deliver goods but also to pick up some goods from the customers. Given a fleet of vehicles and a set of customers with known delivery and/or pickup demands for one commodity VRPPD determines a set of vehicle routes originating and ending at a single depot and visiting all customers exactly once. The objective is to minimize the total distance traversed. In this paper, we consider a special case of the VRPPD where each customer has both a delivery and a pickup demand to be satisfied simultaneously. For this problem, we propose an ant colony algorithm employing a new saving-based visibility function and pheromone updating procedure. The numerical tests with the well-known benchmark problems from the literature show that the proposed approach provides competitive results and improves several best-known solutions. (C) 2010 Elsevier Ltd. All rights reserved.
引用
收藏
页码:6809 / 6817
页数:9
相关论文
共 45 条
[1]  
Angelelli E., 2002, Quantitative approaches to distribution logistics and supply chain management, P249
[2]  
[Anonymous], 1992, OPTIMIZATION LEARNIN
[3]  
[Anonymous], NEW IDEAS OPTIMIZATI
[4]   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
[5]   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
[6]  
Bullmore ET, 1999, HUM BRAIN MAPP, V7, P38, DOI 10.1002/(SICI)1097-0193(1999)7:1<38::AID-HBM4>3.3.CO
[7]  
2-H
[8]   An improved ant system algorithm for the vehicle routing problem [J].
Bullnheimer, B ;
Hartl, RF ;
Strauss, C .
ANNALS OF OPERATIONS RESEARCH, 1999, 89 (0) :319-328
[9]  
Casco D., 1988, VEHICLE ROUTING METH, P127
[10]   Vehicle routing problem with simultaneous deliveries and pickups [J].
Chen, JF ;
Wu, TH .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2006, 57 (05) :579-587