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

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

کلیدواژه ها:

مساله کوتا ه ترین مسیر ، شبکه محدودیت دار ، برنامه ریزی عدد صحیح ، فروشنده دوره گرد اشتا ینر.