مساله پوشش هاب تک تخصیصی بر روی شبکه ستاره‌ای؛ مدل‌بندی، خطی‌سازی و یافتن کران مناسب برای آن‌

در این مقاله دو مساله پوشش هاب تک تخصیصی با ساختار ستاره ای که شامل دو مساله ماکزیمم پوشش pهاب و پوشش هاب با در نظر گرفتن هزینه انتقال جریان است، مورد بررسی قرار میگیرد. ساختار ستاره ای شبکه به گونه ای است که یک هاب مرکزی با مکان مشخص وجود دارد و سایر هاب ها به طور مستقیم به هاب مرکزی متصل می شوند. در مساله اول هدف انتخاب مکان p هاب و تخصیص هر مشتری به حداکثر یک هاب است به طوری که کل تقاضای انتقال یافته بین مشتریان ماکزیمم شود. هدف مساله دوم حداقل سازی مجموع هزینه ثابت احداث هاب ها و هزینه انتقال جریان بین گره های شبکه است به طوری که پوشش کامل در شبکه ایجاد شود. در هر دو مساله اتصال مشتریان به مراکز هاب و هاب ها به هاب مرکزی به گونه ای خواهد بود که فاصله مبادی تا مقاصد با در نظر گرفتن فاکتور تخفیف برای اتصال بین هاب و هاب مرکزی از مقدار از پیش تعیین شده کمتر یا مساوی است. در هر دو مساله پس از ارائه مدل ریاضی، به خطی سازی آن ها و سپس استفاده از آزادسازی لاگرانژ به منظور یافتن کران های مناسبی پرداخته شده است. علاوه بر این، در مساله دوم نامساوی های معتبری معادل دو محدودیت مساله ارائه شده است. در نهایت، نتایج حاصل از حل مدل های خطی، غیرخطی و بکارگیری آزادسازی لاگرانژ بررسی و مقایسه شده است. بررسی این نتایج بر روی مجموعه داده های cab بیانگر آن است که مدل های خطی هم از لحاظ مقدار بهینه تابع هدف و هم زمان اجرا بسیار مطلوبتر از مدل های غیرخطی است. همچنین با توجه به نتایج، کران های بدست آمده از الگوریتم آزادسازی لاگرانژ فاصله کمی با جواب بهینه مسائل دارد.