Adaptive Iterated Local Search with Random Restarts for the Balanced Travelling Salesman Problem

Jacopo Pierotti, Lorenzo Ferretti, Laura Pozzi, J. Theresia van Essen

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

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.

Original languageEnglish
Title of host publicationMetaheuristics for Combinatorial Optimization
EditorsSalvatore Greco, Mario F. Pavone, El-Ghazali Talbi, Daniele Vigo
Place of PublicationCham
PublisherSpringer
Pages37-56
Number of pages20
ISBN (Electronic)978-3-030-68520-1
ISBN (Print)978-3-030-68519-5
DOIs
Publication statusPublished - 2021
EventMetaheuristics Summer School, MESS 2018 - Taormina, Italy
Duration: 21 Jul 201825 Jul 2018

Publication series

NameAdvances in Intelligent Systems and Computing
Volume1332
ISSN (Print)2194-5357
ISSN (Electronic)2194-5365

Conference

ConferenceMetaheuristics Summer School, MESS 2018
CountryItaly
CityTaormina
Period21/07/1825/07/18

Bibliographical note

Accepted author manuscript

Keywords

  • Balanced Travelling Salesman Problem
  • Hamiltonian cycle
  • Iterated Local Search
  • Metaheuristic
  • Travelling Salesman Problem

Fingerprint

Dive into the research topics of 'Adaptive Iterated Local Search with Random Restarts for the Balanced Travelling Salesman Problem'. Together they form a unique fingerprint.

Cite this