In this article, we propose a new variant of the family traveling salesman problem (FTSP). The FTSP is an NP-hard problem that generalizes the traveling salesman problem. In the FTSP, the set of cities is partitioned ...
详细信息
In this article, we propose a new variant of the family traveling salesman problem (FTSP). The FTSP is an NP-hard problem that generalizes the traveling salesman problem. In the FTSP, the set of cities is partitioned into several families and one wants to find the minimum cost route that visits a given number of cities in each family. A new variant arises by introducing incompatibilities between families, that is, cities from incompatible families cannot be visited in the same route, and it is called the FTSP with incompatibility constraints (FTSP-IC). We propose compact and non-compact mixed integer linear programming models for the FTSP-IC where the incompatibility constraints are modeled by defining paths in a compatibility graph for each family. Additionally, we present a set of valid inequalities motivated by the incompatible families. The non-compact models and the valid inequalities were tested using a branch-and-cut framework. To evaluate the models we generated incompatibility matrices for benchmark instances of the FTSP, which are available in the website . With the branch-and-cut algorithm, we were able to obtain the optimal value of instances with up to 127 nodes. We also developed an ant colony optimization (ACO) algorithm and an iterated local search algorithm (ILS) to address the largest sized instances. Both metaheuristics are able to provide solutions for instances that the branch-and-cut algorithm cannot address and to improve the majority of the upper bounds obtained by the branch-and-cut algorithm in less computational time.
暂无评论