Abstract
The Traveling Car Renter Salesman (CaRS) is a combinatorial optimization problem that is NP-hard and thus evolutionary and swarm computation metaheuristics are natural choices for designing a new practical algorithm. Considering that Ant Colony Optimization (ACO) is well suited for other routing type of problems - in this paper we propose ACOCaRS - an algorithm for solving CaRS based on ACO. The proposed algorithm was investigated experimentally and compared with other published algorithms for CaRS. The first results are encouraging since the proposed algorithm was significantly better for smaller problem instances than all the other published algorithms. However, for problem instances of size 100 and larger, ACOCaRS was the second best algorithm, and was outperformed significantly by a Transgenetic Algorithm. These results are based on the average performance of the algorithm and ranks, taking into account the number of wins and average ranks for the algorithms. A Friedman test confirmed that the results are statistically significant. In addition to average performance, data for assessing the peak performance of ACOCaRS are reported, along with a few new best known solutions for CaRS obtained in this research.
This work has been fully supported by the Croatian Science Foundation under the project IP-2019-04-4864.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Goldbarg, M.C., Asconavieta, P.H., Goldbarg, E.F.G.: Memetic algorithm for the traveling car renter problem: an experimental investigation. Memet. Comput. 4(2), 89–108 (2012)
Goldbarg, M.C., Goldbarg, E.F.G., Asconavieta, P.H., Menezes, M., Luna, H.P.L.: A transgenetic algorithm applied to the traveling car renter problem. Expert Syst. Appl. 40(16), 6298–6310 (2013). https://doi.org/10.1016/j.eswa.2013.05.072
Bruglieri, M., Pezzella, F., Pisacane, O.: A two-phase optimization method for a multiobjective vehicle relocation problem in electric carsharing systems. J. Comb. Optim. 36(1), 162–193 (2018). https://doi.org/10.1007/s10878-018-0295-5
Dorigo, M., et al. (eds.): ANTS 2014. LNCS, vol. 8667. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-09952-1
Dorigo, M., Di Caro, G., Gambardella, LM.: Ant algorithms for discrete optimization. Artif Life 5(2), 137–172 (1999) https://doi.org/10.1162/106454699568728
Stützle, T., Hoos, H.H.: MAX-MIN ant system. Future Gener. Comput. Syst. 16(8), 889–914 (2000)
Reed, M., Evering, R.: An ant colony algorithm for recycling waste collection. In: BIOMA, pp. 221–230 (2012)
Taškova, K., Korošec, P., Šilc, J.: A distributed multilevel ant colonies approach. Informatica (Slovenia). 32, 307–317 (2008)
Sabry, G.A., Goldbarg, M.C., Goldbarg, E.F.G., Menezes, M.S., Calheiros, Z.S.A.: Models and linearizations for the traveling car renter with passengers. Optim. Lett 15(1), 59–81 (2020). https://doi.org/10.1007/s11590-020-01585-0
Sabry, G., Goldbarg, M., Goldbarg, E., Menezes, M. and J. Filho, G.: Evolutionary algorithms for the traveling car renter with passengers. In: IEEE Congress on Evolutionary Computation (CEC), pp. 1–8 (2020). https://doi.org/10.1109/CEC48606.2020.9185693
Eftimov, T., Korošec, P., Koroušić Seljak, B.: Data-driven preference-based deep statistical ranking for comparing multi-objective optimization algorithms. In: Korošec, P., Melab, N., Talbi, E.-G. (eds.) BIOMA 2018. LNCS, vol. 10835, pp. 138–150. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-91641-5_12
Panigrahi, B.K., Suganthan, P.N., Das, S., Satapathy, S.C. (eds.): SEMCCO 2011. LNCS, vol. 7076. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-27172-4
Ivkovic, N., Golub, M., Malekovic, M.: A pheromone trails model for MAX-MIN ant system. In: Proceedings of 10th Biennal International Conference on Artificial Evolution, Angers, France, pp. 35–46 (2011)
Matthews, D.C.: Improved lower limits for pheromone trails in ant colony optimization. In: Rudolph, G., Jansen, T., Beume, N., Lucas, S., Poloni, C. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 508–517. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-87700-4_51
López-Ibáñez, M., Dubois-Lacoste, J., Pérez Cáceres, L., Stützle, T., Birattari, M.: The Irace package: iterated racing for automatic algorithm configuration. Oper. Res. Perspect. 3, 43–58 (2016). https://doi.org/10.1016/j.orp.2016.09.002
Dorigo, M., Stützle, T.: Ant Colony Optimization year. Bradford Company, USA (2004)
Ivkovic, N., Jakobovic, D., Golub, M.: Measuring performance of optimization algorithms in evolutionary computation. Int. J. Mach. Learn. Comput. 6(3), 167–171 (2016). https://doi.org/10.18178/ijmlc.2016.6.3.593
Alfian, G., Farooq, U., Rhee, J.: Ant Colony Optimization for Relocation Problem in Carsharing (2013)
Eftimov, T., Korošec, P., Seljak, B.K.: Disadvantages of statistical comparison of stochastic optimization algorithms. In: Proceedings of the Bioinspired Optimizaiton Methods and their Applications, BIOMA, pp. 105–118 (2016)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Popović, E., Ivković, N., Črepinšek, M. (2022). ACOCaRS: Ant Colony Optimization Algorithm for Traveling Car Renter Problem. In: Mernik, M., Eftimov, T., Črepinšek, M. (eds) Bioinspired Optimization Methods and Their Applications. BIOMA 2022. Lecture Notes in Computer Science, vol 13627. Springer, Cham. https://doi.org/10.1007/978-3-031-21094-5_3
Download citation
DOI: https://doi.org/10.1007/978-3-031-21094-5_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-21093-8
Online ISBN: 978-3-031-21094-5
eBook Packages: Computer ScienceComputer Science (R0)