A C++ Library for Developing Evolutionary Algorithms to theQCaRS Problem

• 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

Abstract

The quota traveling car renter problem (QCaRS) consists of minimizing the cost of a trip between a group of cities, visiting only a subgroup, and ensuring the visit of cities that meet with minimum satisfaction for the traveler. Evolutionary algorithms are methods often used to solve the QCaRS problem. Reproducing the results obtained by existing algorithms in the literature can be difficult if the authors did not make their implementations available. This paper presents a C++ library for the development of evolutionary algorithms applied to QCaRS. The library uses the Strategy design pattern to provide the exchange of components of evolutionary algorithms and thus facilitate the evaluation of new solution proposals for the QCaRS problem.

Keywords: QCaRS. Evolutionary Algorithms. Strategy Project Pattern, C Library

References

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.