یک روش محاسباتی کارا برای حل مساله کوتاهترین مسیر در یک شبکه با وزن های کمانی بازه ای

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

کلیدواژه ها:

مساله کوتاهترین مسیر ، الگوریتم دایجکسترا ، اعداد بازه ای ، پیچیدگی محاسباتی