Métodos de solução para um problema de roteamento em arcos capacitados e periódicos com múltiplas tarefas

Abstract

Resumo: O Problema de Roteamento em Arcos Capacitado e Periódicos com Múltiplas Tarefas (PCARPMT) é uma variante dos Problemas de Roteamento em Arcos, em que cada arco possui várias demandas, geralmente associada a uma frequência específica ao longo de um horizonte temporal definido. A solução desse problema exige um planejamento que atenda a todas as demandas de maneira otimizada, sem exceder a capacidade dos veículos envolvidos. O objetivo principal desta tese é apresentar métodos de solução para a modelagem matemática aplicada em um problema que envolve a coleta de dados de consumo de energia dos moradores de uma cidade, além da distribuição de panfletos, sendo todas essas tarefas realizadas por leituristas. Embora o problema tenha a essência do clássico PCARP, ele se distingue pelas características inovadoras aqui propostas, como por exemplo, o método de solução em duas fases. Na primeira fase, busca-se minimizar a quantidade de leiturista através de uma penalização pelo uso de cada leiturista, enquanto na segunda fase, o foco é a minimização da distância percorrida pelos leituristas. Ao final de cada fase, ou quando a solução é ótima, realiza-se uma análise para identificar a presença de subciclos. Caso estes existam serão acrescentadas restrições para eliminá-los, garantindo assim uma solução factível. Os subciclos são identificados por algoritmos especialmente desenvolvidos nesta tese. Foram propostos dois métodos de solução e um levantamento bibliográfico foi realizado para comparar o problema abordado nesta tese com os mais semelhantes encontrados na literatura. A implementação do modelo proposto alcançou resultados positivos, com uma melhoria de 95% em relação a solução ótima ou tempo de solução quando o modelo é executado com a penalização adicional pelo uso de cada leiturista. Entre os dois métodos de solução, o segundo que adiciona um grande conjunto de restrições logo na primeira iteração, mostrou-se mais eficiente que o primeiro, que incrementa restrições para eliminar subciclos ao longo do processo. Além disso, foi realizada uma análise do tempo de trabalho dos leiturista e o que este tempo pode influencia na solução do modelo proposto.

Abstract: The Capacitated and Periodic Arc Routing Problem with Multiple Tasks (PCARPMT) is a variant of Arc Routing Problems, where each arc has multiple demands, typically associated with a specific frequency over a defined time horizon. Solving this problem requires planning that meets all demands in an optimized manner without exceeding the capacity of the vehicles involved. The primary objective of this thesis is to present solution methods for a mathematical model applied to a problem involving the collection of energy consumption data from city residents, in addition to the distribution of pamphlets, all tasks carried out by meter readers. Although the problem retains the essence of the classic PCARP, it is distinguished by innovative features proposed here, such as the two-phases solution method. In the first phase, the goal is to minimize the number of meter readers by penalizing the use of each reader, while in the second phase, the focus shifts to minimizing the distance traveled by the meter readers. At the end of each phase, or when an optimal solution is found, an analysis is conducted to identify the presence of subcycles. If subcycles are detected, constraints are added to eliminate them, thus ensuring a feasible solution. These subcycles are identified using algorithms specifically developed in this thesis. Two solutions methods were proposed, and a literature review was conducted to compare the problem addressed in this thesis with similar problems found in the literature. The implementation of the proposed model achieved positive results, with a 95% improvement in relation to the optimal solution or solution time when the model is executed with the additional penalty for the use of each meter reader. Among the two solutions methods, the second, which adds a large set of constraints in the first iteration, proved more efficient than the first, which incrementally adds constraints to eliminate subcycles throughout the process. Additionally, an analysis was performed on the meter readers' working time and how this time influences the solution of the proposed model.