Assume that instead of knowing exactly which cities the traveling salesman wishes to visit he only knows how many cities he has to visit in a subset of cities, which is called a family. In this case, besides determining the best order to visit the cities, like in the TSP, he also needs to choose which cities are going to be visited in each family. Let us consider that we have a depot and a partition of the set of cities into families. We intend to establish one route that begins and ends at the depot and visits a given number of cities in each family. The costs of traveling between each pair of cities and between the depot and each city are known. Hence, we want to determine the minimum cost route that satisfies the conditions stated previously. The problem described previously is the Family Traveling Salesman Problem (FTSP). Even though the FTSP is not widely studied in the literature, it seems to be a natural extension of routing problems that have a wide variety of real world applications.
We propose several models for the FTSP and provide a theoretical comparison between them. With this models we were able to obtain the optimal value of benchmark instances with 127 nodes which have never been solved up to optimality. For the higher dimension instances, we propose a metaheuristic that was able to improve the optimal values of 8 out of 9 benchmark instances whose optimal value remains unknown.
| Subject : | : | Abstracts |
| Topics | : | TSP Variants |
| PDF version | : |  PDF version |
