A hybrid metaheuristic algorithm based on iterated local search for vehicle routing problem with simultaneous pickup and delivery

被引:23
作者
Oztas, Tayfun [1 ]
Tus, Aysegul [1 ]
机构
[1] Pamukkale Univ, Dept Business Adm, Denizli, Turkey
关键词
VRPSPD; Metaheuristics; Iterated local search; Variable neighborhood descent; Threshold acceptance; Reverse logistics; VARIABLE NEIGHBORHOOD SEARCH; TABU SEARCH; HEURISTIC ALGORITHMS; GENETIC ALGORITHM; OPTIMIZATION; SYSTEM; SINGLE;
D O I
10.1016/j.eswa.2022.117401
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
The vehicle routing problem is an optimization problem that deals with transporting between the depot and the customers in its most general form. On the other hand, vehicle routing problems with simultaneous pickup and delivery involve carrying out pickup and delivery operations simultaneously at the customers' locations. Since this problem is NP-hard, exact methods fail to find near-optimal solutions in a short time. This study aims to solve the vehicle routing problem with pickup and delivery using a hybrid algorithm combining iterated local search, variable neighborhood descent, and threshold acceptance metaheuristics. Iterated local search is the main framework of the proposed algorithm. The nearest neighbor heuristic generates initial solutions. Variable neighborhood descent provides intensifying in the search space by randomly ordering the neighborhood structures. The perturbation mechanism allows exploring different parts of the search space. Since vehicle routing problem with simultaneous pickup and delivery carries out both pickup and delivery operations, the amount of load in the vehicle changes after each customer visit. The fluctuation in load affects the feasibility of the routes. The distances between visited locations on a route affect the total cost. We propose a roulette wheel that uses the information on the routes, with a novel approach that takes these considerations into account to select routes during the perturbation phase. This approach also inspires an operator used in the perturbation mechanism. The acceptance criterion of the algorithm exploits non-improving solutions encountered in the search space using adaptive threshold acceptance. The proposed algorithm consists of low complexity components and has only one parameter. For this reason, the design phase of the algorithm can be completed effortlessly with the advantage of the programming language used. Similarly, parameter tuning can be done quickly compared to other algorithms with many parameters. The proposed algorithm has been tested with problem sets widely used in the literature. The experimental results show that the proposed algorithm reaches the best-known solution values in a reasonable time for most of the test problems used for benchmarking in the literature. The proposed algorithm seems to be particularly successful in small and medium-sized problem instances. These findings indicate that our algorithm can be used for vehicle routing problems with simultaneous pickup and delivery.
引用
收藏
页数:17
相关论文
共 85 条
[1]   No Free Lunch Theorem: A Review [J].
Adam, Stavros P. ;
Alexandropoulos, Stamatios-Aggelos N. ;
Pardalos, Panos M. ;
Vrahatis, Michael N. .
APPROXIMATION AND OPTIMIZATION: ALGORITHMS, COMPLEXITY AND APPLICATIONS, 2019, 145 :57-82
[2]   A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery [J].
Ai, The Jin ;
Kachitvichyanukul, Voratas .
COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (05) :1693-1702
[3]   A self-adaptive local search algorithm for the classical vehicle routing problem [J].
Alabas-Uslu, Cigdem ;
Dengiz, Berna .
EXPERT SYSTEMS WITH APPLICATIONS, 2011, 38 (07) :8990-8998
[4]  
[Anonymous], 2018, ITERATED LOCAL SEARC, DOI DOI 10.1007/978-3-319-07124-4_8
[5]  
[Anonymous], SIAM Review
[6]  
[Anonymous], PASSMARK SOFTWARE LI
[7]   A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with simultaneous pickup and delivery [J].
Avci, Mustafa ;
Topaloglu, Seyda .
EXPERT SYSTEMS WITH APPLICATIONS, 2016, 53 :160-171
[8]   An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries [J].
Avci, Mustafa ;
Topaloglu, Seyda .
COMPUTERS & INDUSTRIAL ENGINEERING, 2015, 83 :15-29
[9]  
Aydogdu B., 2020, GAZI NIVERSITESI MHE, V35, DOI [10.17341/gazimmfd, DOI 10.17341/GAZIMMFD]
[10]   Two-echelon vehicle routing problem with simultaneous pickup and delivery: Mathematical model and heuristic approach [J].
Belgin, Onder ;
Karaoglan, Ismail ;
Altiparmak, Fulya .
COMPUTERS & INDUSTRIAL ENGINEERING, 2018, 115 :1-16