بخشی از مقاله
چکیده
مسئله مکانیابی هاب زیرمجموعه مسائل مکانیابی است که در سالهای اخیر مورد توجه پژوهشگران در طراحی شبکههای مختلف قرار گرفته و به یکی از مباحث مهم و پرکاربرد تبدیل شده است. هابها تسهیلات ویژهای هستند که به عنوان مراکز جمع آوری و توزیع در بسیاری از شبکهها به منظور کاهش ارتباطات مستقیم بین دو نقطه و در جهت افزایش کارایی بیشتر و کاهش هزینهها مورد استفاده قرار میگیرند.
در مسائل مکانیابی هاب هدف پیداکردن مکان مناسب هابها و تخصیص گرههای غیرهاب به هابها در جهت کاهش هزینههایی مانند هزینه اتصال و هزینه ایجاد هابها است. در این پژوهش از الگوریتم بهینهسازی مبتنی بر آموزش و یادگیری برای حل مساله مکانیابی هابها و کاهش هزینهها در شبکه های کامپیوتری استفاده شده و سپس نتایج آن با الگوریتم بهینهسازی ازدحام ذرات مقایسه شده است. نتایج بهدست آمده از این پژوهش نشان میدهد که الگوریتم بهینهسازی مبتنی بر آموزش و یادگیری با دقت بیشتری و در زمان کمتری مکانیابی هابها و تخصیص صحیح گرهها به هابها را انجام میدهد.
-1 مقدمه
در مسائل مکانیابی و تخصیص هدف، انتخاب بهترین مکان برای قرار گرفتن تسهیلات ارائه دهنده سرویس بوده و همچنین سعی میشود تا با تخصیص بهینه مراکز تقاضا به آنها، تقاضای از دست رفته خود را کاهش دهند - Alumar & Yaman, . - 2008 مسائل مکانیابی هاب زیرمجموعه این مسائل بوده و با بکارگیری یک تسهیل به عنوان هاب در کاهش هزینهها بسیار موثراند. مساله مکانیابی هاب جزء مسائل طراحی شبکه است و این مساله زمانی مطرح میشود که نیاز است مقداری جریان اطلاعاتی بین نقاط مبدأ و مقصد منتقل شود، اما برقراری ارتباط مستقیم میان همه نقاط ناممکن و یا بسیار پرهزینه است - . - Alumar & Kara, 2012 در مساله مکانیابی هاب، هدف یافتن مکان مناسب برای هابها و مسیرها جهت ارسال اطلاعات از یک سری مبدأ به یک سری مقصد، به منظور کاهش هزینهها و کسب منافع مورد نظر توسط انتقالهای متعدد بین هابها است.
در مساله مکانیابی هاب، علاوه بر تعیین مکان بهینه هابها، نقاط مبدأ و مقصد به هابها تخصیص داده می-شوند - . این مبحث به جهت کاربردهای وسیع از جمله مسافرتهای هوایی، خدمات پستی، سیستم توزیع، صنعت حمل و نقل، شبکههای مخابراتی و کامپیوتری از اهمیت زیادی برخوردار شده است و این به دلیل عواملی بوده که منجر به هزینههای عملیاتی سنگینی برای سیستم طراحی شده، میگردد - . - de Camargo & Miranda, 2012 هاب ها تسهیلات ویژهای هستند که به عنوان نقاط تعویض، انتقال و و طبقهبندی در بسیاری از سیستمهای توزیع به کار گرفته میشوند. تسهیلات هاب به جای خدمترسانی مستقیم بین هر جفت مبدأ-مقصد، جریان ها را به منظور صرفهجویی اقتصادی ناشی از آن، متمرکز می-نمایند. جریانها از مبدأ یکسان با مقصد های مختلف در یک هاب با جریانهایی که مبدأهای متفاوتی دارند اما مقصد آنها یکسان است ترکیب میشوند.
یکسانسازی بر روی مسیر مبدأ تا هاب، از هاب تا مقصد و نیز بین هابها صورت می-گیرد - . - Campbell & Ernst, 2002 در این پژوهش هدف این است که با استفاده از الگوریتم بهینهسازی مبتنی بر آموزش و یادگیری مساله مکانیابی هابها در شبکههای کامپیوتری حل شود و گرههای غیرهاب به نزدیکترین هاب متصل شوند و هزینههایی مانند هزینه اتصال گرهها هزینه ایجاد هابها کمینه شود. ادامه ساختار این مقاله به این صورت است که در بخش دوم مروری بر پیشینه تحقیقات انجامشده پرداخته شده و در بخش سوم الگوریتمهای بهینهسازی که مورد استفاده قرار گرفتهاند بیان شده است. در بخش چهارم مدل پیشنهادی و ارزیابی نتایج استفاده از الگوریتمهای بهینهسازی در جهت حل مساله مکانیابی هابها ارائه و در نهایت در بخش آخر نتیجهگیری انجام شده است.
-2 مروری بر پیشینه تحقیق
الکساندر بیلی و همکارانش بر این نگرش بودند که طراحی کارآمد و بهینهسازی شبکههای حمل و نقل و شبکههای توزیع شده، تاثیر قابلتوجهی از نظر اقتصادی و خدمات در هردو بخش دولتی و خصوصی خواهد شد. آنها روش جدیدی را مبتنی بر الگوریتم بهینهسازی ازدحام ذرات برای مساله مکانیابی هابهای بدون ظرفیت و با تخصیص تکی مطرح نمودند . اگرچه الگوریتمهای فراابتکاری گوناگونی برای این مشکل پیشنهادشده، اما با استناد به دانش نویسنده این اولین تلاش برای استفاده از روش بهینهسازی ازدحام ذرات بهمنظور حل مشکل بوده است. یک مطالعه تجربی که در آن مشکلات عمومی شناختهشده با تکیهبر اطلاعات ارسالی از 200 گره که توسط هیئت علمی هوانوردی و پست استرالیا بهدست آمد، انجام شد.
نتایج الگوریتم پیشنهادی با الگوریتم های فرااتبکاری دیگری مانند الگوریتم ژنتیک مقایسه شد. نتایج استفاده از آن، سادگی و اثربخشی آن در مقایسه با دیگر الگوریتمهای فراابتکاری است - . - Bailey, 2013 جولیا سندر در مقاله خود از روشی ابتکاری برای حل مسالهی تعیین مکان هاب در زمینه ترافیک باری موجود در شبکه قطارهای باربری کشور آلمان استفاده کرد . این روش سبب بهبود در تخصیص راهحلهای بهینه محلی میشود و در ترکیب با روش Cplex بر روی پایگاهداده شرکت باربری دویچهبان آزمایش شد.
نتایج آن حاکی از بهبود تخصیص مکان هاب نسبت به روشهای پیشین بهکاررفته در این زمینه دارد - Sender . - & Clausen, 2013 ارنست و همکاران روشی کارا برای حل مسئله مکانیابی p-hub میانی با ظرفیت نامحدود ارائه دادند. روش ارائه شده یک برنامهنویسی خطی برای این مسئله بود که از ویژگیهای آن میتوان به داشتن تعداد متغیرهای کمتر و محدودیتهای کمتر نسبت به روشهای مرسوم برای حل این مسئله بود. ایشان یک الگوریتم ابتکاری برای حل مسئله بر اساس الگوریتم شبیهسازی تبرید فلزات ارائه دادند و از کران بالای الگوریتم به عنوان ورودی برنامهریزی خطی شاخهوحد استفاده شد. نتایج شبیهسازی شده نشان میدهند راهحل پیشنهادی میتواند جواب دقیق را در زمان محاسباتی معقولی پیدا کند - . - Ernst & Krishnamoorthy,1996 محمد نعیم و همکارش بیان مینمایند که مسئلهی مکانیابی هاب یک مشکل NP-Hard تلقی میشود غالباًو در طراحی سیستمهای حمل و نقل و سامانههای توزیع یافته، شبکههای پستی و خطوط هواپیمایی کاربرد دارد.
پیشنهاد ساده اما مؤثرآنها برای تخصیص ظرفیت بلا استفادهی هاب استفاده از الگوریتم ژنتیک است. در الگوریتم ژنتیک ارائه شده دو کروموزوم فرزند حاصل، توسط عملگر ادغام از والدین خود بهوجود آمدهاند آنها برای ارزیابی اثربخشی الگوریتم یک سری مطالعات تجربی انجام دادهاند آنها الگوریتم خود را برای طراحی سیستم رایانهای دانشگاه هوانوردی مورد استفاده قرار دادند. الگوریتم پیشنهادی میتواند با توجهبه مشکلات پیشبینی نشده راهحلی متفاوت از راهحل-های قبلی ارائه دهد یا به توسعه راهحلهای پیشین برای حل مسائل بوجود آمده بپردازد - Naeem & Ombuki-Berman, . - 2010 اوکلی و همکاران در روش پیشنهادی خود برای حل مساله مکانیابی هاب با قید میزان هزینه برای دسترسی به سرویس ارائه دادند.
این روش برای شبکههای کامپیوتری با تعداد زیاد کامپیوتر میتواند مورد استفاده قرار گیرد. روش پیشنهادی از دو مرحله متفاوت تشکیل شده است. مرحله اول ایجاد یک الگوریتم تجزیه بندرز است. شبیهسازی گزینههای سرویس سرویسگیرنده بین سرویسهای رقابتی در آزمایشات تجربی مورد بررسی قرار میگیرد. مساله پیشنهادی به زیرمسائلی تقسیمشده و این زیرمسائل از برشهای بندرز بهینه که در زمان محاسباتی معقول انجام میشوند، استفاده میکنند.
نتایج بر روی پایگاهدادههای معروف در این زمینه نشان میدهد روش پیشنهادی ترافیک برروی هابهای شبکه با تغییر میزان سرویسدهی ایجاد میکند همچنین سرویس داده شده دارای هزینه مناسبی است - 2ʼ.HOO\' /XQD' H &DPDUJR' . - de Miranda Jr, 2015 جعفر باقرینژاد و همکارش به مکانیابی هاب، مدلها، کاربردها و روشهای تحلیل پرداختند. در این تحقیق مروری بر ادبیات مربوط به مکانیابی هاب صورت گرفته و جمعبندی از مدلهای کاربردی و روشهای تحلیل آنها ارائه گردیده است. در این رابطه ضمن دستهبندی مدلهای ریاضی والگوریتمهای حل اینگونه مسائل، یافتهها نشان میدهند که کاربردیترین الگوریتم، ژنتیک بوده ودر فاز تخصیص وتعیین محورها، الگوریتم جستجوی ممنوعه به طور مناسب استفاده شده است - باقری نژاد و عابدپور، . - 1393 علی بزرگی امیری و همکاران به مکانیابی هاب سلسله مراتبی با محدودیت ظرفیت و زمان تحویل پرداختند.
مسئلهی مکانیابی هاب سلسله مراتبی سه سطحی در نظر گرفته شده است؛ به گونهای که بالاترین سطح شبکه، شامل هابهای مرکزی است که به صورت یک شبکهی کامل بههم متصل هستند. سطوح دوم و سوم به ترتیب شامل هابها و نقاط تقاضا میباشند که در قالب شبکههای ستارهای به یکدیگر متصل شدهاند. نظر به این که در ادبیات مسئلهی مکانیابی هاب، در قالب سلسله مراتبی، محدودیت ظرفیت دیده نمیشود، در اینجا این فرض به مسئله افزوده شده است و هر نقطهی شبکه، در صورت انتخاب به عنوان هاب، دارای ظرفیت مشخصی خواهد بود.
همچنین همهی ارتباطات بین زوج نقاط در شبکه نیز دارای ظرفیتمحدود بوده و محدودیت زمان تحویل نیز در نظر گرفته میشود. مدل ریاضی مسئله ارائه شده و نتایج حل آن با ابعاد مختلف مسئله ارائه و تجزیه و تحلیل میشود - بزرگی، . - 1392 رضا توکلی مقدم و همکاران به حل مسئله مکانیابی هاب پوششی چندهدفه با رویکرد صف توسط یک الگوریتم فراابتکاری جدید پرداختند.در این مقاله، با توجه به بررسی کامل مسائل مکانیابی هاب، مدل جدید چندهدفه برای مسئله مکانیابی هاب پوششی با تعداد هاب مشخص ارائه میشود به گونهای که با در نظرگرفتن تابع هدف دوم در مدل، محدودیت ظرفیت از مدل حذف میشود.
با توجه به پیچیدگی مدل پیشنهادی و مسئله مکانیابی هاب، از الگوریتم شبیهسازی تبرید موازی - - MOPSA استفاده میشود که برای اولینبار نمایش جواب پیوسته برای این مسئله ارائه میگردد. برای ارزیابی کارایی و توانایی الگوریتم پیشنهادیMOPSA، جوابهای پارتو مربوطه با خروجی الگوریتمهای NSGA-II و PAES مقایسه میشود. در خاتمه برتری الگوریتم پیشنهادی با توجه به شاخصهای مختلف مقایسهای نشان داده میشود - توکلی مقدم، . - 1392 مهدی سیف برقی و همکارش به اعمال نرخ جذابیت مراکز در مدلسازی مسئله مکانیابی-صف وحل آن بهوسیله الگوریتم MOPSO پرداختند.
