ارائه الگوریتم شبه چند جمله‌ای کارا برای محاسبه کوتاهترین مسیر بین هر زوج مبدا-مقصد در شبکه‌های پویا با قابلیت تحلیل حساسیت

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

Keywords:

شبکه‌های پویا , الگوریتم شبه چند جمله‌ای , مسیریابی , تحلیل حساسیت