A parallel branch-and-cut and an adaptive metaheuristic to solve the Family Traveling Salesman Problem

This paper addresses the Family Traveling Salesman Problem (FTSP), a variant of the Traveling Salesman Problem (TSP), in which nodes are grouped into families and the goal is to determine the minimum cost route by visiting only a subset of nodes from each family. We developed two methods to solve the FTSP: (i) a parallel branch-and-cut algorithm with an efficient local search procedure to obtain an optimal solution, and (ii) an adaptive metaheuristic that combines the Biased Random-key Genetic Algorithm (BRKGA) with a reinforcement learning algorithm. In this case, the Q-Learning algorithm is used to control the parameters of the BRKGA during the evolutionary process. Computational experiments were performed on a well-known benchmark data set, which has 185 instances. Our branch-and-cut prove the optimal value for 179 instances and found the best upper bounds for two instances. The BRKGA-QL found the best upper bounds for the other four instances and the optimal solution in 72% of instances. The results were compared with the best results in the literature, and both methods show robustness and efficiency to solve the FTSP.

Citation

Chaves et al., A parallel branch-and-cut and an adaptive metaheuristic to solve the Family Traveling Salesman Problem. Submitted to Computers & Industrial Engineering.

Article

Download

View A parallel branch-and-cut and an adaptive metaheuristic to solve the Family Traveling Salesman Problem