Este trabalho aborda o problema de rotear capelinhas entre fiéis da religião católica em uma paróquia na cidade de Londrina, Paraná.
Na religião católica, o termo "capelinhas" é utilizado para designar a estátua da santa Nossa Senhora de Aparecida. Nessa tradição, a estátua deve sair da paróquia, circular pelas residências de um conjunto de fiéis, e então retornar à paróquia.
Embora possa parecer uma simples tradição, a circulação das capelinhas é um tanto complexa quando posta em prática, devido a necessidade de articular pessoas e necessitar de um trajeto otimizado.
O número de participantes nesta tradição é muito expressivo. De acordo com a Arquidiocese de Curitiba, estimava-se que em 2018 a tradição envolveu mais de 900 mil pessoas mensalmente, somente na região de Curitiba. Assim, a quantidade de pessoas que poderão ser atingidas com este estudo foi tida como motivação para desenvolvimento do trabalho.
O problema de roteamento de capelinhas pode ser interpretado como um problema de caixeiro viajante, consistindo em circular uma capelinha por nós de um grafo.
Sendo assim, para solucionar o problema é utilizado um algoritmo baseado na metaheurística Iterated Local Search, o qual emprega uma busca local baseada numa heurística 2-exchange, que consiste em permutar a posição de dois vértices na rota.
Na paróquia em estudo, são utilizadas 20 capelinhas, que visitam mais de 100 lares no período de um mês. No trabalho desenvolvido, os fiéis foram divididos em setores e o problema consistiu em resolver um caixeiro viajante por setor.
O algoritmo proposto foi implementado utilizando a linguagem C++ e testado com um setor contendo um conjunto de 22 vértices (fiéis), incluindo a paróquia. Como resultado, o algoritmo gerou uma sequência de visita que a capelinha deve seguir para garantir uma rota minimizada em distância.
Para facilitar o planejamento da paróquia, a rota foi plotada em um mapa com auxílio do software QGIS e apresentada ao responsável da paróquia, o qual considerou os resultados satisfatórios.