بهبود یک الگوریتم ژنتیک ترکیبی برای مسئله چندفروشنده دوره‌گرد با هدف کمینه کردن بیشترین زمان سفر

مقالات آماده انتشار

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

نویسندگان

1 دانشجوی دکتری گروه مهندسی کامپیوتر، واحد شیراز، دانشگاه آزاد اسلامی، شیراز، ایران

2 استادیار گروه مهندسی کامپیوتر، واحد شیراز، دانشگاه آزاد اسلامی، شیراز، ایران

10.22034/abmir.2026.24683.1252

چکیده

در سیستم‌های لجستیک مدرن، توزیع بهینه منابع بین چندین عامل (فروشنده) یکی از چالش‌های اصلی است. مسئله چندفروشنده دوره‌گرد با هدف کمینه‌سازی بیشینه زمان سفر به دنبال توزیع عادلانه بار کاری و کاهش زمان کل عملیات است. این مسئله در کاربردهای حیاتی مانند امدادرسانی، توزیع دارو و خدمات اضطراری از اهمیت ویژه‌ای برخوردار است. این پژوهش یک الگوریتم ژنتیک ترکیبی ارتقا یافته ارائه می‌دهد که از سه لایه بهبود اصلی شامل الگوریتم تقسیم پویا برای ارزیابی کروموزوم‌ها، عملگر تقاطع مبتنی بر شباهت تورها برای حفظ ساختارهای خوب و مکانیزم جستجوی محلی خودتطبیق‌پذیر برای بهینه‌سازی محلی بهره می‌برد. اگرچه روش‌های هیبریدی مبتنی بر الگوریتم ژنتیک و جستجوی محلی از مؤثرترین رویکردهای حل مسئله چندفروشنده دوره‌گرد با هدف کمینه‌سازی بیشینه زمان سفر به شمار می‌روند، در روش پیشنهادی با اصلاح راهبرد حذف تقاطع‌های هندسی و بازطراحی سازوکار انتخاب تطبیقی عملگرهای جستجوی محلی، کیفیت جواب‌ها و کارایی فرآیند جستجو بهبودیافته است. نتایج اجرای الگوریتم روی ۶۱ نمونه از چهار مجموعه داده استاندارد نشان می‌دهد که در حدود ۹۲ درصد موارد، عملکردی برابر یا بهتر از روش مرجع دارد، زمان اجرا را به‌طور میانگین حدود ۲۱ درصد کاهش می‌دهد، پایداری نتایج را بهبود می‌بخشد و در ۱۳ نمونه عملکرد بهتر از الگوریتم مرجع ارائه می‌کند.

کلیدواژه‌ها

موضوعات

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

Improving a Hybrid Genetic Algorithm for the Multiple Traveling Salesman Problem with the Aim of Minimizing the Maximum Travel Time

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

  • Somayeh Jafari 1
  • Elham Parvin Nia 2
1 PhD Student, Department of Computer Engineering, Shi.C., Islamic Azad University, Shiraz, Iran
2 Assistant Professor, Department of Computer Engineering, Shi.C., Islamic Azad University, Shiraz, Iran
چکیده [English]

In modern logistics systems, the optimal allocation of resources among multiple salesmen is a fundamental challenge. The min–max multiple traveling salesman problem (mTSP) aims to achieve a balanced workload distribution while minimizing the maximum travel time among all salesmen. This problem is particularly important in critical applications such as emergency response, medical supply distribution, and disaster relief. This paper presents an enhanced hybrid genetic algorithm that incorporates three main components: a dynamic split algorithm for chromosome evaluation, a similarity-based tour crossover operator for preserving high-quality route structures, and an adaptive local search mechanism for solution refinement. Although hybrid approaches combining genetic algorithms and local search have proven effective for solving the min–max mTSP, the proposed method improves the search process by introducing a refined geometric edge-crossing removal strategy and redesigning the adaptive selection mechanism of local search operators. Experimental results on 61 benchmark instances from four standard datasets demonstrate that the proposed algorithm achieves performance equal to or better than the reference method in approximately 92% of the test cases, reduces the average execution time by about 21%, improves the stability of the obtained solutions, and outperforms the reference algorithm on 13 benchmark instances.

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

  • Multiple Traveling Salesman Problem (mTSP)
  • minimizing the maximum tour length
  • hybrid genetic algorithm
  • Split algorithm
  • self-adaptive local search
  • geometric intersection removal
  • population diversity management

مراجع

[1]     França, P. M., Gendreau, M., Laporte, G., & Müller, F. M. (1995). The m-traveling salesman problem with minmax objective. Transportation Science, 29(3), 267-275.
[2]     Dantzig, G., Fulkerson, R., & Johnson, S. (1954). Solution of a large-scale traveling-salesman problem. Operations Research, 2(4), 393-410.
[3]     Lin, S., & Kernighan, B. W. (1973). An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2), 498-516.
[4]     Applegate, D., Cook, W., Dash, S., & Rohe, A. (2002). Solution of a min-max vehicle routing problem. INFORMS Journal on Computing, 14(2), 132-143.
[5]     Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
[6]     Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H., & Shmoys, D. B. (1985). The traveling salesman problem: a guided tour of combinatorial optimization. Wiley.
[7]     Mahmoudinazlou, S., & Kwon, C. (2024). A hybrid genetic algorithm for the min-max multiple traveling salesman problem. Computers & Operations Research, 162, 106455.
[8]     Laporte, G., & Nobert, Y. (1980). A cutting planes algorithm for the m-salesmen problem. Operations Research, 28(5), 1157-1166.
[9]     Applegate, D., Cook, W., Dash, S., & Rohe, A. (2002). Solution of a min-max vehicle routing problem. INFORMS Journal on Computing, 14(2), 132-143.
[10] Tang, L., Liu, J., Rong, A., & Yang, Z. (2000). A multiple traveling salesman problem model for hot rolling scheduling. European Journal of Operational Research, 124(2), 267-282.
[11] Larrañaga, P., Kuijpers, C. M. H., Murga, R. H., Inza, I., & Dizdarevic, S. (1999). Genetic algorithms for the travelling salesman problem: A review of representations and operators. Artificial Intelligence Review, 13, 129-170.
[12] Carter, A. E., & Ragsdale, C. T. (2006). A new approach to solving the multiple traveling salesperson problem using genetic algorithms. European Journal of Operational Research, 175(1), 246-257.
[13] Brown, E. C., Ragsdale, C. T., & Carter, A. E. (2007). A grouping genetic algorithm for the multiple traveling salesperson problem. International Journal of Information Technology & Decision Making, 6(02), 333-347.
[14] Singh, A., & Baghel, A. S. (2009). A new grouping genetic algorithm approach to the multiple traveling salesperson problem. Soft Computing, 13, 95-101.
[15] Junjie, P., & Dingwei, W. (2006). An ant colony optimization algorithm for multiple traveling salesman problem. ICICIC'06, 1, 210-213.
[16] Liu, W., Li, S., Zhao, F., & Zheng, A. (2009). An ant colony optimization algorithm for the multiple traveling salesmen problem. ICIEA 2009, 1533-1537.
[17] Venkatesh, P., & Singh, A. (2015). Two metaheuristic approaches for the multiple traveling salesperson problem. Applied Soft Computing, 26, 74-89.
[18] Soylu, B. (2015). A general variable neighborhood search heuristic for multiple traveling salesmen problem. Computers & Industrial Engineering, 90, 390-401.
[19] Wang, Y., Chen, Y., & Lin, Y. (2017). Memetic algorithm based on sequential variable neighborhood descent for the min-max multiple traveling salesman problem. Computers & Industrial Engineering, 106, 105-122.
[20] He, P., & Hao, J. K. (2022). Hybrid search with neighborhood reduction for the multiple traveling salesman problem. Computers & Operations Research, 142, 105726.
[21] He, P., & Hao, J. K. (2023). Memetic search for the min-max multiple traveling salesman problem with single and multiple depots. European Journal of Operational Research, 307(3), 1055-1070.
[22] Zheng, J., Hong, Y., Xu, W., Li, W., & Chen, Y. (2022). An effective iterated two-stage heuristic algorithm for the multiple traveling salesmen problem. Computers & Operations Research, 143, 105772.
[23] Prins, C. (2004). A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 31(12), 1985-2002.
[24] Potvin, J. Y. (1996). Genetic algorithms for the traveling salesman problem. Annals of Operations Research, 63, 337-370.
[25] Vidal, T., Crainic, T. G., Gendreau, M., Lahrichi, N., & Rei, W. (2012). A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60(3), 611-624.
[26]He, P., Hao, J.-K., & Xia, J. Learning-guided Iterated Local Search for the Min-Max Multiple Traveling Salesman Problem. Computers & Operations Research, Vol. 185, 107255, 2026.
پژوهش های نظری و کاربردی هوش ماشینی

مقالات آماده انتشار، پذیرفته شده
انتشار آنلاین از تاریخ 04 مهر 1405

فایل ها

هم رسانی

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

آمار