Premium
The intermittent travelling salesman problem
Author(s) -
Pham TuSan,
Leyman Pieter,
De Causmaecker Patrick
Publication year - 2020
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12609
Subject(s) - travelling salesman problem , metaheuristic , mathematical optimization , computer science , vertex (graph theory) , neighbourhood (mathematics) , constraint (computer aided design) , bottleneck traveling salesman problem , combinatorial optimization , mathematics , graph , theoretical computer science , mathematical analysis , geometry
In this paper, we introduce a new variant of the travelling salesman problem, namely the intermittent travelling salesman problem (ITSP), which is inspired by real‐world drilling/texturing applications. In this problem, each vertex can be visited more than once and there is a temperature constraint enforcing a time lapse between two consecutive visits. A branch‐and‐bound approach is proposed to solve small instances to optimality. We furthermore develop four variable neighbourhood search metaheuristics which produce high‐quality solutions for large instances. An instance library is built and made publicly available.