Modelagem e Otimização de Rotas de Coleta de Resíduos Urbanos via Heurísticas de VRP

- 337618
Abstract
Favorite this paper
How to cite this paper?
Abstract

A gestão da coleta de resíduos sólidos urbanos representa um desafio logístico em municípios
de pequeno e médio porte. No município de Jandaia do Sul (PR), a ausência de rotas de coleta
bem definidas pode resultar em sobreposição de trajetos e uso ineficiente da frota, aumentando o
tempo de deslocamento e os custos operacionais do serviço.
Para mitigar essas ineficiências, modelou-se a malha viária municipal utilizando dados do
OpenStreetMap. Nesse modelo, as interseções (esquinas) foram convertidas em vértices de um
grafo urbano, enquanto os segmentos de via definem as arestas. Essa abstração permite abordar a
logística de coleta sob a ótica da otimização combinatória, especificamente como um Problema de
Roteirização de Veículos (PRV ou Vehicle Routing Problem - VRP) [4].
Formalmente, seja G = (V, E) um grafo onde V = {0, 1, . . . , n} compreende o depósito e os
pontos de coleta, e E representa as conexões entre eles. Cada aresta possui um custo associado cij ,
correspondente à distância entre os nós. . O objetivo central consiste em otimizar as rotas de coleta
de resíduos urbanos, buscando a redução de uma função de avaliação associada aos deslocamentos,
expressa por:
min ∑ᵢ₌₀ⁿ ∑ⱼ₌₀ⁿ cᵢⱼ xᵢⱼ (1)
A formulação completa inclui restrições de visita única, conservação de fluxo e retorno ao
depósito, típicas do Problema de Roteirização de Veículos.
As soluções iniciais foram geradas por meio da heurística de economia de Clarke e Wright
[1], amplamente reconhecida pela sua eficiência computacional em problemas de roteirização. O
método baseia-se no cálculo das reduções de distância obtidas ao consolidar rotas individuais,
expandindo-as progressivamente. Estudos indicam que essa abordagem permanece eficaz para
problemas clássicos [3] e adaptável a cenários modernos [2]. A base topológica para essa modelagem
é apresentada na Figura 1.
A aplicação preliminar da heurística resultou em um conjunto inicial de trajetórias sobre o
grafo urbano, conforme ilustrado na Figura 2. Posteriormente, essas rotas foram refinadas via
operador de busca local 2-opt, técnica clássica voltada à redução da distância total e eliminação
de cruzamentos de arcos.
Em uma etapa subsequente, buscou-se aumentar o realismo da modelagem da rede viária.
Utilizando a biblioteca OSMnx, as distâncias foram recalculadas sobre o grafo real por meio do
algoritmo de Dijkstra. Nesta fase, a construção das rotas empregou a heurística do Vizinho Mais
Próximo (Nearest Neighbor ), enquanto a organização do cronograma semanal foi estruturada pela
heurística de varredura angular (sweep), responsável por agrupar os pontos em setores geográficos
ao redor do depósito. O refinamento final produziu trajetórias condizentes com a malha viária real
e com a divisão operacional da coleta (Figura 3).
Os resultados preliminares demonstram que a integração dessas heurísticas gera rotas mais
compactas e espacialmente organizadas, reduzindo a redundância de trajetos. Como continuidade
do trabalho, pretende-se incorporar restrições de capacidade de carga dos veículos e realizar uma
comparação quantitativa entre as rotas propostas e o planejamento logístico atual. Este trabalho
mostra como a integração de heurísticas clássicas de roteirização com dados geoespaciais reais pode
apoiar o planejamento logístico da coleta urbana em municípios de pequeno porte.

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!

Institutions
  • 1 Universidade Federal do Paraná
Track
  • ST06 - Mathematics Applied to Engineering 1
Keywords
roteirização de veículos
otimização logística
grafo urbano