Please use this identifier to cite or link to this item:
https://hdl.handle.net/11499/46787
Title: | A hybrid metaheuristic algorithm based on iterated local search for vehicle routing problem with simultaneous pickup and delivery | Authors: | Oztas, Tayfun Tus, Aysegul |
Keywords: | VRPSPD Metaheuristics Iterated local search Variable neighborhood descent Threshold acceptance Reverse logistics Variable Neighborhood Search Tabu Search Heuristic Algorithms Genetic Algorithm Optimization System Single |
Publisher: | Pergamon-Elsevier Science Ltd | Abstract: | 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. | URI: | https://doi.org/10.1016/j.eswa.2022.117401 https://hdl.handle.net/11499/46787 |
ISSN: | 0957-4174 1873-6793 |
Appears in Collections: | İktisadi ve İdari Bilimler Fakültesi Koleksiyonu Scopus İndeksli Yayınlar Koleksiyonu / Scopus Indexed Publications Collection WoS İndeksli Yayınlar Koleksiyonu / WoS Indexed Publications Collection |
Show full item record
CORE Recommender
SCOPUSTM
Citations
23
checked on Aug 17, 2024
WEB OF SCIENCETM
Citations
16
checked on Aug 9, 2024
Page view(s)
76
checked on Aug 9, 2024
Google ScholarTM
Check
Altmetric
Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.