Hibridização de heurísticas, com programação inteira e mineração de dados, para a solução de duas variantes do problema do caixeiro viajante

Abstract

In this work, strategies are presented to solve, in an efficient way, two generalizations of the traveling salesman problem. The first, prize-collecting covering tour problem (PCCTP), it is motivated by the need to obtain a minimum cost route for itinerant staff, who assist communities far from large urban centers. While the second, the prize-collecting traveling salesman problem (PCTSP), has several real applications such as planning helicopter routes for offshore oil platforms, creating routes for tourists, and distributing products to resellers. To solve such problems, heuristic and exact strategies were proposed. For the PCCTP, we proposed a new mathematical formulation, new valid inequalities, seven new reduction rules, and four hybrid heuristics, which combine a state-of-the-art heuristic with integer linear programming (ILP) and data mining. For the PCTSP, a separation procedure is proposed for the cut-sets constraints of a literature’s formulation, a hybrid heuristic that combines GRASP and RVND with PLI, and a new set of instances. In order to validate the proposed strategies, computational experiments were carried out on instances already known in the literature and new ones presented in this work. The results indicate the benefit of the new formulation and the combinations with ILP and data mining, achieving better quality solutions in less processing time for most tests, and proving unprecedented optimality for several cases.