هابها تسهیلاتی هستند که میتوانند به عنوان نقاط تعویض، مرتبسازی، اتصال و تجمیع در شبکههای توزیع متعددی مورد استفاده قرار بگیرند. در شبکههای هاب، تقاضا بین جفت مبدا-مقصد از مراکز واسطه (هاب) ارسال میشود و معمولا ارسال مستقیم در چنین شبکهای مجاز نمیباشد.
بهرهبرداری از امکانات هاب در شبکه منجر به ایجاد لینکهای کمتر در مقایسه با شبکههایی که بین تمامی نقاط، لینکهای مستقیم وجود دارد، خواهد شد. هدف استفاده از هابها، کاهش هزینههای ایجاد شبکه است که مبدا و مقصدهای مختلف را به هم متصل میکند و همچنین جریانات در هابها تجمیع میشوند که باعث صرفهجویی مقیاس خواهد شد.
شکل 1 تفاوت بین یک شبکه کاملا متصل به هم و یک شبکه هاب را نشان میدهد. دایرهها در این شکل، گرههای تقاضا هستند و مربعها نیز تسهیلات هاب را نشان میدهد. همانطور که در شکل مشاهده میشود در شبکه حمل و نقل، بین هر مبدا-مقصد یک مسیر وجود دارد که باعث میشود پیچیدگی و همچنین هزینهی بیشتری نسبت به شبکه هاب داشته باشد.
(الف) (ب)
شکل 1. ساختار (الف) شبکه حمل و نقل و (ب) شبکه هاب
مسئله مکانیابی هاب، یک مسئله طراحی شبکه میباشد که عموما از دو تصمیم اصلی تشکیل شده است: تعیین مکان هابها و تخصیص گرههای تقاضا به تسهیلات هاب. مسیرهای بهینه ارسال جریان در شبکه هاب برای برآورده کردن تقاضا بین جفت مبدا-مقصد نیز تعیین میشوند. ارسال جریان از طریق هابها از مزیتهای صرفهجویی مقیاس است و در نتیجه باعث میشود هزینههای حمل و نقل به واسطه استفاده از هابها کاهش یابند. صرفهجویی مقیاس به این معنی است که با افزایش مقیاس جریانات، هزینهها کاهش مییابد. به عبارت دیگر ارسال حجم زیادی از جریانات باعث میشود که هزینه سرشکن شده به ازای هر کالا کاهش یابد.
مسئله مکانیابی هاب، کاربردهای گستردهای در حمل و نقل و مخابرات دارد. حوزههای کاربرد مکانیابی هاب در حمل و نقل عبارتاند از: حمل و نقل هوایی مسافران، حمل بار، حمل و نقل سریع، سرویس تحویل پستی و سیستمهای ترانزیت سریع. در کاربردهای حمل و نقل، تقاضا به عنوان جریانی از کالاهایی مانند مسافران، پست و کالاهایی که در وسایل نقلیه بین جفت مبدا-مقصد حمل میشوند، مشخص میشود. با توجه به محدوده جغرافیایی، نوع وسایل نقلیهای که در شبکههای فیزیکی جا به جا میشوند، میتوانند تغییر کنند. به عنوان مثال، کامیونها معمولا در جادهها، قطارها در راهآهن، هواپیماها از طریق هوا و کشتیها از طریق آب استفاده میشوند. تسهیلات هاب، پایانههای حمل و نقل یا مراکز مرتبسازی هستند که حجم حمل و نقل زیاد است، بنابراین میتوان به صرفهجویی در هزینههای حمل نقل دست یافت.
کاربردهای مسئله مکانیابی هاب در ارتباطات نیز میتواند شامل طیف گستردهای از شبکههای داده در زمینههایی مانند ارتباطات رایانهای، شبکههای تلفنی، کنفرانسهای تلویزیونی و پردازش رایانهای باشد. در این حوزه، تقاضا برای انتقال اطلاعات (مانند دادهها، ویدیو، صدا) میتواند از طریق انواع پیوندهای فیزیکی (مانند کابلهای نوری) یا از طریق هوا (مانند کانال ماهوارهای) باشد. مسائل مکانیابی هاب را میتوان براساس طراحی شبکه به انواع مختلفی تقسیمبندی نمود که نشاندهنده تخصیص گرههای تقاضا به هابها میباشد.
دو استراتژی اصلی تخصیص در ادبیات وجود دارد: تخصیص واحد[1] و تخصیص چندگانه[2]. در تخصیص واحد، هر گره باید دقیقا به یک هاب متصل شود و در تخصیص چندگانه نیز، محدودیتی در این مورد وجود ندارد، یعنی هر گره میتواند به بیشتر از یک هاب متصل شود. همچنین میتوان مشخص نمود که هر گره دقیقا به تعداد مشخص r از هابها متصل باشد که تحت عنوان مسئله r تخصیص[3] شناخته میشود.
شکل 2، شبکه هاب را با استراتژی تخصیص تکی و استراتژی تخصیص چندگانه نشان میدهد.
(الف) (ب)
شکل 2. مسئله مکانیابی هاب با استراتژی (الف) چند تخصیصه و (ب) تک تخصیصه
بیشتر مدلهای مکانیابی هاب کلاسیک، یکسری از مفروضاتی را در نظر میگیرند. به اینصورت که فرض میشود که شبکه اتصال کامل است و فاصلهها از نابرابری مثلثی پیروی میکنند. مقداری تخفیف برای جریانهایی که از طریق هابها فرستاده میشوند، لحاظ میشود. به عبارت دیگر، هزینه حمل و نقل بین هابها دارای تخفیف میباشد. همچنین فرض میشود که تمام جریانها بین گرههای مبدا-مقصد انتقال داده میشوند، به عبارت دیگر تمام تقاضاها برآورده میشوند. حمل و نقل مستقیم بین جفت گرههای مبدا-مقصد مجاز نمیباشد یعنی بایستی حتما از حداقل یک هاب برای ارسال جریانات استفاده نمود.
از نظر تابع هدف نیز بیشتر مطالعات در مسائل مکانیابی هاب به تابع هدف حداقل کردن هزینه کل توجه داشتهاند. ویژگی مشترک این مسائل این است که با هدف حداقل کردن هزینه شبکه، تمام تقاضاهای بین جفت مبدا-مقصدها بایستی برآورده شوند. در چنین حالتی، هیچ ارزشی (سود) برای انتقال کالاها بدست نخواهد آمد که به طور ضمنی دلالت بر این دارد که کل درآمد، هزینه کل را پوشش میدهد. با این حال، از دیدگاه سود، ممکن است برخی از تقاضاها برآورده نشوند. به ویژه اگر هزینه خدماترسانی به تقاضا بیشتر از درآمد باشد. در چنین شرایطی، هدف حداکثر رساندن سود است، طوری که تصمیمگیری در مورد میزان تقاضای هر کالا برای تامین، بستگی به مبادله بین درآمد و هزینه دارد. مسائل حداکثر رساندن سود، میتوانند پیچیدگی بیشتری نسبت به مدلهای حداقلسازی هزینه داشته باشند زیرا تصمیمات اضافی را ممکن است در بر بگیرند. با این وجود، اینگونه مسائل میتوانند برای بسیاری از کاربردها مفید باشد.
تعریف مجموعهها و پارامترهای مسئله:
: مجموع گرهها و .
: مجموع گرههای پتانسیل هاب و .
: میزان مسافت بین گرههای و .
: میزان تقاضا بین گرههای و .
: هزینه ثابت راه اندازی هاب .
: ضریب انتقال جریان بین گره و هاب .
: ضریب تخفیف بین هابهای و .
: ضریب توزیع بین هاب و گره مقصد .
تعریف متغیرهای تصمیم مسئله:
: متغیر باینری صفر و یک و زمانی برابر یک میشود که هاب در مکان احداث شود.
: میزان کسر جریان که از مبدا شروع میشود و به مقصد میرود توسط هابهای و .
تابع هدف مسئله:
تابع هدف به دنبال کمینه کردن هزینههای ثابت راه اندازی هاب و همچنین هزینههای حمل و نقل جریانات میباشد. ترم اول تابع فوق هزینه راه اندازی تسهیلات هاب را نشان میدهد و ترم دوم نیز هزینههای حمل و نقل میباشد.
محدودیتها:
محدودیت بالا بیان میکند که تمامی تقاضاها بایستی حتما برآورده شوند.
محدودیت بالا نیز از ایجاد ارتباط بین گرههای غیر هاب جلوگیری میکند. به عبارت دیگر جریانات بایستی حتما توسط هابها جا به جا شوند.
دامنه متغیرهای تصمیم نیز توسط دو رابطه بالا تعیین شدهاند.
[1] Single allocation
[2] Multiple allocation
[3] r-allocation
هنوز بررسیای ثبت نشده است.