Otimização de rotas de varredura sob a ótica do problema do caixeiro-viajante: estudo de caso de Leituristas de uma concessionária de Niterói

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorMeza, Lidia Angulo-
Autor(es): dc.contributorSilva, Diogo Ferreira de Lima-
Autor(es): dc.contributorRoboredo, Marcos Costa-
Autor(es): dc.creatorBrito, Fernando Sondahl-
Data de aceite: dc.date.accessioned2024-07-11T17:45:15Z-
Data de disponibilização: dc.date.available2024-07-11T17:45:15Z-
Data de envio: dc.date.issued2023-08-01-
Data de envio: dc.date.issued2023-08-01-
Fonte completa do material: dc.identifierhttp://app.uff.br/riuff/handle/1/29677-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/756818-
Descrição: dc.descriptionOs leituristas desempenham importante papel na rotina de medição da indústria do saneamento no Rio de Janeiro. Realizam a medição dos hidrômetros, emitem e entregam as contas aos clientes; e, para isso, deslocam-se diariamente por vários quilômetros. O objetivo do presente trabalho é apresentar um modelo que minimize os trajetos percorridos pelos leituristas, à fim de reduzir os riscos de afastamentos por lesão, erros no processo de faturamento e retrabalhos. Para que se alcance o propósito do trabalho, a atividade desempenhada pelos leituristas foi modelada matematicamente a partir de um problema clássico de otimização combinatória, o problema do caixeiro viajante. O modelo clássico foi implementado em conjunto com a formulação Dantzig-Fulkerson-Johnson (DFJ), para que sejam restringidas as soluções definidas com subciclos. Para a não explosão exponencial do problema, as restrições DFJ foram geradas sob demanda a partir da técnica de Lazy Constraints. O modelo matemático foi instanciado no python através da biblioteca pyomo, desse modo, garantindo sua utilização em escala. O trabalho foi então desenvolvido através do estudo de caso, aplicando o modelo matemático definido para dados reais de rotas de leitura realizadas em Niterói. As caracteristicas inerentes às rotas de varredura percorridas pelos leituristas impuserem desafio para a convergência do modelo à solução ótima, sendo necessário adotar novas técnicas para que os objetivos fossem alcançados. Nesse sentido, foi utilizada a técnica de Downsampling para que se reduzisse a complexidade do problema e os requisitos computacionais necessários para a solução do modelo; a técnica foi implementada pela Clusterização de nós do problema através de buffer's. Por fim, a minimização do roteiro de leitura sob a perspectiva do modelo matemático do problema do caixeiro-viajante, com apoio do Downsampling, permitiu a determinação de uma rota ótima para o processo de leitura, reduzindo tanto o trajeto total percorrido pelo leiturista, como o tempo computacional.-
Descrição: dc.descriptionMeter readers play an important role in the measurement routine of the sanitation industry in Rio de Janeiro. They perform the meter readings, issue and deliver bills to customers, and for that, they travel several kilometers daily. The objective of this study is to present a model that minimizes the routes taken by meter readers in order to reduce the risks of injury, billing errors, and rework. To achieve the purpose of the work, the activity performed by the meter readers was mathematically modeled based on a classical combinatorial optimization problem, the traveling salesman problem. The classical model was implemented in conjunction with the Dantzig-Fulkerson-Johnson (DFJ) formulation to restrict solutions defined with subcycles. In order to prevent exponential explosion of the problem, the DFJ constraints were generated on-demand using the Lazy Constraints technique. The mathematical model was instantiated in Python using the Pyomo library, ensuring its scalability. The study was then developed through a case study, applying the defined mathematical model to real data of reading routes carried out in Niterói. The inherent characteristics of the routes traversed by meter readers posed challenges for the convergence of the model to the optimal solution, requiring the adoption of new techniques to achieve the objectives. In this regard, the Downsampling technique was used to reduce the complexity of the problem and the computational requirements needed to solve the model; the technique was implemented through clustering the problem's nodes using buffers. Finally, the minimization of the reading route from the perspective of the mathematical model of the Traveling Salesman Problem, with the support of Downsampling, allowed for the determination of an optimal route for the reading process, reducing both the total distance traveled by the reader and the computation time.-
Descrição: dc.description59 p.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Direitos: dc.rightsOpen Access-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectLeiturista-
Palavras-chave: dc.subjectCaixeiro-viajente-
Palavras-chave: dc.subjectProblema do caixeiro-viajante-
Palavras-chave: dc.subjectPython (Linguagem de programação de computador)-
Palavras-chave: dc.subjectOtimização combinatória-
Palavras-chave: dc.subjectProgramação linear-
Palavras-chave: dc.subjectMeter readers-
Palavras-chave: dc.subjectTraveling Salesman Problem-
Palavras-chave: dc.subjectDFJ-
Palavras-chave: dc.subjectLazy Constraint-
Palavras-chave: dc.subjectPython-
Palavras-chave: dc.subjectPyomo-
Palavras-chave: dc.subjectDownsampling-
Título: dc.titleOtimização de rotas de varredura sob a ótica do problema do caixeiro-viajante: estudo de caso de Leituristas de uma concessionária de Niterói-
Tipo de arquivo: dc.typeTrabalho de conclusão de curso-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.