O problema de roteamento periódico e capacitado em arcos com movimentos contínuos

Abstract

Resumo: Esse trabalho aborda o Problema de Roteamento Periódico e Capacitado em Arcos, Periodic Capacitated Arc Routing Problem (PCARP), que pode ser definido como um problema de roteamento em arcos envolvendo um horizonte de tempo composto por mais de um período, os quais podem ser formados por qualquer fração temporal desde que discretas. Um ou mais veículos, ao fazerem suas rotas, devem executar da melhor maneira possível as tarefas que estão associadas a cada arco sem exceder sua capacidade e respeitando as frequências exigidas. Esse trabalho visa classificar as pesquisas acerca do PCARP por meio de uma proposta taxonômica que considera características físicas, foco aplicável ou teórico e abordagem resolutiva. Outra contribuição é um estudo aplicado à inspeção de ferrovias, o qual é classificado como PCARP com Movimentos Contínuos. Rotas com movimentos contínuos são caracterizadas por não terem a obrigatoriedade de serem iniciadas e terminadas em um depósito. O problema tem sua formulação matemática apresentada e sua a resolução é feita utilizando métodos exato, heurístico e híbridos. O método exato consiste na utilização de um solver comercial e a heurística utilizada é um novo algoritmo de Otimização de Colônia de Formigas, Ant Colony Optimization (ACO). Ambos têm seus pontos fortes que se complementam, sendo assim foram propostas três abordagens híbridas. A primeira consiste na utilização da colônia de formigas como solução inicial para o modelo exato, e as outras duas abordagens são variações do algoritmo Busca Iterativa em Espaço Restrito, Iterative Restricted Space Search (IRSS). A IRSS é baseada na exploração estratégica do espaço de soluções de um dado problema que, nesse trabalho, será auxiliada pelo algoritmo ACO. Os resultados alcançados mostram que as estratégias de resolução propostas são capazes de superar os resultados alcançados pelo solver comercial. Palavras-chave: Problema de Roteamento Periódico e Capacitado em Arcos 1. Movimentos Contínuos 2. Otimização da Colônia de Formigas 3. Busca Iterativa em Espaço Restrito 4. Manutenção e Inspeção de Ferrovias 5.

Abstract: The Periodic Capacitated Arc Routing Problem (PCARP) can be defined as an arc routing problem that involves a time horizon, which is greater than one period that can be composed by any fraction of time. One or many vehicles, while into routes, must perform, in the best way possible, all tasks in the arcs without exceeding their capacities and attending the required frequencies. This work classifies researches about PCARP using a taxonomy that considers physical features, applied or academic focus and resolution approach. An additional contribution is a study based on inspection of railroads; this one is classified as PCARP with Continuous Moves. Routes with continuous moves do not need a depot as a starting or finishing point. This work presents the mathematical formulation for the problem and tackles it with exact, heuristic and hybrid methods. The exact approach consists of the use of a commercial solver, and the heuristic is a new Ant Colony Optimization (ACO) algorithm. Both have strengths that may be combined to compose hybrid approaches, three of them are explored. The first one uses the ACO to form an initial solution to the solver, and the two others are variants of the Iterative Restricted Space Search (IRSS) framework. The IRSS strategically exploits the solution space of one problem assisted by an algorithm, in this case, the ACO. The results achieved showed that the strategies proposed are able to overcome the ones from the commercial solver. Keywords: Periodic Capacitated Arc Routing Problem 1. Continuous Moves 2. Ant Colony Optimization 3. Iterative Restricted Space Search 4. Inspection and Maintenance in Railways 5.