Problemas de roteamento de veículos com dependência temporal e espacial entre rotas de equipes de campo

Abstract

This thesis presents two new routing problems, both with objective functions focused on relative positioning of teams during the routing horizon. The relative positioning results in temporal and spatial dependencies among routes and is quantified with a nonlinear dispersion metric, designed to evaluate the instantaneous distances among teams over a time interval. This metric allows the design of objective functions to approximate teams during routes execution, when minimized, or disperse them, when maximized. Both approximation and dispersion are important routing characteristics in some practical applications, and two new optimization problems are proposed with these opposite objectives. The first one is a variation of the Multiple Traveling Salesman Problem, and its goal is to find a set of tours where the salesmen travel close to each other, minimizing dispersion. A Local Search Genetic Algorithm is proposed to solve the problem. It includes specialized genetic operators and neighborhoods. A new set of benchmark instances is proposed, adapted for the new problem from literature instances. Computational results show that the proposed approach provides solutions with the desired characteristics of minimal dispersion. The second problem is a bi-objective arc routing problem in which routes must be constructed in order to maximize collected profit and dispersion of teams. The maximization of the dispersion metric fosters the scattering of the teams during routing procedure. Usually, profit and dispersion objectives are conflicting, and by using a bi-objective approach the decision maker is able to choose a trade-off between collecting profits and scattering teams. Two solution methods are proposed, a Multi-objective Genetic Algorithm and a Multi-objective Genetic Local Search Algorithm, both specialized in order to exploit the characteristics of the problem. It is demonstrated, by means of computational experiments on a new set of benchmark instances, that the proposed approach provides approximation sets with the desired characteristics.