مسیریابی وسایل نقلیه با استفاده از الگوریتم جهش قورباغه مخلوط شده فرد محور
محورهای موضوعی :
سهیلا شفیع زاده
1
(دانش¬آموخته کارشناسی ارشد دانشکده مهندسي کامپیوتر، واحد نجف¬آباد، دانشگاه آزاد اسلامی، نجف¬آباد، ايران)
زهرا بهشتی
2
(دانشیار دانشکده مهندسی کامپیوتر، واحد نجف¬آباد، دانشگاه آزاد اسلامی، نجف¬آباد، ايران)
کلید واژه: مسأله مسیریابی وسایل نقلیه, الگوریتم جهش قورباغه مخلوط شده, هزینه مسیر, جهش, عملگر ترکیب,
چکیده مقاله :
مسأله‌ی مسیریابی وسایل نقلیه، یکی از مهم‌ترین مسائل مدیریت زنجیره‌ی تأمین است، زیرا تخصیص مطلوب وسایل نقلیه تأثیر زیادی بر کاهش هزینه‌ها دارد. این مسأله در دسته مسائل سخت قراردارد و الگوریتم های دقیق کارایی لازم را برای حل آن ندارند. از این رو، می توان از الگوریتم فراابتکاری استفاده کرد که راه حل های خوبی برای حل مسائل سخت ارائه می دهند. یکی از این الگوریتم ها، الگوریتم جهش قورباغه مخلوط شده است که از کارایی بالایی برخوردار است، اما در بعضی مواقع، تنوع جمعیت در آن به دلیل گروه-بندی قورباغه ها به سرعت کاهش می یابد، از این رو در دام بهینه های محلی گرفتار می آید. در این تحقیق، الگوریتم جهش قورباغه مخلوط شده فرد محور ارائه می گردد که از طریق تبادل اطلاعات سراسری و محلی، قابلیت اکتشاف و بهره برداری الگوریتم قورباغه را بهبود می دهد. به منظور ارزیابی الگوریتم پیشنهادی، از مسائل مسیریابی در ابعاد مختلف استفاده می گردد و نتایج آن با چند الگوریتم بهبود یافته جهش قورباغه مخلوط شده، شبیه سازی تبرید و الگوریتم ژنتیک مقایسه می شود. نتایج نشان می دهند که الگوریتم پیشنهادی، از نظر طول مسیر طی شده برای بهترین نتایج، میانگینی برابر با 1130.442 دارد و الگوریتم بعدی شبیه سازی تبرید با میانگینی برابر 1228.725می باشد. سایر الگوریتم ها با اختلاف زیادی در رده های بعدی قرار دارند.
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.