Emparelhamentos aplicados ao Problema do Carteiro Chinês Ponderado: uma análise de algoritmos exatos e não exatos

• Ano de defesa: 2023
• Autor(a) principal: Portella, Leonardo Cordeiro
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade do Estado do Rio de Janeiro; Centro de Tecnologia e Ciências::Instituto de Matemática e Estatística; Brasil; UERJ; Programa de Pós-Graduação em Ciências Computacionais
• Palavras-chave em Português: Weighted Chinese Postman Problem; Matching; Heuristics; Randomized; Teoria dos grafos; Heurística; Algoritmos de computador; Problema do Carteiro Chinês Ponderado; CPP; Emparelhamento; Randomizado; CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://www.bdtd.uerj.br/handle/1/20473

O Problema do Carteiro Chinês Ponderado é um problema clássico da Teoria de Grafos e consiste em identificar um percurso que contém cada aresta pelo menos uma vez, iniciando e terminando no mesmo vértice, de forma a minimizar o custo do percurso. A solução clássica inclui a identificação de um emparelhamento entre os vértices de grau ímpar do grafo. Algoritmos exatos para identificar tal emparelhamento são de difícil implementação e auditoria. Neste contexto, algoritmos não exatos, mais simples e geralmente mais rápidos, que retornam um resultado inferior ao ótimo e, alguns, com uma garantia de resultado mínimo comparado com o ótimo, são utilizados pela indústria. Neste trabalho comparamos os principais algoritmos exatos e não exatos. Solucionamos o CPP utilizando estes algoritmos e empregando dados de diversas regiões geográficas. Resultados para os piores casos para os algoritmos não exatos são discutidos. Fundamentos matemáticos para a compreensão do problema e dos algoritmos também estão inclusos.