یک مدل صف M/M/C برای مسئله مکانیابی پوشش هاب
چکیده:
مسئله مکانیابی هاب در انواع برنامه های کاربردی ظاهر می شود. از جمله سیستمهای هواپیمایی، سیستم های تحویل محموله و طراحی شبکه های مخابرات. مسائل مکانیابی هاب با یافتن مکان تسهیلات هاب و تخصیص نقاط تقاضا به این تسهیلات هاب مکانیابی شده سر و کار دارند. ما مسئله شبکه hub-and-spoke با تراکم یا ازدحام در سیستم را در نظر می گیریم. زمان حمل و نقل و نرخ ورود کامیون ها به هر هاب متغیرهای تصادفی هستند. به علاوه یک هاب نمی تواند به همه ی کامیون ها به طور همزمان خدمات ارائه دهد و محدودیتهایی مانند محدودیت ظرفیت و محدودیتهای زمان خدمت دارد. هاب ها ، که شلوغ ترین بخش شبکه هستند، به عنوان سیستمهای صف m/m/c مدل می شوند. در استفاده از مدل ارائه شده برای یک سیستم حمل و نقل محموله، تعداد کامیونها از توزیع احتمال پواسون در سیستم صف پیروی می کند. در این مقاله ابتدا یک برنامه ریزی ریاضی غیرخطی برای یافتن یک جواب بهینه برای مسئله در نظر گرفته شده ارائه شده است. یک محدودیت احتمالاتی که احتمال بودن b کامیون در یک صف کمتر از مقدار آستانه ی θ برای هر هاب است را تضمین می کند، شامل شده است. سپس محدودیتهای غیرخطی معرفی شده ی مدل برنامه ریزی ریاضی را به محدودیتهای خطی تبدیل می کنیم.با توجه به پیچیدگی محاسباتی مدل منتج، یک متاهیوریستیک بهبود یافته برمبنای الگوریتم رقابت استعماری و الگوریتم ژنتیک برای یافتن جواب بهینه ی مسئله ارائه می کنیم. عملکرد راه حل پیداشده توسط متاهیوریستیک بهبود یافته ارائه شده با جوابهای GA خالص و جوابهای مدل برنامه ریزی ریاضی مقایسه شده است.
کلمات کلیدی:
مکانیابی، طراحی و برنامه ریزی تسهیلات، مکانیابی پوشش هاب، صف، محاسبات تکاملی، الگوریتم رقابت استعماری.
- مقدمه
شبکه های hub-and-spoke در بسیاری از حوزه های زندگی روزمره از سفر مسافر از طریق یک شبکه ی شرکت هواپیمایی فرودگاهها تا تحویل پستی، ارتباطات، شبکه های حمل و نقل عمومی و بار معمول است. شبکه های هاب کاربردهای زیادی در سیستم های ارتباط از راه دور و حمل و نقل که چندین نقطه ی مبدا/مقصد ارسال و دریافت محصولات دارند. ویژگیهای کلیدی این شبکه ها این است که مسیریابی محصولات از طریق یک زیرمجموعه ی خاص از لینکها به جای مسیریابی هر محصول با یک لینک مستقیم از مبداش به نقطه ی مقصدش، است.
به طورخاص شبکه های هاب یک مجموعه از گره های هاب را برای یکی کردن و تغییر مسیر جریانها استفاده می کنند و یک تعداد کاهش یافته از لینکها که صرفه به مقیاس به کار رفته است، که به مجموعه ی نقاط مقصد و مبدا (معمولا بزرگ) متصل شود.همپنین مسائل مکانیابی هاب (HLP) مکان یک مجموعه ی گره های هاب و طراحی شبکه ی هاب را در نظر می گیرد. در ادبیات چهارنوع اصلی از مسائل هاب وجود دارد شامل: مسئله مکانیابی هاب ارتقایافته و نیافته، مسائل میانه ی p-hub ، مسائل مرکزی p-hub و مسئله مکانیابی پوشش هاب.
در مسئله مکانیابی هاب (HLP) هدف این است که هزینه کل مکانیابی هابها و جریانهای حمل و قل بار از میان شبکه ی هاب را مینیمم کند. ظرفیت هر هاب ممکن است محدود باشد (LHLP) یا محدود نباشد (uHLP). بیشتر مسائل موردی واقعی LHLP هستند.
در مسئله میانه p-hub (pHMP) هدف مکانیابی p هاب در شبکه است به طوری که هزینه کل جریانهای حمل و نقل از میان شبکه min شود. برخلاف UHLP تعداد هاب به عنوان ورودی داده شده است.
در مسئله مرکزی p-hub (pHCP) ، هدف یافتن مکان بهینه ی p هاب و تخصیص گره های غیر هاب به هاب ها و مینیمم کردن طولانی ترین مسیر در شبکه است.
در مسئله مکانیابی پوشش هاب (HCLP) تعداد هاب ها، داده نشده و هدف یافتن بهترین مکان هاب ها در شبکه و تخصیص گره ها به هاب ها است به طوریکه هزینه ی کل مکانیابی هاب ها مینیمم شود. HCLP شامل محدودیتهای پوشش است، که تعداد گره های غیر هاب که می توانند به هر هاب تخصیص یابند را محدود می کند. Campbell سه معیار پوشش برای هاب هاتعریف کرده است. هر جفت مبدا و مقصد (i , j) با هابهای k و m پوشش داده شود اگر:
- هزینه i به j توسط k و m از یک مقدار مشخص تجاوز نکند.
- هزینه هر لینک در مسیر از i به j توسط k و m از یک مقدار مشخص تجاوز نکند.
- هر لینک هاب مبدا و هاب مقصد با مقدار مشخص جداگانه مواجه شود.
همه ی انواع بالا در دوبخش اصلی تقسیم شده است : مسائل مکانیابی هاب تخصیص چندگانه و تکی. در شبکه های تخصیص تکی هاب ، هر گره غیرهاب فقط به یک هاب تخصیص می یابد، در شبکه های تخصیص چندگانه یک گره غیرهاب می تواند به بیشتر از یک هاب تخصیص یابد.
در این مقاله ما یک مسئله مکانیابی پوشش ارتقا یافته ی تخصیص تکی هاب با ازدحام را در نظر گرفتیم.
مسئله مکانیابی هاب ابتدا توسط O’Kelly معرفی شد. در کار دیگری O’Kelly یک فرمول ریاضی مکانیابی هاب برای شبکه های حمل و نقل هواپیمایی ارائه داد.
فرمول اولیه برای مورد تخصیص چندگانه توسط Campbell داده شده بود. بقیه ی ادبیات در مسئله مکانیابی هاب در درجه اول روی خطی سازی مدل درجه دوم ارائه شده در [3] تمرکز کرده، به طور مثال [4-7] . این مطالعات فرمولهای ریاضی مختلف و روشهای حل برای مینیمم کردن هزینه ی حمل و نقل کل را معرفی کردند. Campbell درجه دوم را به خوبی فرمولهای خطی برای هر دو تخصیص چندگانه و تکی برای مسائل مختلف ارائه داد.
اولین نتایج محاسباتی برای مسئله پوشش تخصیص تکی هاب Tansel , Kara ارائه شده بود. Ernst et al یک فرمول ریاضی بهتر برای مسئله ی پوشش هاب با استفاده از تفکر “radius” (شعاع دایره) ارائه دادند. برای مسئله مکانیابی هاب ارتقانیافته با تخصیص تکی ، Yaman , Labbe یک خانواده از اختلافات موثر که به اختلافات facet-defining تعمیم یافته و می تواند در مدت چندجمله ای جدا شده باشد را نتیجه گرفتند. مورد تخصیص چندگانه ارتقایافته توسط Aykin , Ebrey et al , Boland et al و Marin مطالعه شده بود. مسئله تخصیص تکی ارتقایافته همچنین توسط Ernst , Krishnamorthy, Labbe et al , Contreras et al وتوسط Contreras مطالعه شده بود. خواننده علاقمند به بررسی جامع روی ماده توسط Alumur , Kara , Campbell et al رجوع کرده بود. بهترین اطلاع ما فقط دو مقاله که تراکم و ازدحام بین یک مدل hub-and-spoke را در نظر گرفته اند از [20,21] هستند. Serra , Marianov شبکه ی hub-and-spokeرا به عنوان یک شبکه ی صف M/D/C برای سیستم هواپیمایی مدل کردند و یک محدودیت احتمالاتی را تحمیل کردند که احتمال داشتن بیش از یک تعداد مشخص از وجودها(هواپیما) منتظر در صف را محدود کرد. آنها محدودیت احتمالاتی را خطی سازی کردند و مدل را با استفاده از تابو سرچ حل کردند. Xiaolong , Elhedhli تاثیر ازدحام در یک هاب معین با استفاده از تابع هزینه محدب مدل کردند که به صورت نمایی افزایش می یابد به عنوان جریانهای بیشتر از میان آن هاب مسیریابی شده اند.
اختلافات اصلی مطالعه ی ما با منابع اشاره شده در بالا به صورت زیر هستند:
- Ernst et al مینیمم سازی هزینه های حمل و نقل بین گره ها را به عنوان تابع هدف ارائه دادند. اینجا ما این تابع هدف را با اضافه کردن هزینه ثابت باز کردن یک هاب جدید بسط دادیم.
- ما هردو جریان به طور مستقیم آمده از گره های مبدا وجریان آمده ازطریق هاب های دیگر به یک هاب مکانیابی شده در مدلهای ریاضی مان را در نظر گرفتیم. اما [9] فقط اولین نوع جریان را در نظر گرفته است.
- ما مدل ازدحام صف M/D/C از Serra , Marianov را به M/M/C بسط دادیم. این بسط به این دلیل است که زمان خدمت برای هر کامیون در سیستم حمل و نقل محموله قطعی نیست. همچنین ما کار Serra , Marianove را با در نظر گرفتن بعضی محدودیتهای پوشش که در سیستم حمل و نقل محموله معمول هستند، بسط دادیم.
- ما یک بیان جدید برای نرخ رسیدن به یک هاب ارائه دادیم که دقیق تر از قبلی در ادبیات است.
- ما یک نتیجه تحلیلی برای معیارهای زمان انتظار برای طراحی مسئله مکانیابی هاب ارائه می دهیم.
فرضیات دیگر مسئله ما به شرح زیر هستند:
- مطابق با [20] ما یک تحلیل ساعت پیک را استفاده کردیم، با فرض اینکه در طول ساعت پیک متوسط نرخ رسیدن و نرخ خدمت هر دو ثابت اند.
- ما تعداد ثابت از کمانهای هاب را مکانیابی نمی کنیم و ما شبکه کمان هاب ها را مجبور می کنیم که کاملا متصل شوند. بنابراین ما هیچ ساختاری در شبکه هاب را تحمبل نمی کنیم.
- مافرض می کنیم که هر هاب یک شعاع محدود برای پوشش غیر هابها دارد.
- جریانهای ورودی به هر هاب ممکن است در یک صف منتظر بمانن که خدمت لازم را دریافت کنند.
فرمت : pdf , Word
تعداد صفحات : 25
برای خرید با 10 درصد تخفیف اینجا کلیک کنید
یک مدل صف M/M/C برای مسئله مکانیابی پوشش هاب