برای دسته بندی مسایل مکان یابی هاب ،به تعاریف وطبقه بندی زیر می پردازیم:

 

برای دانلود متن کامل پایان نامه به سایت fotka.ir مراجعه نمایید.

 

 

فضای جواب : شبکه (تمام گره های شبکه می تواند به عنوان نقاط کاندید برای هاب در نظر گرفته شود) ، گسسته (نقاط کاندید برای هاب ها،یکسری از گره های خاص می باشند) ، پیوسته (فضای جواب برای هابه یک صفحه است).

معیار: مینیمم[۴] ماکسیمم[۵] (بیشترین هزینه انتقال از مبدا به مقصد مینیمم شود) ، مینیمم مجموع (مجموع هزینه های مکان یابی هاب و تخصیص نقاط غیر هاب به هاب مینیمم شود)

تعداد گره های هاب : یکی ،بیشتر از یکی

ظرفیت : بدون محدودیت ، با محدودیت

هزینه مکان یابی هاب: بدون هزینه ، با هزینه ثابت ،هزینه متغیر

تخصیص نقاط غیر هاب به هاب : به یک هاب (تکی) ، به بیشتر از یک هاب (چندگانه)

هزینه ارتباط نقاط غیر هاب به هاب : بدون هزینه ، با هزینه ثابت ،هزینه متغیر

۱-۵- مدلهای شبکه هاب

بادر نظر گرفتن تعاریف و طبقه بندی ذکر شده ، مسایل مکان یابی هاب به مدلهای متنوعی بیان می شود که عبارتند از :

 

۱-۵-۱- مسایل مکان یابی میانه[۶]:

در مسایل مکان یابی میانه با تعداد مراکز مشخص، تابع هدف مکان یابی بهینه p تا هاب در شبکه است؛ به طوری که کل هزینه حمل و نقل جریان تقاضا در شبکه کمینه شود. همانطور که ملاحظه می شود ،تعداد مراکزی که در شبکه ایجاد می شود ،به عنوان یک پارامتر داده شده است و به عنوان تابع هدف مطرح نیست.

 

۱-۵-۲- مسایل مکان یابی هاب با درنظرگرفتن هزینه ثابت[۷]:

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

 

۱-۵-۳- مسایل مکان یابی هاب با در نظرگرفتن هزینه ثابت هر ارتباط[۸]:

در این نوع مسایل مکان یابی ، برای هر ارتباط بین هر نقطه تقاضا و هاب یک هزینه ثابت محاسبه می شود.

 

۱-۵-۴- مسایل مکان یابی هاب با در نظر گرفتن حداقل مقدار جریان هر ارتباط[۹]:

در این نوع مسایل مکان یابی ، مقدار جریانی که از هر نقطه تقاضا به هاب می باشد باید بزرگتر یا مساوی با حداقل جریان داده شده باشد.

 

۱-۵-۵- مسایل مکان یابی هاب با در نظر گرفتن محدودیت ظرفیت[۱۰]:

در این نوع مسایل مکان یابی ، ظرفیت های تسهیلات هاب، جریان های درون شبکه را محدود می کنند. در حقیقت ، جریان های ورودی وخروجی برای هر هاب باید کوچکتر یا مساوی ظرفیت آن هاب باشد.

 

۱-۵-۶- مسایل مکان یابی هاب پیوسته[۱۱]:

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

 

۱-۵-۷- مسایل مکان یابی هاب چند هدفه[۱۲]:

در این نوع مسایل مکان یابی ، چند هدف بیان می شود که اولین هدف کل هزینه جریان حمل ونقل را مینیمم می کند و هدف دیگر ،بیشترین زمانی را که یک هاب برای پردازش جریان انجام می دهد مینیمم می کند( مثلا بیشترین زمان سرویس در هاب ها را مینیمم می کند).

 

۱-۵-۸- مسایل مکان یابی مرکز[۱۳]:

در مساله مکان یابی مرکز با تعداد هاب مشخص ، هدف یافتن مکان بهینهp هاب و تخصیص گره های تقاضا به این مراکز است به طوری که طولانی ترین مسیر در شبکه کمینه شود. برای مثال این مساله برای مکان یابی تسهیلات اورژانسی مناسب است. این مساله از نوع مسایل مینی ماکس[۱۴] است.

 

۱-۵-۹- مسایل مکان یابی پوششی هاب[۱۵]:

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

 

۱-۵-۱۰- مسایل مکان یابی هاب با ساختار شبکه ستاره[۱۶]:

در این مسالهک هاب مرکزی با یک مجموعه نقاط می باشد که تلاش می کنیمp هاب انتخاب کنیم که بصورت مستقیم به هاب مرکزی ارتباط برقرار کنند. هر نقطه تقاضا باید به یک هاب متصل باشد. در نتیجه آن ساختار شبکه بصورت یه ستاره یا شبکه ستاره ای می شود.

 

۱-۶- اهمیت و ضرورت موضوع:

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

 

۱-۷- هدف از اجراء :

هدف از این تحقیق، پیدا کردن مکان بهینه هابها با توجه به گره های موجود و تخصیص جریان تقاضا به گره ها و هابها بطوریکه مجموع هزینه های مسیریابی مینیمم گردد، می باشد.

 

۱-۸- سوالات تحقیق :

 

 

چگونه می توان عدم قطعیت موجود در برآورد پارامتر تقاضا در مساله را مدل سازی نمود؟

چگونه می توان مکان یابی هاب را در یک محیط رقابتی تعریف کرد؟

۱-۹- ساختار پایان نامه :

در ادامه در فصل ۲، ادبیات موضوعی و زمینه های علمی تحقیق را مورد بررسی قرار خواهیم داد. ادبیات موضوع در حوزه شبکه های هاب با در نظرگرفتن طبقه بندی های صورت گرفته در آن ارائه می شود. در فصل ۳ به تشریح مساله ومدل پیشنهادی می پردازیم. در ادامه فصل ،با توجه به پیچیدگی های مدل پیشنهادی در مقیاس های بزرگ، یک الگوریتم فراابتکاری (الگوریتم ژنتیک)معرفی خواهیم کرد. نتایج محاسبات مربوط به الگوریتم پیشنهادی در فصل ۴ مورد بررسی ومقایسه قرار خواهیم داد. در نهایت ، تعدادی از توسعه های آتی به همراه نتیجه گیری در فصل ۵ ذکر شده است.

 

 

 

فصل دوم : ادبیات و پیشینه تحقیق

 

۲-۱- ادبیات موضوع

 

۲-۱-۱- مقدمه :

ایده شبکه هاب در سال ۱۹۶۹ توسط گلدمن مطرح شد[۱]. سپس اوکلی در سال ۱۹۶۸ اولین مطالعه شبکه های هاب را در زمینه شبکه هوایی مطرح ساخت[۲] .همچنین اوکلی در سال ۱۹۸۷ اولین مدل ریاضی درج دومی را برای شبکه های هاب ارائه کرد[۳] . از ان زمان، پژوهشگران متعددی در زمینه های مختلف مسایل مکان یابی هاب کار کرده اند. این میزان توجه عمدتا به سبب ضرورت ایجاد زیر ساخت های نوین برای سیستم های حمل ونقل و ارتباطات است[۴] . زیرا به دلیل کاربردی بودن این مباحث ، با گذشت زمان وطراحی سیستم های پیچیده ، دیگر این ساختارها از مدل های شبکه های سنتی پیروی نمی کنند. در شبکه های خدمت دهی سنتی ،هر محل تقاضا، تقاضایش را به صورت مستقیم و بی واسطه از منبع تقاضا دریافت می کنند. در صورتی که در شبکه های نوین ، تعدادی از نقاط در شبکه انتخاب می شوند و یک ساختار میانی را تشکیل می دهند. لذا جریان تقاضا از مبدا به مقصد از طریق این نقاط میانی منتقل می شوند ، این نقاط میانی در شبکه هاب نامیده می شوند.
مکان یابی هاب در طراحی شبکه مراکز تقاضا و هاب نقش پایه ای دارد. چون کل هزینه حمل ونقل ، ظرفیت مراکز میانی واز این رو زمان خدمت دهی و میزان تراکم در سیستم را تحت تاثیر قرار می دهد[۳] .چند بررسی کلی در مورد مسایل مکان یابی هاب وجود دارد که جدیدترین انها مقاله آلمور و همکاران می باشد که تمام مدلهای مکان یابی هاب تحت شبکه تا سال ۲۰۰۷ گرداوری شده است[۵]. همچنین زنجیرانی و همکاران مقالات وتحقیقات انجام شده در مساله مکان یابی هاب را در انواع مختلف مسائل تحت شبکه ،گسسته، پیوسته ،.. از سال ۲۰۰۷ به بعد ، جمع آوریکرده اند[۶].

 

۲-۲- شبکه های هاب با تخصیص تکی وچندگانه

دو نوع اساسی از شبکه های هاب موجود است : تخصیص تکی و تخصیص چندگانه. این دو نوع در چگونگی تخصیص نقاط تقاضا به هاب با یکدیگر متفاوتند. همانطور که در شکل ۲-۱ نشان داده شده است در تخصیص تکی، همه ی ترافیک ورودی و خروجی هر مرکز تقاضا توسط یک هاب مسیریابی می شود. در تخصیص چندگانه ، هر مرکز تقاضا می تواند جریان را از طریق بیش از یک هاب دریافت و ارسال کند.

شکل (۲-۱) طبقه بندی شبکه هاب از لحاظ تخصیص

برخی مطالعات در این زمینه تنها با جنبه تخصیص مساله سر وکار دارند اما چون تخصیص بهینه متاثر از مکان یابی هاب و مکان یابی بهینه هاب متاثر از تصمیمات تخصیص است ، لذا مسایل مکان یابی و تخصیص باید با هم در طراحی شبکه هاب در نظرگرفته شوند. علاوه بر این تقسیم بندی ، محدودیت ظرفیت را نیز می توان به مسایل مکان یابی هاب افزود ، که می تواند محدود کننده ی ظرفیت سرویس دهی باشد یا حجم ارتباطی از طریق یال ها را محدود کند. در شکل ۲-۲ طبقه بندی مسایل هاب را در حوزه ظرفیت و نوع تخصیص نشان می دهد.

 

شکل (۲-۲)طبقه بندی مسایل هاب

تحقیقاتی که در زمینه شبکه هاب صورت گرفته است را می توان به دو دسته کلی تقسیم کرد:
دسته اول تحقیقاتی هستند که در آن ها سعی شده است با ارائه مدل ریاضی ، شبکه بهینه برای سیستم های توزیع ایجاد شود و دسته دوم شامل تحقیقاتی است که در آنها از روش های ابتکاری وفرا ابتکاری برای بهینه سازی سیستم موجود در ادبیات موضوع استفاده می شود.

 

۲-۳- مدل ها و روش های حل

 

۲-۳-۱- مدل تک تخصیصی

همان طور که در بالا یاد شد، اولین مدل ریاضی برای مساله مکان یابی تک تخصیصی بدون در نظر گرفتن محدودیت ظرفیت توسط اوکلی[۱۷] در شبکه حمل ونقل هوایی آمریکا ارائه شد[۳].مدل بصورت یک مدل درجه دوم شامل n2متغیر تصمیم دودویی و ۲n+1 محدودیت خطی است. در این بررسی هزینه داخل مراکز منظور نشده است.
همچنین اولین مدل ریاضی خطی عدد صحیح برای مساله مکان یابی میانه با p هاب توسط کمپل[۱۸] در سال ۱۹۹۴ ارائه شد[۷]. او در سال ۱۹۹۶ نیز مدل خطی عدد صحیح برای حالت تک تخصیصی مساله بالا ارائه کرد[۸]. در سال ۱۹۹۶، اسکورین[۱۹] وهمکاران یک مدل برنامه ریزی عدد صحیح آمیخته برای مساله تک تخصیصی مکان یابی میانه با p هاب بدون در نظر گرفتن محدودیت ظرفیت ارائه کرد[۹] . همچنین در سال ۱۹۹۶، ارنست و کریشنامورتی[۲۰] یک مدل ریاضی برای مساله تک تخصیصی مکان یابی با p تعداد هاب معرفی کردند که در مقایسه با مدل های قبلی، تعداد متغیر و محدودیت کمتری داشت[۱۰].
در سال ۲۰۰۱ ، ابری[۲۱] یک مدل برنامه ریزی عدد صحیح آمیخته جدید برای مسأله تک تخصیصی مکان یابی میانه با p تعداد هاب بدون در نظر گرفتن محدودیت ظرفیت ارائه کرد که اولین مدلی بود که تنها شامل متغیر تصمیم و محدودیت بوده، همچنین وی نشان داد که مدل از لحاظ زمان حل کامپیوتری بسیار کاراست وتوانایی حل مسائل با اندازه ی بالا را داراست[۱۱]. سیلوا[۲۲] و همکاران در سال ۲۰۰۹ سه نوع روش ابتکاری برای حل مسئله هاب با تخصیص تکی و بدون در نظر گرفتن محدودیت ظرفیت را معرفی کردند و کارایی این روش ها را در مورد مسائل بزرگ سنجیدند[۱۲] . نتایج به دست آمده نشان دهنده دستیابی به جواب بهینه در زمان بسیار کوتاه تر بود، که امکان حل مسائل در اندازه های بالا را در زمان کم فراهم کرد. ایلیچ[۲۳] و همکاران در سال ۲۰۱۰ یک روش فرا ابتکاری جستجوی همسایگی برای حل مسأله یاد شده معرفی کردند . آنها با هدف مکان یابی بهینه مراکز با کمترین هزینه جریان مواد بین همه مراکز تقاضای مبدأ و مقصد روش حل کارایی را از نظر کیفیت جواب ها و زمان حل ارائه کردند.[۱۳]

 

۲-۳-۲- مدل چند تخصیصی

اولین مدل ریاضی خطی عدد صحیح برای مسأله چند تخصیصی مکان یابی میانه با P تعداد هاب توسط کمپل در سال ۱۹۹۲ ارائه شد[۱۴] . همچنین او در سال ۱۹۹۴ برای مسائل مکان یابی میانه با P تعداد هاب بدون در نظر گرفتن محدودیت ظرفیت نیز مدل ریاضی معرفی کرد[۷]. در سال ۱۹۹۶، اسکورین- کاپف[۲۴] و همکاران یک مدل برای مسأله چند تخصیصی مکان یابی میانه با P تعداد هاب بدون در نظر گرفتن محدودیت ظرفیت ارائه کردند[۹]. در سال ۱۹۹۸، ارنست و کریشنامورتی مدلی کاراتر از مدل ارائه شده در [۹]پیشنهاد کردند که حل مسائل با اندازه بزرگتر را امکان پذیر ساخت[۱۵] . در سال ۱۹۹۹، ساساکی[۲۵] و همکاران مسأله خاصی از مسأله چند تخصیصی مکان یابی میانه با p تعداد هاب ارائه کردند، با این فرض که در هر مسیر تنها یک هاب وجود داشت[۱۶]. این مسأله در ادبیات موضوع با عنوان مسأله ای با یکبار توقف شناخته می شود. در سال ۲۰۰۷ یک روش ابتکاری دوگان – افزایشی[۲۶] را برای حل مسأله هاب با تخصیص چند گانه توسط کانوواس[۲۷] و همکاران[۱۷]معرفی شد. آنها کارایی روش خود را از نقطه نظر جواب و زمان حل، با اجرا بر روی مسأله معیار نشان دادند . در سال ۲۰۰۸ ، کامارگو[۲۸] و همکاران از روش تجزیه گاز انبری برای حل مسأله یاد شده ، استفاده کردند و با بهره گرفتن از آن موفق به حل مسأئل در اندازه های بزرگتر شدند که با روش های حل دقیق این امکان میسر نبود[۱۸]. همچنین در سال ۲۰۰۹ مسأله مکان یابی هاب به صورت تخصیص چند گانه را تحت شرایط ازدحام در هاب، بررسی کردند. آنها در این مطالعه، تعادلی را بین هزینه حمل و نقل و هزینه های ناشی از ازدحام در مراکز ایجاد کردند[۱۹].

 

۲-۳-۳- مدل های با هزینه ثابت ایجاد و ظرفیت محدود:

یکی از متغییر های تصمیم در مسأله مکان یابی هاب ، تعداد هابی است که نیاز است برای برقراری ارتباط گره های تقاضا در شبکه ایجاد می شود. برای این کار ، یا برای هر مرکز هزینه ایجاد در نظر گرفته می شود یا یک بودجه مشخصی برای آن در نظر گرفته می شود .
برای اولین بار اوکلی در سال ۱۹۹۲ مقدار هزینه ثابت را به عنوان هزینه ایجاد هاب در تابع هدف مدل به کار برد. در این مدل، تعداد هاب به جای اینکه از قبل به صورت ثابت فرض شود، به عنوان متغیر تصمیم در نظر گرفته می شود[۲۰]. کمپل در سال ۱۹۹۴ مدلی ارائه کرد که در آن برای هر یال شبکه، یک حداقل جریان به عنوان میزان آستانه جریان در نظر گرفت[۷]. در ضمن هزینه ثابت ایجاد یال های تقاضا را نیز در مدل مسأله مکان یابی میانه با p تعداد هاب در نظر گرفت. نیکل و همکاران در سال ۲۰۰۱ یک مدل ریاضی برای مسأله مکان یابی هاب ارائه کردند، که در آن هزینه ثابت ایجاد ، علاوه بر مراکز تقاضا، برای یال های اتصالی گره های تقاضا و یالهای اتصالی مراکز تقاضا نیز در نظر گرفته شد[۲۱].
وقتی تعداد هاب در شبکه به صورت ثابت فرض نشود، برای معرفی انواع دیگری از مسائل تک تخصیصی و چند تخصیصی مکان یابی هاب ، مفهوم ظرفیت در سیستم به کار برده می شود. اولین مدل ریاضی مسائل تک تخصیصی و چند تخصیصی مکان یابی هاب با در نظر گرفتن محدودیت ظرفیت و بدون در نظر گرفتن آن توسط کمپل در سال ۱۹۹۴ مطرح شده است[۷].
در سال ۱۹۹۹ ، ارنست و کریشنامورتی دو مدل ریاضی تک تخصیصی مکان یابی هاب با در نظر گرفتن محدودیت ظرفیت ارائه کردند به طوری که مدل دوم با داشتن متغیر و محدودیت کمتر در مقایسه با دیگر مطالعات ، جواب بهتری تولید می کرد[۲۲].

 

۲-۴- مکان یابی هاب در محیط رقابتی[۲۹] :

در این مسایل ، مکان یابی هاب با توجه به فضای رقابتی موجود بین هاب های جدید و هاب های موجود انجام می شود. از آنجایی که مشتریان نیز با توجه به فاکتورهای چون زمان، فاصله،هزینه، سطح کیفیت، …. انتخاب های خود را انجام می دهند، لذا مکان یابی هاب در شرایط رقابتی از اهمیت برخوردار است. در این مسایل، هدف از مکان یابی حداکثر کردن جذب جریان[۳۰] می باشد در جاییکه رقبای فعلی در این بازار فعالیت می کنند. این جذب جریان می تواند با توجه به پارامترهایی چون زمان کمتر برای انجا تقاضا، سطح سرویس بهتر، فاصله کمتر ، هزینه کمتر بین نقطه مبدا و مقصد و…. باشد. این مدل برای شبکه های حمل ونقل بار[۳۱] و جریان مسافر هوایی[۳۲] مناسب است، همچنین این مدل در خدمات پستی که زمان تحویل بسیار مهم است و تسهیلاتی که زمان تحویل کمتری ارائه دهند امکان جذب مشتری را دارند، کاربرد دارد.

 

۲-۴-۱- پیشینه مکان یابی هاب در محیط رقابتی :