O problema do carteiro chinês dirigido, não dirigido e misto para otimização de rotas com visualização gráfica da solução

Detalhes bibliográficos
Ano de defesa: 2017
Autor(a) principal: Vasconcelos, Rodrigo Bastos
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Universidade Estadual do Ceará
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: https://siduece.uece.br/siduece/trabalhoAcademicoPublico.jsf?id=82751
Resumo: <div style="">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.&nbsp;<span style="font-size: 10pt;">Palavras-chave: Problema do Carteiro Chinês. PCC. PCC dirigido. PCC não dirigido. PCC misto. Coleta de Lixo.</span></div>