An Effective Genetic Algorithm for Solving the Multiple Traveling Salesman Problem
سال انتشار: 1389
نوع سند: مقاله ژورنالی
زبان: انگلیسی
مشاهده: 415
فایل این مقاله در 8 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
این مقاله در بخشهای موضوعی زیر دسته بندی شده است:
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
JR_JOIE-4-8_008
تاریخ نمایه سازی: 22 آبان 1397
چکیده مقاله:
The multiple traveling salesman problem (MTSP) involves scheduling m > 1 salesmen to visit a set of n > m nodes so that each node is visited exactly once. The objective is to minimize the total distance traveled by all the salesmen. The MTSP is an example of combinatorial optimization problems, and has a multiplicity of applications, mostly in the areas of routing and scheduling. In this paper, a modified hybrid metaheuristic algorithm called GA2OPT for solving the MTSP is proposed. In this algorithm, at the first stage, the MTSP is solved by the modified genetic Algorithm (GA) in each iteration, and, at the second stage, the 2-Opt local search algorithm is used for improving solutions for that iteration. The proposed algorithm was tested on a set of 6 benchmark instances from the TSPLIB and in all but four instances the best known solution was improved. For the rest instances, the quality of the produced solution deviates less than 0.01% from the best known solutions ever
کلیدواژه ها:
Genetic algorithm ، Multiple traveling salesman problem ، NP-Hard problems ، 2-Opt local search algorithm
نویسندگان
Mohammad Sedighpour
Instructor, Department of Mathematics, Hamedan Branch, Islamic Azad University, Hamedan, Iran
Majid Yousefikhoshbakht
Instructor, Young Researchers Club, Hamedan Branch, Islamic Azad University, Hamedan, Iran
Narges Mahmoodi Darani
Instructor, Department of Mathematics, Malayer Branch, Islamic Azad University, Malayer, Iran