وبلاگ

یک ناحیه مهم کاربرد مدل‌های LPSDC، مکان‌یابی تسهیلات خدمات اورژانسی (مانند بیمارستان‌ها)، ایستگاه‌های پلیس، ایستگاه‌های آتش نشانی و آمبولانس‌ها هستند. توانایی پاسخگویی به یک درخواست برای خدمت‌رسانی در زمان مناسب، به چنین سیستم‌هایی اختصاص دارد (مثلاً استاندارد رایج برای آمبولانس‌ها در آمریکای شمالی برای پاسخگویی به تلفن‌های با ارجحیت بالا، ۳ دقیقه می‌باشد). خصوصیت پایه چنین سیستم‌هایی غیرقابل پیش بینی بودن تعداد و زمان رسیدن تلفن‌ها برای درخواست و اثری که روی کارایی سیستم تراکمی می‌گذارد است و هنگامی‌که بعضی از این تسهیلات درخواست‌های بسیاری را برای خدمت در دوره زمانی مشخصی دریافت می‌کنند، نتیجه آن مشخص می‌شود. به راستی که از لحاظ تاریخی، مسأله مکان‌یابی تسهیلات خدمات اورژانسی، محرّک اصلی برای تحقیقات بیشتر در این زمینه را فراهم کرده‌است.

دیگر ناحیه مهم کاربرد این مسائل که کمتر مورد تجزیه و تحلیل قرار گرفته‌است، مکان‌یابی خرده فروشی‌ها یا تسهیلات خدمت‌رسانی دیگر است که مقدار کل تجارت (تقاضای مشتری) در یک تسهیل ممکن است هنگامی‌که نرخ خدمت‌رسانی به علت تراکم کاهش می‌یابد، به طور معکوس عمل کند. درحالی که بعضی از مدل‌هایی که برای مکان‌یابی تسهیلات اورژانسی توسعه پیدا کرده‌اند، می‌توانند به خوبی برای تسهیلات غیراورژانسی نیز به کار روند، این دو دسته از کاربردها، خصوصیات مختلف خودشان را نیز ایجاد می‌کنند.
۲-۲-۵-۱- مرور ادبیات مسائل مکانیابی تسهیلات با تقاضای تصادفی و تراکم [۱۰]
باتوجه به انعطاف پذیری تقاضا، دسترسی به یک تسهیل می‌تواند برحسب مجاورت با مشتریان بالقوه اش (وِرتر و لاپیِره^[۵۵])، به صورت کل زمان موردنیاز برای دریافت سرویس (پارکر و سرینیواسان^[۵۶]) مدل سازی شود. در این مورد یا موارد دیگر، شکل تابع تقاضای مورداستفاده، گسترشی از انعطاف پذیری تقاضا را نشان می‌دهند. بیشتر توابع تقاضای رایج در مقالات به شکل‌های زیر هستند: تابع خطی (وِرتر و لاپیِره؛ پارکر و سرینیواسان)؛ تابع نمایی (بِرمن و پارکان^[۵۷]؛ بِرمن و کاپلان^[۵۸] و درِزنِر)؛ و تابع مرحله‌ای (بِرمن و کِراس).
اگر انتخاب مشتری را درنظر بگیریم ( که بدین معنی است که هر عضو این حق را دارد که خود تسهیلش را انتخاب کند و نه اینکه توسط یک مرکز به یکی اختصاص پیدا کند)، یک گروه از مقالات، انتخاب بهینه را فرض می‌کنند، یعنی، هر مشتری، تسهیلی که برحسب مزیتش بهینه است را انتخاب می‌کند. بسیاری از نویسندگان به سادگی فرض می‌کنند که مشتریان به نزدیکترین تسهیل مراجعه می‌کنند، درحالیکه پارکر و سرینیواسان فرض می‌کنند که مشتریان، تسهیلی که بیشترین منفعت را دارد انتخاب می‌کنند. درمقابل، گروه دوم مطالعات، انتخاب احتمالی را فرض می‌کنند، یعنی، انتخاب تسهیل توسط مشتری، براساس توزیع احتمالی است که از سودمندی و مجاورت هر تسهیل ایجاد می‌شود. این فرض اغلب در محیط بازار استفاده می‌شود و شاید یک کار اصولی از هاف^[۵۹]، مؤثرترین مدل در این دسته باشد. همچنین ماریانوف^[۶۰] و همکارانش یک مسأله مکانیابی تسهیلات با تراکم را پیشنهاد کردند که از یک مدل انتخابی احتمالی برای نشان دادن رفتار تخصیص مشتریان استفاده می‌کرد.
مسأله موردنظر ما که تا حدودی در تئوری مکان‌یابی تسهیلات، پایه‌ای به حساب می‌آید، توجّهات بسیاری را در مقالات به خود جلب کرده‌است؛ مخصوصاً اینکه تقابل جنبه‌های مکانیابی و تصادفی (صف بندی)، آن را چالش برانگیز کرده‌است [۱۱]. این مسأله متعلق به دسته‌ای از مسائل مکانیابی با تقاضای تصادفی و تراکم و سرویس دهندگان ثابت (LPSDC) است که توسط بِرمن و کراس مرور شده‌است. مطالعه مدل‌هایی از این نوع، با ماریانوف و سِرا^[۶۱] در سال ۱۹۹۸ شروع شده‌است. مقالات دیگری نیز در این زمینه نوشته شده‌است که می‌توان به مقالات بِرمن، کراس و وانگ^[۶۲]؛ ماریانوف و ریوس^[۶۳]؛ ماریانوف و سِرا؛ وانگ، باتا^[۶۴] و رامپ^[۶۵] اشاره کرد. به علت پیچیدگی باطنی مسأله، همه مقالاتی که در بالا آورده شده، ساده سازی‌های بزرگی را انجام داده‌اند: فرض می‌شود که تقاضا گسسته است، یا فرض می‌شود که تعداد یا ظرفیت تسهیلات (یا هر دو) ثابت هستند، فرض می‌شود که مکان‌های تسهیلات بالقوه گسسته و بینهایت هستند، فرض می‌شود که فرایند رسیدن تقاضا پواسن باشد و همچنین معمولاً فرض می‌شود که فرایند خدمت‌رسانی نمایی است.
ترکیب حالت تصادفی (شامل تراکم بالقوه در تسهیلات) در مدل‌های نوع پوشش تسهیلات، با مسأله مکانیابی حداکثر پوشش موردانتظار (MEXCLP) توسط داسکین شروع شد؛ و تعداد قابل ملاحظه‌ای از دیگر کاربردها نیز در ادامه آن آورده شد. اما این مدل شامل بعضی ساده سازی‌های بزرگی بود، برای مثال: احتمال اینکه یک خدمت‌رسان مشغول باشد، مستقل از هر خدمت دهنده دیگری است و این موضوع برای همه خدمت دهندگان یکسان است؛ این احتمالات نسبت به مکان و حجم کار یکسان هستند. ماریانوف و سِرا فرض کردند که: (۱) تقاضای مشتریان توسط یک فرایند پواسن تولید می‌شود؛ (۲) توزیع زمان خدمت نمایی است؛ (۳) هر تسهیل به صورت یک سیستم صف M/M/1/a با ظرفیت محدود a عمل می‌کند؛ و (۴) همه تقاضاها هنگامی‌که برای خدمت‌رسانی به سیستم می‌رسند، اگر سیستم پر باشد، فرض می‌شود که تقاضا از دست می‌رود. توسط این مدل، تقاضای مشتریان ممکن است ازبین برود، چون یا تسهیل در شعاع پوشش آن وجود ندارد و یا تسهیلات مسدود شده‌اند. هدف، قرار دادن m تسهیل به گونه‌ای است که تقاضا‌ها را هرچه بیشتر پاسخ دهد. ماریانوف و ریوس این مدل را برای مکانیابی دستگاه‌های خودپرداز به کار گرفتند. در مدل آن‌ها، دستگاه‌ها، حافظه کوچکی دارند که هر کدام می‌تواند تعداد ثابتی، b، درخواست را نگهدارند که آن به این علت است که درخواست‌های دستگاه‌ها، اندازه ثابتی (۵۳ بایت) دارند. همچنین دستگاه‌ها به صورت یک صف M/M/1، حداکثر b درخواست در صف (یعنی حافظه) را انجام می‌دهد. اگر یک درخواست درحالی برسد که حافظه پر است، آن درخواست ازدست می‌رود (و باید دوباره فرستاده شود)، و برای اینکه مطمئن باشیم که این رویداد نادر است، یک محدودیت سطح سرویس  اعمال شده‌است. به هر حال تعداد کل دستگاه‌ها،به جای اینکه به عنوان قسمتی از فرایند بهینه سازی تعیین شود، ثابت هستند. مدل LSCP این مدل توسط ماریانوف و سِرا گسترش داده شد که در آن، هدف، پیدا کردن حداقل تعداد تسهیلات به گونه‌ای است که همه مشتریان، یک تسهیل در شعاع پوششان داشته باشند و محدودیت بر روی حداکثر نسبت تقاضای از دست رفته (یا حداکثر زمان انتظار) رعایت شود. باید به یاد داشته باشیم که این مدل، فرض می‌کند که مشتریان به جای اینکه به نزدیکترین تسهیل مراجعه کنند، می‌توانند به هر تسهیل باز شده‌ای در شعاع پوشش تخصیص یابند. بنابراین، آنها به جای مکانیسم انتخاب مشتری، مکانیسم انتخاب هدایت شده را انتخاب می‌کنند.
۲-۲-۵-۲- مکانیابی تسهیلات با تقاضای تصادفی و تراکم
دو منبع بالقوه برای از دست دادن تقاضا به صورت زیر است [۱۲]:

 

1. 1. عدم پوشش: این مورد زمانی اتفاق می‌افتد که هیچ کدام از تسهیلات به اندازه کافی به مشتری نزدیک نیستند که سطح مناسبی از راحتی را فراهم کنند.

 

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

 

برای مدل سازی تقاضایی که به علت تراکم از دست می‌رود، ما هر تسهیل را به صورت یک صف مارکفی با ظرفیت ثابت معین درنظر می‌گیریم و فرض می‌کنیم که اگر این ظرفیت به دست آمده باشد، تقاضای مشتری هنگامی‌که درطول این دوره می‌رسد، از دست می‌رود (یعنی، مشتریان بالقوه‌ای که هنگام پر بودن سیستم می‌رسند، مسدود می‌شوند).
مدل‌های LPSDC اصولاً به تقابل چهار مجموعه از عناصر مربوط می‌شود [۹]:

 

• • مشتریان: که برای انجام خدمت، درخواست می‌دهند.

 

• • تسهیلات: که به منابعی (خدمات دهندگان) که برای انجام خدمات موردنیاز است مکان می‌دهند.

 

• • خدمت دهندگان: که خدمت درخواست شده را انجام می‌دهند، و

 

• • درخواست انجام خدمت: که توسط مشتریان انجام می‌شود و بوسیله اتصال یک مشتری با یک خدمت دهنده دردسترس، رسیدگی می‌شود.

 

دیگر اجزاء موردنیاز برای توصیف یک مدل LPSDC به صورت زیر هستند: انواع فراهم شدن خدمت (که یا مشتریان به تسهیلات سفر می‌کنند تا به خدمت دهندگان دست یابند و یا خدمت‌دهندگان متحرّک، به مکان مشتریان سفر می‌کنند)، طبیعت و نتایج تراکم (هنگامی‌که یک تسهیل درخواست‌های بسیار زیادی برای انجام خدمت دریافت می‌کند، چه عکس العملی از خود نشان می‌دهد؟)، فرضیات رفتار مشتری (مشتریان تصمیم می‌گیرند که برای بدست آوردن خدمت، به کدام تسهیل مراجعه کنند یا یک «مرجع مرکزی» وجود دارد که مشتریان را به تسهیلات متصل می‌کند)، نوع اهداف و احتیاجات خاص دیگر مانند «استانداردهای پوشش» (که معمولاً به صورت محدودیت‌ها بیان می‌شود).
یک شبکه مشخص را فرض می‌کنیم  ، که N، مجموعه گره‌ها و A مجموعه کمان‌هاست. برای  از  استفاده می‌کنیم که به کوتاهترین مسیر از x به y است.

 

1. 1. مشتریان: فرض می‌شود که مشتریان در گره‌های شبکه واقع می‌شوند. نسبت  را برای همه درخواست‌هایی که برای انجام خدمت از گره  ایجاد می‌شود درنظر می گیریم که  . معمولاً فرض می‌شود که کل تقاضای مشتریان برای خدمت‌رسانی، یک فرایند پوآسن از جنس زمان با نرخ  است. همچنین فرایند درخواست خدمت برای هر گره i، یک فرایند پوآسن با نرخ  می‌باشد. درحالیکه بیشتر مدل‌ها، از ساختار تقاضای مشتریانی که در بالا توضیح داده شد استفاده می‌کنند، بعضی تلاشها برای دخالت دادن امکان ازدست دادن تقاضا به علت تراکم انجام شده‌است. این می‌تواند بوسیله تعریف دوباره نرخ تقاضا در گره i به صورت  تعریف شود که C، بعضی اندازه‌های هزینه تراکم است که بوسیله مشتریان اتفاق می‌افتد و  یک تابع غیر افزایشی است. در ادامه این بخش، به طور عمومی فرض می‌کنیم که  تحت تأثیر تراکم قرار نمی‌گیرد.

 

1. 1. تسهیلات: ما فرض می‌کنیم که حداکثر M تسهیل وجود دارد که باید مکان‌یابی شود. ما فرض میکنیم که یک مجموعه گسسته از مکان‌های بالقوه تسهیلات X تعیین شده‌است (که  ) و  . این فرضیات نیز بدون از دست دادن عمومیت انجام می‌شود: باتوجه به استدلالاتی که توسط بِرمن، لارسون^[۶۶] و چیو^[۶۷] انجام شده‌است می‌توان نشان داد که اگر به تسهیلات اجازه دهیم که در هر جایی در طول کمان واقع شوند، یک حل بهینه در یک مجموعه گسسته از مکان‌ها بدست می‌آید که شامل گره‌های شبکه است که بوسیله بعضی نقاط داخلی در طول کمان ایجاد شده‌است. بنابراین، با تکمیل کردن مجموعه گره‌های اصلی بوسیله بعضی گره‌های «ساختگی» اضافی، می‌توان فرض کرد که X گره‌ای است.

 

1. 1. خدمت دهندگان: هر تسهیل j می‌تواند بین ۱ و K خدمت دهنده داشته باشد. بسته به ماهیت خدمتی که بوسیله این تسهیل انجام می‌شود، خدمت دهندگان یا ثابت هستند، یعنی به طور ثابت در تسهیل واقع می‌شوند، یا متحرک هستند، یعنی برای انجام خدمت به مکان مشتریان سفر می‌کنند. تعداد خدمت دهندگانی  که در تسهیل j واقع می‌شوند، یک متغیرتصمیم گیری در مدل می‌باشد.

 

1. 1. درخواست خدمت: معمولاً یک درخواست برای انجام خدمت، به یک «یارگیری» بین مشتری ایجاد کننده درخواست و یکی از خدمت دهندگان موجود در سیستم احتیاج دارد. این کار معمولاً به صورت زیر انجام می‌شود:

 

 

 

• • اول باید تعیین کنیم که آیا مکان i بوسیله سیستم پوشش داده می‌شود یا خیر؟ معمولاً برای اینکه یک مشتری پوشش داده شود فرض می‌شود که با استاندارد‌های پوشش معینی مطابقت دارد (مثلاً، تعداد خدمت دهنده کافی باید در اطراف مشتری واقع شده باشد و غیره). این استانداردهای پوشش اغلب از طریق قانونگذاری یا قوانین اجرایی ایجاد می‌شود. اگر مکان مشتری i پوشش داده نشده باشد، همه درخواست‌های خدمت که از i ایجاد می‌شود، به صورت خودکار بوسیله سیستم برگردانده می‌شود (صرفنظر از اینکه آیا سیستم در حال حاضر متراکم هست یا خیر؟). معمولاً برای از دست دادن پوشش مجموعه یک جریمه درنظر گرفته می‌شود. یک تفسیر دیگر از گسترش ندادن پوشش به یک مشتری این است که مشتری بوسیله بعضی خدمات «دیگر» یا «ذخیره» پوشش داده شود (مثلاً، یک خدمت آمبولانس غیردولتی)؛ پس جریمه پوشش ندادن، می‌تواند به عنوان حق الزحمه قرارداد فرعی تفسیر می‌شود.

 

• • زمانی که معین می‌شود که درخواست خدمت از یکی از مشتریان «پوشش داده شده» بیاید، یک ارزیابی انجام می‌شود که آیا حالت فعلی سیستم اجازه می‌دهد که فرایند درخواست انجام شود یا خیر؟ این ارزیابی معمولاً در دو مرحله اتفاق می‌افتد: اول، قوانین منطقه‌ای و مکان مشتری برای تعیین «زیرسیستم» مشتری، استفاده می‌شود، یعنی، کدام تسهیلات و خدمت دهندگان می‌توانند به طور بالقوه به این درخواست پاسخ دهند (این ممکن است شامل همه خدمت دهندگان در شبکه شود و یا فقط خدمت دهندگانی که در شعاع سفر معینی از مکان مشتری واقع شده‌اند و غیره). بعد، تعداد درخواست‌های انجام نشده در زیرسیستم ارزیابی می‌شود و تصمیم گیری می‌شود که آیا این درخواست پذیرفته شود یا رد شود؟ این تصمیم معمولاً براساس ظرفیت زیرسیستم صورت می‌پذیرد (مثلاً برای یک صف «ازدست رفته»، اگر هیچ خدمت دهنده‌ای در حال حاضر دردسترس نباشد، یک عدم پذیرش ممکن است اتفاق بیفتد؛ در موارد دیگر ممکن است این محدودیت وجود داشته باشد که چه تعداد درخواست می‌تواند در یک زمان مشخص در صف وجود داشته باشد). معمولاً یک جریمه مرتبط با قبول نکردن یک درخواست وجود دارد. باز هم تأکید می‌کنیم، برخلاف نپذیرفتن یک درخواست از مشتریانی که پوشش داده نشده‌اند که به صورت خودکار است، نپذیرفتن درخواست یک مشتری که پوشش داده شده‌است، براساس حالت سیستم است. به خاطر داشته باشید که قوانین منطقه ای، درجه همکاری بین تسهیلات گوناگون و خدمت دهندگان را در سیستم معین می‌کند.

 

• • بعد، درخواست پذیرفته شده به یکی از تسهیلات متصل می‌شود (یعنی تخصیص پیدا می‌کند). این تخصیص ممکن است به قوانین اتصال مطمئن بستگی داشته باشد، همانطور که به حالت فعلی سیستم بستگی دارد (مثلاً، یک درخواست ممکن است به نزدیکترین تسهیل متصل شود و یا ممکن است به نزدیکترین تسهیل با حداقل یک خدمت دهنده آزاد متصل شود و غیره). همچنین قوانین اتصال به فرضیات رفتار مشتریان نیز بستگی دارد، یعنی اینکه کدام تسهیل باید این درخواست را انجام دهد به مشتری بستگی دارد یا به بعضی مراجع مرکزی. ما، این مورد را که مشتری تصمیم می‌گیرد که کدام تسهیل باید به درخواستش رسیدگی کند به عنوان «انتخاب کاربر» و موردی که یک مرجع مرکزی این تصمیم را می‌گیرد به عنوان «انتخاب هدایت شده» می‌شناسیم.

 

• • معمولاً یک درخواست پذیرفته شده در یک تسهیل معین، در صف قرار می‌گیرد تا یک خدمت دهنده، دردسترس قرار گیرد. زمانی که این اتفاق می‌افتد، خدمت دهنده و مشتری «یارگیری» کرده‌اند. درمورد خدمت دهندگان متحرک، لازم است که این خدمت‌دهندگان از مکان فعلی شان به مکان مشتری سفر کنند (که متحمل هزینه سفر می‌شوند).

 

معمولاً مسائل مکانیابی با خدمت دهندگان متحرک، دارای مشخصات زیر هستند:

 

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

 

1. 1. اگر یک کاربر، درخواستی را انجام دهد و نزدیکترین خدمت دهنده مشغول باشد، خدمت دهنده دیگری ارسال می‌شود. یعنی، این تخصیص، در حالت مطلق، به نزدیکترین تسهیل اتفاق نمی‌افتد.

 

1. 1. مسائل مکانیابی احتمالی اغلب می‌توانند به خوبی به صورت مجموعه مستقلی از سیستم‌های صف، مدل سازی شوند. این استقلال، ازطریق ابزاری ناشی می‌شود که حتی اگر زمان‌های خدمت از یک توزیع نمایی پیروی کنند، درمورد هنگامی‌که زمان سفر احتمالی است، این امر صادق نیست. بنابراین، تئوری صف M/G/m مناسب‌تر از تئوری M/M/m است.

 

حال به فرموله کردن مسأله می‌پردازیم. محدودیت‌های مسأله معمولاً شامل موارد ذیل است:
- یک حد بالای M بر روی کل تعداد تسهیلاتی که می‌توانند واقع شوند:
(۱۴.۲)
- یک حد بالای K بر روی کل تعداد خدمت دهندگانی که می‌تواند واقع شوند:
(۱۵.۲)
- استانداردهای پوشش: بسته به احتیاجات پوششی که استفاده می‌شود، می‌تواند شکل‌های گوناگونی به خود بگیرد. شاید ساده ترین (و قدیمی‌ترین) شکل این محدودیت‌ها، به این نیاز دارد که حداقل تعداد مشخصی از این خدمت دهندگان ،  ، باید در حداکثر فاصله مشخصی از هر مکان مشتری i، واقع شوند. اجازه دهید  زیرمجموعه‌ای از مکان‌های تسهیلات بالقوه در فاصله موردنیاز از i باشد. پس این محدودیت می‌تواند به صورت زیر بیان شود:
(۱۶.۲)