|
عنوان
|
ارائه مدل و الگوریتم حل برمبنای ترکیبی از رویکردهای دقیق و ابتکاری برای مسأله مکان یابی هاب سلسله مراتبی با توپولوژی درختی
|
|
نوع پژوهش
|
پایان نامه
|
|
کلیدواژه‌ها
|
مکان یابی هاب، شبکه های سلسله مراتبی، ساختار درختی ،الگوریتم های ترکیبی، شاخه زنی محلی، تجزیه بندرز
|
|
چکیده
|
مسائل مکان یابی هاب، نقش مهمی در شبکه های ارتباطی و سیستم های حمل ونقل دارند. در تحقیق حاضر به مطالعه یک شبکه هاب سه سطحی با ساختار سلسله مراتبی پرداخته ایم که سطح مرکزی شبکه یاد شده به شکل درخت می باشدهدف از این امر، حداقل کردن هزینه لازم برای ایجاد یالها و مسیرهای ارتباطی است.گره های باقیمانده در این شبکه ساختار ستاره ای دارند . بنابراین هدف این تحقیق؛ جایابی برای تعداد مشخصی از هاب های مرکزی، اتصال آنها به کمک یک درخت و نیز اختصاص هاب های سطح دوم و گره های تقاضا به شبکه هاب مرکزی است به گونه ای که کل هزینه های مسیریابی در شبکه کمینه شود و طول مسیرهای بوجود آمده از مقدار مشخصی بیشتر نشود(محدودیت سطح سرویس). در تحقیق حاضر، یک مدل برنامه ریزی عدد صحیح چهار اندیسه مبتنی بر مسیر برای شبکه هاب-گره مورد نظر پیشنهاد شده است. مدل ارائه شده دارای آزاد سازی خطی فشرده ای است. در ادامه برای حل مسائل بزرگ تر از رویکرد شاخه زنی محلی استفاده گردید. این الگوریتم از حل کننده های برنامه ریزی عدد صحیح مختلط برای حل همسایگی هایی که توسط نامساوی های خطی(برش محلی) تعریف می شود در چارچوب مدل استفاده می کند. بنابراین می توان آنرا الگوریتمی ترکیبی دانست که مفاهیم برنامه ریزی ریاضی را با مکانیزم های موجود درمتاهیورستیک ها همچون جستجوی محلی و تعریف همسایگی ترکیب می کند. به علاوه، برای ایجاد جواب های مرجع متفاوت جهت اجرای جستجوی محلی الگوریتم در ساختار رویکرد تجزیه بندرز تعبیه گردید.در نهایت مدل و الگوریتم ارائه شده در محیط نرم افزار GAMSکد گردیده و با حل کننده CPLEX به اجرای آنها پرداختیم. نتایج محاسباتی برروی مجموعه داده هواپیمایی ایران کارایی الگوریتم توسعه داده شده را تأیید می کند.
|
|
پژوهشگران
|
خالد برزگر (دانشجو)، عیسی نخعی کمال آبادی (استاد مشاور)، علیرضا عیدی (استاد راهنما)
|