ساختار پایان نامه

ساختار پایان نامه

چگونه می توان عدم قطعیت موجود در برآورد پارامتر تقاضا در مساله را مدل سازی نمود؟
چگونه می توان مکان یابی هاب را در یک محیط رقابتی تعریف کرد؟
1-9- ساختار پایان نامه :
در ادامه در فصل 2، ادبیات موضوعی و زمینه های علمی تحقیق را مورد بررسی قرار خواهیم داد. ادبیات موضوع در حوزه شبکه های هاب با در نظرگرفتن طبقه بندی های صورت گرفته در آن ارائه می شود. در فصل 3 به تشریح مساله ومدل پیشنهادی می پردازیم. در ادامه فصل ،با توجه به پیچیدگی های مدل پیشنهادی در مقیاس های بزرگ، یک الگوریتم فراابتکاری (الگوریتم ژنتیک)معرفی خواهیم کرد. نتایج محاسبات مربوط به الگوریتم پیشنهادی در فصل 4 مورد بررسی ومقایسه قرار خواهیم داد. در نهایت ، تعدادی از توسعه های آتی به همراه نتیجه گیری در فصل 5 ذکر شده است.
فصل دوم : ادبیات و پیشینه تحقیق
2-1- ادبیات موضوع
2-1-1- مقدمه :
ایده شبکه هاب در سال 1969 توسط گلدمن مطرح شد[1]. سپس اوکلی در سال 1968 اولین مطالعه شبکه های هاب را در زمینه شبکه هوایی مطرح ساخت[2] .همچنین اوکلی در سال 1987 اولین مدل ریاضی درج دومی را برای شبکه های هاب ارائه کرد[3] . از ان زمان، پژوهشگران متعددی در زمینه های مختلف مسایل مکان یابی هاب کار کرده اند. این میزان توجه عمدتا به سبب ضرورت ایجاد زیر ساخت های نوین برای سیستم های حمل ونقل و ارتباطات است[4] . زیرا به دلیل کاربردی بودن این مباحث ، با گذشت زمان وطراحی سیستم های پیچیده ، دیگر این ساختارها از مدل های شبکه های سنتی پیروی نمی کنند. در شبکه های خدمت دهی سنتی ،هر محل تقاضا، تقاضایش را به صورت مستقیم و بی واسطه از منبع تقاضا دریافت می کنند. در صورتی که در شبکه های نوین ، تعدادی از نقاط در شبکه انتخاب می شوند و یک ساختار میانی را تشکیل می دهند. لذا جریان تقاضا از مبدا به مقصد از طریق این نقاط میانی منتقل می شوند ، این نقاط میانی در شبکه هاب نامیده می شوند.
مکان یابی هاب در طراحی شبکه مراکز تقاضا و هاب نقش پایه ای دارد. چون کل هزینه حمل ونقل ، ظرفیت مراکز میانی واز این رو زمان خدمت دهی و میزان تراکم در سیستم را تحت تاثیر قرار می دهد[3] .چند بررسی کلی در مورد مسایل مکان یابی هاب وجود دارد که جدیدترین انها مقاله آلمور و همکاران می باشد که تمام مدلهای مکان یابی هاب تحت شبکه تا سال 2007 گرداوری شده است[5]. همچنین زنجیرانی و همکاران مقالات وتحقیقات انجام شده در مساله مکان یابی هاب را در انواع مختلف مسائل تحت شبکه ،گسسته، پیوسته ،.. از سال 2007 به بعد ، جمع آوریکرده اند[6].
2-2- شبکه های هاب با تخصیص تکی وچندگانه
دو نوع اساسی از شبکه های هاب موجود است : تخصیص تکی و تخصیص چندگانه. این دو نوع در چگونگی تخصیص نقاط تقاضا به هاب با یکدیگر متفاوتند. همانطور که در شکل 2-1 نشان داده شده است در تخصیص تکی، همه ی ترافیک ورودی و خروجی هر مرکز تقاضا توسط یک هاب مسیریابی می شود. در تخصیص چندگانه ، هر مرکز تقاضا می تواند جریان را از طریق بیش از یک هاب دریافت و ارسال کند.
شکل (2-1) طبقه بندی شبکه هاب از لحاظ تخصیص
برخی مطالعات در این زمینه تنها با جنبه تخصیص مساله سر وکار دارند اما چون تخصیص بهینه متاثر از مکان یابی هاب و مکان یابی بهینه هاب متاثر از تصمیمات تخصیص است ، لذا مسایل مکان یابی و تخصیص باید با هم در طراحی شبکه هاب در نظرگرفته شوند. علاوه بر این تقسیم بندی ، محدودیت ظرفیت را نیز می توان به مسایل مکان یابی هاب افزود ، که می تواند محدود کننده ی ظرفیت سرویس دهی باشد یا حجم ارتباطی از طریق یال ها را محدود کند. در شکل 2-2 طبقه بندی مسایل هاب را در حوزه ظرفیت و نوع تخصیص نشان می دهد.
شکل (2-2)طبقه بندی مسایل هاب
تحقیقاتی که در زمینه شبکه هاب صورت گرفته است را می توان به دو دسته کلی تقسیم کرد:
دسته اول تحقیقاتی هستند که در آن ها سعی شده است با ارائه مدل ریاضی ، شبکه بهینه برای سیستم های توزیع ایجاد شود و دسته دوم شامل تحقیقاتی است که در آنها از روش های ابتکاری وفرا ابتکاری برای بهینه سازی سیستم موجود در ادبیات موضوع استفاده می شود.
2-3- مدل ها و روش های حل
2-3-1- مدل تک تخصیصی
همان طور که در بالا یاد شد، اولین مدل ریاضی برای مساله مکان یابی تک تخصیصی بدون در نظر گرفتن محدودیت ظرفیت توسط اوکلی در شبکه حمل ونقل هوایی آمریکا ارائه شد[3].مدل بصورت یک مدل درجه دوم شامل n2متغیر تصمیم دودویی و 2n+1 محدودیت خطی است. در این بررسی هزینه داخل مراکز منظور نشده است.
همچنین اولین مدل ریاضی خطی عدد صحیح برای مساله مکان یابی میانه با p هاب توسط کمپل در سال 1994 ارائه شد[7]. او در سال 1996 نیز مدل خطی عدد صحیح برای حالت تک تخصیصی مساله بالا ارائه کرد[8]. در سال 1996، اسکورین وهمکاران یک مدل برنامه ریزی عدد صحیح آمیخته برای مساله تک تخصیصی مکان یابی میانه با p هاب بدون در نظر گرفتن محدودیت ظرفیت ارائه کرد[9] . همچنین در سال 1996، ارنست و کریشنامورتی یک مدل ریاضی برای مساله تک تخصیصی مکان یابی با p تعداد هاب معرفی کردند که در مقایسه با مدل های قبلی، تعداد متغیر و محدودیت کمتری داشت[10].
در سال 2001 ، ابری یک مدل برنامه ریزی عدد صحیح آمیخته جدید برای مسأله تک تخصیصی مکان یابی میانه با p تعداد هاب بدون در نظر گرفتن محدودیت ظرفیت ارائه کرد که اولین مدلی بود که تنها شامل متغیر تصمیم و محدودیت بوده، همچنین وی نشان داد که مدل از لحاظ زمان حل کامپیوتری بسیار کاراست وتوانایی حل مسائل با اندازه ی بالا را داراست[11]. سیلوا و همکاران در سال 2009 سه نوع روش ابتکاری برای حل مسئله هاب با تخصیص تکی و بدون در نظر گرفتن محدودیت ظرفیت را معرفی کردند و کارایی این روش ها را در مورد مسائل بزرگ سنجیدند[12] . نتایج به دست آمده نشان دهنده دستیابی به جواب بهینه در زمان بسیار کوتاه تر بود، که امکان حل مسائل در اندازه های بالا را در زمان کم فراهم کرد. ایلیچ و همکاران در سال 2010 یک روش فرا ابتکاری جستجوی همسایگی برای حل مسأله یاد شده معرفی کردند . آنها با هدف مکان یابی بهینه مراکز با کمترین هزینه جریان مواد بین همه مراکز تقاضای مبدأ و مقصد روش حل کارایی را از نظر کیفیت جواب ها و زمان حل ارائه کردند.[13]
2-3-2- مدل چند تخصیصی
اولین مدل ریاضی خطی عدد صحیح برای مسأله چند تخصیصی مکان یابی میانه با P تعداد هاب توسط کمپل در سال 1992 ارائه شد[14] . همچنین او در سال 1994 برای مسائل مکان یابی میانه با P تعداد هاب بدون در نظر گرفتن محدودیت ظرفیت نیز مدل ریاضی معرفی کرد[7]. در سال 1996، اسکورین- کاپف و همکاران یک مدل برای مسأله چند تخصیصی مکان یابی میانه با P تعداد هاب بدون در نظر گرفتن محدودیت ظرفیت ارائه کردند[9]. در سال 1998، ارنست و کریشنامورتی مدلی کاراتر از مدل ارائه شده در [9]پیشنهاد کردند که حل مسائل با اندازه بزرگتر را امکان پذیر ساخت[15] . در سال 1999، ساساکی و همکاران مسأله خاصی از مسأله چند تخصیصی مکان یابی میانه با p تعداد هاب ارائه کردند، با این فرض که در هر مسیر تنها یک هاب وجود داشت[16]. این مسأله در ادبیات موضوع با عنوان مسأله ای با یکبار توقف شناخته می شود. در سال 2007 یک روش ابتکاری دوگان – افزایشی را برای حل مسأله هاب با تخصیص چند گانه توسط کانوواس و همکاران[17]معرفی شد. آنها کارایی روش خود را از نقطه نظر جواب و زمان حل، با اجرا بر روی مسأله معیار نشان دادند . در سال 2008 ، کامارگو و همکاران از روش تجزیه گاز انبری برای حل مسأله یاد شده ، استفاده کردند و با استفاده از آن موفق به حل مسأئل در اندازه های بزرگتر شدند که با روش های حل دقیق این امکان میسر نبود[18]. همچنین در سال 2009 مسأله مکان یابی هاب به صورت تخصیص چند گانه را تحت شرایط ازدحام در هاب، بررسی کردند. آنها در این مطالعه، تعادلی را بین هزینه حمل و نقل و هزینه های ناشی از ازدحام در مراکز ایجاد کردند[19].
2-3-3- مدل های با هزینه ثابت ایجاد و ظرفیت محدود:

Share