Applying a variation of the ant colony optimization algorithm to solve the multiple traveling salesmen problem to route the teams of the electric power distribution companies

• Denilson Barbosa Federal Technological University of Paraná
• Carlos Jr. Federal Technological University of Paraná
• André Kashiwabara Federal Technological University of Paraná

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

Abstract

This paper presents a methodology to optimize the execution of the commercial services of electric power distribution companies. This activity represents a significant portion of the operational costs of these companies. How to distribute the services to the teams and define efficient routes is a complex problem due to the great number of possible combinations. The set of geographical positions of the services can be seen as an instance of the multiple traveling salesmen problem. We created a variation of the ant colony optimization algorithm to obtain optimized solutions for the distribution of the services and the route of each team. Our methodology was applied to 17 real word instances obtained from an electric power distribution company from the city of Cornélio Procópio, Brazil. Our method obtained an improvement of 42,23% on average when compared to the solutions that were performed in the real world. To allow the reproduction of our results, the source-code of our system and the dataset are freely available at https://github.com/denilsonfag/STACS.

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

References

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.