يافتن كوتاه ترين مسير هميلتوني براي شهرهاي ايران با استفاده از الگوريتم هاي جستجوي ممنوعه و ممتيك

Finding the Shortest Hamiltonian Path for Iranian Cities, using Tabu Search and Memetic algorithms

هدف مسيله يافتن كوتاه ترين مسير هميلتوني، به دس تآوردن كوتا هترين مسير بين مجموعه اي از شهرهاست، به گونه اي كه هر شهر فقط يك بار در مسير قرار گرفته و مسير ساخته شده به شهر اول منتهي شود. اين مسيله علاوه بر جنبه نظري از جنبه كاربردي نيز اهميت فراواني دارد و در ساخت تراش ههاي الكترونيكي، زمانبندي كارها، تعيين توالي كارها و در مسيريابي وسايل نقليه مورد استفاده قرار م يگيرد. با توجه به اهميت و كاربرد گسترده يافتن كوتاه ترين مسير هميلتوني، در اين مقاله براي اولين بار، اين مسيله بين 423 شهر ايران با استفاده از الگوريتمهاي فراابتكاري حل شده است. با توجه به تفاوت الگوريتمهاي فراابتكاري، الگوريتم جستجوي ممنوعه به عنوان يك الگوريتم فراابتكاري مبتني بر جواب منفرد و الگوريتم ممتيك به عنوان يك الگوريتم فراابتكاري مبتني بر جمعيت، براي حل اين مسيله استفاده شده است. به منظور ارزيابي عملكرد الگوريتمهاي پيشنهادي، مسايل استاندارد با ابعاد مختلف 16 شهر تا 1060 شهر انتخاب گرديده است. پياد هسازي الگوريتمهاي پيشنهادي با استفاده از زبان جاوا صورت گرفته و در نهايت عملكرد هر الگوريتم با توجه به كيفيت جواب به دست آمده و زمان حل، ارزيابي شده و نتايج مورد مقايسه قرار گرفته اند. نتايج به دست آمده نشان دهنده كارآيي و اثربخشي بسيار الگوريتمهاي پيشنهادي است.

The traveling salesman problem (TSP) is a well-known and important combinatorial optimization problem. The goal is to find the shortest tour that visits each city in a given list exactly once and then returns to the starting city. Despite this simple problem statement, solving the TSP is difficult since it belongs to the class of NP-hard problems. This means that no known algorithm is guaranteed to solve all TSP instances to optimality within reasonable execution time. Due to the different nature of metaheuristics algorithms and the importance and application of TSP in different fields, in this paper the shortest Hamiltonian path is achieved between 423 Iranian cities by the two types of algorithms. for the first time Tabu search as a single-solution-based algorithm and memetic algorithm as a population-based algorithm is selected. To evaluate the accuracy and efficiency of the proposed algorithms, standard problems with size from 16 cities to 1060 cities have been used. Results demonstrate the performance and effectiveness of proposed algorithms. Java programming language to code algorithms has been used in this research. Parameters tuning for each algorithm is done separately and ultimately the best value for each parameter has been determined. Finally, the performances of each algorithm determined by quality of solution and CPU time and the results have been compared.