عنوان مقاله :
يك الگوريتم تركيبي كارآمد بهبوديافته براي مسئله‌ي سفر چند فروشنده در مقياس بزرگ
عنوان به زبان ديگر :
AN IMPROVED EFFICIENT COMBINED ALGORITHM FOR LARGE-SCALE MULTIPLE TRAVELING SALESMEN PROBLEM
پديد آورندگان :
ميرمحمدي، حميد دانشگاه صنعتي اصفهان - دانشكده مهندسي صنايع وسيستم ها , اميري، سيما دانشگاه صنعتي اصفهان - دانشكده مهندسي صنايع وسيستم ها , فيض الهي، پريسا دانشگاه صنعتي اصفهان - دانشكده مهندسي صنايع وسيستم ها
كليدواژه :
الگوريتم ژنتيكي پارتنو , الگوريتم كلوني مورچه‌ها , مسئله‌ي فروشنده‌ي دوره‌گرد چندگانه همراه با الگوريتم تركيبي بهبوديافته , روش جستجوي محلي -2opt
چكيده فارسي :
مسئله‌ي چندين فروشنده‌ي دوره‌گرد (MTSP) گسترشي مشهور از مسئله‌ي فروشنده‌ي دوره‌گرد (TSP) است. تحقيقات اين مسئله بر خلاف مسئله‌ي TSP كه گستردگي آن توجه زيادي را به خود معطوف كرده است، بسيار محدودبوده و ازاين رو الگوريتم جديد تركيبي موجود به نام الگوريتم ژنتيك ـ مورچگان بهبوديافته (IAC-PGA) ارائه شده است كه در آن از يك روش جستجوي محلي به منظور بهبود الگوريتم بهره گرفته شده است. ايده‌ي اصلي اين مقاله آن است كه از الگوريتم ژنتيك براي تعيين تعداد شهرها و نقطه‌ي شروع هر فروشنده بهره بگيريم و سپس از الگوريتم مورچگان براي تعيين بهترين تور استفاده كنيم. نتايج حاصل از مقايسه‌ي نتايج الگوريتم با ديگر الگوريتم‌هاي موجود در ادبيات موضوع و تجزيه و تحليل آن نشان مي‌دهد كه الگوريتم پيشنهادي در حل MTSP در مقياس بزرگ مؤثر است.
چكيده لاتين :
The Multiple Traveling Salesmen Problem (MTSP) is a generalized Traveling Salesmen Problem (TSP). The difference with the traveling salesmen problem is that all cities are visited by multiple salesmen, and each salesman from the city that initiated the move must go back to the same city, which is, in fact, suitable for modeling practical problems in real life than TSP. To solve MTSP with a few starting points, you need the minimum and maximum number of cities each salesman should visit. The total number of cities that salesmen go through should be equal to all cities. In this article, The hybrid Algorithm (IAC-PGA), which combines Parteno Genetic Algorithms (PGA) and Ant Colony (ACO)
and uses the 2-opt local search method to improve the algorithm. This method provides full double displacement to improve the response. The main idea in this article is to use the PGA algorithm to search for the best number of cities visited as well as to obtain the starting point of each salesman using the genetic algorithm, and then to use the ACO algorithm to accurately determine the cities visited and the best tour for each salesman. The objective function for this problem is to minimize the distance traveled by all salesmen. For the purpose of analysis, the parameters of each algorithm are selected according to the number of experimental samples in the most appropriate case, and then the results of the algorithm are compared with other algorithms including PGA, Improved PGA (IPGA), Two-part Wolf Pack Search (TWPS),
Artificial Bee Colony (ABC), and Invasive Weed Optimization (IWO). Statistics show the algorithm improvement for problem solving. The results of comparative experiments show that the proposed IAC-PGA algorithm is sufficiently effective in solving large-scale MTSP and is not worse than other algorithms on a small scale and performs better than the existing algorithms.
عنوان نشريه :
مهندسي صنايع و مديريت شريف
