پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 162 |
| تعداد شماره‌ها | 6,693 |
| تعداد مقالات | 72,239 |
| تعداد مشاهده مقاله | 129,219,984 |
| تعداد دریافت فایل اصل مقاله | 102,048,653 |
روش ابتکاری ساخت و بهبود تور مسئله فروشنده دوره‌گرد نامتقارن | ||
| نشریه دانشکده فنی | ||
| مقاله 9، دوره 40، شماره 4 - شماره پیاپی 1033، آبان 1385 اصل مقاله (311.58 K) | ||
| نویسندگان | ||
| علیرضا امیری؛ محمدسعید صباغ* | ||
| چکیده | ||
| در این مقاله، یک روش ابتکاری برای یافتن یک تور خوب مسئله فروشنده دوره‌گرد نامتقارن ارائه‌شده است. در این روش، ابتدا با استفاده از ماتریس نرمال‌سازی شده، سعی می‌شود توری ساخته شود که شهرهای تور به‌گونه‌ای انتخاب شوند تا درمراحل بعدی، از رفتن به شهرهای پرهزینه (مسافت یا زمان طولانی) پرهیز شود. سپس اندازه تور مذکور به‌کمک روش ابداعی، بهبود داده‌شده است. برای انجام این پژوهش، برنامه رایانه‌ای روش نرمال‌سازی ماتریس هزینه تخصیص خطی و روش پیشنهادی به زبان C++ نوشته شده و مسائل زیادی تا 500 شهر حل شده است. مسائل حل شده عبارتند از تعدادی مسائل تصادفی از نوع نامتقارن و تمامی مسائل محک فروشنده دوره‌گرد نامتقارن. نتایج بدست‌آمده حاکی از آن است که این روش، برای تمام مسائل آزمون‌شده، تور خیلی خوبی بدست‌می‌دهد. | ||
| کلیدواژه‌ها | ||
| بهبود تور؛ تخصیص خطی؛ ساخت تور؛ فروشنده دوره‌گرد نامتقارن (ATSP)؛ نرمال‌سازی | ||
| عنوان مقاله [English] | ||
| - | ||
| چکیده [English] | ||
| This paper presents a heuristic method to find out a good tour for the asymmetric traveling salesman problem. At first, the proposed approach uses the normalized cost matrix to construct a tour by choosing the cities in such a way that it avoids having to go to very high cost (distance or time) cities later on. In order to improve further the size of this tour, it uses a developed tour improvement method. To evaluate its performance, the cost normalization algorithm for the solution of the linear assignment problem as well as the proposed method have been coded in C++ and many problems with up to 500 cities have been tested. The solved problems include a number of asymmetric random problems and all the benchmark asymmetric traveling salesman problems. The results indicate that the method returns a very good tour on all tested problems. | ||
|
آمار تعداد مشاهده مقاله: 1,725 تعداد دریافت فایل اصل مقاله: 2,627 |
||
سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب