A two-level diploid genetic based algorithm for solving the family traveling salesman problem
Petrică C. Pop, Oliviu Matei, Camelia-M. Pintea · Proceedings of the Genetic and Evolutionary Computation Conference · 2018
In this paper, we consider the Family Traveling Salesman Problem (FTSP), which is a variant of the classical Traveling Salesman Problem (TSP). Given a partition of the nodes into a predefined number of clusters, called families, the aim of the FTSP is to find a minimum cost tour visiting a given number of nodes from each family. We describe a novel solution approach for solving the FTSP obtained by decomposing the problem into two smaller subproblems: a macro-level subproblem and a micro-level subproblem, and solving them separately. The goal of the first subproblem is to provide tours visiting the families using a classical genetic algorithm and a diploid genetic algorithm, while the aim of the second subproblem is to find the minimum-cost tour, corresponding to the above mentioned tours, visiting a given number of nodes from each family. The second subproblem is solved by transforming each global tour into a traveling salesman problem (TSP) which then is optimally computed using the Concorde TSP solver. The preliminary computational results on a usually used set of benchmark instances prove that our solution approach provides competitive solutions in comparison to the existing methods for solving the FTSP.