Abstract
This paper investigates the Prize-Collecting Vehicle Routing Problem (PCVRP), to simulate a tourist trip design problem, and the solution of it via a hybrid Firefly Algorithm (FA), namely the Firefly Algorithm based on Coordinates (FAC). To the best of our knowledge, there is no publication found in the literature, focusing on the solution of the PCVR via FA. The hybridization that we propose is founded on the position, in the 2D-space, of each node included in a solution. Thus, the update mechanism of the original FA can be applied on non-probabilistic, continuous, problem-rated values. In order to demonstrate the effectiveness of the proposed algorithm, computational experiments were conducted over benchmark instances found in the literature. The results obtained by the FAC were compared to the corresponding solutions of another hybrid metaheuristic algorithm, the Distance Related Differential Evolution (DRDE) Algorithm and the CPLEX solver.
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
Alinaghian, M., & Naderipour, M. (2016). A novel comprehensive macroscopic model for time-dependent vehicle routing problem with multi-alternative graph to reduce fuel consumption: A case study. Computers & Industrial Engineering, 99, 210–222.
Baghlani, A., Makiabadi, M. H., & Sarcheshmehpour, M. (2014). Discrete optimum design of truss structures by an improved firefly algorithm. Advances in Structural Engineering, 17(10), 1517–1530.
Chandrasekaran, K., Simon, S. P., & Padhy, N. P. (2013). Binary real coded firefly algorithm for solving unit commitment problem. Information Sciences, 249, 67–84.
Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568–581.
Fister, I., Yang, X. S., & Brest, J. (2013). A comprehensive review of firefly algorithms. Swarm and Evolutionary Computation, 13, 34–46.
Gavalas, D., Konstantopoulos, C., Mastakas, K., & Pantziou, G. (2014). A survey on algorithmic approaches for solving tourist trip design problems. Journal of Heuristics, 20(3), 291–328.
Goel, R., & Maini, R. (2018). A hybrid of ant colony and firefly algorithms (HAFA) for solving vehicle routing problems. Journal of Computational Science, 25, 28–37.
Jati, G. K. (2011). Evolutionary discrete firefly algorithm for travelling salesman problem. In Adaptive and intelligent systems (pp. 393–403). Berlin: Springer.
Jia, S. J., Yi, J., Yang, G. K., Du, B., & Zhu, J. (2013). A multi-objective optimisation algorithm for the hot rolling batch scheduling problem. International Journal of Production Research, 51(3), 667–681.
Li, K., & Tian, H. (2016). A two-level self-adaptive variable neighborhood search algorithm for the prize-collecting vehicle routing problem. Applied Soft Computing, 43, 469–479.
Long, J., Sun, Z., Pardalos, P. M., Hong, Y., Zhang, S., & Li, C. (2019). A hybrid multi-objective genetic local search algorithm for the prize-collecting vehicle routing problem. Information Sciences, 478, 40–61.
Osaba, E., Yang, X. S., Diaz, F., Onieva, E., Masegosa, A. D., & Perallos, A. (2017). A discrete firefly algorithm to solve a rich vehicle routing problem modelling a newspaper distribution system with recycling policy. Soft Computing, 21(18), 5295–5308.
Pan, F., Ye, C., Wang, K., & Cao, J. (2013). Research on the vehicle routing problem with time windows using firefly algorithm. JCP, 8(9), 2256–2261.
Sayadi, M., Ramezanian, R., & Ghaffari-Nasab, N. (2010). A discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems. International Journal of Industrial Engineering Computations, 1(1), 1–10.
Simić, D., Kovačević, I., Svirčević, V., & Simić, S. (2015). Hybrid firefly model in routing heterogeneous fleet of vehicles in logistics distribution. Logic Journal of the IGPL, 23(3), 521–532.
Singh, A., Thapar, S., Bhatia, A., Singh, S., & Goyal, R. (2015). Disk scheduling using a customized discrete firefly algorithm. Cogent Engineering, 2(1), 1011929.
Stavropoulou, F., Repoussis, P. P., & Tarantilis, C. D. (2019). The vehicle routing problem with profits and consistency constraints. European Journal of Operational Research, 274(1), 340–356.
Tang, L., & Wang, X. (2006). Iterated local search algorithm based on very large-scale neighborhood for prize-collecting vehicle routing problem. The International Journal of Advanced Manufacturing Technology, 29(11–12), 1246–1258.
Tilahun, S. L., & Ngnotchouye, J. M. T. (2017). Firefly algorithm for discrete optimization problems: A survey. KSCE Journal of Civil Engineering, 21(2), 535–545.
Tiwari, A., Chang, P. C., Elangovan, G., & Annadurai, S. P. (2015, May). A hybrid edge recombination approach to solve price collecting vehicle routing problem. In 2015 International Conference on Control, Automation and Robotics (pp. 200–203). IEEE.
Trachanatzi, D., Rigakis, M., Taxidou, A., Marinaki, M., Marinakis, Y., & Matsatsinis, N. (2019). A novel solution encoding in the differential evolution algorithm for optimizing tourist trip design problems. In International conference on learning and intelligent optimization (pp. 253–267). Cham: Springer.
Yang, X. S. (2009, October). Firefly algorithms for multimodal optimization. In International symposium on stochastic algorithms (pp. 169–178). Berlin: Springer.
Yang, X. S. (2010). Nature-inspired metaheuristic algorithms. Bristol: Luniver Press.
Yang, X. S. (2014). Cuckoo search and firefly algorithm: Overview and analysis. In X. S. Yang (Ed.), Cuckoo search and firefly algorithm (Studies in Computational Intelligence) (Vol. 516). Cham: Springer.
Yang, X. S., & He, X. (2013). Firefly algorithm: Recent advances and applications. International Journal of Swarm Intelligence, 1(1), 36–50.
Zhang, T., Chaovalitwongse, W. A., Zhang, Y. J., & Pardalos, P. M. (2009). The hot-rolling batch scheduling method based on the prize collecting vehicle routing problem. Journal of Industrial and Management Optimization, 5(4), 749–765.
Acknowledgments
This research is co-financed by Greece and the European Union (European Social Fund—ESF) through the Operational Programme “Human Resources Development, Education and Lifelong Learning” in the context of the project “Strengthening Human Resources Research Potential via Doctorate Research” (MIS-5000432), implemented by the State Scholarships Foundation (ΙΚΥ).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Rigakis, M., Trachanatzi, D., Marinaki, M., Marinakis, Y. (2020). A Hybrid Firefly Algorithm Based on Coordinates for the Prize-Collecting Vehicle Routing Problem. In: Krassadaki, E., Baourakis, G., Zopounidis, C., Matsatsinis, N. (eds) Operational Research in Agriculture and Tourism. Cooperative Management. Springer, Cham. https://doi.org/10.1007/978-3-030-38766-2_8
Download citation
DOI: https://doi.org/10.1007/978-3-030-38766-2_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-38765-5
Online ISBN: 978-3-030-38766-2
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)