Randomized heuristics for the family traveling salesperson problem

Abstract. This paper introduces the family traveling salesperson prob-lem (FTSP), a variant of the generalized traveling salesman problem. In the FTSP, a subset of nodes must be visited for each node cluster in the graph. The objective is to minimize the distance traveled. We describe an integer programming formulation for the FTSP and show that the commercial-grade integer programming solver CPLEX 11 can only solve small instances of the problem in reasonable running time. We propose two randomized heuristics for finding optimal and near-optimal solutions of this problem. These heuris-tics are a biased random-key genetic algorithm and a GRASP with evolu-tionary path-relinking. Computational results comparing both heuristics are presented. 1