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

• Ano de defesa: 2016
• Autor(a) principal: Dhein, Guilherme
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Santa Maria; BR; Engenharia Elétrica; UFSM; Programa de Pós-Graduação em Engenharia Elétrica
• Palavras-chave em Português: Algoritmo genético; Algoritmo genético com busca local multiobjetivo; Rotas sincronizadas; Multiple traveling salesman problem; Arc routing; Dispersion metric; Dispersion minimization; Dispersion maximization; Profit collection; Genetic algorithm; Multiobjective genetic local search algorithm; Synchronized routes; CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA
• Link de acesso: http://repositorio.ufsm.br/handle/1/3700

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.