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

Exportar este item:

Use este identificador para citar ou linkar para este item: http://www.bdtd.uerj.br/handle/1/20473

Tipo do documento:	Dissertação
Título:	Emparelhamentos aplicados ao Problema do Carteiro Chinês Ponderado: uma análise de algoritmos exatos e não exatos
Título(s) alternativo(s):	Matchings applied to the Weighted Chinese Postman Problem: an analysis of exact and not exact algorithms
Autor:	Portella, Leonardo Cordeiro
Primeiro orientador:	Oliveira, Fabiano de Souza
Segundo orientador:	Pinto, Paulo Eustáquio Duarte
Primeiro membro da banca:	Rocha, Danilo Artigas da
Segundo membro da banca:	Coelho, Igor Machado
Terceiro membro da banca:	Bento, Lucila Maria de Souza
Resumo:	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.
Abstract:	The Weighted Chinese Postman Problem is a classic problem of Graph Theory and consists of identifying a route that contains each end at least once, starting and ending at the same vertex, in order to minimize the cost of the route. Classic solution includes identifying a matching between the vertices of odd degree of the graph. Exact algorithms for identifying such matching are difficult to implement and audit. In this context, algorithms that are not exact, simpler that return a lower result than optimal and, in most cases, with a minimum result guarantee compared to the optimal, are used by the industry. In this work we compared the main exact and not exact algorithms. We solved the CPP using these algorithms and using data from different geographic regions. Results for the worst cases for the not exact algorithms are discussed. Mathematical fundamentals and algorithms for problem understanding are also included in this work
Palavras-chave:	Weighted Chinese Postman Problem Matching Heuristics Randomized Teoria dos grafos Heurística Algoritmos de computador Problema do Carteiro Chinês Ponderado CPP Emparelhamento Randomizado
Área(s) do CNPq:	CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Idioma:	por
País:	Brasil
Instituição:	Universidade do Estado do Rio de Janeiro
Sigla da instituição:	UERJ
Departamento:	Centro de Tecnologia e Ciências::Instituto de Matemática e Estatística
Programa:	Programa de Pós-Graduação em Ciências Computacionais
Citação:	PORTELLA, Leonardo Cordeiro. Emparelhamentos aplicados ao Problema do Carteiro Chinês Ponderado: uma análise de algoritmos exatos e não exatos. 2023. 71 f. Dissertação (Mestrado em Ciências Computacionais) - Instituto de Matemática e Estatística, Universidade do Estado do Rio de Janeiro, Rio de Janeiro, 2023.
Tipo de acesso:	Acesso Aberto
URI:	http://www.bdtd.uerj.br/handle/1/20473
Data de defesa:	25-Jan-2023
Aparece nas coleções:	Mestrado em Ciências Computacionais

Arquivos associados a este item:

Arquivo	Descrição	Tamanho	Formato
Dissertação - Leonardo Cordeiro Portella - Completa.pdf	Dissertação completa	4,4 MB	Adobe PDF	Baixar/Abrir Pré-Visualizar ×

Mostrar registro completo do item Recomendar este item Visualizar estatísticas