CIVILICA We Respect the Science
(ناشر تخصصی کنفرانسهای کشور / شماره مجوز انتشارات از وزارت فرهنگ و ارشاد اسلامی: ۸۹۷۱)

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

عنوان مقاله: یک روش محاسباتی کارا برای حل مساله کوتاهترین مسیر در یک شبکه با وزن های کمانی بازه ای
شناسه (COI) مقاله: REGCMAES02_045
منتشر شده در دومین همایش ملی ریاضیات و کاربردهای آن در علوم مهندسی در سال ۱۳۹۴
مشخصات نویسندگان مقاله:

اسحاق هاشمی - گروه ریاضی، دانشگاه آزاد اسلامی واحد قائمشهر، قائمشهر، ایران
علی ابراهیم نژاد - ریاضی، دانشگاه آزاد اسلامی واحد قائمشهر، قائمشهر، ایران

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

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

صفحه اختصاصی مقاله و دریافت فایل کامل: https://www.civilica.com/Paper-REGCMAES02-REGCMAES02_045.html