We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Heuristic approaches for the family traveling salesman problem.
- Authors
Bernardino, Raquel; Paias, Ana
- Abstract
In this article, we address the family traveling salesman problem (FTSP), an NP‐hard problem that may be seen as a generalization of the traveling salesman problem. In the FTSP, the set of cities is partitioned into several families and one wants to find the minimum cost route that visits a given number of cities in each family. We propose two metaheuristics, a population‐based method and a local search method, and a hybrid algorithm, which combines a branch‐and‐cut algorithm with a local search procedure. All the proposed methods improve the best known upper bounds from the literature. The local search method and the hybrid algorithm improve the best known upper bounds for all the benchmark instances with unknown optimal value, while the population‐based method improves the best known upper bounds for all instances, except two. Furthermore, we developed an instance generator to create additional test instances with different visit patterns. These newly generated instances were considered in the computational experiment and, thus, we provide optimal values or upper bounds for each instance. Additionally, we created a website dedicated to the FTSP, where this information is made available to the scientific community (http://familytsp.rd.ciencias.ulisboa.pt/).
- Subjects
TRAVELING salesman problem; FAMILY travel; ALGORITHMS; METAHEURISTIC algorithms; SEARCH algorithms
- Publication
International Transactions in Operational Research, 2021, Vol 28, Issue 1, p262
- ISSN
0969-6016
- Publication type
Article
- DOI
10.1111/itor.12771