Técnicas da Pesquisa Operacional aplicadas a um Problema de Cobertura de Arcos
DOI:
https://doi.org/10.5540/tema.2004.05.02.0347Resumo
Neste trabalho, é proposta uma metodologia para a obtenção de uma solução otimizada de um problema de cobertura de arcos utilizando algumas técnicas da Pesquisa Operacional. A metodologia aqui apresentada consta de duas fases. Na 1a fase utiliza-se um algoritmo genético aplicado ao problema das p-medianas cuja resposta pode ser melhorada com a heurística clássica de Teitz e Bart. A partir da definição das medianas necessárias para o problema, determina-se os grupos (clusters) de pontos de demanda a serem designados a cada mediana através do algoritmo de Gillett e Johnson Adaptado. Na 2a fase, a partir da definição dos clusters de atendimento, é feito o roteamento em cada cluster para ter-se a seq¨uência de pontos a serem transpassados, utilizando o modelo matemático do Problema Carteiro Chinês. A validação da metodologia foi obtida através da aplicação da mesma a um estudo de caso comparando-se a solução otimizada com a solução adotada por ocasião a coleta de dados.Referências
[1] H. Barbosa, “Introdução aos Algoritmos Genéticos”, CNMAC, Gramado, RS, 1997.
L.D. Bodin, B.L. Assad e A. Ball, Routing and Scheduling of Vehicles and Crew, The State of the Art. Computers & Ops. Res., 10 (1983), 69-211.
E.S. Corrêa, M.T.A. Steiner, A.A. Freitas e C. Carnieri, A Genetic Algorithm for solving a Capacitated P-Median Problem. Numerical Algorithms, Kluwer Academic Publishers, 35 (2004), 373-388.
D.M.B. Costa, M.T.A. Steiner, C. Carnieri, L.V.S. Zamboni e A.C.L. da Silva, Técnicas da Pesquisa Operacional na Otimização dos Serviços Postais, Gestão & Produção, 8, No. 1 (2001), 37-55.
J. Edmonds e E. L. J. Matching, Euler tour and the Chinese Postman, Mathematical Programming, 5 (1973), 88-124.
R.W. Eglese e H. Murdock, Routing Road Sweepers in a Rural Area, JORS, 4 (1991), 281-288.
G. Ghiani e G. Improta, An Algorithm for the Hierarchical Chinese Postman Problem, JORS, 26 (2000), 27-32.
D. Goldberg, “Genetic Algorithms in Search, Optimization, and Machine Learning”, Addison-Wesley, Menlo Park, CA, 1986.
K. Mei-ko, Graphic Programming using Odd and Even Points, Chinese Mathematics, 1 (1962), 273-277.
E.L.F. Senne e L.A.N. Lorena, Abordagens Complementares para o Problema de P-Medianas, Revista Produção, 13 (2003), 78-87.
A. Smiderle, “Técnicas da Pesquisa Operacional Aplicadas a um Problema de Cobertura de Arcos”, Dissertação de Mestrado, PPGMNE, UFPR, PR, 2001.
H.I. Stern e M. Dror, Routing Eletric Meter Readers, Computers & Operations Research, 6 (1978), 209-223.
M.B. Teitz e P. Bart, Heuristics Methods for Estimating the Generalized Vertex Median of a Weighted Graph, Operations Research, 16 (1968), 955-961.
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Política para Periódicos de Acesso Livre
Autores que publicam nesta revista concordam com os seguintes termos:
- 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 Attribution que permite o compartilhamento do trabalho com reconhecimento da autoria e publicação inicial nesta revista.
- 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.
- 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 (Veja O Efeito do Acesso Livre).
- Esta é uma revista de acesso aberto, o que significa que todo o conteúdo é livremente disponível gratuitamente para o usuário ou sua instituição. Os usuários estão autorizados a ler, baixar, copiar, distribuir, imprimir, pesquisar ou vincular os textos completos dos artigos, ou usá-los para qualquer outro propósito legal, sem pedir permissão prévia do editor ou do autor. Isso está de acordo com a definição de acesso aberto do BOAI.
Todo o conteúdo do periódico está licenciado sob uma Licença Creative Commons do tipo atribuição BY.