Solving the shortest path tour problem

در این مقاله، مسئله تور کوتاه ترین مسیر را بررسی می کنیم که در آن یک کوتاه ترین مسیر از یک گره خاص ارجاع به یک گره مقصد مشخص در یک نمودار هدایت شده با طول های قوس غیر منفی یافت می شود. چنین مسیری نیاز به پیروی از یک زیر مجموعه گره دارد که در یک سفارش ثابت داده می شود. این زیرمجموعه ها بی ارتباط هستند و ممکن است متفاوت باشند. یک کاهش چندجملهای زمانبندی مشکل به یک مسئله کوتاهترین مسیر کلاسیک بر یک دیفر اصلاح شده توصیف شده و به ترتیب دو راه حل مبتنی بر کاهش و برنامه ریزی پویا مطرح شده و با روش حل مسئله پیشرفته مقایسه شده است . روشهای پیشنهادی بر روی مجموعه داده های موجود برای این مشکل و در یک کلاس بزرگ از نمونه های جدید معیار آزمایش شده اند. تجربه محاسباتی نشان می دهد که هر دو روش پیشنهادی، عملکرد سازگار بهبود یافته را از نظر زمان محاسبات با توجه به روش راه حل موجود نشان می دهد.