Resumo: 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%.
| Identifer | oai:union.ndltd.org:IBICT/oai:dspace.c3sl.ufpr.br:1884/26945 |
| Date | 11 May 2012 |
| Creators | Konowalenko, Flávia |
| Contributors | Costa, Deise Maria Bertholdi, 1969-, Nunes, Luiz Fernando Teixeira, Universidade Federal do Paraná. Setor de Tecnologia. Programa de Pós-Graduaçao em Métodos Numéricos em Engenharia |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Repositório Institucional da UFPR, instname:Universidade Federal do Paraná, instacron:UFPR |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0175 seconds