مسئله مکانیابی تسهیلات صف بندی شده (بخش دوم): مدل پایه

مقدمه

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

اجزای اصلی مدل های مسئله مکانیابی تسهیلات صف بندی شده

مدل های مسئله مکانیابی تسهیلات صف بندی شده دارای چهار جز اصلی می باشند. این چهار جز شامل موارد زیر است:

مشتریان

جمعیتی هستند که درخواست خدمت می کنند و فرض می شود بروی گره های شبکه مسئله مستقر شده اند. معمولا سهم تولید تقاضا در هر گره با h_i نشان داده می شود که برای هر i متعلق به N داریم:

𝛴_i𝜖N h_i=1

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

λ_i= h_i×λ

تسهیلات

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

سرورها (سرویس دهنده ها)

هر تسهیل j می تواند به عنوان محل قرارگیری ۱ تا K سرور عمل کند. بسته به نوع سرویسی که در تسهیل فراهم می شود و اینکه سرورها ثابت یا سیار هستند تعداد سرورها در هر تسهیل باید تعیین شوند. در واقع تعداد سرورهای k_j مستقر شده در تسهیل j متغیرهای تصمیم مدل می باشند.

درخواست برای خدمت

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

• ابتدا باید معین شود که آیا مکان i به وسیله سیستم پوشش داده می شود. معمولا فرض می شود به منظور این که یک پوشش ایجاد شود باید استانداردهای پوشش تحقق یابد. لازم به ذکر است استانداردهای پوشش توسط مسئله یا به طور دقیق تر توسط قانون گذار معین می شود. اگر مکان iمورد پوشش قرار نگرفته باشد همه درخواست های تولید شده برای خدمت توسط سیستم رد می شود (صرف نظر از این که تراکم وجود دارد یا نه). همچنین جریمه ای برای تحت پوشش قرار نگرفتن منطقه مورد نظر در نظر گرفته می شود. البته در عمل تفسیر این که یک منطقه مورد پوشش قرار نگیرد این است که بایستی در این مناطق از سرویس های جایگزین استفاده شود (مانند سرویس های اورژانس خصوصی).
• دومین مورد این است که بایستی درخواست برای خدمتی که توسط مشتری تحت پوشش قرار گرفته، ارزیابی شود. این ارزیابی در دو مرحله صورت می پذیرد: اول اینکه باید قوانین مسئله در مورد پتانسیل خدمت رسانی سرورها مشخص باشد (به عنوان مثال برای ارائه خدمت، استقرار سرور آزاد در هر جای شعاع پوشش کافی است یا لازم است حتما سرور در تسهیل مستقر باشد و غیره). دوم اینکه تعداد درخواست های در صف قرار گرفته توسط سیستم سنجیده شود و سپس پذیرش یا عدم پذیرش یک درخواست صورت پذیرد که این تصمیم وابسته به ظرفیت صف در هر یک از زیر سیستم ها است. پس یک جریمه برای عدم پذیرش تقاضای پوشش داده شده داریم. تاکید می کنیم که عدم پذیرش تقاضا پوشش داده شده با عدم پذیرش تقاضای پوشش داده نشده متفاوت است.
• نکته بعد تخصیص یک درخواست مورد پذیرش به یکی از تسهیلات است. این تخصیص به قوانین و شرایط مسئله وابسته است. به عنوان مثال ممکن است یک درخواست برای خدمت همیشه به نزدیکترین تسهیل یا به نزدیکترین تسهیل با حداقل یک سرور آزاد تخصیص یابد یا حتی ممکن است تسهیل مورد نظر توسط خود مشتری انتخاب شود(User Choice) و یا این که مرکزی مسئولیت تخصیص مشتریان به تسهیلات را در دست داشته باشد (Director Choice).
• مطلب دیگر این که پاسخگویی به مشتریان شامل دو جز مهم و حیاتی می باشد: زمان سفر بین محل سرور و محل مشتری و زمان انتظار برای ارضای تقاضا. یک درخواست پذیرفته شده در یک تسهیل معین عموما تا زمانی که یک سرور در دسترس قرار گیرد، در صف قرار می گیرد. در حالتی که سرورها سیار باشند نیاز است آن ها به محل مشتریان سفر کنند (متحمل هزینه سفرشوند) و به محض ارضای تقاضای مورد نظر به محل تقاضای بعدی یا تسهیل خود باز گردند.

سایر اجزای مدل های مکانیابی تسهیلات صف بندی شده

دیگر اجزایی که ممکن است در این مدل ها موجود باشند شامل:

• انواع تدارک برای خدمت (آیا مشتری به محل سرور می رود یا برعکس؟)
• پیامدهای تراکم ایجاد شده در شبکه (هنگامی که یک تسهیل بیش از ظرفیت خود تقاضا دریافت می کند چه اتفاقی می افتد؟)
• فرضیات رفتار مشتری (به عنوان مثال مشتریان تصمیم می گیرند که کدام تسهیل جوابگوی تقاضای آنان باشد یا سیستم؟)
• انواع اهداف و محدودیت ها و استاندارد های پوشش که وابسته به نوع مسئله می باشند.

مدل سازی عمومی مسائل مکانیابی تسهیلات صف بندی شده

در این بخش مدل عمومی مسائل مکانیابی تسهیلات صف بندی شده را ارائه خواهیم کرد. در این مدل تقاضا به صورت احتمالی در نظر گرفته خواهد شد. برای نمایش اختصارات مدل از نشانه گذاری استانداردی که در مقاله (Berman&Krass,2002) ارائه شده است استفاده می نماییم.

• x_j  برابر است با k اگر یک تسهیل در مکان j موجود باشد و k سرویس دهنده به آن اختصاص یابد (k عدد صحیح است) و در غیر اینصورت برابر است با صفر.
• y_i  برابر است با یک اگر مشتری i توسط یک تسهیل پوشش داده شود و در غیر اینصورت برابر است با صفر.

در حقیقت از x برای نشان دادن متغیر مکان تسهیل و از y برای نشان دادن عامل پوشش استفاده می شود. حال در اینجا به بیان اجزای اصلی تابع هدف مسئله می پردازیم.

اجزای اصلی تابع هدف مسئله

ابتدا NC را به عنوان هزینه فراهم نشدن پوشش برای مشتری موجود در مکان i (برپایه هر تماس برای سرویس) تعریف می کنیم. پس هزینه کل عدم پوشش برابر است با:

(البته می توان _iλ برابر با h_i×λ در نظر گرفت که نشاندهنده نرخ تماس تولید شده در مکان i است.) از اجزای دیگر تابع هدف هزینه عدم پذیرش تماس مشتری پوشش داده شده است. در اینجا RC را به عنوان هزینه نپذیرفتن یک تماس از مشتری i که پوشش داده شده در نظر می گیریم. همچنین احتمال نپذیرفتن چنین تماسی را با P_Rⁱ در نظر می گیریم (توجه کنید که مقدار این عامل وابسته به هر دو عامل x و y است). بنابراین:

لازم به ذکر است درصورتی که این تماس های رد شده بوسیله واحدهای جایگزین پوشش داده شوند، می توان فرض کرد RC=NC.

از دیگر هزینه هایی که باید برای تابع هدف در نظر گرفت هزینه انتظار برای هر فراخوانی برای سرویس است که شامل دو جز است:

• زمان انتظار در صف برای فراخوانی سرویس و
• زمان مورد انتظار سفر بین مشتری و سرور

که این هزینه WC نامیده می شود. همچنین T_wⁱ زمان مورد انتظار در صف بعد از فراخوانی سرویس که توسط مشتری i تولید شده است، می باشد. P_D^ij( احتمال این است که فراخوانی سرویس تولید شده توسط مشتری i بوسیله سروری در مکان j پاسخ داده شود. توجه کنید که مقادیر بالا وابسته به شرایط مسئله، ثابت یا سیار بودن سرورها، توزیع های زمانی در صحنه بودن یا نبودن سرورها و قواعد مسیریابی است. در ضمن متوسط سرعت سفر مفروض برابر v و (d(i,j کوتاه ترین مسافت بین مکان های i و j می باشد. بنابراین:

LC^jk هزینه قرارگیری k سرور در در مکان j می باشد. پس هزینه کل استقرار تسهیل برابر است با:

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

محدودیت های عمومی مسئله

محدودیت های عمومی این مسائل نیز بدین شکل است:

۱- کران بالای M برای تعداد کل تسهیلاتی که می توانند قرار گیرند:

۲- کران بالای K برای تعداد سرورها:

۳- استانداردهای پوشش: این محدودیت به فرم های گوناگون بیان می شود، که ساده ترین شکل آن این است که مینیمم تعداد سرور b_i باید برای ماکزیمم فاصله هر مشتری i قرارگیرد. همچنین N_i زیر مجموعه مکان هایی است که پتانسیل قرارگیری تسهیل برای فاصله مورد نیاز i دارند. بنابراین داریم:

فرم سطح بالاتری از این محدودیت ممکن است به صورت فواصل اطمینان تعریف شود. به طور مثال زمان پاسخ ۳ دقیقه ای برای سرویس های اورژانس بدین صورت بیان می شود که زمان پاسخ ۳ دقیقه در حداقل ۹۵٪ اوقات اتفاق بیافتد. فرم دیگری از این نوع محدودیت ممکن است بر اساس کران بالا به نسبت تماس های پذیرفته نشده باشد. برای این منظور می توان نوشت SLi متغیر تصادفی سطح سرویس ارائه شده توسط سیستم به مشتری i  باشد که می توان فرض کرد سطح سرویس مطلوب متناسب با محدودیت استاندارد پوشش u_i باشد. بنابراین می خواهیم تضمین کنیم که در α­­_i درصد مواقع SL_i کمتر از u_i باشد. بنابراین داریم:

درست است که این نوع محدودیت ها چندان خوشایند استفاده کنندگان این مدل ها نیست ولی می توان آن را با فرض های ساده ساز در مسائل به محدودیت قدیمی و ساده استاندارد پوشش نزدیک کرد. حال می توانیم مدل عمومی مسائل QFLP را فرمول بندی کنیم:

ساده سازی مدل

برای ساده تر کردن این مدل روش های متعددی وجود دارد که دو روش زیر از جمله این روش ها قلمداد می شود (Berman&Krass, 2002):

• بکارگیری فرض های ساده ساز برای مسئله مثل قوانین و شرایط ساده برای مسئله یا اغماض از زمان سفر بین مشتری و تسهیل یا بکار بردن تخمین هایی از آن ها،
• بکار بردن تکنیک هایی مثل شبیه سازی یا استفاده از الگوریتم های ابتکاری برای حل مدل که در بخش های بعد مورد بحث قرار می گیرد.

مقایسه مدل های پوشش و میانه با وجود تراکم تقاضا در سیستم

دو مدل عمومی در ادبیات مکانیابی مدل های پوشش و میانه[۱] هستند که در مسائل QFLP نیز به موازات هم قرار می گیرند.

مدل پوشش

مدل پوشش سعی می کند تا پوشش مناسبی برای مشتری فراهم کند. در مدل های قطعی، پوشش به معنی آن است که حداقل یک تسهیل با ماکزیمم فاصله مشخص شده از مشتری وجود داشته باشد. در این مدل i𝜖N را برای نشان دادن تعداد محل های تسهیل که پوشش کافی برای مشتری ایجاد می کنند می شناسند، در واقع می توان برای محدودیت زیر N_i=1 را در نظر گرفت.

مدل پوشش دارای دو زیر گروه می باشد:

• مسائل پوشش مجموعه[۲]
• مسائل حداکثر پوشش وزنی[۳]

مسائل پوشش مجموعه

در مسائل قطعی پوشش مجموعه هر مشتری باید پوشش داده شود و هدف مینیمم کردن تعداد کل تسهیلات است. در این مجموعه از مسائل با توجه به مدل سازی عمومی مسائل QFLP، هزینه های TC_NC، TC_RC و TC_WC حذف می شوند زیرا پوشش کافی در محدودیت ها تضمین می شود. در واقع می توان متغیر y را حذف کرد و با ساده سازی هایی مسئله به یک مسئله خطی تبدیل شود.

مسائل حداکثر پوشش وزنی

در مسائل حداکثر پوشش وزنی ضرورتی نیست که تمام مشتریان پوشش داده شوند، بلکه مجموعه ای تعیین شده از تسهیلات باید مستقر شوند. در واقع هدف ماکزیمم کردن پوشش تقاضای پوشش داده شده است. در معادله QFLP این مسائل هزینه های  TC_LC، TC_RC و TC_WC حذف می شوند و محدودیت های زیر به محدودیت هایی مشابه تبدیل می شوند.

می توان دید که تابع هدف این مدل خطی است و می توانیم این مدل را به طور کامل خطی کنیم اگر محدودیت زیر را بتوان با فرض هایی خطی کرد (Berman&Krass,2002).

مدل میانه

اما مدل میانه به دنبال مینیمم کردن متوسط (یا کل) هزینه سفر همه مشتریان است. معمولاً فرض می شود که تعداد تسهیلات ثابت است و همه مشتریان به صورت طبیعی پوشش داده می شوند، به عبارت دیگر هیچ محدودیتی که به طور روشن پوشش کافی را بیان کند وجود ندارد، در ضمن هر مشتری از نزدیک ترین تسهیل به خود سرویس می گیرد. در مفهوم احتمالی این مدل هزینه های TC_NC و TC_LC حذف می شوند و محدودیت های زیر به معادل هایشان تبدیل می شوند و متغیر y حذف می شود اما با وجود محدودیت های خطی تابع هدف آن غیر خطی است.

بنابراین تنها راه حل های ابتکاری برای این گروه از مدل ها مناسب به نظر می رسد. از زیر گروه های جالبی که در مدل های QFLP میانه وجود دارد، مدل هایی با تقاضای انعطاف پذیر می باشد. در این مدل ها هزینه تراکم به صورت مجموع هزینه های TC_WC و TC_RC  می باشد این مدل ها که به طور خاص برای مکانیابی تسهیلات غیر اورژانسی مناسب است در(Brendau,1998) به تفصیل مورد بحث قرار گرفته است. متاسفانه این مدل ها از لحاظ مدل سازی بسیار مشکل هستند و برای اندازه های واقعی غیر کاربردی می باشند.

مقایسه سرورهای ثابت و سیار

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

برای درک بهتر تفاوت ها در چنین سیستم هایی، سیستمی را با یک تسهیل، K سرور، ظرفیت صف ۱ و با توزیع سرویس دهی نمایی فرض کنید. ابتدا شرایطی را بررسی می کنیم که سرورها سیار باشند. در این حالت تسهیل مذکور با صف M/M/K/1 کار می کند که مشخصه های سیستم مانند زمان مورد انتظار و نسبت تماس های از دست رفته و… توسط تئوری صف قابل اندازه گیری است. از این رو فرمول سازی دقیق این مدل به خوبی قابل تحلیل است. هرچند که چنین مدلی هم در محدودیت ها و هم در تابع هدف غیر خطی است. حال اگر فرض کنیم سرورها سیار باشند، سرور برای سرویس دهی باید به محل مشتری سفر کند (سرویس دهی با توزیع نمایی) سپس قبل از اعزام شدن برای سرویس دهی بعدی باید به تسهیل بازگردد. در این حالت زمان سرویس دهی دارای جمع دو توزیع نمایی است که ممکن است زمان سفر در دوحال متفاوت باشد. در واقع باید گفت توزیع زمان سفر نمایی باقی نمی ماند و تسهیل با صف M/G/K/1 عمل می کند. همان طور که مشاهده می شود تحلیل چنین فرمول سازی بسیار مشکل است و باید تخمین های زیادی برای تحلیل آن بکار برد.

در نهایت در این زمینه باید گفت که مدل های کاربردی برای مسائل QFLP که در واقع دارای تقاضای اورژانسی یا غیر اورژانسی هستند وابسته به نوع سرور و فرضیات رفتار مشتری هستند. معمولا مدل هایی که برای سرویس دهی اورژانسی (مانند آتش نشانی، ایستگاه های پلیس و اورژانس) بکار می روند دارای سرورهای سیار، انتخاب سرور از سوی مدیریت سیستم (Directed Choice) و پوشش استاندارد همراه با حالات احتمالی هستند. اما سرویس های غیر اورژانس شامل سرورهای ثابت و انتخاب سرور از سوی مشتری (User Choice) هستند، پوشش استاندارد در این حالت ممکن است در نظر گرفته نشود (مشتریان به صورت اتوماتیک پوشش داده شوند) یا در حالت قطعی (مشتریان درون شعاع معینی از تسهیل پوشش داده شوند) باشد.

پاورقی ها

• [۱] Median
• [۲] Set Cover-type problems
• [۳] Maximal Weight Cover-Type Problems