Problema do carteiro chinês não orientado e misto para a otimização de rotas na cidade de Irati /PR

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorCosta, Deise Maria Bertholdi, 1969--
Autor(es): dc.contributorNunes, Luiz Fernando Teixeira-
Autor(es): dc.contributorUniversidade Federal do Paraná. Setor de Tecnologia. Programa de Pós-Graduação em Métodos Numéricos em Engenharia-
Autor(es): dc.creatorKonowalenko, Flávia-
Data de aceite: dc.date.accessioned2025-09-01T11:21:10Z-
Data de disponibilização: dc.date.available2025-09-01T11:21:10Z-
Data de envio: dc.date.issued2024-05-16-
Data de envio: dc.date.issued2024-05-16-
Data de envio: dc.date.issued2012-
Fonte completa do material: dc.identifierhttps://hdl.handle.net/1884/26945-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/1884/26945-
Descrição: dc.descriptionOrientadora: Profa. Dra. Deise Maria Bertholdi Costa-
Descrição: dc.descriptionCoorientador: Prof. Dr. Luiz Fernando Nunes-
Descrição: dc.descriptionDissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas e Setor de Tecnologia, Programa de Pós-Graduação em Métodos Numéricos em Engenharia. Defesa: Curitiba, 01/02/2012-
Descrição: dc.descriptionBibliografia: fls. 83-87-
Descrição: dc.descriptionÁrea de concentração: Programação matemática-
Descrição: dc.descriptionResumo: O Problema do Carteiro Chinês caracteriza-se pela roteirização de arcos e tem como objetivo a cobertura de arcos de um grafo, criando uma rota que passe ao menos uma vez em cada um destes arcos. O problema pode ser subdividido em casos, de acordo com o tipo do grafo analisado. Entre os casos, tem-se o Problema do Carteiro Chinês Não-Orientado, cuja característica é que nenhuma das arestas do grafo associado ao problema possui orientação. Um segundo caso, é denominado Problema do Carteiro Chinês Orientado, quando todos os arcos são orientados, e finalmente, um terceiro caso que é chamado de Problema do Carteiro Chinês Misto, que possui arcos (orientados) e arestas (sem orientação ou duplo sentido). Nesta pesquisa, o estudo do Problema do Carteiro Chinês foi aplicado na área central da cidade de Irati/PR, região representada por um grafo caracterizado como misto, pois possui ruas de mão única e também ruas de mão dupla. Um primeiro estudo foi otimizar a rota percorrida pelo caminhão de coleta de resíduos sólidos. Nesta parte, foi aplicado o caso Misto e para a resolução utilizou-se modelos de programação Linear Inteira. Considerando-se ainda a mesma região da cidade, porém sem levar em conta as orientações das ruas, buscou-se também uma solução para do Problema do Carteiro Chinês Não Orientado. Os resultados encontrados são para a construção da rota para os varredores de ruas, entregadores de correspondências, ou outros serviços que exijam coberturas de arcos e que possam ser executados por funcionários percorrendo as ruas à pé, ou seja, sem o uso de veículos. Para este último caso utilizou-se uma heurística. Os resultados obtidos foram satisfatórios, visto que o melhor valor foi para o problema do grafo misto, através do modelo exato de programação linear inteira, o qual otimizou a rota percorrida pelo caminhão de coleta de resíduos sólidos em 12,67%.-
Descrição: dc.descriptionAbstract: The Chinese Postman Problem distinguishes by the routing of arches, targeting to cover all the arches of a graph, passing through them at least once. The problem may have particular characteristics which are presented according to the kind of graph being analyzed. So, the Chinese Postman Problem is a called a Nonoriented one when none of the edges of the analyzed problem has one orientation. It is called an Oriented Chinese Postman Problem when all of the arches are oriented and, finally, it’s called a Mixed Chinese Postman Problem when it has arches (oriented) and edges (non-oriented or double-guided). The present research was developed at the central area of Irati/PR, a place marked as Mixed, because it has one-way roads and also two-way roads. The objectives were to optimize the route traveled by the solid waste collect truck. It demanded the usage of Full Linear Programming models. Using the same analyzed area, but without considering the way of the roads, it was pursued a solution to the Non-Oriented Chinese Postman Problem, seeking the use of the results by street dustmen, mailmen and other services which require the cover of arches and may be executed by workers wandering the roads on foot (without using vehicles). This last case demanded the usage of a heuristic process. The obtained results were satisfactory, being that the greatest value was given to the mixed graph case, through the exact full linear programming model, which has optimized the route traveled by the solid waste collect truck in 12,67%.-
Formato: dc.format108f. : il. [algumas color.], grafs., tabs.-
Formato: dc.formatapplication/pdf-
Formato: dc.formatapplication/pdf-
Relação: dc.relationDisponível em formato digital-
Palavras-chave: dc.subjectAlgorítmos-
Palavras-chave: dc.subjectProgramação linear-
Palavras-chave: dc.subjectRotas comerciais-
Palavras-chave: dc.subjectAnálise numérica-
Título: dc.titleProblema do carteiro chinês não orientado e misto para a otimização de rotas na cidade de Irati /PR-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositório Institucional - Rede Paraná Acervo

Não existem arquivos associados a este item.