An ALNS metaheuristic for the family multiple traveling salesman problem

• Published in: Computers & operations research 2024-09, Vol.169, p.106750, Article 106750
• Main Authors: Cunha, Claudio B., Massarotto, Dieferson Flori, Fornazza, Sergio Luiz, Mendes, André Bergsten
• Format: Article
• Language: English
• Subjects: ALNS; Combinatorial optimization; Family multiple traveling salesman problem; Metaheuristic; Multiple tours
• ISSN: 0305-0548; 1873-765X
• DOI: 10.1016/j.cor.2024.106750

This paper presents a novel variant of the Family Traveling Salesman Problem (FTSP), a well-known NP-hard problem introduced by Morán-Mirabal et al. (2014). In the FTSP, the set of nodes is partitioned into several subsets called families, and the aim is to determine the minimum-cost cycle that begins and ends at the depot and visits a predefined number of nodes in each family. We extend the FTSP by requiring that m tours be generated, each having a number of nodes between a minimum and a maximum quantity, thus yielding the family multiple traveling salesman problem (FmTSP). We present a two-index MIP formulation and develop an ALNS metaheuristic as a solution method for large-sized instances. Our proposed ALNS was initially employed to solve the FTSP benchmark instances and allowed us to improve some of the best-known solutions. The results for new derived instances requiring multiple tours show that our ALNS also achieves optimality for all instances with proven-optimal solutions. •We introduce a novel variant of the Family Traveling Salesman Problem (FTSP).•The Family Multiple Traveling Salesman Problem (FmTSP) requires a number of tours to be built.•Each tour must have a minimum and maximum number of nodes.•We propose an Adaptive Large Neighborhood Search (ALNS) to solve it.•Our ALNS obtains excellent results by solving both the FmTSP and the FTSP.