مقاله ترجمه شده روش محاسبه دقیق فروشنده دوره گرد(TSP) نامتقارن

روش محاسبه دقیق فروشنده دوره گرد(TSP) نامتقارن

ا. مقدمه

در این فصل ما تمرکز خود را بر روی روش محاسبه دقیق در ارتباط با نامتقارن بودن TSP در بررسی های انجام شده، به دنبال تحقیقات افرادی چون بالاس و توس، قرار می دهیم. در بخش 2، دو روش مشخص شاخه و کران، بر مبنای راه حل مرتبط به مسئله انتقال به شکل بازسازی شده، نشان داده و مقایسه شده اند. در بخش 3، روش شاخه و کران بر مبنای محاسبه کران جمع پذیر شرح داده شده است، در حالی که در بخش 4 روش شاخه و کران به بحث گذاشته می شود. در نهایت تمام این روش ها بر مبنای محاسبه بر روی مجموعه بزرگی از نمونه ها تست شده، و با کدهای قابل اجرا شاخه و کران برای TSP نامتقارن مقایسه می گردند.

تعریف قراردادی این مسئله به صورت زیر می باشد. فرض کنید G = (V, A) دو گراف جهت دار کامل باشد، به این ترتیب به عنوان بالاترین نقطه (راس) مجموعه بوده و مجموعه کمان (منحنی) می باشد، و فرض کنید هزینه مرتبط به کمان باشد.

ص 2

دور جهت دار هامیلتون از G به عنوان سیکل هدایت شده هر کمان v دقیقا با یک دور می باشد، یعنی زیرگراف جهت دار فراگیر از G به گونه ای که و شدیدا مرتبط به هم می باشند، یعنی برای هر کمان مجزا دو مسیر از i تا j و از j تا i در وجود دارد.

مسئله مربوط به عدم تقارن فروشنده سیار( ATSP) بر مبنای یافتن دور جهت دار هامیلتون از G بوده که هزینه حداقل می باشد. بدون از دست رفتن عمومیت، ما را برای هر کمان در نظر می گیریم. فرمول برنامه نویسی خطی اعداد صحیح زیر از ATSP شناخته شده می باشد.

تعداد صفحات ترجمه شده :45

تعداد صفحات انگلیسی:37

• مشخصات محصول
• دسته‌بندی محصول
• برچسب‌ها
• دیدگاه‌ها