مدلهای مکانیابی در یک زمینه گسترده از کاربردها استفاده میشود. بعضی از این موارد شامل موارد ذیل است: مکانیابی انبار در زنجیره تأمین برای مینیمم کردن متوسط زمان فاصله تا بازار؛ مکانیابی سایتهای مواد خطرناک برای مینیمم کردن درمعرض عموم قرار گرفتن؛ مکانیابی ایستگاههای راه آهن برای مینیمم کردن تغییرپذیری زمان بندیهای تحویل بار؛ مکانیابی دستگاههای خودپرداز برای بهترین سرویس دهی به مشتریان بانک و مکانیابی ایستگاههای عملیات تجسس و نجات ساحلی برای مینیمم کردن ماکزیمم زمان پاسخ به حادثههای ناوگان دریایی. با اینکه این پنج مسأله توابع هدف مختلفی دارند، همه این مسائل در حوزه مکانیابی تسهیلات واقع میشوند. درواقع، مدلهای مکانیابی تسهیلات میتوانند در موارد ذیل متفاوت باشند: توابع هدفشان، معیارهای فاصلهای که به کار میبرند، تعداد و اندازه تسهیلاتی که قرار است مکانیابی شوند و چندین معیار تصمیم گیری مختلف دیگر. بسته به کاربرد خاص هر مسأله، درنظرگرفتن این معیارهای مختلف در فرموله کردن مسأله، منتهی به مدلهای مکانیابی بسیار متفاوتی خواهدشد.
۱-۳- بیان مسأله
هدف از اجرای این تحقیق، مکانیابی سیستمهای خدمات رسانی ثابت با ظرفیت خدمت محدود میباشد. یعنی دستگاههای خدمترسان به چه تعداد و در چه محلهایی استقرار یابند و چه مراکز تقاضایی به این دستگاه های خدمترسان تخصیص یابند. در چنین سیستمهایی، زمانی که برای انجام سرویس موردنیاز است تصادفی است و همچنین تقاضای انجام خدمت در نقاط تصادفی از زمان میرسند که این تقاضا از جمعیت بزرگی از مشتریان سرچشمه میگیرد و معمولاً این سرویسدهی در نزدیک ترین تسهیل انجام میشود. چنین سیستمهای خدمترسانی، سیستمهای صف را تشکیل میدهند. مدلهای مختلفی برای حل این مسائل مکانیابی سیستم صف ارائه شدهاست.
دو ناحیه کاربردی وجود دارد که ما با این مدلها روبه رو میشویم [۴]: اولی در طراحی سیستم ارتباط کامپیوتری مانند اینترنت میباشد. در یک سیستم ارتباط کامپیوتری، ترمینالهای مشتری (کاربران اینترنت) به کامپیوترهای میزبان (سرورهای پروکسی، سرورهای آینه) وصل میشوند که قابلیت پردازش بالا و/یا پایگاه دادههای بزرگ میزبان دارند. زمانی که طول میکشد تا سرور درخواست را پردازش کند بستگی به سرعت پردازش سرور و و نوع درخواست دارد که آن هم تصادفی است. زمانی که مشتری برای پاسخ سرور منتظر میماند نیز بستگی به تعداد و اندازه درخواستهای دادهای است که در حال حاضر در صف هستند. به طور کلی، درخواستهای مشتریها به نزدیکترین سرور وصل میشود. این مکان و ظرفیت سرورها، پارامترهای طراحی بحرانی هستند. این انتخاب پارامترها تأثیری قابل توجه روی کیفیت خدمات دارد، به طوری که بوسیله یک مشتری درک میشود.
کاربرد دوم شامل طراحی یک سیستم دستگاه خودپرداز برای بانک است. مشتریها به صورت تصادفی به یک دستگاه خودپرداز میرسند. اگر هنگامیکه آنها میرسند، دستگاه آزاد باشد، آنها بلافاصله سرویس دهی میشوند. در غیر این صورت ، آنها به صف میپیوندند یا آن جا را ترک میکنند. زمان تصادفی که یک مشتری در یک دستگاه سپری میکند بستگی به تعداد و نوع تراکنشی (مثلاً مانده حساب، دریافت وجه، انتقال وجه و غیره) دارد که او انجام میدهد. منبع قابل توجه دیگر زمان مشتری در یک دستگاه، شامل تأخیر ارسال در مدت شبکه ارتباط بانک است. از آن جا که دستگاهها ثابت هستند، مشتریها باید به یک مکان خودپرداز مراجعه کنند تا یک تراکنش را انجام دهند. گاهی اوقات، مردم در طول مسیر خود (مثلاً از خانه به محل کار) برای استفاده از یک دستگاه خودپرداز به آن مراجعه میکنند؛ گاهی اوقات هم، آنها آن را طبق یک مسیر از پیش برنامهریزیشده (مثلاً مسیر روزانه بین خانه و کار) استفاده میکنند. به طور کلی، آنها از تسهیل با کمترین هزینه قابل دسترس استفاده میکنند. برای مثال، هنگامیکه هزینهها بوسیله مسافت سفر تعیین میشود، مشتریها نزدیکترین تسهیل به محل کار/خانه یا نزدیکترین مسیر روزانه شان را انتخاب میکنند. ما فرض میکنیم که مشتریها هیچ اطلاعی از تأخیرات دستگاههای خودپرداز ندارند و از این رو نزدیکترین تسهیل را برای درخواست سرویسشان انتخاب میکنند.
فرضیاتی که برای این مسأله درنظر گرفته میشود به شرح زیر میباشد:
-
- گره مشتری وجود دارد که هر یک درخواستی را برای سرویس ایجادمیکند؛
-
- تعداد درخواستها در واحد زمان، یک جریان پوآسن مستقل را تشکیل میدهند؛
-
- گره خدمترسان بالقوه وجود دارد؛
-
- مشتریان از مراکز تقاضا به سمت مکان این دستگاهها حرکت میکنند؛
-
- هر جایگاه خدمت فقط یک خدمت دهنده دارد؛
-
- زمان سرویس یک دستگاه به صورت تصادفی و توزیع نمایی دارد؛
-
- مکان دستگاهها ثابت هستند؛
-
- مشتریها بوسیله نزدیکترین دستگاه خودپرداز خدمترسانی میشوند؛
-
- میزان زمان انتظار مشتریان در صف نباید از یک حد ازپیش تعیین شده، فراتر رود؛
-
- ماکزیمم تعداد دستگاههای خدمترسان از قبل تعریف شدهاست.
در مسائل مکانیابی تک هدفه، هدف مسأله معمولاً هزینه یا پوشش بودهاست، امّا در مسائل چندهدفه، حداقل یک هدف دیگر وجود دارد که باتوجه به طبیعت این گونه مسائل، با هدف اوّلی درتضاد است.
براین اساس، ما مروری بر روی اهدافی که در مسائل مکانیابی چندهدفه توسعه یافته میکنیم. این اهداف میتوانند به صورت زیر توصیف شوند:
-
- هزینه: انواع مختلفی از هزینه وجود دارد. این انواع میتوانند به دو قسمت ثابت و متغیر تقسیم شوند. هزینههای ثابت شامل هزینه شروع و نصب به همراه سرمایه گذاری میباشد. هزینههای متغیر میتواند هزینه حمل و نقل، عملیات، تولید، خدمات، توزیع، تدارکات، دفع پسماند، نگهداری و محیطی باشد. هزینه حمل و نقل بیشترین و هزینه نصب بعد از آن قرار دارد. مسائل مختلفی از یک معیار «هزینه کل» استفاده کردهاند که شامل همه هزینهها تحت یک هدف میشود.
-
- ریسکهای محیطی: این هدف شامل ریسک حمل و نقل، ریسک طبیعی، دفع پسماند یا ریسک رفتاری، یا «اثرات نامطلوب» عمومی است که جایگاه بزرگی دارد. به هر حال نسبت ریسک محیطی در مسائل مکانیابی کمتر از دیگر هزینههاست.
-
- پوشش: تقریبا مجموعه کامل مسائل مکانیابی درباره پوشش مسافت، زمان، مبلغ و یا حتی انحراف پوشش است. اگرچه بسیاری از مسائل از مسافت و پوشش جمعیّت به عنوان هدفشان استفاده میکنند، اما در بعضی مسائل نیز زمان مهّم است.
مفهوم تساوی نیز در این طبقه قرار میگیرد، زیرا این نوع مسائل، روشی منصفانه در برخورد با مسأله پوشش دارند.
-
- سطح و کارائی خدمت: در این طبقه، هدف سطح سرویس به همراه کارائی قرارمیگیرد.
-
- سود: بعضی مسائل به سود خالص (تفاوت بین سودها و هزینهها) علاقمندند.
-
- اهداف دیگر: بعضی اهداف دیگر که در مسائل مکانیابی استفاده میشوند، مانند دستیابی به منابع به همراه ریسکهای سیاسی و اجتماعی که نمیتوانند در دیگر دسته ها قرار بگیرند.
سه هدف برای مسأله موردنظر ما درنظر گرفته شدهاست که هدف اول، مینیمم کردن متوسط تعداد مشتریان درحال سفر؛ هدف دوم، مینیمم کردن متوسط تعداد مشتریان در حال انتظار و هدف سوم، ماکزیمم کردن مجموع کارکرد دستگاهها در واحد زمان میباشد.
۱-۴- روش حل
به طور کلی مسائل مکانیابی تسهیلات اصولاً NP-Hardهستند و بعید است بدون کاربرد الگوریتمهای فراابتکاری بتوان حلّی بهینه را در زمان معقول پیدا کرد و زمان محاسباتی نیز با توجه به اندازه مسأله به صورت نمایی افزایش می یابد.
مسائل بهینه یابی چندهدفه، به طور کلی با یافتن حلهای بهینه پارتو یا حلهای مؤثّر کارمیکنند. چنین حلهایی غیرمغلوب هستند، یعنی هنگامیکه همه اهداف درنظر گرفته شوند، هیچ حل دیگری برتر از آنها نیست. بیشترین روشهایی که برای حل مسائل بهینه سازی چندهدفه به کار میروند، روش های ابتکاری و فراابتکاری هستند.
برای مسائلی که در کلاس NP-Hard قرار می گیرند، تاکنون روشهای دقیقی که بتواند در حالت کلی و در زمانی معقول به جواب دست یابد توسعه داده نشدهاست. از این رو روشهای ابتکاری و فراابتکاری مختلفی را برای حل این دسته از مسائل به کار می برند تا به جوابهای بهینه یا نزدیک به بهینه دست یابند.
در این تحقیق سعی شدهاست که از چندین الگوریتم بهینه سازی چندهدفه استفاده شود. الگوریتم [۶]NSGA-II به این خاطر انتخاب شدهاست که این الگوریتم در بسیاری از مقالات به عنوان الگوریتم مرجع مقایسه گردیدهاست. الگوریتم [۷]CNSGA-II نیز به این علت انتخاب شدهاست که روشی مناسب برای برخورد با محدودیتهای حل مسأله ارائه میکند. چون باتوجه به ماهیت مسأله، چندین محدودیت سر راه حل مسأله ایجاد شدهاست که راهکار مناسبی برای رسیدگی به این محدودیتها ایجاب میکند. الگوریتم [۸]NRGA نیز چون جزء جدیدترین الگوریتمهای ارائه شده در زمینه بهینه سازی چندهدفه میباشد مورداستفاده قرار گرفتهاست. در سالهای اخیر، الگوریتمهای بهینه سازی مبتنی بر ایمنی مصنوعی بسیار مورد توجه قرار گرفتهاست که به همین علت، ما در این تحقیق سعی بر آن داریم که از کارآمدترین این الگوریتمها استفاده کنیم. از میان الگوریتمهای چندهدفه ایمنی، ما از [۹]MISA، [۱۰]VIS و [۱۱]NNIA استفاده کرده ایم که در ادامه و در بخشهای بعدی به نتایج خوبی که دراثر استفاده از این الگوریتمها بدست میآید، اشاره میکنیم.
۱-۵- اهمیت و ضرورت تحقیق
امروزه پایانه فروش، پایانه شعب، دستگاههای خودپرداز و … نماد بانکداری الکترونیک است و یافتن مکان بهینه برای این پایانهها و دستگاهها میتواند نقش مهمی در حضور یک بانک یا مؤسسه در بازارهای داخلی و خارجی داشته باشد.
در این تحقیق سعی شدهاست که محدودیتها و چالشهای فراروی این مسأله در دنیای واقعی تا حد ممکن درنظر گرفته شود. به همین منظور محدودیتهایی ازقبیل ماکزیمم دستگاه خدمترسانی که میتواند به کار گرفته شود و حدّ بالای زمان انتظار برای مشتریان منظور شدهاست. همچنین بهدلیل اینکه یک هدف، پاسخگوی انگیزه ایجاد شده برای انجام این طرح نمیباشد، این مسأله به صورت یک مسأله چند هدفه درنظر گرفته شدهاست تا به دنیای واقعی هر چه نزدیکتر گردد تا در درجه اول سود بانک یا مؤسسه ازطریق انتخاب بهینه دستگاههای خودپرداز افزایش یابد و در درجه دوم رضایت مشتریان جلب گردد، به صورتی که هم پوشش مناسب برای خدمترسانی داده شود و هم مدت زمان خدمترسانی به مشتریان حداقل گردد.
۱-۶- اهداف تحقیق
اهدافی که برای اجرای این تحقیق درنظر گرفته شدهاست عبارتند از:
-
- مروری بر مدلهای مکانیابی تسهیلات به صورت کلّی
-
- مروری بر مدلهای مکانیابی تسهیلات با تقاضای تصادفی و تراکم
-
- بهینه نمودن استفاده از دستگاههایهای خدمترسان؛ یعنی دستگاههای خدمترسان به چه تعداد و در چه محلهایی استقرار یابند و چه مراکز تقاضایی به این دستگاه های خدمترسان تخصیص یابند، بهصورتی که هم رضایت مشتریان جلب شود (این هدف را به صورت کمینه کردن مجموع زمان خدمترسانی به مشتریان که شامل زمان سفر مشتریان از مراکز تقاضا به مراکز خدمترسانی و زمان انتظار آنها برای خدمترسانی درنظر گرفته ایم) و هم مجموع کارکرد دستگاهها بیشینه گردد.
-
- تطبیق الگوریتمهای مختلف با مسئله مورد بررسی
- تجزیه و تحلیل الگوریتمهای مختلف با بهره گرفتن از روش های مقایسه الگوریتمها
موضوعات: بدون موضوع
[پنجشنبه 1400-07-29] [ 04:44:00 ب.ظ ]