بخشی از مقاله
چکیده
هدف مسئله مکانیابی پوشش سلسله مراتبی کلاسیک پیدا کردن مکان تسهیلات در چند سطح است به نحویکه تعداد مشتریان پوشش داده شده را حداکثر کند؛ مشتریانی پوشش یافته فرض میشوند که درون فاصله خاصی از تسهیل واقع شوند. در مکانیابی پوشش سلسله مراتبی تعمیمیافته مشتریان خواهان سطح معینی از خدمات هستند که میتواند توسط تسهیلی با سطح برابر یا بیشتر از سطح نیاز ارائه شود.
در این مقاله برای سیستم بهداشت و درمان شامل سه سطح کلینیک، بیمارستان و درمانگاه در ابتدا از روش جستجوی محلی جدیدی مبتنی بر وزندهی ردیفی برای حل مسئله پوشش مجموعه با هزینهی یکسان استفاده شده است که تعداد بهینه هر تسهیل در هر سطح بدست آید و بعد از آن با استفاده از الگوریتم کلونی مورچگان مکان مناسب تسهیلات سلسله مراتبی را پیدا میکنیم و سپس کیفیت بالای روش حل در زمان محاسباتی منطقی در چندین مثال نشان داده شده است.
-1 مقدمه
هدف مسئله چینش تسهیل سلسله مراتبی - HFLP - 1 مکانیابی تسهیلات است به طوریکه تسهیلات با سطح بالاتر بتوانند نیازهای سطوح پایینتر را با کارایی و اثربخشی بیشتری پوشش دهند. کاربردهای فراوانی در دنیای واقعی از HFLP وجود دارد مانند: سیستمهای آموزشی، سیستمهای بهداشتی، سیستمهای مدیریت مواد زائد، خدمات پستی، سیستمهای بانکی، سیستمهای تولید-توزیع، کامپیوتر/شبکههای ارتباط تصویری.
مسئله مکانیابی حداکثر پوشش - MCLP - 2 توسط چارچ و ریوله در سال 1974 برای محاسبه اینکه کدام تسهیل جهت بیشینه کردن کل تقاضاهای پوشش داده شده باز باشد معرفی شده است.[3] در این مسئله یک مشتری پوشش داده شده در نظر گرفته میشود اگر درون فاصلهای خاص از تسهیل واقع شود. مسئلهی مکانیابی پوشش میتواند با شرایط مختلف و فرمهای متعددی سازگار شود
مسئله مکانیابی پوشش سلسله مراتبی - HCLP - 3 در ابتدا برای سیستم بهداشت و درمان معرفی شده است. در بکارگیری مسئله مکانیابی حداکثر پوشش - MCLP - فرض میشود که انواع مختلفی از خدمات برای مشتریان میتواند فراهم شود. مسئلهی مکانیابی پوشش سلسله مراتبی کلاسیک مسئلهای است برای پیدا کردن مکان تسهیلات در چند سطح به طوری که تعداد مشتریان پوشش داده شده حداکثر شود: مشتریانی پوشش داده شده فرض میشوند که درون فاصلهای خاص از تسهیل واقع شوند و در غیر این صورت پوشش داده نمیشوند. وقتی پوشش ویژه در HCLP جایز باشد مسئله به مکانیابی پوشش سلسله مراتبی تعمیمیافته تبدیل میشود. - G-HCLP - 4 وقتی فاصله از تسهیل از محدوده خاصی بیشتر باشد حتی اگر در فاصله پوشش واقع شود پوشش ویژه رخ میدهد. S و L دو پارامتر پوشش ویژه هستند.
در این مسئله مشتری میتواند به طور کامل پوشش داده شود اگر فاصله آن از تسهیل خدمت دهنده کمتر از S باشد، مشتری تحت پوشش ویژه قرار میگیرد اگر فاصله آن از تسهیل بین S و L باشد و اگر فاصله مشتری از تسهیل بیشتر از L باشد، مشتری تحت پوشش قرار نمیگیرد. در G-HCLP پوشش خدمت نیز تعمیمیافته است به این صورت که مشتریان سطح معینی از خدمات را میخواهند که میتواند توسط تسهیلی که سطح آن با خدمت مساوی یا بیشتر است پوشش داده شود. همچنین هر سطح از تسهیل، فاصله پوشش و نوع خدمت به مشتری مختص به خود را دارد.
سیستم تسهیلات سلسله مراتبی عموماً دارای دو یا چند سطح ازتسهیلات میباشند. برای مثال: سیستم درمانی ممکن است شامل کلینکها، بیمارستانها و درمانگاهها باشد و سیستم تولید-توزیع ممکن است شامل کارخانهها و انبارها باشد
تاکنون مطالعات متعددی در مورد HCLP انجام شده است. مندل در سال 1998 یک مدل پوششی برای سیستم خدمات اورژانس دوسطحی ارائه کرد . [14] لی در سال 1994 مسئلهی توزیع سلسله مراتبی با چندین مراکز توزیع را شرح داد. [12] مارینوف در سال 2001 موضوع مکانیابی تسهیلات سلسله مراتبی را در مراکز پر جمعیت بیان کرد.
مور و ریوله در سال 1982 مسئله سلسله مراتبی دوسطحی را معرفی و حل کردند.[16] بامب در سال 2001 الگوریتمی تقریبی را بر اساس روش گرد کردن تصادفی برای مسئلهی مکانیابی تسهیل بدون ظرفیت دوسطحی توسعه داد.[2] ایگناسیو، فیلهو و گالواو در سال 2008 مسئلهی مکانیابی سلسله مراتبی دوسطحی در شبکههای کامپیوتری را حل کردند.[9] تکسیرا و آنتونز در سال 2008 برای برنامهریزی تسهیل سلسله مراتبی عمومی گسسته مدلی ارائه کردند
در سال 2010 لی و لی الگوریتم جستجوی ممنوعه5 را برای حل مسئلهی مکانیابی پوشش سلسله مراتبی تعمیمیافته بهکار بردند.[13] در سال 2011 کاستا و همکارانش شبکه دوسطحی با تسهیل میانی و کاربرد در شبکههای توزیع الکتریکی را طراحی کردند.[5] در سال 2012 اکسن و همکارانش مدل مکانیابی دستگاههای شارژ ثابت را ارائه دادند .[1] همچنین در سال 2012 شو و همکارانش مدل برنامهریزی شبکه تسهیلات سلسله مراتبی برای شبکههای لجستیکی سراسری ارائه دادند.[18] برای اطلاعات بیشتر در مورد مدلهای مختلف مسئله مکانیابی سلسله مراتبی و روشهای مختلف حل این مسائل به [20] رجوع کنید.
-2 توصیف ریاضی مسئله
مور و ریوله در سال 1982 فرمول G-HCLP را به شرح زیر ارائه دادند.[16] باید توجه داشت که هدف مدل محاسبه مکانیابی تسهیل با پوشش بیشترین مشتری است.
متغیرهای تصمیم:
دو متغیر تصمیم صفر و یک xijk و yjl داریم که اگر یک مشتری در گره i توسط خدمت نوع k و تسهیل قرارگرفته در گره j پوشش داده شود، xijk برابر یک میباشد و در غیر اینصورت برابر صفر است. همچنین اگر تسهیل سطح l در مکان بالقوهj قرار بگیرد yjl برابر یک میباشد و در غیر اینصورت برابر صفر است.
پارامترها:
:Cijk نسبت پوشش مشتری گره i که توسط تسهیل قرار گرفته در گره j خدمت نوع k را دریافت کرده است.
: fik جمعیت مشتریان نیازمند خدمت نوع k در گره i
: tjk ظرفیت خدمت نوع k در تسهیل قرار گرفته در مکان j : pl تعداد تسهیلات مجاز برای پوشش با سطح l
بر اساس - 1 - ، هدف بیشینهسازی پوشش مشتریان است که توسط همه سطوح تسهیلات خدمترسانی شدهاند. محدودیت - 2 - نشان میدهد که مشتریان میتوانند به تسهیل در مکان j اختصاص یابند اگر تسهیل مجاز بتواند خدمتی مساوی یا بیشتر از نیاز مشتری ایجادکند. محدودیت - 3 - بیان می کند که مشتری گره i ام با تقاضای k ام ، حداکثر توسط یک تسهیل در گره j پوشش داده می شود. محدودیت - 4 - بیان میکند که تعداد کل تسهیلات با سطح L قرارگرفته در مکانهای j نباید از تعداد کل تسهیلات داده شده بیشتر شود. محدودیت - 5 - اشاره دارد که کل جمعیتی که هر تسهیل در مکان j و خدمت k میتواند پوشش دهد نباید از ظرفیت تسهیل بیشتر باشد. محدودیت - 6 - تأکید دارد که در هر مکان j حداکثر یک تسهیل می تواند واقع شود. محدودیتهای - 7 - و - 8 - متغیرهای صفر و یک را در مدل نشان می دهند.
در حالت کلی بالاترین سطح تسهیلات برابر یا بیشتر از سطح خدمتی است که مشتری نیاز دارد. برای مثال: .K=L درتابع هدف Cijk. که نسبت پوشش است به شرح Cijk =f - Rij, Sk, Lk - تعریف شده است که Rij فاصله بین تسهیلj و مشتریi است و Sk فاصله پوشش کامل در نوع خدمت k است و Lk بیشترین فاصله پوشش ویژه است.
-3 الگوریتم پیشنهادی حل مسئله
مسائل پوشش مجموعه - SCP - 6 و G-HCLP دارای پیچیدگی محاسباتی بالایی هستند و جز مسائل NP-hard به حساب میآیند. بر این اساس الگوریتمهای ابتکاری و فرا ابتکاری برای حل این مسائل در زمان محاسباتی منطقی میتوانند سودمند باشد.
حالت خاصی از SCP وجود دارد که در آن هزینههای پوشش برای همه مجموعهها یکسان است که به آن USCP7 میگویند در این مقاله برای سیستم بهداشت و درمان شامل سه سطح کلینیک و بیمارستان و درمانگاه در ابتدا از روش جستجوی محلی جدیدی مبتنی بر وزندهی ردیفی - RWLS - 8 برای حل مسئله USCP استفاده شده است که تعداد بهینه هر تسهیل در هر سطح بدست آید و بعد از آن با استفاده از الگوریتم کلونی مورچگان مکان مناسب تسهیلات سلسله مراتبی را پیدا میکنیم.
بنابرابن الگوریتم پیشنهادی در این مقاله شامل دو مرحله اصلی است: - 1 - الگوریتم RWLS برای بدست آوردن تعداد بهینه تسهیلات در هر سطح به صورت جداگانه، - 2 - استفاده از الگوریتم کلونی مورچگان برای پیدا کردن مکان مناسب تسهیلات در هر سطح با هدف بیشینه کردن کل پوشش مشتریان.
