RESUMO
Os problemas de roteamento têm como objetivo determinar, em um grafo, um circuito de custo
mínimo passando por todos os vértices ou por todas as arestas deste grafo, dependendo se o
problema abordado está na classe de Problemas do Caixeiro Viajante (PCV) ou na classe de
Problemas do Carteiro Chinês (PCC). Este trabalho discorre especificamente sobre os problemas
contidos na classe de Problemas do Carteiro Chinês. Os problemas contidos nesta classe são
NP-completos, deste modo, não existe algoritmo determinístico polinomial que encontre a
solução exata para qualquer instância do problema. O problema tratado consiste em determinar
um caminho mínimo que se inicie em algum vértice do grafo, passe por todos as arestas dele pelo
menos uma vez e retorne ao vértice inicial. As variações deste problema se dividem basicamente
em: Problema do Carteiro Chinês Dirigido (PCCD), Problema do Carteiro Chinês Não Dirigido
(PCCND) e Problema do Carteiro Chinês Misto (PCCM), dependendo da natureza do grafo
utilizado. Este trabalho formaliza uma maneira de calcular o percurso do carteiro chinês em cada
uma destas variações, e fornece também uma visualização gráfica do grafo com uma animação
do percurso realizado pelo carteiro. Além disso, o algoritmo desenvolvido é aplicado em um
exemplo real do problema de coleta de lixo na cidade de Fortaleza.
Palavras-chave: Problema do Carteiro Chinês. PCC. PCC dirigido. PCC não dirigido. PCC
misto. Coleta de Lixo
