An Individual-Oriented Shuffled Frog Leaping Algorithm for Solving Vehicle Routing Problem
Subject Areas :
Soheila Shafiezadeh
1
,
Zahra Beheshti
2
*
1 - Master's student
2 - Faculty of Computer Engineering, Najafabad Branch, Islamic Azad University, Najafabad, Iran
Keywords: Vehicle Routing Problem (VRP), Shuffled Frog Leaping Algorithm (SFLA), Route cost, Mutation, Crossover operation.,
Abstract :
The Vehicle Routing Problem (VRP) is one of the most important problems in supply chain management because the optimal allocation of vehicles has a significant impact on reducing costs. VRP is in the class of NP-hard problems and exact algorithms cannot find the best solution in an acceptable time. Hence, meta-heuristic algorithms can be employed to solve it. Shuffled Frog Leaping Algorithm (SFLA) is one of the meta-heuristic algorithms, which is efficient, but in some cases, its population diversity rapidly reduces, and the algorithm falls in local optima. In this study, an Individual-Oriented Shuffled Frog Leaping Algorithm (IO-SFLA) is proposed to enhance the exploration and exploitation of SFLA by exchanging the global and local information. Several VRPs in different dimensions are applied to evaluate the performance of IO-SFLA. The efficiency of IO-SFLA is compared with several improved shuffled frog leaping algorithms, Simulated Annealing (SA) and Genetic Algorithm (GA). The results show that IO-SFLA provides significant results compared with the other competitor algorithms. IO-SFLA achieves an average of 1130.442 for the best path cost. The next rank belongs to SA with an average of 1228.725. Other compared algorithms are in the lower ranks with high differences in results.
[1] G. B. Dantzig and J. H. Ramser, “The Truck Dispatching Problem.” Management Science, vol. 6, no.1, pp. 80–91, 1959.
[2] A. Boonkleaw, N. Suthikarnnarunai, and R. Srinon, “Strategic Planning for Newspaper Delivery Problem Using Vehicle Routing Algorithm with Time Window ( VRPTW ),” Eng. Lett., vol. 18, no. 2, pp. 183-192. 2010.
[3] J. K. Lenstra and A. H. G. R. Kan, “Complexity of Vehicle Routing and Scheduling Problems,” vol. 11, no. 2, pp. 221–227, 1981.
[4] Z. Beheshti, S. M. Shamsuddin, S. Hasan, and N. E. Wong, “Improved centripetal accelerated particle swarm optimization,” Int. J. Adv. Soft Comput. its Appl., vol. 8, no. 2, pp. 1–26, 2016.
[5] M. H. Nadimi-Shahraki, S. Taghian, and S. Mirjalili, “An improved grey wolf optimizer for solving engineering problems,” Expert Syst. Appl., vol. 166, p. 113917, 2021.
[6] A. Faramarzi, M. Heidarinejad, S. Mirjalili, and A. H. Gandomi, “Marine Predators Algorithm: A nature-inspired metaheuristic,” Expert Syst. Appl., vol. 152, p. 113377, Aug. 2020.
[7] Z. Beheshti, “UTF: Upgrade transfer function for binary meta-heuristic algorithms,” Appl. Soft Comput., vol. 106, p. 107346, 2021.
[8] Z. Beheshti, “A novel x-shaped binary particle swarm optimization,” Soft Comput., vol. 25, pp. 3013–3042, 2021.
[9] Z. Beheshti, “BMNABC: Binary Multi-Neighborhood Artificial Bee Colony for High-Dimensional Discrete Optimization Problems,” Cybern. Syst., vol. 49, no. 7–8, pp. 452–474, 2018.
[10] R. P. Parouha and P. Verma, “Design and applications of an advanced hybrid meta-heuristic algorithm for optimization problems,” Artif. Intell. Rev., pp. 1–80, 2021.
[11] B. Morales-Castañeda, D. Zaldívar, E. Cuevas, F. Fausto, and A. Rodríguez, “A better balance in metaheuristic algorithms: Does it exist?,” Swarm Evol. Comput., vol. 54, p. 100671, 2020.
[12] M. Eusuff, K. Lansey, and F. Pasha, “Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization,” Eng. Optim., vol. 38, no. 2, pp. 129–154, 2006.
[13] Y. Li and Z. Yan, “Improved shuffled frog leaping algorithm on system reliability analysis,” Brain Informatics, vol. 6, no. 1, pp. 1–7, 2019.
[14] M. L. Pérez-Delgado, “Color image quantization using the shuffled-frog leaping algorithm,” Eng. Appl. Artif. Intell., vol. 79, no. January, pp. 142–158, 2019.
[15] P. Kaur and S. Mehta, “Resource provisioning and work flow scheduling in clouds using augmented Shuffled Frog Leaping Algorithm,” J. Parallel Distrib. Comput., vol. 101, pp. 41–50, 2017.
[16] A. Sarkheyli, A. M. Zain, and S. Sharif, “The role of basic, modified and hybrid shuffled frog leaping algorithm on optimization problems: a review,” Soft Comput., vol. 19, no. 7, pp. 2011–2038, 2015.
[17] J. E. Bell and P. R. McMullen, “Ant colony optimization techniques for the vehicle routing problem,” Adv. Eng. Informatics, vol. 18, no. 1, pp. 41–48, 2004.
[18] B. Yu, Z. Z. Yang, and B. Z. Yao, “A hybrid algorithm for vehicle routing problem with time windows,” Expert Syst. Appl., vol. 38, pp. 435–441, 2011.
[19] B. Eksioglu, A. Volkan, and A. Reisman, “The vehicle routing problem : A taxonomic review,” Comput. Ind. Eng., vol. 57, no. 4, pp. 1472–1483, 2009.
[20] J. R. Montoya-Torres, J. López Franco, S. Nieto Isaza, H. Felizzola Jiménez, and N. Herazo-Padilla, “A literature review on the vehicle routing problem with multiple depots,” Comput. Ind. Eng., vol. 79, pp. 115–129, 2015.
[21] H. Park, D. Son, B. Koo, and B. Jeong, “Waiting strategy for the vehicle routing problem with simultaneous pickup and delivery using genetic algorithm,” Expert Syst. Appl., vol. 165, p. 113959, 2021.
[22] V. F. Yu and S. Lin, “A simulated annealing heuristic for the open location-routing problem,” Comput. Oper. Res., vol. 62, pp. 184–196, 2015.
[23] I. R. Abdelhalim Hiassata, Ali Diabatb, “A genetic algorithm approach for location-inventory-routing problem with perishable products,” J. Manuf. Syst., vol. 42, pp. 93–103, 2017.
[24] R. A. S. Abdel Monaem F.M. AbdAllah, Daryl L. Essam, “On solving periodic re-optimization dynamic vehicle routing problems,” Appl. Soft Comput. J., vol. 55, pp. 1–12, 2017.
[25] E. Osaba, X. S. Yang, F. Diaz, E. Onieva, A. D. Masegosa, and A. Perallos, “A discrete firefly algorithm to solve a rich vehicle routing problem modelling a newspaper distribution system with recycling policy,” Soft Comput., vol. 21, no. 18, pp. 5295–5308, 2017.
[26] G. Ninikas and I. Minis, “Load transfer operations for a dynamic vehicle routing problem with mixed backhauls,” J. Veh. Routing Algorithms, vol. 1, no. 1, pp. 47–68, 2018.
[27] K. M. Ferreira and T. A. De Queiroz, “Two effective simulated annealing algorithms for the Location-Routing Problem,” Appl. Soft Comput. J., vol. 70, pp. 389–422, 2018.
[28] F. Arnold and K. Sörensen, “Knowledge-guide d local search for the vehicle routing problem,” Comput. Oper. Res., vol. 105, pp. 32–46, 2019.
[29] ف. مدرس خیابانی، ن. مصیب زاده، ”بررسی مقایسه ای الگوریتم های فرا ابتکاری برای مسیریابی وسیله نقلیه پویا به منظور بهره وری و کارایی سیستم های حمل و نقل،“ مدیریت بهره وری (فراسوی مدیریت)، شماره 10، صفحه 310-287، 1396.
[30] م. ربانی، م. توحیدی فرد، م. پرتوی و ح. فرخی اصل، ”حل مسأله مسیریابی وسایل نقلیه چند انباره با در نظر گرفتن پنجره زمانی و تقاضای فازی با استفاده از الگوریتم های فرا ابتکاری در خدمات بهداشت خانگی،“ تصمیم گیری و تحقیق در عملیات، شماره 3، صفحه 127-114، 1397.
[31] م. تقوی فرد، ک. شیخ و آ. شهسواری، ”ارایه روش اصلاح شده کلونی مورچگان جهت حل مساله مسیریابی وسایل نقلیه به همراه پنجره های زمانی،“ نشریه بین المللی مهندسی صنایع و مدیریت تولید، شماره 20، صفحه 30-23، 1388.
[32] E. Ruiz, V. Soto-Mendoza, A. E. Ruiz Barbosa, and R. Reyes, “Solving the Open Vehicle Routing Problem with capacity and distance constraints with a biased Random Key Genetic Algoritm,” Comput. Ind. Eng., vol. 133, pp. 207-219, 2019.
[33] Ç. Koç, T. Bektaş, O. Jabali, and G. Laporte, “Thirty years of heterogeneous vehicle routing,” Eur. J. Oper. Res., vol. 249, no. 1, pp. 1–21, 2016.
[34] R. Elshaer and H. Awad, “A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants,” Comput. Ind. Eng., vol. 140, p. 106242, 2020.
[35] M. M. Eusuff and K. E. Lansey, “Optimization of Water Distribution Network Design Using the Shuffled Frog Leaping Algorithm,” J. Water Resour. Plan. Manag., vol. 129, no. 3, pp. 210–225, 2003.
[36] N. Christofides, “The vehicle routing problem,” Rev. française d’automatique, informatique, Rech. opérationnelle. Rech. opérationnelle, vol. 10, no. V1, pp. 55–70, 1976.
[37] A. M. Dalavi, P. J. Pawar, and T. P. Singh, “Tool path planning of hole-making operations in ejector plate of injection mould using modified shuffled frog leaping algorithm,” J. Comput. Des. Eng., vol. 3, no. 3, pp. 266–273, 2016.
[38] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by Simulated Annealing,” Science, vol. 220, no. 4598, pp. 671–680, 1983.
[39] R. Cueva and M. Tupia, “A continuous genetic algorithm for pickup and delivery problem in a VRP environment,” Adv. Inf. Sci. Serv. Sci., vol. 5, no. 10, p. 1110, 2013.
[40] J. Derrac, S. Garcia, D. Molina, and F. Herrera, “A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms,” Swarm Evol. Comput., vol. 1, no. 1, pp. 3–18, 2011.