An intensification-driven search algorithm for the family traveling salesman problem with incompatibility constraints

The family traveling salesman problem with incompatibility constraints (FTSP-IC) is a variant of the well-known traveling salesman problem. Given a set of candidate nodes divided into several subsets (families), the FTSP-IC is to find several routes such that the sum of their total traveling distance is minimized, while ensuring a predetermined number of nodes from each family is visited and satisfying the incompatibility constraints. The FTSP-IC has a number of real-life applications, yet it is challenging to solve the problem due to its NP-hard nature. In this work, we introduce a competitive intensification-driven search algorithm for solving this relevant problem. The proposed algorithm significantly intensifies the search by performing extensive searches in the nearby area of discovered local optima. Computational results on 63 benchmark instances from the literature show that our algorithm is able to improve 29 best-know solutions (new upper bounds) and match all the remaining 34 proven optimal solutions. The impacts of the key components of the algorithm on its performance are experimentally analyzed. • The family traveling salesman problem with incompatibility constraints has many applications. • An intensification-driven search algorithm is presented for solving the problem. • The algorithm is assessed on 63 benchmark instances. • 29 improved best-known results (new upper bounds) are reported.