Instances of "The Capacitated Family Traveling Salesperson Problem"

Instances of the "The Capacitated Family Traveling Salesperson Problem". Abstract: This paper addresses the Capacitated Family Traveling Salesperson Problem (CFTSP), a variant of the Family Traveling Salesperson Problem. In the CFTSP, the nodes of a graph are partitioned into disjoint families; the problem is to visit a given quantity of nodes of each family by using a set of capacitated agents to minimize the total distance traveled by the agents. No agent exceeds its capacity in a feasible solution, and the required number of nodes for each family is visited. We propose two integer linear programming formulations for the CFTSP and show that commercial solvers achieve optimal solutions for small instances. As an alternative, we propose a Biased Random-Key Genetic Algorithm with four decodification algorithms that find high-quality, optimal, or near-optimal solutions in short computational times. Experimental results obtained by exact and non-exact methods are presented and compared.