Planejamento de rotas para leitura de medidores
uma aplicação do problema do carteiro chinês
DOI:
https://doi.org/10.26853/Refas_ISSN-2359-182X_v10n04_02Palavras-chave:
Otimização combinatória, Programação linear, Roteamento em ArcosResumo
Alocar de forma eficiente mão de obra e recursos, garantindo a cobertura de determinada área geográfica e minimizando os custos operacionais, é um desfio que contempla empresas ligadas ao fornecimento de serviços essenciais, como água, gás e energia elétrica. Visando considerar a problemática de gerar rotas para realizar a leitura de medidores de determinada região, foi proposto este estudo. O objetivo foi simular um serviço de leitura, com base em dados geográficos reais, e obter um trajeto fechado de atendimento que garanta a cobertura de todos os medidores, e onde a distância total percorrida seja mínima. Instâncias de teste, baseadas em dados reais, foram geradas. O problema foi modelado como um Problema do Carteiro Chinês não direcionado e resolvido por meio de programação linear, usando um solver comercial. A partir da solução gerada pelo modelo, foi aplicado um algoritmo para obtenção do sequenciamento de atendimento. Os resultados mostraram que, para as instâncias criadas, que contemplaram até 200 vértices e 634 arcos, a metodologia aplicada foi eficiente, gerando a solução ótima de forma rápida.
Downloads
Referências
APARECIDO, W. G. Modelagem e heurísticas para problemas de roteamento de veículos com atendimento suficientemente próximo. Dissertação (Mestrado) – Mestrado em Ciência da Computação, Universidade Federal de Viçosa, Viçosa, 2018.
ASSAD, A. A.; GOLDEN, B. L. Arc routing methods and applications. In: BALL, M.O.; MAGNANTI, T.L.; MONMA, L.C.; NEMHAUSSER, G. L. (Eds). Network Routing. Elsevier, 1995 (Handbooks of Operations Research and Management Science, v. 8).
BRASIL. Lei Nº 11.107, de 06 de abril de 2005. Dispõe sobre normas gerais de contratação de consórcios públicos e dá outras providências. Disponível em: https://www.planalto.gov.br/ccivil_03/_ato2004-2006/2005/lei/l11107.htm Acesso em: 06 jun. 2023.
CORBERÁN, Á.; EGLESE, R.; HASLE, G.; PLANA, I.; SANCHIS, J. M. Arc routing problems: A review of the past, presente, and future. Networks, v. 77, n.1, p. 88-115, 2021.
CORBERÁN, Á.; PRINS, C. Recent results on arc routing problems: An annotated bibliography. Networks, v. 56, p. 50-69, 2010.
DIESTEL, R. Graph teory. 5. ed. Berlin: Springer, 2017.
EISELT, H. A.; GENDREAU, M.; LAPORTE, G. Arc routing problems, Part 1: The Chinese postman problem. Operations Research, v. 43, p. 231–242, 1995.
EULER, L. Leonhard Euler and the Königsberg bridges. Scientific American, v. 189, n. 1, p. 66-70, 1953.
GOOGLE EARTH. Google Earth 10.35.3.4, 2023. Disponível em: https://www.earth.google.com/web Acesso em: 14 mar. 2023.
GUROBI OPTIMIZER INC. Gurobi Optimizer version 10.0.1 (programa), 2023. Disponível em: https://www.gurobi.com Acesso em: 28 mar. 2023.
IRNICH, S. Solution of real-world postman problems. European Journal of Operational Research, v. 190, p. 52–67, 2008.
LIMA, L. E. S. de. Modelagem do roteamento de leituristas: uma abordagem cluster first – route second para o Problema do Carteiro Chinês Capacitado. Dissertação (Mestrado) - Mestrado em Engenharia da Produção, Universidade Federal de Pernambuco, Recife, 2021.
LUKMAN, R. K.; CERINŠEK, M.; VIRTIČ, P; HORVAT, B. Improving efficient resource usage and reducing carbon dioxide emissions by optimizing fleet management for winter services. Journal of Cleaner Production, v. 177, p. 1-11, 2018.
PAPADIMITRIOU, C. On the Complexity of Edge Traversing. Journal of A.C.M., v. 23, n. 3, p. 544-554, 1976.
SHAFAHI, A.; HAGHANI, A. Generalized maximum benefit multiple chinese postman problem. Transportation Research Part C: Emerging Technologies, v. 55, p. 261-272, 2015.
SILVA, A. A. da. Uma abordagem heurística para o problema do carteiro chinês capacitado na coleta de lixo urbano. Dissertação (Mestrado) - Mestrado em Engenharia da Produção, Universidade Federal de Pernambuco, Pernambuco, 2020.
STERN, H. I; DROR, M. Routing electric meter readers. Computers & Operations Research, v. 6, n. 4, p. 209-223, 1979.
VASCONCELOS, R. B. O problema do carteiro chinês dirigido, não dirigido e misto para otimização de rotas com visualização gráfica da solução. Dissertação (Mestrado) - Mestrado em Ciência da Computação, Universidade Estadual do Ceará, Fortaleza, 2017.
WØHLK, S.; LAPORTE, G. A fast heuristic for large-scale capacitated arc routing problems. Journal of the Operational Research Society, v. 68, n. 12, p. 1877-1887, 2018.
YILMAZ, M.; ÇODUR, M. K.; YILMAZ, H. Chinese postman problem approach for a largescale conventional rail network in Turkey. Tehnicki Vjesnik-Technical Gazette, v. 24, n. 5, p. 1471-1477, 2017.
ZIVIANI, N. Projeto de algoritmos. São Paulo: Cengage, 2019.
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Copyright (c) 2024 Refas - Revista Fatec Zona Sul
Este trabalho está licenciado sob uma licença Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
1 - As fontes dos dados, as autorizações pertinentes e os textos publicados na revista são de inteira responsabilidade de seus autores.
2 - É permitida a reprodução, desde que citada a fonte e o autor.
3 - Após o artigo aprovado, o autor principal deverá enviar declaração, conforme o modelo:
Refas - Revista Fatec Zona Sul
Autorização par publicação
(Nome do autor), (no caso de vários autores citar todos), autorizo (ou autorizam, no caso de diversos autores) a publicação do artigo (nome do artigo), com exclusividade para a primeira publicação pela Revista Fatec Zona Sul, em meio eletrônico.
A contribuição é original e inédita, e não está sendo avaliada para publicação por outra revista; caso contrário, deve-se justificar em "Comentários ao editor".
Dados de todos os autores:
Nome completo:
Instituição:
E-mail:
Telefone:
Obs.: Informar os códigos dos serviços DDD e DDI.
Assinatura do autor principal: ____________________________________
Aviso de Direito Autoral
Autores que publicam nesta revista concordam com os seguintes termos:
a) Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
b) Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto antes ou durante o processo editorial, já que isso pode gerar alterações produtivas, bem como aumentar o impacto e a citação do trabalho publicado.
c)Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Licença Creative Commons CC Attribution-NonCommercial-NoDerivatives 4.0, acessável em Licença Creative Commons Attribution, que permite o compartilhamento do trabalho com reconhecimento da autoria e publicação inicial nesta revista.