Algoritmos exatos e heurísticos para problemas seletivos de roteamento de veículos com restrições de cobertura

Abstract

In this work, we investigate two Combinatorial Optimization problems: the Min-Max Selective Vehicle Routing Problem and the Multi-vehicle Covering Tour Problem. The former models the design of energy-efficient sensor networks; the latter models the delivery of mobile health-care facilities. We propose a Column Generation algorithm and two heuristics for the Min-Max Selective Vehicle Routing Problem. Computationalexperiments were performed to assess the quality of the solutions obtained by these heuristics in comparison to those given by the methods found in the literature. The experiments indicate that the methods proposed here for the Min-Max Selective Vehicle Routing Problem are not as efficient and effective as those found in the literature for the majority of considered instances. For example, one of the proposed heuristics provided new best upper-bounds for seven out of seventy instances considered, though this heuristic required much more time than that required by the other methods. In the context of the Multi-vehicle Covering Tour Problem, we propose a Branch-and- Price algorithm and a heuristic. The Branch-and-Price algorithm solved to proven optimality nine out of thirty instances considered in the computational experiments. In conclusion, one can observe that the algorithm proposed for the second problem had superior performance when compared to the algorithm proposed for the first one, although the same set of techniques were applied for solving both problems