این سایت در حال حاضر پشتیبانی نمی شود و امکان دارد داده های نشریات بروز نباشند
مهندسی حمل و نقل، جلد ۲، شماره ۲، صفحات ۱۸۱-۱۹۶
عنوان فارسی یافتن کوتاه ترین مسیر همیلتونی برای شهرهای ایران با استفاده از الگوریتم های جستجوی ممنوعه و ممتیک
چکیده فارسی مقاله هدف مسئله یافتن کوتاه ترین مسیر همیلتونی، به دست آوردن کوتا هترین مسیر بین مجموعه ای از شهرهاست، به گونه ای که هر شهر فقط یک بار در مسیر قرار گرفته و مسیر ساخته شده به شهر اول منتهی شود. این مسئله علاوه بر جنبه نظری از جنبه کاربردی نیز اهمیت فراوانی دارد و در ساخت تراشه های الکترونیکی، زمانبندی کارها، تعیین توالی کارها و در مسیریابی وسایل نقلیه مورد استفاده قرار می گیرد. با توجه به اهمیت و کاربرد گسترده یافتن کوتاه ترین مسیر همیلتونی، در این مقاله برای اولین بار، این مسئله بین 423 شهر ایران با استفاده از الگوریتمهای فراابتکاری حل شده است. با توجه به تفاوت الگوریتمهای فرا ابتکاری، الگوریتم جستجوی ممنوعه به عنوان یک الگوریتم فراابتکاری مبتنی بر جواب منفرد و الگوریتم ممتیک به عنوان یک الگوریتم فراابتکاری مبتنی بر جمعیت، برای حل این مسئله استفاده شده است. به منظور ارزیابی عملکرد الگوریتمهای پیشنهادی، مسائل استاندارد با ابعاد مختلف 16 شهر تا 1060 شهر انتخاب گردیده است. پیاده سازی الگوریتمهای پیشنهادی با استفاده از زبان جاوا صورت گرفته و در نهایت عملکرد هر الگوریتم با توجه به کیفیت جواب به دست آمده و زمان حل، ارزیابی شده و نتایج مورد مقایسه قرار گرفته اند . نتایج به دست آمده نشان دهنده کارآیی و اثربخشی بسیار الگوریتمهای پیشنهادی است.
کلیدواژه‌های فارسی مقاله
عنوان انگلیسی Finding the Shortest Hamiltonian Path for Iranian Cities,using Tabu Search and Memetic algorithms
چکیده انگلیسی مقاله 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.
کلیدواژه‌های انگلیسی مقاله
نویسندگان مقاله
نشانی اینترنتی http://jte.sinaweb.net/article_1581_cb78a452e098e3d6012978d0cb6422aa.pdf
فایل مقاله اشکال در دسترسی به فایل - ./files/site1/rds_journals/1231/article-1231-223547.pdf
کد مقاله (doi)
زبان مقاله منتشر شده fa
موضوعات مقاله منتشر شده
نوع مقاله منتشر شده
برگشت به: صفحه اول پایگاه   |   نسخه مرتبط   |   نشریه مرتبط   |   فهرست نشریات