بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
مروری بر تحقیقات انجام شده در زمینه ی مسئله ی مکانیابی پوشش هاب
چکیده
هاب ها نقاطی هستند که به منظور بهره برداری از صرفههای اقتصادی در انواع شبکههای مخابراتی، حمل و نقل، توزیع محصولات، خدمات پستی و غیره کاربرد دارند. مسئله ی مکانیابی پوشش هاب نیز مرتبط با مسئله ی مکانیابی هاب میباشد از آنجا که در سالیان اخیر این مسئله مد نظر محققین قرار گرفته است در این تحقیق سعی بر آن شده است که مروری بر ادبیات تحقیق انجام شده دربارهی این موضوع پرداخته شود که از دو جنبه مورد مطالعه قرار گرفته است، یکی از جنبهی مکانیابی هاب با پوشش کلی و دیگری از جنبهی مکانیابی هاب با حداکثر پوشش میباشد که هر کدام اهداف و فرمولهای ریاضی متفاوتی دارند. پس از انجام مروری بر ادبیات تحقیق، گپها و شکافهای تحقیقاتی مشخص و پیشنهاداتی جهت تحقیقات آتی ارایه خواهد شد.
واژههای کلیدی: مکانیابی پوشش هاب، مکانیابی هاب با پوشش کلی، مکانیابی هاب با حداکثر پوشش، فرمولهای ریاضی، ادبیات تحقیق.
-1 مقدمه:
هابها، تسهیلات خاصی هستند که به عنوان نقاط تبادل (سویچینگ)، انتقال و ادغام در سیستمهای توزیع چند در چند خدمت ارایه میدهند. به جای خدمت نمودن به هر زوج مبدأ-مقصد به طور مستقیم، تسهیلات هاب به منظور بهره برداری از صرفههای اقتصادی بر جریانات متمرکز میشوند. جریانات از همان مبدأ با مقاصد مختلف بر روی مسیرشان در هابها ادغام میشوند و با جریاناتی که مبادی مختلف دارند اما با همان مقصد ترکیب میشوند. ادغام بر روی مسیر از مبدأ به هاب و از هاب به مقصد و نیز بین هابها میباشد (آلومور و کارا1، 2008a، .(21-1
مسئله ی مکانیابی هاب با استقرار تسهیلات هاب و تخصیص گرههای تقاضا به هاب به منظور مسیریابی ترافیک بین زوج مبادی-مقاصد مرتبط میباشد. مسئله ی مکانیابی هاب یکی از زمینههای تحقیقاتی جدید و قابل توسعه در نظریهی مکانیابی است. به منظور ارضای تقاضا، مسئله ی مکانیابی هاب شامل جابه جایی افراد، کالاها یا اطلاعات بین زوج مبدأ-مقصد مورد نیاز میباشد (فراهانی و همکاران2، 2013، .(1109-1096
هزینههای یک شبکهی هاب بستگی به ساختارش دارد. فواصل کل آرکها با اتصال کل شبکه ممکن است در یک شبکهی هاب کم تر باشد، اما فاصلهی کل سفر ممکن است بزرگتر باشد از آن جا که هیچ تضمینی وجود ندارد که تعداد افراد یا اطلاعات با جابه جایی روی اتصالات هاب به هاب بزرگتر از جابه جایی بین هاب و میلهها باشد بنابراین، تعیین مکان تسهیلات و نیز تخصیص مشتریان (گرههای تقاضا) به آنها پیچیده و بسیار مشکل خواهد بود (کمپبل و همکاران3 ، 2007، .(835-819 اولین مقاله در زمینهی مسئله ی مکانیابی هاب که اولین فرمولها و روشهای حل ارایه گردید به دلیل تلاشهای اوکلی1986a) 4، 105-92 و 1986b، (356-343 بوده است.
با توجه به ادبیات تحقیق صورت گرفته در زمینهی مسئله ی مکانیابی هاب، مسئله ی مکانیابی پوشش هاب نسبت به سایر مسایل مکانیابی هاب، کمتر مورد توجه قرار گرفته است. مسئله ی مکانیابی پوشش هاب، که ابتدا توسط کمپبل 1994)، (405-387 معرفی گردید، تعمیمی از مسایل کلاسیک مکانیابی پوشش میباشد. این مسئله در تلاش برای استقرار تسهیلات هاب میباشد که در آن، زوج مبادی و مقاصد دو گرهی غیرهاب توسط زوج گرههای هاب پوشش مییابد. در حقیقت، زوج مبادی و مقاصد پوشش مییابند تنها اگر تسهیلات هاب در فواصل از پیش تعیین شدهای از اتصلاتشان وجود دارد. در واقع، هزینهی حمل و نقل از گرههای شروع به گرههای انتهایی از میان گرههای هاب منتخب میبایستی کوچکتر یا برابر مقدار از پیش تعیین شده باشد (فراهانی و همکاران، 2013، -1096 .(1109
در این تحقیق مروری بر تحقیقات و پژوهشهای انجام شده در زمینهی مسئله ی مکانیابی پوشش هاب پرداخته میشود، که در سالیان اخیر به دلیل کاربردهای وسیعی که در حمل و نقل، ارتباطات مخابراتی، توزیع محصولات و مکانیابی تسهیلات اضطراری و غیره دارد، محققان و علاقهمندان زیادی را در این حوزه به خود جذب نموده است که در قسمت دوم، مسئله ی مکانیابی پوشش تشریح میگردد، در قسمت سوم مسئله ی مکان یابی پوشش هاب بیان و سپس مروری بر تحقیقات انجام شده توسط محققین و پژوهشگران در این زمینه صورت میگیرد و در نهایت در قسمت آخر، پیشنهادات جهت تحقیقات آتی از گپهای موجود در ادبیات تحقیق در مسئله ی مکانیابی پوشش هاب، بیان میگردد.
-2 مسئله ی مکانیابی پوشش
در واقع یکی از متداولترین مدلها در مدلهای مسئله ی مکانیابی تسهیلات، مسئله ی پوشش میباشد، در حالی که مدلهای پوشش، جدید نیستند تنها علاقهمندان زیادی را در این زمینه جذب نموده است. آن هم به دلیل کاربردی که در دنیای واقعی دارند به خصوص
برای تسهیل اورژانسی و خدمات استفادهی زیادی دارند. در برخی از مسایل پوشش، یک مشتری میبایستی خدمت را توسط حداقل یک تسهیل در یک فاصلهی داده شده (نه لزوماً به نزدیکترین تسهیل) دریافت نماید. در بیشتر مسایل پوشش، مشتریان خدمات را توسط تسهیلات دریافت میکنند که البته بستگی به مسافت بین مشتری و تسهیلات دارد. مشتریان میتوانند خدمات را از هر تسهیل که فاصلهی تسهیلات از مشتری برابر یا کمتر از مقدار از پیش تعیین شده است دریافت نمایند. این فاصلهی از پیش تعیین شده، فاصلهی پوشش یا شعاع پوشش نامیده میشود (فلاح و همکاران5 ، 2009، ;176-145 فراهانی و همکاران، 2012، .(407-368
مسئله ی پوشش کاربردهای وسیعی دارد برای مثال در تحویل محصول، طراحی مدار سویچینگ، اعزام کامیون، بازیابی اطلاعات، تقسیمبندی سیاسی، زمانبندی خدمهی خط هوایی، مکانیابی تسهیلات مرکزی، تعادل خط مونتاژ، مکانیابی انبار، توزیع محصولات و مکانیابی تسهیلات سرویسدهی اضطراری میتوان اشاره کرد (فرانسیس و همکاران6، .(1992
مسئله ی پوشش به دو شاخهی شبکههای درختی و شبکههای کلی تقسیمبندی میگردد. مسئله ی پوشش، برپایهی پوشش همهی گرههای تقاضا یا برخی از نقاط تقاضا، به دو زیر مسئله ی پوشش کلی و پوشش جزیی تقسیمبندی میشود که فاصلهی پوشش میتواند هزینه، فاصله یا زمان پوشش باشد و زمانی یک تسهیل گرههای تقاضا را پوشش میدهد، اگر از فاصله، زمان پوشش یا هزینهی پوشش فراتر نرود (فلاح و همکاران، 2009، .(176-145
-3مسئله ی مکانیابی پوشش هاب7
در مسایل پوشش تسهیلات، اگر گرههای تقاضا در یک فاصلهی مشخصی از یک تسهیل باشند پوشش مییابند. کمپبل 1994)، -387 (405 سه معیار پوشش را برای هابها مشخص نمود. زوج مبدأ-مقصد i) و (j میتوانند توسط هابهای k و m پوشش یابند اگر:
(1 هزینه از i به j که از هابهای k و m میگذرند از یک مقدار مشخصی فراتر نرود.
(2 هزینه برای هر اتصال در مسیر از i به j که از هابهای k و m میگذرند از یک مقدار مشخصی فراتر نرود. (3 هر کدام از اتصالات مبدأ به هاب و هاب به مقصد مقادیر مشخص مجزایی را میگیرند.
-1-3 مسئله ی مکانیابی هاب با پوشش کلی
در حالت کلی مسئله ی مکانیابی پوشش هاب میتواند به دو مسئله ی مکانیابی هاب با پوشش کلی و مسئله ی مکانیابی هاب با حداکثر پوشش تقسیمبندی شود. در مسئله ی مکانیابی هاب با پوشش کلی فرض بر آن است که مسئله مانند مسئله ی میانهی p هاب است به جز آنکه تعداد هابها مشخص نمیباشد و هزینهی ثابت مکانیابی هاب در مدل ترکیب میگردد و تابع هدف با محدودیتهای مرتبط آن به شکل زیر میباشد (حکمتفر و پیشوایی8، 2009، .(270-243
مسئله ی مکانیابی پوشش هاب ابتدا توسط کمپبل 1994)، (405-387 معرفی شد. او مسئله ی متفاوت مکانیابی هاب p) هاب مرکزی- پوشش هاب) را در ادبیات موضوع معرفی نمود و توابع هدف متفاوت را درنظرگرفت به خصوص آنکه، مسئله ی پوشش هاب هزینهی کل استقرار تسهیلات هاب را کاهش میدهد بنابراین، هزینه (یا زمان سفر) بین هر زوج مبدأ- مقصد در یک حد معلومی می-باشد. او در این تحقیق یک فرمول درجهی دو و نیز فرمولهای خطی را پیشنهاد نمود. اولین تلاش برای فراهم نمودن نتایج محاسباتی مسئله ی پوشش هاب با تخصیص تکی از تحقیقات کارا و تنسل2003) 9، (64-59 بود. آنها فرمولهای مختلف خطی را پیشنهاد دادند به طوری که نتایج نشان داد مدل جدید خطی آنها بهتر از روشهای قبلی عمل میکند. همچنین آنها NP-hard بودن مسئله ی پوشش هاب را نیز نشان دادند.
ارنست و همکارانش(2005) 10 یک فرمول ریاضی بهتری را برای مسئله ی پوشش هاب با تخصیص تکی با استفاده از ایدهی شعاع هاب مطرح نمودند و نشان دادند مدل آنها در زمان محاسباتی کمتری نسبت به مدل کارا و تنسل در سال 2003 حل میشود.
هاماچر و میر (2006) 11 فرمولهای مختلفی را برای مسئله ی پوشش هاب و جستجوی باینری یرپایهی ارتباط معکوس بین مسئله ی مرکز p هاب و پوشش هاب معرفی نمودند.
تان12 و کارا 2007)، (39-28 مسایل متفاوت پوشش هاب را مطالعه کردند. آنها فرمول برنامهریزی عددی صحیح و اجرا با مقیاس بزرگ مدلهای پوشش هاب را در سیستم تحویل کارگو( محصول) در ترکیه ارایه نمودند.
واگنر 2008) 13، (938-932 مدل بهبود یافتهای را برای مسئله ی پوشش هاب در حالت تخصیص تکی و تخصیص چندگانه پیشنهاد نمود. کالیک و همکارانش2009) 14، (3096-3088 مسئله ی پوشش هاب با تخصیص تکی را بر روی یک شبکه ی ناکامل هاب معرفی نمودند. آنها مدل برنامهریزی عددی صحیح با هدف کاهش هزینهی کل استقرار هابها با در نظر گرفتن شعاع پوشش هاب را پیشنهاد نمودند و سپس مدل پیشنهادی آنها توسط یک روش ابتکاری کارا بر پایهی جستجوی ممنوعه 15(TS) حل گردید. همچنین، آلومور و کارا 2008b)، (1359-1349 مسئله ی مکانیابی پوشش هاب را در شبکههای ناکامل هاب با درنظرگرفتن کاربرد کارگو (محموله) معرفی نمودند. در واقع، آنها شبکهای را مورد مطالعه قرار دادند که از حداکثر سه هاب میگذرد و نشان دادند که برای الزامات زمان خدمت در بسیاری از موارد که حتی ایجاد شبکهی کامل هزینهبر و نیاز به سرمایه گذاری بالایی دارد، در این صورت احتیاجی به شبکهی کامل نمیباشد.
محمدی و همکارانش 2010) 16، (116-109 یک مدل برنامهریزی ترکیبی عددی صحیح را در مسئله ی پوشش هاب با تخصیص تکی با محدودیت ظرفیت را بر روی شبکهی کامل هاب با هدف یافتن مکان هاب و تخصیص گرههای غیرهاب ارایه نمودند. آنها برای حل مدل خود از یک الگوریتم هیبریدی بر پایهی الگوریتم ژنتیک 17(GA) و شبیهسازی تبرید 18(SA) استفاده نمودند و نشان دادند که الگوریتم هیبریدی در مقایسه با الگوریتم ژنتیک و شبیهسازی تبرید نتایج بهتری میدهد. همچنین محمدی و همکاران 2011)، (2638-2623 یک مدل صف M/M/C را برای مسئله ی مکانیابی پوشش هاب با محدود نمودن طول صف در هر هاب که از یک مقدار مشخص شدهای فراتر نمیروند را پیشنهاد کردند که آنها زمان حمل و نقل و نرخ کامیونهای رسیده به هر هاب را به صورت یک
متغیر تصادفی درنظرگرفتند. با توجه به اینکه پرترددترین بخش یک شبکه، هابها میباشند این مدل صف پیشنهاد گردید که برای مسئله یک مدل غیرخطی پیشنهاد و با تبدیل به مدل خطی با الگوریتمهای فراابتکاری بهبود یافتهی رقابت استعماری 19(ICA) و ژنتیک حل گردید. دو سال بعد از این تحقیق، محمدی و همکاران 2013)، (10073-10053 یک مسئله ی جدید احتمالی چند هدفه با حمل و نقل چند وجهی در مکانیابی پوشش هاب را ارایه کردند که در این تحقیق برخلاف اکثر مقالات مکانیابی هاب، دو تابع هدف جدید یکی کاهش کل هزینههای سرمایه گذاری و دیگری کاهش حداکثر زمان حمل بین زوج مبادی و مقاصد را درنظرگرفتند که در مدل آنها با درنظر گرفتن فاکتور ریسک، زمان حمل به صورت یک متغیر تصادفی نرمال مستقل میباشد. در نهایت آنها برای حل مدل از الگوریتم رقابت استعماری چند هدفه 20(MOICA) استفاده و عملکرد آن را با الگوریتم ژنتیک با مرتب سازی نامغلوب 21 (NSGA-II) و الگوریتم ارزیابی برپایهی پارتو 22(PAES) مقایسه کردند.
قدسی و همکاران2010) 23، (208-204 مسئله ی پوشش هاب با تخصیص تکی تحت محدودیت ظرفیت را در یک شبکهی کامل هاب درنظر گرفتند و فرمول برنامهریزی عددی صحیح را در آخر پیشنهاد نمودند. آنها رویکرد الگوریتم رقابت استعماری را برای حل مسئله ی مکانیابی پوشش استفاده نمودند.
کریمی و بشیری2011) 24، (1578-1571 مسئله ی پوشش هاب را با انواع متفاوت پوشش روی شبکهی کامل هاب مطالعه کردند. آن-ها روشهای خطی کردن برای مسئله ی پوشش کلی هاب و پوشش ماکزیمم هاب در دو حالت تخصیص تکی و چندگانه پیشنهاد نمودند و سپس مدل را بر روی یک شبکهی پستی در ترکیه و 37 فرودگاه فعال ایران با روشهای دقیق و ابتکاری حل کردند.
فاضل زرندی و همکارانش2012) 25، (911-907 مسئله ی مکانیابی پوشش کلی هاب با تخصیص چندگانه را با درنظرگرفتن پوشش پشتیبان و پراکندگی اجباری هابها معرفی نمودند. آنها برای اولینبار با توجه به ادبیات تحقیق که تاکنون انجام نشده است طراحی شبکهی هاب و میله با پوشش پشتیبان را بررسی کردند که در شبکه از مسیرهای جایگزین برای افزایش سطح خدمت استفاده میکنند که هر تقاضا در حداقل Q زمان پوشش مییابد و نیز یک حد پایینی در فاصلهی بین هابها برای پراکندگی اجباری آنها مورد توجه قرار دادند.
اقبالی و همکاران2013) 26، (11-1 مسئله ی چند هدفهی پوشش هاب با تخصیص تکی را ارایه نمودند، مسئله ی آنها با دو تابع هدف، کاهش هرینهی کل و افزایش رضایتمندی مشتریان (کاهش تعداد اتصالات میانی میان مبدأ-مقصد) مورد توجه قرار گرفت که عملکرد شبکه با توجه به قابلیت اطمینان در همهی مسیرهای مبدأ-مقصد از یک مقدار مشخصی کمتر نگردید و سپس مدل آنها با روش الگوریتم ژنتیک با مرتب سازی نامغلوب حل گردید.
ستاک27 و کریمی 2014)، (148-145 یک مسئله ی پوشش هاب تدریجی با استراتژی تخصیص تکی ارایه نمودند. با توجه به اینکه ممکن است یک به هم ریختگی ناگهانی در مسئله ی پوشش مشکل آفرین باشد که در مسئله ی پوشش جزیی وجود ندارد آنها دو شعاع پوشش w و β را درنظرگرفتند که اگر یک زوج گرهی مبدأ-مقصد با دو هاب در کمتر از زمان w باشند به طور کامل پوشش می-یابند. اگر زمان خدمت بین w و β باشد به طور جزیی پوشش داده میشود و در نهایت اگر بیش از β باشد هیچگاه پوشش نمییابد.
