بهبود حل مسئله VRPSPD با الگوریتم جستجوی ممنوعه

نوع مقاله : مقاله پژوهشی

نویسندگان

1 دانشجوی کارشناسی ارشد، گروه عمران، دانشکده مهندسی، دانشگاه زنجان، زنجان، ایران

2 دانشیار، گروه عمران، دانشکده مهندسی، دانشگاه زنجان، زنجان، ایران

چکیده

توسعه حمل و نقل تأثیر بسزایی در سیستم‌های اقتصادی اعم از تولیدی و خدماتی دارد که باعث ویژه شدن جایگاه مسئله مسیریابی وسیله‌نقلیه می‌شود. از مهم‌ترین تصمیمات در بخش‌های اجرایی توجه ویژه به یافتن مسیر‌های بهینه، حذف مسیرهای غیرضروری، بهبود در میزان مسافت مسیر طی شده، و کاهش تعداد ناوگان است. در همین راستا یکی از مسائل پیچیده و در عین حال بسیار با اهمیت در شبکه حمل و نقل است که این مسئله پتانسیل بالایی در تعیین مجموعه بهینه از ناوگان وسایل‌نقلیه با هدف خدمت‌رسانی به مجموعه‌ای از مشتریان را دارد و تلاش‌های بسیاری برای حل آن صورت گرفته است. الگوریتم‌های فرا ابتکاری گوناگونی طی سال‌های اخیر توسعه پیدا کرده‌اند، یکی از آنها الگوریتم جستجوی ممنوعه است زیرا قدرت و توانایی مناسبی در حل مسائل پیچیده دارد. در این تحقیق از الگوریتم Tabu Search برای حل مسئله مسیریابی وسیله‌نقلیه با دریافت و تحویل همزمان کالا استفاده شد. با اعمال برخی تغییرات در کدُنویسی آن در نرم افزار متلب و تعیین کردن مؤلفه‌های مقدار تکرار اجرای الگوریتم، مشخص کردن تعداد همسایگان و مقدار لیست ممنوعه باعث بهبود نتایج حاصل در مسافت‌های طی شده توسط وسایل‌نقلیه و بهینه کردن تعداد ناوگان گردید. نهایتاً الگوریتم پیشنهادی جدید روی 14 مسئله نمونه استاندارد از سری مسائل سلهی و نگی اجرا شد و مقادیر به دست آمده با بهترین نتایج موجود از سایر الگوریتم‌ها مقایسه شد که نتایج رضایتبخشی در مسائل کوچک مقیاس داشت.

کلیدواژه‌ها

موضوعات

عنوان مقاله [English]

Improved Solution of VRPSPD with the Tabu Search Algorithm

نویسندگان [English]

  • Seyed Amirali Seyednezhad 1
  • Amir Masoud Rahimi 2
1 M.Sc., Student, Department of Civil Engineering, Faculty of Engineering, University of Zanjan, Zanjan, Iran.
2 Associate Professor, Department of Civil Engineering, Faculty of Engineering, University of Zanjan, Zanjan, Iran.
چکیده [English]

The development of transportation has a significant impact on economic systems, both production and service, which makes the vehicle routing problem a special issue, one of the most important decisions in executive departments is to pay special attention to finding optimal routes, eliminating unnecessary routes, improving the distance traveled and reducing the number of fleets. In this regard, it is one of the complex and very important problem in the transportation network, this problem has a high potential in determining the optimal set of vehicle fleets with the aim of serving a set of customers, which many efforts have been made to solve it. Various meta-heuristic algorithms have been developed in recent years, one of them is the tabu search algorithm because it has good performance and ability to solve NP-Hard problems, and now in this article, the tabu search algorithm is used to solve the vehicle routing problem with simultaneous pick-up and delivery of goods which by applying some changes in its coding in MATLAB software. Determining the parameters of the repetition value of the algorithm, specifying the number of neighborhoods and the amount of the tabu list improved the results obtained in the distances traveled by vehicles and optimized the number of fleets. Finally, the new proposed algorithm was implemented on 14 standard sample problems from the Salhi and Nagi series of problems, and the obtained values were compared with the best available results from other algorithms, which had satisfactory results in small-scale problems.
.

کلیدواژه‌ها [English]

  • Optimization Algorithm
  • VRPSPD
  • Vehicle Routing Problem

مراجع

-وحید رجبی و امیرمسعود رحیمی. (1391). بهبود روش حل مسائل دریافت و تحویل همزمان کالا با استفاده از الگوریتم فرا ابتکاری ژنتیک. پایان نامه کارشناسی ارشد، استاد راهنما: امیرمسعود رحیمی، قزوین: دانشکده عمران، دانشگاه بین المللی امام خمینی (ره).
-فرشاد حمیدی و امیرمسعود رحیمی. (1395). ارزیابی کارایی الگوریتم کلونی زنبور مصنوعی در حل مسائل بهینه‌سازی ترکیبی. پایان نامه کارشناسی ارشد. استاد راهنما: امیرمسعود رحیمی. زنجان: دانشکده عمران، دانشگاه زنجان.
-یقینی، مسعود و اخوان کاظم زاده، محمدرحیمی، (1395). الگوریتم‌های بهینه‌سازی فرا ابتکاری. جهاد دانشگاهی واحد دانشگاه صنعتی امیرکبیر.
-Ai, T. J., & Kachitvichyanukul, V. (2009). A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research, 36(5), 1693-1702.
-Altabeeb, A. M., Mohsen, A. M., Abualigah, L., & Ghallab, A. (2021), Solving capacitated vehicle routing problem using cooperative firefly algorithm. Applied Soft Computing, 108, 107403.­
-Barbarosoglu, G., & Ozgur, D. (1999). A tabu search algorithm for the vehicle routing problem. Computers & Operations Research, 270-255,(3)26.
-Braekers, K., Ramaekers, K., & Van Nieuwenhuyse, I. (2016). The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 99, 300-313.­
-Cheikhrouhou, O., & Khoufi, I. (2021). A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches and taxonomy. Computer Science Review, 40, 100369.
-Daham, H. A., & Mohammed, H. J. (2021). An evolutionary algorithm approach for vehicle routing problems with backhauls. Materials Today: Proceedings.­
-Glover, F. W., & Kochenberger, G. A. (2006). Handbook of metaheuristics, Vol. 57. Springer Science & Business Media.­
-Goksal, F. P., Karaoglan, I., & Altiparmak, F. (2013). A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery. Computers & Industrial Engineering, 65(1), 39-53.
-Golden, B. L., Assad, A. A., & Wasil, E. A. (2002). Routing vehicles in the real world: applications in the solid waste, beverage, food, dairy, and newspaper industries. In The vehicle routing problem, 245-286. SIAM.
-Koç, Ç., Laporte, G., & Tükenmez, İ. (2020). A review of vehicle routing with simultaneous pickup and delivery. Computers & Operations Research, 122, 104987.­
-Li, L., Meng, J., & Chen, Y. (2019). Brief algorithm review on vehicle routing problems with different backhaul constraints. 2019 Chinese Control And Decision Conference (CCDC).
-Meliani, Y., Hani, Y., Elhaq, S. L., & El Mhamedi, A. (2019). A developed Tabu Search algorithm for heterogeneous fleet vehicle routing problem. IFAC-PapersOnLine, 52(13), 1051-1056.
-Michalik, M., & Ochelska-Mierzejewska, J. (2021). Comparison of Selected Algorithms Solving Vehicle Routing Problem with Simultaneous Delivery and Pickup. In Wojciechowski A.(Ed.), Napieralski P.(Ed.), Lipiński P.(Ed.)., TEWI 2021 (Technology, Education, Knowledge, Innovation), Seria: Monografie PŁ; Nr 2378, Wydawnictwo Politechniki Łódzkiej, Łódź 2021, ISBN 978-83-66741-10-2.
DOI. 10.34658/9788366741102. Wydawnictwo Politechniki Łódzkiej.­
-Mohammadi, M., Mahmoodian, N., & Mohammadi, H. (2022). A Simulated Annealing Approach (SA) to Vehicle Routing Problem with Time Windows (VRPTW). 2022 8th International Conference on Control, Instrumentation and Automation (ICCIA).
-Silva, P. P. B., Riveros, D. P. B., & Bermudez, Y. V. C. A Hybrid Model Applied to the Vehicles Routing Problem With Simultaneous Pickups and Deliveries–VRPSPD.­
-Toth, P., & Vigo, D. (2002a). An overview of vehicle routing problems. The vehicle routing problem, 1-26.
-Zhang, W., Yang, D., Zhang, G., & Gen, M. (2020). Hybrid multiobjective evolutionary algorithm with fast sampling strategy-based global search and route sequence difference-based local search for VRPTW. Expert Systems with Applications, 145, 113151.

فایل ها

هم رسانی

ارجاع به این مقاله

آمار