ارائه یک الگوریتم حل دقیق برای مسأله جایابیp هاب میانه با تخصیصی r-تایی

Abstract

مسائل جایابی هاب نقش مهمی در شبکه‌های حمل‌ونقل و سیستم‌های مخابراتی دارند. این مسائل در دهه‌های اخیر، بسیار مورد توجه بوده‌اند. در مسأله جایابی هاب میانه باید p گره در شبکه به‌عنوان تسهیلات هاب انتخاب شده و سایر گره‌ها به نحوی به نقاط انتخابی اختصاص داده شوند که هزینه‌های مسیریابی در شبکه کمینه شود. در تحقیق حاضر مسأله جایابی هاب میانه با تخصیص r-تایی مورد مطالعه قرار گرفته است. در این مسأله هر گره غیر هاب می‌تواند حداکثر به r عدد از pهاب جایابی شده اختصاص یابد. هدف تحقیق کنونی مطالعه و طراحی یک الگوریتم حل دقیق بر مبنای رویکرد تجزیه بندرز برای مسأله ذکر شده است و بر اساس ساختار مسأله مورد مطالعه، راهکارهایی برای بهبود الگوریتم تجزیه بندرز کلاسیک ارائه شده است. نتایج محاسباتی الگوریتم دقیق ارائه شده با استفاده از مجموعه داده شبکه ترکیه و USA423 انجام شده است. آزمایشات محاسباتی کارایی الگوریتم پیشنهادی را تأیید می­کند.