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.
دو فصلنامه علمي فناوري اطلاعات و ارتباطات ایران | سال چهاردهم، شمارههای 51 و 52 ، بهار و تابستان1401 صص: 37_54 |
|
مسیریابی وسایل نقلیه با استفاده از الگوریتم جهش قورباغه مخلوط شده فرد محور
سهیلا شفیعزاده * زهرا بهشتی**
*دانشآموخته کارشناسی ارشد دانشکده مهندسي کامپیوتر، واحد نجفآباد، دانشگاه آزاد اسلامی، نجفآباد، ايران
**استادیار دانشکده مهندسي کامپیوتر، واحد نجفآباد، دانشگاه آزاد اسلامی، نجفآباد، ايران
تاریخ دریافت: 07/01/1400 تاریخ پذیرش: 28/11/1400
نوع مقاله: پژوهشی
چكیده
مسألهی مسیریابی وسایل نقلیه، یکی از مهمترین مسائل مدیریت زنجیرهی تأمین است، زیرا تخصیص مطلوب وسایل نقلیه تأثیر زیادی بر کاهش هزینهها دارد. این مسأله در دسته مسائل سخت قراردارد و الگوریتمهای دقیق کارایی لازم را برای حل آن ندارند. از این رو، میتوان از الگوریتم فراابتکاری استفاده کرد که راه حلهای خوبی برای حل مسائل سخت ارائه میدهند. یکی از این الگوریتمها، الگوریتم جهش قورباغه مخلوط شده است که از کارایی بالایی برخوردار است، اما در بعضی مواقع، تنوع جمعیت در آن به دلیل گروهبندی قورباغهها به سرعت کاهش مییابد، از اینرو در دام بهینههای محلی گرفتار میآید. در این تحقیق، الگوریتم جهش قورباغه مخلوط شده فرد محور ارائه میگردد که از طریق تبادل اطلاعات سراسری و محلی، قابلیت اکتشاف و بهرهبرداری الگوریتم قورباغه را بهبود میدهد. به منظور ارزیابی الگوریتم پیشنهادی، از مسائل مسیریابی در ابعاد مختلف استفاده میگردد و نتایج آن با چند الگوریتم بهبود یافته جهش قورباغه مخلوط شده، شبیهسازی تبرید و الگوریتم ژنتیک مقایسه میشود. نتایج نشان میدهند که الگوریتم پیشنهادی، از نظر طول مسیر طی شده برای بهترین نتایج، میانگینی برابر با 1130.442 دارد و الگوریتم بعدی شبیه سازی تبرید با میانگینی برابر 1228.725میباشد. سایر الگوریتمها با اختلاف زیادی در ردههای بعدی قرار دارند.
واژگان کلیدی: مسأله مسیریابی وسایل نقلیه، الگوریتم جهش قورباغه مخلوط شده، هزینه مسیر، جهش، عملگر ترکیب.
مقدمه
بسیاری از مسائل دنیای واقعی، مسائل بهینه سازی هستند که کاربردهای بسیاری در علوم مختلف دارند. از اینرو، توسعه روشهای تولید جواب و حل این مسائل، یکی از حوزههای مهم تحقیقاتی است.
مسأله مسیریابی وسایل نقلیه1، یک مسأله بهینهسازی ترکیبی2 و گسسته است که هدف آن سرویس دهی به مشتریان با استفاده از ناوگانی از وسایل نقلیه در جهت کمینه کردن هزینه مسیر در انتقال کالا از ایستگاه مرکزی به سمت مشتریان است [1].
این مسأله، یکی از مهمترین مسائل مدیریت زنجیره تأمین است و این اهمیت از آنجا ناشی میشود که تخصیص مطلوب وسایل به مسیرهای مختلف، تأثیر بسیار زیادی بر کاهش هزینهها دارد و کاربردهای فراوانی در دنیای واقعی دارد. به عنوان مثال، میتوان به جمعآوری زبالههای جامد، توزیع و پخش مواد غذایی، دارو و سوخت، مسیریابی سرویس مدارس و کارمندان، جمعآوری و پخش نامههای پستی، توزیع روزنامه، برنامهریزی مسیر حرکت کشتیها و یا حرکت رباتها اشاره کرد [2]. اجزای اصلی و پایهای مسأله مسیریایی وسایل نقلیه عبارتند از: شبکه مسیرها، مشتریان، انبارها، وسایل نقلیه و رانندگان. در عمل، محدودیتها و شرایط مختلفی میتواند بر هر یک از این اجزای اصلی تحمیل شود که هر یک از آنها منجر به ایجاد نوع خاصی از مسائل مسیریابی وسایل نقلیه می شود [1]. حل این مسأله به دو دلیل بسیار مورد توجه پژوهشگران بوده است: یکی کاربرد عملی این مسأله و دیگری سختی حل آن است. پیچیدگی زمانی مسائل مسیریابی وسایل نقلیه محاسبه گردید و اثبات شد که تمامی این مسائل از نوع سخت هستند و با افزایش ابعاد مسأله، فضای جستجو برای حل مسأله به صورت نمایی افرایش مییابد [3]. از این رو، الگوریتمهای دقیق در زمان معقولی قادر به حل این مسائل در ابعاد بالا نیستند و میتوان از الگوریتمهای تقریبی در حل آنها استفاده کرد.
از جمله الگوریتمهای تقریبی میتوان به الگوریتمهای فراابتکاری اشاره کرد. این الگوریتمها در حل بسیاری از مسائل بهینهسازی پیوسته[4]–[6] و ناپیوسته[7]–[9] نتایج خوبی را ارائه کردهاند. اما از آنجا که تمام فضای حل مسأله توسط این الگوریتمها بررسی نمیگردد، در دام بهینههای محلی گرفتار میآیند. بنابراین محققان، درصدد ارائه راه حلهایی برای فرار از بهینههای محلی در این الگوریتمها هستند [9]–[11]. در این میان، الگوریتم جهش قورباغه مخلوط شده دارای ویژگیهایی است که میتواند راه حلهای خوب را افزایش و وزن راه حلهای بد را کاهش دهد [12]. سادگی پیادهسازی و سرعت اجرای بالا همراه با دقت مناسب، از خصوصیاتی است که باعث محبوبیت این الگوریتم شده است [13]–[15]. اما مانند تمام الگوریتمهای فراابتکاری، در بعضي موارد این الگوريتم قادر به پيدا كردن جواب خوب نیست و به ركود و افتادن در بهينه محلي دچار میگردد. ركود الگوريتم ممكن است به دو دليل زير باشد [16]:
الف) دراین الگوريتم، قورباغهها متناسب با شايستگيشان مرتب و سپس همه جمعيت به چند زير مجموعه تقسيم ميگردند. اين نوع گروهبندي نامتعادل است، زيرا عملكرد زير مجموعه اول نسبت به زير مجموعههاي ديگر بهتر است. اين توزيع نامتعادل قورباغهها باعث ايجاد مشكلاتي در روند يادگيري ميشود چون قورباغههاي خوب در زير مجموعه آخر وجود ندارند.
ب) در این الگوریتم تغییر موقعیت، برای قورباغه بدتر تعریف شده است، قورباغه بدتر فقط از قورباغه بهتر تاٌثير میپذيرد و قورباغه بهتر شانس كمتري براي يادگيري پيدا ميكند، مگر اين كه قورباغههاي بهتر در طول تكامل تبديل به قورباغه بدتر گردند. در ضمن، بدترین قورباغه در هر مجموعه، یک شانس برای حرکت آگاهانه به سمت بهترین جواب ممکن، دارد و در صورت عدم پرش مناسب و محقق نشدن شرط، یک قورباغه تصادفی جایگزین بدترین قورباغه می شود. بنابراين اين الگوريتم از روش يادگيري مناسبي برخوردار نيست.
در این تحقیق، هدف ارائه الگوریتم ناپیوسته بهبود یافتهای به نام الگوریتم جهش قورباغه مخلوط شده فرد محور است که در آن تمام راه حلهای خوب و بد امکان بهتر شدن دارند. الگوریتم پیشنهادی با چند الگوریتم بهبود یافته جهش قورباغه مخلوط شده، شبیهسازی تبرید و الگوریتم ژنتیک پیوسته مقایسه شده است. نتایج تجربی نشان میدهد الگوریتم پیشنهادی نتایج بهتری را ارائه میدهد.
سازماندهی این تحقیق بدین صورت است: در بخش دوم ابتدا به مسأله مسیریابی وسایل نقلیه پرداخته میشود و اجزای اصلی و پایهای آن بیان میشود. سپس، پژوهشهای انجام شده در خصوص مسأله مسیریابی وسایل نقلیه بررسی میگردد. در بخش سوم، الگوریتم جهش قورباغه مخلوط شده شرح داده میشود و در بخش چهارم، الگوریتم پیشنهادی برای بهبود الگوریتم جهش قورباغه مخلوط شده توضیح داده میشود. بعد از آن چگونگی نگاشت الگوریتم پیشنهادی برای مسیریابی وسایل نقلیه بیان میگردد. در بخش پنجم، به منظور ارزیابی روش پیشنهادی، مجموعه آزمایشهایی با استفاده از مسائل استاندارد در ابعاد مختلف انجام میشود و الگوریتم پیشنهادی با برخی از الگوریتمهای مورد استفاده در مسأله مسیریابی وسایل نقلیه مقایسه میگردد. در پایان نیز، خلاصه ای از تحقیق انجام شده، نتایج به دست آمده و راهکارهایی برای تحقیقات آتی بیان میگردد.
مسأله مسیریابی وسایل نقلیه
مسأله مسیریابی وسایل نقلیه به نحوی سعی در طراحی بهینه مجموعهای از مسیرها برای ناوگان حمل و نقل دارد که به تعداد معینی مشتری خدمت رسانی شود. این مسأله دارای محدودیتهای جانبی مختلفی است [17]. هدف، پیدا کردن مجموعهاي از مسیرها براي چندین وسیله نقلیه از یک انبار و برگشتن به انبار برای سرویس دادن به مشتریان است، بدون اینکه محدودیت ظرفیت هر وسیله نقلیه نقض شود، و حداقل هزینه به دست آید. به دلیل آن که ترکیب مشتريها به انتخاب مسیرهاي حمل و نقل محدود نیست، این مسأله به عنوان یک مسأله بهینه سازي ترکیبی مورد توجه است. در این مسأله، تعداد جواب هاي شدنی براي مسأله به طور نمایی با رشد تعداد مشتريها افزایش مییابد.
2. 1 اجزای اصلی و پایهای مسأله مسیریابی وسایل نقلیه
مسأله مسیریابی وسایل نقلیه به صورت گراف، شبیهسازی میشود. در این حالت گرههای گراف، بیانگر مشتریان و یالهای آن نشاندهنده راههای موجود بین مشتریان است. هزینه به صورت زمان یا مسافت، متناسب با هر یال گراف تعریف میشود. گرافها، بسته به این که مسیرها یک طرفه یا دوطرفه باشند، یا هزینه سفر رفت و برگشت بین دو گره یکسان یا غیر یکسان باشد، به صورت جهت دار یا غیر جهت دار تعریف میشوند. هر یک از این اجزا خصوصیاتی دارند که به عنوان فرضهای مسأله و پارامترهای ورودی در نظر گرفته میشوند [18]. شکل 1 نمونهای از جوابهای مسأله مسیریابی وسایل نقلیه را نشان میدهد.
شکل 1. نمونه جوابهای مسأله مسیریابی
تا به حال نسخه های تغییریافته و متنوعی از مسیریابی وسایل نقلیه مورد مطالعه قرار گرفته است که با اضافه کردن محدودیتهای مختلفی به آن، به دنیای واقعی نزدیکتر میشوند. جدول 1 تنوع محدودیتهای این مسأله را نشان میدهد [19]. چند مورد از توابع هدف این مسأله عبارتند از [20]:
• حداقل كردن هزينه (زمان – سفر) كل سيستم.
• استفاده از حداقل تعداد وسایل نقلیهي ممكن براي سرويس دهي به مشتريان.
• حداکثر كردن تعداد مشترياني كه توسط وسایل نقلیه به آنها سرويس داده ميشود.
• توازن در سيستم، براي امكان سرويس دهي به مشتريان در بازههاي زماني تعيين شده.
• حداقل كردن زيانهاي ناشي از عدم برآورده شدن برخي خواستههاي مشتريان.
• حداقل كردن زيانهاي ناشي از عدم استفاده از كل ظرفيت وسایل نقلیه.
2. 2 پژوهشهای انجام شده در زمینهی مسیریابی وسایل نقلیه
با توسعه فناوری اطلاعات و ارتباطات از راه دور و استقبال گسترده از تلفن های هوشمند، مصرف کنندگان به تدریج الگوی خرید خود را به سمت خرید آنلاین تغییر میدهند. آنها میتوانند هر لحظه از هر مکان از تلفنهای هوشمند خود محصولات را سفارش دهند و حجم و تنوع محصولات تحویل شده به مصرف کنندگان به طرز انفجاری افزایش مییابد. شرکتهای این صنعت، باید راهکارهای عملیاتی را برای تأمین تقاضای روزافزون برای تحویل و بازگشت محصولات تنظیم کنند، و تمرکز آنها باید مشکلات مسیریابی وسایل نقلیه در دنیای واقعی با در نظر گرفتن سفارشات پویا اضافی در طول زمان نیز باشد.
جدول 1. انواع محدودیتهای مسیریابی وسایل نقلیه [19]
| شاخص | انواع | ||
1 | تعداد وسائل نقلیه | دقیقا" n وسیله | حداکثرn وسیله | نامحدود |
2 | تعداد مشتریان | قطعی | تصادفی |
|
3 | نوع پنجره زمانی | قطعی | تصادفی | نامشخص |
4 | ساختار پنجره زمانی | نرم | سخت | آمیخته |
5 | مکان مشتریان | رأس ها | یال ها |
|
6 | ظرفیت وسائل | محدود | نامحدود |
|
7 | نوع وسائل نقلیه | همگن | ناهمگن |
|
8 | نوع تقاضا | جمع آوری | تحویل | جمع آوری و تحویل |
9 | تفکیک بار | با تفکیک بار | بدون تفکیک بار |
|
10 | هزینه | وابسته به زمان سفر | وابسته به مسافت | وابسته به نوع وسیله |
11 | تعداد تسهیلات | یک تسهیل | چند تسهیل |
|
12 | نوع مدل | ایستا | پویا |
|
13 | افق زمانی | یک دورهای | چند دورهای |
|
در پژوهشی، یک استراتژی انتظار، برای مشکل مسیریابی خودرو با وانت و تحویل همزمان با استفاده از الگوریتم ژنتیک پیشنهاد شد و اهمیت و کاربرد استراتژی انتظار از طریق آزمایشهای متعدد بررسی و تأیید شد [21]. همچنین در تحقیقی دیگر، یک روش مبتنی بر الگوریتم شبیهسازی تبرید، برای حل مسیریابی وسایل نقلیه ارائه گردید [22].
روشی نیز برای مسیریابی براساس مکان و موجودی محصولات فاسدشدنی معرفی شد [23]. این مدل تعداد و محل انبارهای مورد نیاز، سطح موجودی در هر خرده فروش و مسیرهای پیموده شده توسط هر وسیله نقلیه را با استفاده از الگوریتم ژنتیک تعیین میکرد.
در مسائل بهینه سازی پویا، حداقل یک بخش از مسأله با گذشت زمان تغییر می کند. برای مسیریابی وسایل نقلیه پویا، مشتریان میتوانند تغییر کنند. در این راستا، با استفاده از الگوریتم ژنتیک بهبود یافته، الگوریتمی ارائه گردید تا با ایجاد تنوع، امکان فرار از بهینه محلی را فراهم آورند و به راه حلهای مناسب دست یابند [24].
برای مشکل توزیع روزنامه در دنیای واقعی با سیاست بازیافت، طرحی پیشنهاد شد [25]. به منظور رفع تمامی محدودیت های پیچیده موجود در چنین مشکلی، یک مسأله مسیریابی وسیله نقلیه با استفاده از الگوریتم کرم شب تاب توسعهیافته طراحی شد که به تواند به طور خاص به عنوان یک مسأله مسیریابی با بارگیری و تحویل همزمان، هزینههای متغیر و مسیرهای ممنوعه را در برگیرد.
در تحقیقی دیگر، مسأله مسیریابی پویا وسیله نقلیه بررسی شد که به دنبال برنامهریزی برای تحویل سفارشات وانتهای پویایی است که در زمان واقعی میرسند[26]. یک برنامه از پیش تعیین شده هم برای ارائه سفارشات تحویل ثابت، اجرا میگردد. واگذاری اولیه سفارشات تحویل به وسایل نقلیه ممکن است عملکرد سیستم را محدود کند، زیرا تغییرات در وضعیت سیستم ناشی از ورود سفارشات پویا ممکن است موجب واگذاری مجدد سفارشات شود. بنابراین در این تحقیق اجازه داده شد که سفارشات بین وسایل نقلیه در حین اجرای طرح، منتقل شوند. روش پیشنهادی با آن دسته مسائلی که اجازه انتقال ندارند مقایسه شد و نتایج بهتری را نشان داد.
دو روش مبتنی بر شبیهسازی تبرید برای حل مسأله مسیریابی موقعیت مکانی ظرفیت دار ارائه شد [27]. روش پیشنهادی براساس تولید جمعیت اولیه مبتنی بر روش حریصانه و تخصیص به نزدیکترین وسایل نقلیه بود که برای هر عضو چهار همسایه نیز در نظر گرفته میشد. سپس راهحلها براساس مسأله کوله پشتی صفر و یک و الگوریتم ابتکاری بهبود مییافت تا بهترین مسیر پیدا گردد.
در پژوهش دیگری نشان داده شد که اگر جستجو محلی به خوبی در مسأله مسیر یابی وسایل نقلیه استفاده شود، راه حلهایی با کیفیت بالا به دست میآید [28]. برای این منظور سه روش جستجو محلی قدرتمند را با هم ترکیب شد و در آزمایشها نشان داده شد که چگونه جستجو محلی میتواند از دانش مشخصی برای مسأله استفاده کند تا جستجو را به راه حلهای امیدوارکننده هدایت کند.
همچنین، عملکرد الگوريتمهای ژنتیک، جستجوی ممنوعه و کلونی مورچگان، براي مسيريابي وسيله نقليه پويا به منظور بهره وري و کارايي سيستمهاي حمل و نقل مورد بررسی قرار گرفت [29]. نتایج نشان داد که الگوریتم ژنتیک نتایج بهتری ارائه میدهد.
در پژوهش دیگری، نتایج مسأله مسيريابي وسايل نقليه چند انباره با در نظر گرفتن پنجره زماني و تقاضاي فازي، با استفاده از الگوریتمهای ژنتیک و بهینهسازی ازدحام ذرات برای خدمات بهداشتی خانگی بررسی شد [30]. در این تحقیق نیز الگوریتم ژنتیک نتایج بهتری را نشان میداد. محققان دیگری، عملکرد الگوریتمی بهبود یافته از کلوني مورچگان را درمساله مسيريابي وسايل نقليه به همراه پنجرههاي زماني بررسی کردند [31].
یک الگوریتم ژنتیک تصادفی هم برای حل مسأله مسیریابی باز با محدودیتهای ظرفیت و فاصله ارائه شد. در این مسأله، وسایل نقلیه به منظور تحویل کالاهای مورد نیاز مشتریان از انبار خارج شده و بعد از سرویس به آخرین مشتری، بدون مراجعه به انبار به کار خود پایان میدهند. در تابع هدف این مسأله، با توجه به ظرفیت و حداکثر محدودیتهای فاصله، فاصله کل سفر باید حداقل گردد. الگوریتم پیشنهادی برای انجام جستجوی محلی طراحی شد که این جستجو به کاهش تعداد تکرار مورد نیاز برای رسیدن به همگرایی کمک میکرد [32].
روشهای ارائه شده برای حل مسائل مسیریابی وسایل نقلیهتوسط الگوریتمهای فراابتکاری بسیار متنوع هستند و تنوع و اهمیت آن، باعث انجام پژوهشهای بسیاری در خصوص انواع محدودیتها و راه حلهای مختلف برای آن شده است [33]. روشهای ارائه شده، از الگوریتمهای پیوسته و ناپیوسته فراابتکاری استفاده کردهاند [34]. از آنجایی که روشهای ارائه شده از الگوریتمهایی استفاده کردهاند که یا جستجوی محلی را تقویت کردهاند و یا جستجوی سراسری را، به نظر میرسد که الگوریتمی که بهتواند با یک رویکرد هوشمندانه، هر دو جستجو را در کنار هم تقویت کند میتواند راهحلهای مناسبی را تولید کند.
3. الگوریتم جهش قورباغه مخلوط شده
این الگوریتم، یکی از الگوریتمهای فراابتکاری است که در دو نسخه ناپیوسته [12] و پیوسته [35] ارائه شده است و از رفتار اجتماعی قورباغهها الهام گرفته شده است. در واقع از ترکیب قابلیتهای تکاملی الگوریتم ژنتیک و جستجوی تصادفی الگوریتم جستجوی تصادفی کنترل شده3 الهام گرفته شده است و میتوان آن را در دسته الگوریتمهای تقلیدگرا4 طبقهبندی کرد. در این الگوریتم، جمعیت قورباغهها به چندین زیرمجموعه تقسیم میشوند که هر قورباغه رفتار مختص به خود را دارد و میتواند از رفتارها یا ایدههای قورباغههای دیگر در طول روند تکامل استفاده کند.
3. 1 الگوریتم جهش قورباغه مخلوط شده پیوسته
مانند سایر الگوریتمهای فراابتکاری ابتدا جمعیت مقداردهی اولیه میگردد، سپس عملیات بعدی روی جمعیت انجام میشود.
1. 1 تولید جمعیت اولیه قورباغهها
همانند الگوریتمهای فراابتکاری، جمعیت اولیه به صورت تصادفی در بازه مسأله با توجه به رابطه (1) مقداردهی میشود:
(1)
که در آن، 
موقعیت هر عضو از جمعیت، 
کران پایین ، 
کران بالا وrand یک عدد تصادفی با توزیع یکنواخت در بازه 0 تا 1 است. موقعیت قورباغه در فضای جستجو به عنوان یک راه حل در مسأله بهینهسازی در نظر گرفته میشود. در مرحله بعدي، با استفاده از تابع هدف تعريف شده، هر يك از جوا بهاي مسأله ارزيابي ميگردند و راه حلها، با توجه به مقادير شايستگي شان، مرتب میگردند.
3. 1. 2 گروهبندی قورباغهها
اگر جمعیت اولیه با P قورباغه تولید شده باشد و به m مجموعه تقسیم شوند، قورباغهها در این گروهها براساس تابع هدف تقسیمبندی میشوند. پس از مرتبسازی، قورباغه اول به مجموعه اول، قورباغه دوم به مجموعه دوم و قورباغه m به مجموعه mام تعلق دارند. این روند تا قورباغه آخر به این صورت تکرار میشود.بنابراین، نحوه گروهبندی قورباغهها به این صورت است که هر مجموعه m دارای n قورباغه میگردد به صورتی که داریم:
(2) 
3. 1. 3 مراحل جستوجوی محلی در الگوریتم
در هر گروه، به بدترین قورباغه شانس بهتر شدن میدهند. اختلاف بین قورباغه بهتر با بهترین شایستگی
و بدترین قورباغه با بدترین شایستگی
در هر گروه محاسبه میگردد (
) و بدترین قورباغه در هر گروه براساس رابطه (4) دارای موقعیت جدیدی (
)میگردد. چنانچه موقعیت جدید بهتر از موقعیت قبلی باشد، موقعیت جدید جایگزین میگردد، در غیر این صورت یک موقعیت تصادفی جایگزین بدترین موقعیت گروه میگردد.
(3) |
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
(4) |
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
(5) |
|
[1] نویسنده مسئول: زهرا بهشتی z-beheshti@iaun.ac.ir
[2] . 1 Vehicle Routing Problem (VRP)
2 Combinatorial optimization problem
[3] Controlled Random Search (CRS)
[4] 2 Memetic Algorithm
شکل 2. روندنما الگوریتم پیشنهادی جهش قورباغه مخلوط شده فرد محور
Function io-SFLA1 (Memeplex {k}) /*k: The kth Memeplex as input*/ Output: Updated_Mempelex BEGIN NewPopulation= Memeplex {k} Calculate fitness NewPopulation ImprovementStep2 = false Selecting the BestSol from NewPopulation /* It is the first member of NewPopulation */ For i=2: size (k) Do NewSol1.Position = Crossover (BestSol, NewPopulation(i)) NewSol1.Cost = CostFunction (NewSol1.Position) If NewSol1.Cost is better than NewPopulation(i).Cost then NewPopulation(i) = NewSol1 Else ImprovementStep2 = true End if If ImprovementStep2= true NewSol2.Position = mutition (NewPopulation(i)) NewSol2.Cost = CostFunction (NewSol2.Position) If NewSol2.Cost is better than NewPopulation(i).Cost NewPopulation(i) = NewSol2 End if End if End for Updated_Mempelex = NewPopulation Return Updated_Mempelex END |
Pseudocode of IO-SFLA Input: maxiteration, m /* m: The number of Memeplex */ Output: SBest BEGIN Generating population randomly Calculating fitness functions While iteration < maxiteration Do Selecting the best solution (SBest) Sorting Population Initializing Memeplexes Array For k = 1: m Memeplex Formation Updated_Memeplex =Call io-SFLA1 (Memeplex {k}) Replacing Updated_Memeplex into the population End for Merging Memeplexes Qrand = TournamentSelection (Population) NewQrand = Call io-SFLA2 (Qrand, SBest, Worst Solution) Replacing NewQrand in the poulation End while Return SBest END |
شکل 4. شبه کد مرحله اول بهبود الگوریتم پیشنهادی
Function io-SFLA2 (Qrand, Best Solution, Worst Solution) /*input parameters*/ Output: NewQrand BEGIN While i < size (Qrand) NewSol1 = Qrand (i) NewSol2 = Crossover (WorstSol, NewSol1) NewSol.Position = Crossover (BestSol, NewSol2) NewSol.Cost = CostFunction (NewSol.Position) If NewSol.Cost is better than Qrand (i).Cost Qrand (i) = NewSol End if End while NewQrand = Qrand Return NewQrand END |
شکل 5. شبه کد مرحله دوم بهبود الگوریتم پیشنهادی
4. 2 نگاشت الگوریتم جهش قورباغه مخلوط شده فرد محور به مسأله مسیریابی وسایل نقلیه
الگوریتم پیشنهادی، برای بهینه کردن مسألهی مسیریابی وسایل نقلیه استفاده میشود. قورباغهها راه حلها را می سازند که یک مسیر است. هدف روش پیشنهادی، کمینهسازی طول کل سفر (طول مسیر) است. با توجه به علائم، پارامترها و متغیرهای تعریف شده، مدل ریاضی پیشنهادی متشکل از یک تابع هدف و محدودیت ظرفیت میباشد. در این تحقیق یک مسأله مسیریابی وسایل نقلیه ظرفیت دار برای شبکه توزیع استفاده میگردد که شامل اجزا زیر است:
I: مجموعه مشتریان که باید ملاقات شوند.
گره 0 به عنوان انبار شناخته می شوند.
: مجموعه یالها (اتصالات ما بین گرهها و یا نقاط تقاضا) است.
: طول یال ما بین دو گره i 
و k به طوری که:
(شبکه راهها متقارن است).
: طول یال مابین انبار و گره i است.
: مجموعه وسایل نقلیه در دسترس است. 
: ظرفیت وسیله نقلیه j ام است.
: تقاضای مشتری i ام است. 
: فهرست مشتریان تخصیص داده شده به وسیله نقلیه j ام است.
محدودیت ظرفیت: 
برای نگاشت الگوریتم جهش قورباغه پیشنهادی به مسأله مسیریابی وسایل نقلیه، موقعیت هر قورباغه به عنوان راه حلی برای یک مسیر در نظر گرفته میشود. یعنی موقعیت هر قورباغه شامل مسیر طی شده توسط وسایل نقلیه موجود می باشد.
مثالی از ساختار ابعاد یک قورباغه با توجه به تخصیص مشتریان به وسایل نقلیه در شکل 6 نشان داده شده است. در این شکل، 9 مشتری وجود دارد که با i3, i2, i1 i9, i8, i7, i6, i5, i4, نشان داده شدهاند. مشتریان توسط وسایل نقلیه سرویسدهی می شود که با j3, j2 ,j1 مشخص شدهاند.
شکل 6: مثالی از ساختار یک قورباغه در الگوریتم پیشنهادی
هدف اصلی، سرویس دهی وسایل نقلیه به مشتریان به صورتی است که مسیر طی شده توسط هر وسیله نقلیه به حداقل برسد. در هر مسیر تعدادی از مشتریان به وسایل نقلیه تخصیص داده میشوند، اما ممکن است تعداد مشتریان تخصیص داده شده از ظرفیت وسیله نقلیه بیشتر گردد، در این صورت تخطی1 از ظرفیت مجاز را خواهیم داشت. در صورتی که تعداد مشتریان تخصیص داده شده کمتر از ظرفیت مجاز یا مساوی با آن باشند، تخطی صفر خواهد بود. به عنوان مثال اگر ظرفیت مجاز برای یک وسیله نقلیه C0 باشد و راه حلی از C ظرفیت استفاده کرده باشد، میزان تخطی به نسبت ظرفیت مجاز وسیله نقلیه محاسبه میگردد و برابر است با:
(6) |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
(7) |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
(8) |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
(9) |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
مرتبسازی جمعیت بر اساس مقادیر تصادفی:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
شکل 7. مجموعه الگوهای جمعیت اولیه
4. 2. 2 دستهبندی گروهها
در ادامه جمعیت، براساس مقدار تابع هدف مرتب هر قورباغه میشود. و سپس به 3 گروه تقسیم میشوند. روند تقسیم بندی قورباغهها بدین صورت است که قورباغه اول به مجموعه اول، قورباغه دوم به مجموعه دوم و قورباغه m به مجموعه m ام تعلق دارند. این روند به صورت مشابه تا قورباغه آخر تکرار میشود. در شکلهای 8 ، 9 و 10 گروهها را به تفکیک مشخص شدهاند.
|
شکل 8. مجموعه الگوهای گروه اول
|
شکل 9. مجموعه الگوهای گروه دوم
مقدار تابع هدف
|
شکل 10. مجموعه الگوهای گروه سوم
4. 2. 3 فاز اول بهبود الگوریتم جهش قورباغه مخلوط شده فرد محور
در این فاز، قورباغههای گروهها بهبود پیدا میکنند. هدف از این کار جلوگیری از تصمیمگیری سریع در انتخاب موقعیت بهتر است. بهترین الگو هر گروه مشخص میشود. در مرحله بعد تک تک اعضا گروه با بهترین الگو گروه ترکیب میشوند. ترکیب اعضا به صورت تصادفی به یکی از سه روش زیر انجام می شود:
ترکیب یک نقطهای
ترکیب دو نقطهای
ترکیب با استفاده از ماسک
شکل 11 بهترین الگوی گروه اول را نشان میدهد. در ترکیب یک نقطهای از یک نقطه به بعد ژنهای دو والد جابجا میشوند. در ترکیب دو نقطهای، دو ژن مشخص میگردند و کلیه ژنهای بین این دو نقطه در دو والد جابجا میشوند. در ترکیب با ماسک، ماسکی از صفر و یکها تولید میشود و براساس آن عمل ترکیب انجام میشود. ابتدا یک الگو همانند شکل 12 به طول قورباغههای والد و به صورت تصادفی با مقادیر صفر و یک تولید میشود. از این الگو به عنوان ماسک استفاده کرده و در قورباغه فرزند از چپ شروع کرده هر مقدار در ماسک تولید شده صفر بود از والد دوم و هرمقدار یک بود از والد اول کپی میشود. شکل 13 ترکیب تولید شده از دو والد را نمایش می دهد.
|
شکل 11. بهترین الگوی گروه اول
|
شکل 12. ماسک تولید شده به صورت تصادفی
|
شکل 13. ترکیب دو والد و فرزند جدید
پس از ترکیب دو والد تابع هدف فرزند جدید محاسبه میشود. در صورتی که فرزند جدید بهتر از قورباغه قبلی بود، جایگزین میشود. در غیر این صورت قورباغه قبلی به صورت تصادفی توسط یکی از سه روش زیر جهش داده می شود جابجایی، درج . معکوس. در روش جابجایی، دو ژن در یک کروکوزوم با یکدیگر جابجا میشوند. در روش درج، یک ژن از جای اصلی خودش حذف و در جای دیگری درج میگردد. در این مثال از جهش معکوس استفاده میشود. برای جهش به روش معکوس، دو نقطه تصادفی در الگو انتخاب میشود، برای مثال نقاط 8 و 1 و مقادیر بین آنها به صورت معکوس در الگو کپی میشود. شکل 14 الگو ایجاد شده از جهش را نمایش می دهد.
|
شکل 14. جهش قورباغه و تولید فرزند جدید
در مرحله بعد اگر قورباغه جدید بهتر از قبل بود جایگزین قورباغه قبلی میشود در غیر این صورت قورباغه بدون تغییر به مرحله بعد میرود. شکل 15 جمعیت بهبودیافته بعد از فاز اول را نشان میدهد. گروهها با هم ادغام میشوند و بخشی از جمعیت به صورت انتخاب مسابقهای برگزیده میشود و وارد فاز دوم بهبود میشوند.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
شکل 15. جمعیت بهبودیافته بعد از فاز اول
4. 2. 4 فاز دوم بهبود الگوریتم جهش قورباغه فرد محور
در فاز دوم برای جلوگیری از همگرایی زودرس الگوریتم و توقف در بهینه محلی، بخشی از جمعیت به صورت مسابقهای انتخاب شدهاند، برای بهبود وارد این مرحله میگردند. برای مثال همان طور که در شکل 16 دیده میشود، از بین جمعیت 3 قورباغه به صورت انتخاب مسابقهای برگزیده میشوند که عبارتند از: {1و2و3} و مقدار تابع هدف آنها {24/220 و 89/254 و 19/244} میباشد و وارد فاز بهبود میشوند.
در این مرحله بدترین و بهترین قورباغه با تکتک قورباغههای جمعیت انتخابی ترکیب میشوند. ابتدا با بدترین قورباغه مشخص شده ترکیب میشود و سپس قورباغه به وجود آمده از ترکیب، با بهترین کل جمعیت ترکیب میشود.
| ||||||||||||||||||||||||||||||||||||||||||||
شکل 16. بخشی از جمعیت برای فاز دوم بهبود
ترکیب الگو همانند فاز اول به یکی از سه روش به صورت تصادفی انجام میگیرد. قورباغه جدید مورد ارزیابی قرار میگیرد و در صورت بهتر بودن از قورباغه قبلی جایگزین میشود. این روند برای تک تک زیر جمعیت انتخابی ادامه مییابد. سپس زیر جمعیت بهبود یافته جایگزین قورباغههای قبلی میشود. در این مرحله، بهترین عضو جمعیت مشخص میشود. این روند به تعداد تکرار مشخص ادامه مییابد تا شرط خاتمه برقرار شود. شکل 17 بهترین مسیر به دست آمده توسط قورباغهها برای مسیر یابی وسایل نقلیه در مثال فوق را نشان میدهد. روندنما الگوریتم پیشنهادی در شکل 18 نمایش داده شده است.
|
شکل 17. بهترین مسیر به دست آمده توسط قورباغهها برای مثال مسیر یابی وسایل نقلیه
|
شکل18. روندنما الگوریتم جهش قورباغه مخلوط شده فرد محور برای مسیریابی وسایل نقلیه
5. ارزیابی الگوریتم پیشنهادی در مسأله مسیریابی وسایل نقلیه
در این بخش، با استفاده از مجموعه دادگان استاندارد [36]، نتایج الگوریتم پیشنهادی روی مسأله مسیر یابی وسایل نقلیه، ارزیابی میشود.
5. 1 مجموعه دادگان مورد استفاده در مسأله مسیریابی وسایل نقلیه
از 6 مسأله مسیریابی استاندارد برای ارزیابی روش پیشنهادی استفاده شده است که میتوان آنها را به مسائلی با ابعاد کوچک، متوسط و بزرگ تقسیم بندی کرد. مشخصات مربوط به هر مسأله مسیریابی در جدول 2 نشان داده شده است. این نمونه داده از دادههای ارائه شده توسط کریستوفیدس و همکارانش استخراج شده است [36]. در هر مسأله، تعداد وسیله نقلیه، تعداد مشتریان و ظرفیت وسیله نقلیه مشخص شده است.
جدول2. تعداد وسایل نقلیه، تعداد مشتریان و ظرفیت وسیله نقلیه استفاده شده در آزمایشها
مسأله مسیریابی | تعداد وسیله نقلیه | تعداد مشتریان | ظرفیت وسیله نقلیه | بعد |
1 | 5 | 51 | 160 | کوچک |
2 | 10 | 76 | 140 | |
3 | 10 | 101 | 200 | متوسط |
4 | 7 | 121 | 200 | |
5 | 14 | 151 | 200 | بزرگ |
6 | 18 | 200 | 200 |
5. 2 آزمایشها و ارزیابی نتایج
نتایج الگوریتم جهش قورباغه بهبودیافته پیشنهادی با شش الگوریتم جهش قورباغه مخلوط شده ناپیوسته [12] و پیوسته [35]، جهش قورباغه بهبودیافته لی و یان [13]، جهش قورباغه اصلاح شده [37]، شبیهسازی تبرید [38] و الگوریتم ژنتیک پیوسته [39] مقایسه شده است. الگوریتمها با مسائل استاندارد در ابعاد کوچک، متوسط و بزرگ مورد ارزیابی قرار گرفتهاند.
تعداد تکرار در هر اجرا 500 در نظر گرفته شده و هر الگوریتم 10 بار برای هر مسأله اجرا شده است. در این آزمایشها تعداد گروهها 7 و تعداد جمعیت هر گروه 15 در نظر گرفته شده است. این مقادیر بهترین مقادیر به دست آمده براساس تحلیل حساسیت بر روی متغیرهای مستقل و وابسته میباشد. نتایج این تحلیل در جدول 3 نشان داده شده است.
جدول3. نتایج تحلیل حساسیت برروی متغیرهای مستقل جهت انتخاب پارامترهای مناسب الگوریتم
میانگین طول مسیر بهینه | حداکثر تعداد تکرار | جمعیت هر گروه | تعداد گروهها |
1049.5 | 400 | 15 | 7 |
1081 | 500 | 15 | 5 |
1078 | 500 | 10 | 5 |
1039.10 | 500 | 15 | 7 |
میانگین بهترین جواب، انحراف معیار، بهترین مقدار به دست آمده و رتبهی هر الگوریتم براساس میانگین بهترین جواب در جداولهای 4 و 5 برای مسأله مسیریابی 1 و 2 در بعد کوچک، در جدولهای 6 و 7 برای مسأله مسیریابی 3 و4 در بعد متوسط و در جدولهای 8 و 9 برای مسأله مسیریابی 5 و6 در بعد بزرگ نشان داده شده است.
همان طور که مشاهده میشود، الگوریتم پیشنهادی، راه حلهای بهتری در مقایسه با الگوریتمهای دیگر ارائه کرده است. در ابعاد پایین نتایج به دست آمده از الگوریتم پیشنهادی به الگوریتم شبیه سازی تبرید نزدیک است. با افزایش ابعاد، الگوریتم جهش قورباغه مخلوط شده فرد محور راهحلهای بهتری نسبت به سایر الگوریتمها ارائه میدهد و هر چه ابعاد مسأله بزرگتر میگردد این تفاوت قابل توجهتر است. الگوریتم ژنتیک پیوسته عملکرد ضعیفی را از خود ارائه میدهد.
در بین الگوریتمهای جهش قورباغه مورد مقایسه در این تحقیق، الگوریتم جهش قورباغه پیوسته، از همه ضعیفتر عمل کرده است. همانطور که در این جدولها مشاهده میشود دو الگوریتم ژنتیک پیوسته و جهش قورباغه پیوسته عملکرد ضعیفتری نسبت به الگوریتمهای ناپیوسته دارند.
جدول4. نتایج الگوریتمها برای مسأله مسیریابی 1
رتبه | الگوریتم | میانگین | بهترین | انحراف معیار |
6 | جهش قورباغه پیوسته | 2253.80 | 2150.60 | 49.54 |
3 | جهش قورباغه گسسته | 1515.80 | 1245.40 | 116.80 |
5 | جهش قورباغه لی و یان | 2043.50 | 1929.40 | 97.26 |
4 | جهش قورباغه اصلاحشده | 1942.00 | 1823.70 | 91.40 |
7 | ژنتیک پیوسته | 2310.00 | 2088.00 | 208.40 |
1 | شبیهسازی تبرید | 704.65 | 672.18 | 31.03 |
2 | جهش قورباغه فرد محور | 708.89 | 672.98 | 19.64 |
جدول 5. نتایج الگوریتمها برای مسأله مسیریابی 2
الگوریتم | میانگین | بهترین | انحراف معیار | |
6 | جهش قورباغه پیوسته | 2614.50 | 2428.20 | 98.40 |
3 | جهش قورباغه گسسته | 2081.60 | 1846.40 | 130.92 |
5 | جهش قورباغه لی و یان | 2538.70 | 2293.00 | 139.51 |
4 | جهش قورباغه اصلاحشده | 2156.50 | 1950.70 | 116.69 |
7 | ژنتیک پیوسته | 3195.60 | 2889.80 | 155.92 |
2 | شبیهسازی تبرید | 845.84 | 809.34 | 28.79 |
1 | جهش قورباغه فرد محور | 807.59 | 785.21 | 27.90 |
جدول 6. نتایج الگوریتمها برای مسأله مسیریابی 3
رتبه | الگوریتم | میانگین | بهترین | انحراف معیار |
6 | جهش قورباغه پیوسته | 4010.00 | 3734.00 | 154.43 |
3 | جهش قورباغه گسسته | 2959.90 | 2622.80 | 173.38 |
5 | جهش قورباغه لی و یان | 3712.90 | 3525.80 | 140.06 |
4 | جهش قورباغه اصلاحشده | 3387.00 | 2963.50 | 256.43 |
7 | ژنتیک پیوسته | 4677.90 | 4381.80 | 246.47 |
2 | شبیهسازی تبرید | 979.53 | 931.33 | 36.51 |
1 | جهش قورباغه فرد محور | 913.61 | 895.64 | 21.66 |
جدول 7. نتایج الگوریتمها برای مسأله مسیریابی 4
رتبه | الگوریتم | میانگین | بهترین | انحراف معیار |
7 | جهش قورباغه پیوسته | 17346.00 | 16334.00 | 646.60 |
3 | جهش قورباغه گسسته | 9786.60 | 8669.00 | 627.14 |
4 | جهش قورباغه لی و یان | 10613.00 | 9437.40 | 643.41 |
5 | جهش قورباغه اصلاحشده | 14123.00 | 11579.00 | 1119.30 |
6 | ژنتیک پیوسته | 14807.00 | 13100.00 | 1201.70 |
2 | شبیهسازی تبرید | 2943.70 | 2849.70 | 94.41 |
1 | جهش قورباغه فرد محور | 2717.40 | 2625.60 | 65.20 |
جدول 8. نتایج الگوریتمها برای مسأله مسیریابی 5
الگوریتم | میانگین | بهترین | انحراف معیار | |
6 | جهش قورباغه پیوسته | 3981.30 | 3814.80 | 88.43 |
4 | جهش قورباغه گسسته | 3451.80 | 3228.20 | 188.28 |
5 | جهش قورباغه لی و یان | 3859.30 | 3666.10 | 150.87 |
3 | جهش قورباغه اصلاحشده | 3408.70 | 3250.50 | 144.66 |
7 | ژنتیک پیوسته | 5150.30 | 4743.60 | 224.93 |
2 | شبیهسازی تبرید | 939.26 | 888.00 | 26.07 |
1 | جهش قورباغه فرد محور | 800.03 | 781.12 | 20.02 |
جدول9. نتایج الگوریتمها برای مسأله مسیریابی 6
رتبه | الگوریتم | میانگین | بهترین | انحراف معیار |
6 | جهش قورباغه پیوسته | 5466.60 | 5336.90 | 104.16 |
4 | جهش قورباغه گسسته | 4933.90 | 4583.90 | 210.33 |
5 | جهش قورباغه لی و یان | 5208.50 | 4753.60 | 256.47 |
3 | جهش قورباغه اصلاحشده | 4579.50 | 4251.90 | 249.34 |
7 | ژنتیک پیوسته | 7960.30 | 7636.40 | 131.04 |
2 | شبیهسازی تبرید | 1265.40 | 1221.80 | 30.95 |
1 | جهش قورباغه فرد محور | 1039.10 | 1022.10 | 12.37 |
شکلهای 19 تا 24، سرعت همگرایی الگوریتم های جهش قورباغه پیوسته، جهش قورباغه گسسته، جهش قورباغه بهبودیافته لی و یان، جهش قورباغه اصلاح شده، شبیهسازی تبرید، ژنتیک پیوسته و جهش قورباغه فرد محور برای مسألههای مسیریابی شماره 1 تا شماره 6 نشان میدهد. شکلهای 19 و 20 برای ابعاد کوچک، شکلهای 21 و 22 برای ابعاد متوسط و شکلهای 23 و 24 برای ابعاد بزرگ مسأله مسیریابی وسایل نقلیه هستند.
همان طور که مشاهده میشود، روش پیشنهادی دارای سرعت همگرایی بالایی نسبت به سایر الگوریتمهای مورد مقایسه است. همچنین الگوریتم ژنتیک پیوسته، در همان ابتدای اجرا، گرفتار همگرایی زودرس میگردد و به دام بهینه محلی گرفتار میآید. از نمودار همگرایی الگوریتمهای مورد مقایسه چنین میتوان نتیجه گرفت که الگوریتمهای ناپیوسته، عملکرد بهتری نسبت به الگوریتمهای پیوسته دارند و راهحلهای بهتری را ارائه کردهاند. همچنین با افزایش ابعاد مسأله، کارایی الگوریتم پیشنهادی در مقایسه با سایر الگوریتمها، قابل توجه میباشد.
شکل 19. سرعت همگرایی الگوریتمها برای مسأله مسیریابی شماره 1 |
شکل 20. سرعت همگرایی الگوریتمها برای مسأله مسیریابی شماره 2 |
شکل 21. سرعت همگرایی الگوریتمها برای مسأله مسیریابی شماره 3 |
شکل 22. سرعت همگرایی الگوریتمها برای مسأله مسیریابی شماره 4 |
شکل 23. سرعت همگرایی الگوریتمها برای مسأله مسیریابی شماره 5 |
شکل 24. سرعت همگرایی الگوریتمها برای مسأله مسیریابی شماره 6 |
جدول 10، نتایج آزمون فریدمن [40] بر روی مسائل مختلف مسیریابی وسایل نقلیه را نشان میدهد. همانطور که در جدول مشاهده میشود، روش پیشنهادی بهترین نتیجه را دارد و دارای رتبه اول است. به غیر از مسأله 1 که الگوریتم شبیهسازی تبرید و الگوریتم پیشنهادی دارای یک رتبه هستند، در بقیه موارد الگوریتم پیشنهادی، عملکرد بهتری داشته است. در این جدول الگوریتم شبیه سازی تبرید، در رتبه دوم قرار دارد و الگوریتم ژنتیک پیوسته بدترین رتبه را دارد. همچنین الگوریتم جهش قورباغه گسسته از سایر نسخههای الگوریتم جهش قورباغه به غیر از الگوریتم پیشنهادی رتبه بهتری را در این جدول داراست.
جدول 10. نتایج آزمون فریدمن روی مسائل مختلف مسیریابی وسایل نقلیه
مسأله مسیریابی الگوریتم | جهش قورباغه پیوسته | جهش قورباغه گسسته | جهش قورباغه لی و یان | جهش قورباغه اصلاحشده | ژنتیک پیوسته | شبیهسازی تبرید | جهش قورباغه فرد محور |
1 | 6.4 | 3 | 4.3 | 4.9 | 6.4 | 1.5 | 1.5 |
2 | 5.6 | 3.3 | 3.7 | 5.4 | 7 | 2 | 1 |
3 | 5.7 | 3 | 4.3 | 5 | 7 | 1.9 | 1.1 |
4 | 7 | 3.2 | 5.3 | 3.8 | 5.7 | 2 | 1 |
5 | 5.7 | 3.7 | 3.4 | 5.2 | 7 | 2 | 1 |
6 | 5.9 | 3.9 | 3.2 | 5 | 7 | 2 | 1 |
جمع | 36.3 | 20.1 | 24.2 | 29.3 | 40.1 | 11.4 | 6.6 |
رتبه | 6 | 3 | 4 | 5 | 7 | 2 | 1 |
جدول 11، میانگین نتایج الگوریتمهای مورد مقایسه را روی بهترین و میانگین جوابها برای تمام مسائل نشان میدهد. همانطور که در جدول مشخص است، الگوریتم پیشنهادی بهترین راه حلها را ارائه داده است.
جدول 11. میانگین نتایج الگوریتمها روی تمام مسائل مسیر یابی وسایل نقلیه
رتبه | الگوریتم | میانگین | بهترین |
6 | جهش قورباغه پیوسته | 5633.083 | 5945.367 |
3 | جهش قورباغه گسسته | 3699.283 | 4121.6 |
4 | جهش قورباغه لی و یان | 4267.550 | 4662.65 |
5 | جهش قورباغه اصلاحشده | 4303.217 | 4932.783 |
7 | ژنتیک پیوسته | 5806.600 | 6350.183 |
2 | شبیهسازی تبرید | 1228.725 | 1279.73 |
1 | جهش قورباغه فرد محور | 1130.442 | 1164.437 |
6. نتیجه گیری
در این تحقیق الگوریتم جهش قورباغه مخلوط شده فرد محور که الگوریتمی بهبودیافته از الگوریتم جهش قورباغه میباشد، ارائه شد و عملکرد آن با الگوریتمهایی چون الگوریتمهای جهش قورباغه مخلوط شده ناپیوسته و پیوسته، جهش قورباغه بهبودیافته لی و یان، جهش قورباغه اصلاح شده، شبیهسازی تبرید و الگوریتم ژنتیک پیوسته روی مسأله مسیر یابی وسایل نقلیه مورد آزمایش قرار گرفت تا توانایی الگوریتمها در به دست آوردن راه حلهای بهتر ارزیابی گردند. اهمیت موضوع این تحقیق از آنجا ناشی میشود که در چند دهه اخیر مسأله مسیریابی وسائل نقلیه کاربرد بسیار بالایی در عمل داشته و برای بهبود کارایی و بهرهوری سیستمهای حمل و نقل مطرح بوده است. این مسأله در دسته مسائل سخت است و الگوریتمهای دقیق، کارایی مناسب را در حل آن ندارند. همچنین الگوریتمهای فراابتکاری نیز در بسیاری از موارد نیازمند بهبود هستند تا به توانند فضای جواب را به شکل هدفمند جستجو کنند و به جواب نهایی مناسب برسند. الگوریتم جهش قورباغه مخلوط شده یکی از این الگوریتمهاست که در این تحقیق، سعی بر آن شده است که مشکلات همگرایی زودرس و گرفتاری در بهینه محلی آن بهبود یابد. مجموعه آزمایشها روی مجموعه دادههای استاندارد نشان میدهد که الگوریتم پیشنهادی رتبه بهتری نسبت به الگوریتمهای مورد مقایسه دارد. همچنین نمودارها نشان میدهد که الگوریتم جهش قورباغه مخلوط شده فرد محور، سرعت همگرایی قابل توجهی نسبت به الگوریتمهای مقایسه شده، دارد. هرچند الگوریتم پیشنهادی دارای عملکرد بالایی در حل مسأله مسسیریابی وسائل نقلیه است ولی میتوان در جهت گسترش این تحقیق برای راهکارهای آینده، به موارد زیر اشاره کرد:
ارزیابی عملکرد الگوریتم پیشنهادی در سایر مسائل بهینهسازی
پیاده سازی الگوریتم چند هدفه از الگوریتم پیشنهادی جهش قورباغه مخلوط شده فرد محور
استفاده از راهکارهای مورد استفاده در الگوریتم پیشنهادی در جهت بهبود راه حلها در سایر الگوریتمهای فراابتکاری
حل انواع دیگری از مسائل مسیریابی وسایل نقلیه با الگوریتم پیشنهادی و ارزیابی نتایج آن
مراجع
[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.
An Individual-Oriented Shuffled Frog Leaping Algorithm for Solving Vehicle Routing Problem
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.
Keywords: Vehicle Routing Problem (VRP), Shuffled Frog Leaping Algorithm (SFLA), Route cost, Mutation, Crossover operation.
The rights to this website are owned by the Raimag Press Management System.
Copyright © 2017-2024