Solving the family traveling salesman problem

In this paper we address the family traveling salesman problem (FTSP), an NP-hard problem in which the set of nodes of a graph is partitioned into several subsets, which are called families. The objective is to visit a predefined number of nodes in each family at a minimum cost. We present several compact and non-compact models for the FTSP. Computational experiments with benchmark instances show that the non-compact models outperform the compact ones. One of the non-compact models is able to solve instances with 127 nodes, in less than 70 seconds, and one of the instances with 280 nodes in 3615 seconds. The optimal values of these instances were not known. For the higher dimensioned instances, the ones whose optimal value remains unknown, we propose an iterated local search algorithm that is able to improve the best known upper bounds from the literature.