Title
Adaptive Iterated Local Search with Random Restarts for the Balanced Travelling Salesman Problem
Author
Pierotti, J. (TU Delft Discrete Mathematics and Optimization)
Ferretti, Lorenzo (Università della Svizzera Italiana)
Pozzi, Laura (Università della Svizzera Italiana)
van Essen, J.T. (TU Delft Discrete Mathematics and Optimization)
Contributor
Greco, Salvatore (editor)
Pavone, Mario F. (editor)
Talbi, El-Ghazali (editor)
Vigo, Daniele (editor)
Date
2021
Abstract
Metaheuristics have been widely used to solve NP-hard problems, with excellent results. Among all NP-hard problems, the Travelling Salesman Problem (TSP) is potentially the most studied one. In this work, a variation of the TSP is considered; the main differences being, edges may have positive or negative costs and the objective is to return a Hamiltonian cycle with cost as close as possible to zero. This variation is called the balanced TSP (BTSP). To tackle this new problem, we present an adaptive variant of the iterated local search metaheuristic featuring also random restart. This algorithm was tested on the MESS2018 metaheuristic competition and achieved notable results, scoring the 5th position overall. In this paper, we detail all the components of the algorithm itself and present the best solutions identified. Even though this metaheuristic was tailored for the BTSP, with small modifications its structure can be applied to virtually any NP-hard problem. In particular, we introduce the uneven reward-and-punishment rule which is a powerful tool, applicable in many contexts where fast responses to dynamic changes are crucial.
Subject
Balanced Travelling Salesman Problem
Hamiltonian cycle
Iterated Local Search
Metaheuristic
Travelling Salesman Problem
To reference this document use:
http://resolver.tudelft.nl/uuid:f71c7230-629c-4d72-9f4e-3bd0a502eb78
DOI
https://doi.org/10.1007/978-3-030-68520-1_4
Publisher
Springer, Cham
Embargo date
2022-08-16
ISBN
978-3-030-68519-5
Source
Metaheuristics for Combinatorial Optimization
Event
Metaheuristics Summer School, MESS 2018, 2018-07-21 → 2018-07-25, Taormina, Italy
Series
Advances in Intelligent Systems and Computing, 2194-5357, 1332
Bibliographical note
Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.
Part of collection
Institutional Repository
Document type
conference paper
Rights
© 2021 J. Pierotti, Lorenzo Ferretti, Laura Pozzi, J.T. van Essen