Aplicação da otimização por colônia de formigas ao problema de múltiplos caixeiros viajantes no atendimento de ordens de serviço nas empresas de distribuição de energia elétrica

• Denilson Barbosa Universidade Tecnológica Federal do Paraná
• Carlos Jr. Universidade Tecnológica Federal do Paraná
• André Kashiwabara Universidade Tecnológica Federal do Paraná

DOI: https://doi.org/10.5753/sbsi.2015.5797

Resumo

Este artigo apresenta uma metodologia para otimização do atendimento comercial nas empresas de distribuição de energia elétrica, atividade que representa uma parcela significativa dos custos operacionais dessas empresas. Como distribuir as ordens de serviço entre as equipes de atendimento e como definir rotas eficientes são problemas complexos devido à grande quantidade de combinações possíveis. Através da criação de instâncias de Problemas de Múltiplos Caixeiros Viajantes a partir das posições de execução das ordens e da aplicação de um algoritmo baseado na Otimização por Colônia de Formigas nessas instâncias, foram obtidas solu- ções otimizadas para distribuição das ordens e roteamento das equipes. O método desenvolvido foi aplicado a 17 instâncias construídas a partir de dados reais de uma agência de atendimento e mostrou-se eficiente ao diminuir em média 42,23% das distâncias percorridas pelas equipes em comparação com as rotas reais. Para possibilitar a replicação dos experimentos realizados, o código fonte do protótipo desenvolvido e os dados reais utilizados encontram-se disponíveis em https://github.com/denilsonfag/STACS.

Palavras-chave: Distribuição de energia elétrica, problema de múltiplos caixeiros viajantes, otimização por colônia de formigas

Referências

A. R. Mascia, W. d. M. Reck, V. J. Garcia, D. P. Bernardon, M. Sperandio, and C. do Vale. Algoritmo heurístico para agrupamento de ordens de serviço em concessionárias de distribuição de energia elétrica considerando priorização. In Anais do Congreso Internacional de Distribuicion Electrica, pages 1–5, Buenos Aires, 2010.

C. E. d. S. Costa, D. M. B. Costa, and A. R. T. Goes. Determinação de setores de atendimento em uma concessionária de energia. In Anais do Simpósio Brasileiro de Pesquisa Operacional - SBPO, pages 951–962, Goiânia, 2006.

C. Okonjo-Adigwe. An effective method of balancing the workload amongst salesmen. Omega, 16(2):159–163, Jan. 1988.

D. M. Machado Jr and M. A. Dal Santo. Considerações acerca de Trabalhos em Areas de Divisa ´ de Fusos UTM. In Anais do Congresso Brasileiro de Cadastro Técnico Multifinalitário, pages 1–14, 2004.

I. Vallivaara. A team ant colony optimization algorithm for the multiple travelling salesmen problem with minmax objective. In Proceedings of the 27th IASTED International Conference on Modelling, Identification and Control, pages 387–392, Anaheim, CA, USA, 2008.

IPARDES. Caderno estatístico do município de Cornélio Procópio. Instituto Paranaense de Desenvolvimento Econômico e Social, 2014.

J. Augustine. Offline and online variants of the traveling salesman problem. PhD thesis, Louisiana State University, Department of Electrical and Computer Engineering, 2002.

J. Y. Kanda. Sistema de meta-aprendizado para a seleção de meta-heurísticas para o problema do caixeiro viajante. In X SBSI - Simpósio Brasileiro de Sistemas de Informação, pages 651–662, Londrina, 2014.

M. Dorigo and L. Gambardella. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1):53–66, Apr. 1997.

M. Dorigo and T. Stutzle. Ant Colony Optimization. The MIT Press, Cambridge, Massachusetts, 2004.

M. Dorigo, V. Maniezzo, and a. Colorni. The Ant System: optimization by a colony of cooperating agents. IEEE transactions on systems, man, and cybernetics., 26(1):29–41, Jan. 1996.

T. Bektas. The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega, 34(3):209–219, June 2006.

V. Garcia, D. Bernardon, M. Sperandio, C. do Vale, and J. Fernandes. Service order dispatching in electric utilities. In 45th International Universities Power Engineering Conference (UPEC), pages 1 – 7, Cardiff, Wales, 2010. IEEE.