Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/259720
Full metadata record
DC FieldValueLanguage
dc.contributor.CRUESPUNIVERSIDADE ESTADUAL DE CAMPINASpt_BR
dc.identifier(Broch.)pt_BR
dc.descriptionOrientador: Paulo Morelato Françapt_BR
dc.descriptionDissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computaçãopt_BR
dc.format.extent117p. : il.pt_BR
dc.format.mimetypeapplication/pdfpt_BR
dc.languagePortuguêspt_BR
dc.typeDISSERTAÇÃOpt_BR
dc.titleAlgoritmos para o problema de roteamento de leituristaspt_BR
dc.title.alternativeAlgrorithms for the routing meter readers problempt_BR
dc.contributor.authorUsberti, Fábio Luiz, 1982-pt_BR
dc.contributor.advisorFrança, Paulo Morelato, 1949-pt_BR
dc.contributor.institutionUniversidade Estadual de Campinas. Faculdade de Engenharia Elétrica e de Computaçãopt_BR
dc.contributor.nameofprogramPrograma de Pós-Graduação em Engenharia Elétricapt_BR
dc.subjectProgramação heurísticapt_BR
dc.subjectOtimização combinatóriapt_BR
dc.subjectPesquisa operacionalpt_BR
dc.subjectTeoria dos grafospt_BR
dc.subject.otherlanguageArc routing problemen
dc.subject.otherlanguageRural postman problemen
dc.subject.otherlanguageCombinatorial optimizationen
dc.subject.otherlanguageOperational researchen
dc.description.abstractResumo: Esse trabalho se dedicou ao estudo dos algoritmos para roteamento de leituristas, incluindo propostas de alteração que resultem na melhoria da qualidade dos resultados. A motivação é proveniente da alta demanda por soluções computacionais para esse problema, ainda pouco estudado devido às peculiaridades que lhe são inerentes. Encontram-se na literatura duas heurísticas, de estratégias distintas e antagônicas para esse problema. Uma das heurísticas procura construir a rota ignorando a restrição de capacidade, para posterior particionamento dessa rota em subrotas, cada qual destinada a um leiturista (¿route first, cluster second¿). A outra heurística, em uma abordagem inversa, primeiramente subdivide a região de trabalho dos leituristas, para posterior roteamento dessas partições (¿cluster first, route second¿). Essas duas heurísticas foram testadas exaustivamente, tornando possível localizar aspectos sujeitos à melhoria, dando origem a duas novas heurísticas. Foi gerada uma base de testes contendo 144 instâncias que simulam as condições reais de trabalho dos leituristas, classificadas de acordo com o tamanho e dificuldade. A partir das soluções provenientes dos quatro algoritmos foi possível analisá-los comparativamente, avaliando o melhor em um âmbito geral (envolvendo todos os algoritmos) e específico (algoritmos de mesmo tipo, ¿route first cluster second¿ ou ¿cluster first route second¿), segundo critérios de qualidade pré-definidos: número de rotas, tempo de percurso, violação da carga horária e tempo computacional. Os resultados revelam que os novos algoritmos foram melhores tanto na comparação específica quanto na comparação geralpt
dc.description.abstractAbstract: This work¿s main study object consists on algorithms for routing meter readers, from which proposals towards solution¿s improvement are made. The demand for computational results concerning this problem, added to literature little attention due to its inherited peculiarities, has been the outmost motivation. Two preexisting heuristics from literature, with distinct and antagonic strategies, are pointed out. One of these heuristics atempt to create a single route, dismissing the capacity restriction, and then partitionates this route into subroutes, each of them destinated to one meter reader (route first, cluster second). The other heuristic, in an inverse approach, first splits the meter reader¿s working area, and only then routes each of these partitions (cluster first, route second). The two heuristics were tested to exaustion, allowing enumeration of weak aspects subject to improvement. Therefore, two new heuristics were developed, based upon the originals, however adapted in order to outperform solution¿s quality. A testing base containing 144 instances was generated, simulating meter readers realistic labor¿s conditions, classified by size and difficulty. Through solutions provided by the four algorithms, comparison analyses have taken place, evaluating in a general (involving all algorithms) and specific manner (same kind algorithms, i.e., route first, cluster second or cluster first, route second), considering four predefined quality criteria: number of routes, deadheading time, violation of shiftwork time and computational time. Results revealed that the new algorithms achieved better solutions on specific and general comparisonsen
dc.publisher[s.n.]pt_BR
dc.date.issued2007pt_BR
dc.identifier.citationUSBERTI, Fábio Luiz. Algoritmos para o problema de roteamento de leituristas. 2007. 117p. Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação, Campinas, SP. Disponível em: <http://www.repositorio.unicamp.br/handle/REPOSIP/259720>. Acesso em: 9 ago. 2018.pt_BR
dc.description.degreelevelMestradopt_BR
dc.description.degreedisciplineAutomaçãopt_BR
dc.description.degreenameMestre em Engenharia Elétricapt_BR
dc.contributor.committeepersonalnameLyra Filho, Christianopt_BR
dc.contributor.committeepersonalnameCosta, Alysson Machadopt_BR
dc.date.defense2007-06-06T00:00:00Zpt_BR
dc.date.available2018-08-09T05:57:31Z-
dc.date.accessioned2018-08-09T05:57:31Z-
dc.description.provenanceMade available in DSpace on 2018-08-09T05:57:31Z (GMT). No. of bitstreams: 1 Usberti_FabioLuiz_M.pdf: 37565259 bytes, checksum: cddb8b852bd82318a8c784f1f223a076 (MD5) Previous issue date: 2007en
dc.identifier.urihttp://repositorio.unicamp.br/jspui/handle/REPOSIP/259720-
Appears in Collections:FEEC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Usberti_FabioLuiz_M.pdf36.68 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.