Abordagens heurísticas, meta-heurísticas e de programação linear inteira para o Covering Salesman Problem

Abstract

In this term paper, a variation of the Traveling Salesman Problem, called The Covering Salesman Problem, was studied. In this problem, a set of cities and a matrix of distances between them are given. The objective is to find a minimum cost cycle in a subset of cities, within the set of n given cities, such that each city that is not part of the cycle is within coverage distance S of some city that is in the cycle. Throughout the work, an approximation algorithm based on integer linear programming called Lagrangian Relaxation, a Greedy heuristic and two meta heuristics called Tabu Search and Ant Colony Optimization were proposed to solve the problem. The strategy used from these approaches was to divide the problem into two classic problems: The Set Coverage Problem and the Traveling Salesman Problem. In this way, the Lagrangian Relaxation, the Greedy Heuristic and the Tabu Search were used to solve the Set Coverage Problem firstly, with the objective of minimizing the number of cities that are part of the cycle, so that Ant Colony Optimization can solve the problem. Traveling Salesman Problem, with the answers given by the algorithms responsible for solving the first part, seeking the Hamiltonian cycle of minimum cost among the selected cities. For the computational experiments, the results obtained by an algorithm from the literature based on local search called LS2 were used for comparison purposes. The results were not satisfactory, with the developed algorithms not managing to obtain any better response than the one found by LS2, which shows that the strategy used in this work is inefficient to solve the Covering Salesman Problem. However, it was observed that, for practically all the cycles generated by the elaborated algorithms, the amount of vertices present in them was smaller than in the LS2 algorithm, this caused the problem of this work to be re-elaborated, associating a cost to add the cover vertices to the cycle. With this CSP variation, the algorithms that used the approach of this work presented better results than the LS2 algorithm in most cases where the cost of adding new coverage vertices to the cycle is high.