ارایه مدلی برای شبکه های کوتاه ترین مسیر با محدودیت گره
ارایه مدلی برای شبکه های کوتاه ترین مسیر با محدودیت گره
محمد حسین کریم نژاد1 اصغر عینی2
1) کارشناسی ارشد مهندسی صنایع،دانشگاه آزاد واحد تهران شمال
2) عضو هیئتعلمی گروه مهندسی صنایع، دانشگاه آزاد واحد تهران شمال
محل انتشار :
اولین کنفرانس بین المللی اصول فناورانه در مدیریت و مهندسی صنایع (iem2019.ir)
چکیده :
مساله کوتاهترین مسیر یکی از مسائل مشهور ، بنیادی و پرطرفدار در نظریه گراف و شبکهها میباشد که بهسبب کاربردهای فراوان آن توسط محققان زیادی مورد مطالعه قرارگرفته است. شبکه کوتاهترین مسیر بامحدودیت گره، یافتن کوتاه ترین مسیر در شبکهی جهتدار با وزن کمانهای قطعی که موظف به بازدید از مجموعهای از گرههای مشخص در طول مسیر است. به عبارت بهتر، یکی از خلاء موجود در مبحث شبکه های کوتاه ترین مسیر، عدم وجود مدلی برای بیان محدودیت ها و تابع هدف این دسته از شبکه می باشد. در این مقاله، برای مدلسازی این مسائل، دو مدل پیشنهادی مبتنیبر مدل برنامهریزی عددصحیح اولیه – ثانویه و مدل توسعهیافته فروشنده دورهگرد اشتاینر ارائه گردیده است. این مدل های تلفیقی کارا با توجه به محاسبات ، مدل های بسیار مناسبی برای مدل سازی شبکه های کوتاه ترین مسیر با محدودیت گره می باشند که در کنار تعریف محدودیت جدیدی که بر شبکه های کوتاه ترین مسیر اعمال گردیده ،خود یک مزیت بزرگ در حوزه آموزشی محسوب میگردد.
کلمات کلیدی :
مساله کوتاهترین مسیر
شبکه محدودیت دار
برنامهریزی عددصحیح
فروشنده دورهگرد اشتاینر.