|
|
|
|
یک الگوریتم ترکیبی کارآمد بهبودیافته برای مسئله‌ی سفر چند فروشنده در مقیاس بزرگ
|
|
|
|
|
|
|
|
نویسنده
|
میرمحمدی حمید ,امیری سیما ,فیض الهی پریسا
|
|
منبع
|
مهندسي صنايع و مديريت شريف - 1400 - دوره : 37-1 - شماره : 2 - صفحه:123 -133
|
|
چکیده
|
مسئله‌ی چندین فروشنده‌ی دوره‌گرد )mtsp( گسترشی مشهور از مسئله‌ی فروشنده‌ی دوره‌گرد (tsp) است. تحقیقات این مسئله بر خلاف مسئله‌ی tsp که گستردگی آن توجه زیادی را به خود معطوف کرده است، بسیار محدودبوده و ازاین رو الگوریتم جدید ترکیبی موجود به نام الگوریتم ژنتیک مورچگان بهبودیافته )iacpga( ارائه شده است که در آن از یک روش جستجوی محلی به منظور بهبود الگوریتم بهره گرفته شده است. ایده‌ی اصلی این مقاله آن است که از الگوریتم ژنتیک برای تعیین تعداد شهرها و نقطه‌ی شروع هر فروشنده بهره بگیریم و سپس از الگوریتم مورچگان برای تعیین بهترین تور استفاده کنیم. نتایج حاصل از مقایسه‌ی نتایج الگوریتم با دیگر الگوریتم‌های موجود در ادبیات موضوع و تجزیه و تحلیل آن نشان می‌دهد که الگوریتم پیشنهادی در حل mtsp در مقیاس بزرگ موثراست.
|
|
کلیدواژه
|
الگوریتم ژنتیکی پارتنو، الگوریتم کلونی مورچه‌ها، مسئله‌ی فروشنده‌ی دوره‌گرد چندگانه همراه با الگوریتم ترکیبی بهبودیافته، روش جستجوی محلی opt2
|
|
آدرس
|
دانشگاه صنعتی اصفهان, دانشکده مهندسی صنایع وسیستم ها, ایران, دانشگاه صنعتی اصفهان, دانشکده مهندسی صنایع وسیستم ها, ایران, دانشگاه صنعتی اصفهان, دانشکده مهندسی صنایع وسیستم ها, ایران
|
|
پست الکترونیکی
|
parisafeizollahy@in.iut.ac.ir
|
|
|
|
|
|
|
|
|
|
|
|
|
|
AN IMPROVED EFFICIENT COMBINED ALGORITHM FOR LARGESCALE MULTIPLE TRAVELING SALESMEN PROBLEM
|
|
|
|
|
Authors
|
|
|
Abstract
|
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 (IACPGA), which combines Parteno Genetic Algorithms (PGA) and Ant Colony (ACO) and uses the 2opt 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), Twopart 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 IACPGA algorithm is sufficiently effective in solving largescale MTSP and is not worse than other algorithms on a small scale and performs better than the existing algorithms.
|
|
Keywords
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|