Uma biblioteca C++ para Desenvolvimento de Algoritmos Evolucionários para o Problema QCaRS

• Tiago Funk Universidade do Estado de Santa Catarina
• Fernando Santos Universidade do Estado de Santa Catarina

DOI: https://doi.org/10.5753/eniac.2020.12142

Resumo

O problema do caixeiro viajante com quota (QCaRS) consiste em minimizar o custo de uma viagem entre um grupo de cidades, visitando apenas um subgrupo, e garantindo a visita de cidades que cumpram com uma satisfação mínima para o viajante. Algoritmos evolucionários são métodos frequentemente utilizados para resolver o problema QCaRS. No entanto, reproduzir os resultados obtidos por algoritmos existentes na literatura pode ser difícil caso os autores não disponibilizaram suas implementações. Este artigo apresenta uma biblioteca C++ para desenvolvimento de algoritmos evolucionários aplicados no QCaRS. A biblioteca utiliza o padrão de projeto Strategy para proporcionar o intercâmbio de componentes dos algoritmos evolucionários e deste modo facilitar a avaliação de novas propostas de solução para o QCaRS.

Palavras-chave: QCaRS. Algoritmos Evolucionários. Padrão de projeto Strategy, Biblioteca C

Referências

Asconavieta, P. (2011). O Problema do Caixeiro Alugador: um estudo algorítmico. PhD thesis, Tese (Doutorado em Ciência da Computação)–Universidade Federal do Rio Grande do Norte. da Silva Menezes, M., Goldbarg, M. C., and Goldbarg, E. F. (2014). A memetic algorithm for the prize-collecting traveling car renter problem. 2014 IEEE Congress on Evolutionary Computation (CEC), pages 3258–3265.

Gamma, E., Helm, R., Johnson, R., and Vlissides, J. (2000). Padrões de projeto: Soluções Reutilizáveis de Software Orientado a Objetos. Bookman, Porto Alegre, Brasil.

Goldbarg, M. C., Goldbarg, E. F., Menezes, M. d. S., and Luna, H. P. (2016). Quota traveling car renter problem: Model and evolutionary algorithm. Information Sciences, 367:232–245.

Linden, R. (2008). Algoritmos genéticos (2a ediçao). Brasport, Brasil.

Menezes, M. d. S., Goldbarg, M. C., Goldbarg, E. F., Ferreira, V. E. S., and ColaÇo, G. C. (2017). Abordagens GRASP aplicadas ao problema quota cars. Anais do 49 Simpósio Brasileiro de Pesquisa Operacional, pages 1807–1818.

Reinelt, G. (1995). Tsplib95. Interdisziplinäres Zentrum für Wissenschaftliches Rechnen (IWR), Heidelberg, 338:1–16.

Talbi, E.-G. (2009). Metaheuristics: from design to implementation, volume 74. John Wiley & Sons, United States.

Wolfe, H. E. (2012). Introduction to non-Euclidean geometry. Courier Corporation.

Asconavieta, P. (2011). O Problema do Caixeiro Alugador: um estudo algorítmico. PhD thesis, Tese (Doutorado em Ciência da Computação)–Universidade Federal do Rio Grande do Norte. da Silva Menezes, M., Goldbarg, M. C., and Goldbarg, E. F. (2014). A memetic algorithm for the prize-collecting traveling car renter problem. 2014 IEEE Congress on Evolutionary Computation (CEC), pages 3258–3265.

Gamma, E., Helm, R., Johnson, R., and Vlissides, J. (2000). Padrões de projeto: Soluções Reutilizáveis de Software Orientado a Objetos. Bookman, Porto Alegre, Brasil.

Goldbarg, M. C., Goldbarg, E. F., Menezes, M. d. S., and Luna, H. P. (2016). Quota traveling car renter problem: Model and evolutionary algorithm. Information Sciences, 367:232–245.

Linden, R. (2008). Algoritmos genéticos (2a ediçao). Brasport, Brasil.

Menezes, M. d. S., Goldbarg, M. C., Goldbarg, E. F., Ferreira, V. E. S., and ColaÇo, G. C. (2017). Abordagens GRASP aplicadas ao problema quota cars. Anais do 49 Simpósio Brasileiro de Pesquisa Operacional, pages 1807–1818.

Reinelt, G. (1995). Tsplib95. Interdisziplinäres Zentrum für Wissenschaftliches Rechnen (IWR), Heidelberg, 338:1–16.

Talbi, E.-G. (2009). Metaheuristics: from design to implementation, volume 74. John Wiley & Sons, United States.

Wolfe, H. E. (2012). Introduction to non-Euclidean geometry. Courier Corporation.