
نزدیکترین دستگاه خودپرداز خدمترسانی میشوند؛
9) میزان زمان انتظار مشتریان در صف نباید از یک حد ازپیش تعیین شده، فراتر رود؛
10) ماکزیمم تعداد دستگاههای خدمترسان از قبل تعریف شدهاست.
در مسائل مکانیابی تک هدفه، هدف مسأله معمولاً هزینه یا پوشش بودهاست، امّا در مسائل چندهدفه، حداقل یک هدف دیگر وجود دارد که باتوجه به طبیعت این گونه مسائل، با هدف اوّلی درتضاد است.
براین اساس، ما مروری بر روی اهدافی که در مسائل مکانیابی چندهدفه توسعه یافته میکنیم. این اهداف میتوانند به صورت زیر توصیف شوند:
1) هزینه: انواع مختلفی از هزینه وجود دارد. این انواع میتوانند به دو قسمت ثابت و متغیر تقسیم شوند. هزینههای ثابت شامل هزینه شروع و نصب به همراه سرمایه گذاری میباشد. هزینههای متغیر میتواند هزینه حمل و نقل، عملیات، تولید، خدمات، توزیع، تدارکات، دفع پسماند، نگهداری و محیطی باشد. هزینه حمل و نقل بیشترین و هزینه نصب بعد از آن قرار دارد. مسائل مختلفی از یک معیار «هزینه کل» استفاده کردهاند که شامل همه هزینهها تحت یک هدف میشود.
2) ریسکهای محیطی: این هدف شامل ریسک حمل و نقل، ریسک طبیعی، دفع پسماند یا ریسک رفتاری، یا «اثرات نامطلوب» عمومی است که جایگاه بزرگی دارد. به هر حال نسبت ریسک محیطی در مسائل مکانیابی کمتر از دیگر هزینههاست.
3) پوشش: تقریبا مجموعه کامل مسائل مکانیابی درباره پوشش مسافت، زمان، مبلغ و یا حتی انحراف پوشش است. اگرچه بسیاری از مسائل از مسافت و پوشش جمعیّت به عنوان هدفشان استفاده میکنند، اما در بعضی مسائل نیز زمان مهّم است.
مفهوم تساوی نیز در این طبقه قرار میگیرد، زیرا این نوع مسائل، روشی منصفانه در برخورد با مسأله پوشش دارند.
4) سطح و کارائی خدمت: در این طبقه، هدف سطح سرویس به همراه کارائی قرارمیگیرد.
5) سود: بعضی مسائل به سود خالص (تفاوت بین سودها و هزینهها) علاقمندند.
6) اهداف دیگر: بعضی اهداف دیگر که در مسائل مکانیابی استفاده میشوند، مانند دستیابی به منابع به همراه ریسکهای سیاسی و اجتماعی که نمیتوانند در دیگر دستهها قرار بگیرند.
سه هدف برای مسأله موردنظر ما درنظر گرفته شدهاست که هدف اول، مینیمم کردن متوسط تعداد مشتریان درحال سفر؛ هدف دوم، مینیمم کردن متوسط تعداد مشتریان در حال انتظار و هدف سوم، ماکزیمم کردن مجموع کارکرد دستگاهها در واحد زمان میباشد.
1-4- روش حل
به طور کلي مسائل مکانیابی تسهیلات اصولاً NP-Hardهستند و بعيد است بدون کاربرد الگوريتمهای فراابتکاری بتوان حلّي بهينه را در زمان معقول پيدا کرد و زمان محاسباتي نيز با توجه به اندازه مسأله به صورت نمايي افزايش مي يابد.
مسائل بهینه یابی چندهدفه، به طور کلی با یافتن حلهای بهینه پارتو یا حلهای مؤثّر کارمیکنند. چنین حلهایی غیرمغلوب هستند، یعنی هنگامیکه همه اهداف درنظر گرفته شوند، هیچ حل دیگری برتر از آنها نیست. بیشترین روشهایی که برای حل مسائل بهینه سازی چندهدفه به کار میروند، روشهای ابتکاری و فراابتکاری هستند.
براي مسائلی که در کلاس NP-Hard قرار مي گيرند، تاکنون روشهاي دقيقي که بتواند در حالت کلي و در زماني معقول به جواب دست يابد توسعه داده نشدهاست. از اين رو روشهاي ابتکاري و فراابتکاري مختلفي را براي حل اين دسته از مسائل به کار مي برند تا به جوابهاي بهينه يا نزديک به بهينه دست يابند.
در این تحقیق سعی شدهاست که از چندین الگوریتم بهینه سازی چندهدفه استفاده شود. الگوریتم 6NSGA-II به این خاطر انتخاب شدهاست که این الگوریتم در بسیاری از مقالات به عنوان الگوریتم مرجع مقایسه گردیدهاست. الگوریتم 7CNSGA-II نیز به این علت انتخاب شدهاست که روشی مناسب برای برخورد با محدودیتهای حل مسأله ارائه میکند. چون باتوجه به ماهیت مسأله، چندین محدودیت سر راه حل مسأله ایجاد شدهاست که راهکار مناسبی برای رسیدگی به این محدودیتها ایجاب میکند. الگوریتم 8NRGA نیز چون جزء جدیدترین الگوریتمهای ارائه شده در زمینه بهینه سازی چندهدفه میباشد مورداستفاده قرار گرفتهاست. در سالهای اخیر، الگوریتمهای بهینه سازی مبتنی بر ایمنی مصنوعی بسیار مورد توجه قرار گرفتهاست که به همین علت، ما در این تحقیق سعی بر آن داریم که از کارآمدترین این الگوریتمها استفاده کنیم. از میان الگوریتمهای چندهدفه ایمنی، ما از 9MISA، 10VIS و 11NNIA استفاده کرده ایم که در ادامه و در بخشهای بعدی به نتایج خوبی که دراثر استفاده از این الگوریتمها بدست میآید، اشاره میکنیم.
1-5- اهمیت و ضرورت تحقیق
امروزه پایانه فروش، پایانه شعب، دستگاههای خودپرداز و … نماد بانکداری الکترونیک است و یافتن مکان بهینه برای این پایانهها و دستگاهها میتواند نقش مهمی در حضور یک بانک یا مؤسسه در بازارهای داخلی و خارجی داشته باشد.
در این تحقیق سعی شدهاست که محدودیتها و چالشهای فراروی این مسأله در دنیای واقعی تا حد ممکن درنظر گرفته شود. به همین منظور محدودیتهایی ازقبیل ماکزیمم دستگاه خدمترسانی که میتواند به کار گرفته شود و حدّ بالای زمان انتظار برای مشتریان منظور شدهاست. همچنین بهدلیل اینکه یک هدف، پاسخگوی انگیزه ایجاد شده برای انجام این طرح نمیباشد، این مسأله به صورت یک مسأله چند هدفه درنظر گرفته شدهاست تا به دنیای واقعی هر چه نزدیکتر گردد تا در درجه اول سود بانک یا مؤسسه ازطریق انتخاب بهینه دستگاههای خودپرداز افزایش یابد و در درجه دوم رضایت مشتریان جلب گردد، به صورتی که هم پوشش مناسب برای خدمترسانی داده شود و هم مدت زمان خدمترسانی به مشتریان حداقل گردد.
1-6- اهداف تحقیق
اهدافی که برای اجرای این تحقیق درنظر گرفته شدهاست عبارتند از:
• مروری بر مدلهای مکانیابی تسهیلات به صورت کلّی
• مروری بر مدلهای مکانیابی تسهیلات با تقاضای تصادفی و تراکم
• بهینه نمودن استفاده از دستگاههایهای خدمترسان؛ یعنی دستگاههای خدمترسان به چه تعداد و در چه محلهایی استقرار یابند و چه مراکز تقاضایی به این دستگاههای خدمترسان تخصیص یابند، بهصورتی که هم رضایت مشتریان جلب شود (این هدف را به صورت کمینه کردن مجموع زمان خدمترسانی به مشتریان که شامل زمان سفر مشتریان از مراکز تقاضا به مراکز خدمترسانی و زمان انتظار آنها برای خدمترسانی درنظر گرفته ایم) و هم مجموع کارکرد دستگاهها بیشینه گردد.
• تطبیق الگوریتمهای مختلف با مسئله مورد بررسی
• تجزیه و تحلیل الگوریتمهای مختلف با استفاده از روشهای مقایسه الگوریتمها
1-7- جمع بندی
مسأله مکانیابی تسهیلات در حالت کلی به عنوان یک مسأله NP-Hard شناخته میشود. بهخصوص در حالتی که محدودیتهای دیگری نظیر محدودیت انتظار مشتریان در صف و محدودیت در تعداد تسهیلات باز شده نیز مطرح باشد، پیچیدگی این مسأله چندین برابر میشود.
هدف اول، مینیمم کردن متوسط تعداد مشتریان درحال سفر؛ هدف دوم، مینیمم کردن متوسط تعداد مشتریان در حال انتظار و هدف سوم، ماکزیمم کردن مجموع کارکرد دستگاهها در واحد زمان میباشد.
پایان نامه دارای ساختار زیر است: در فصل دوم برای آنکه خواننده با مفاهیمی که در این پایاننامه به کار گرفته شدهاست و همچنین موضوعاتی که در این تحقیق مطرح میشود، مروری جامع بر ادبیات موضوعات در بخشهای مختلف اعم از مکانیابی تسهیلات به صورت کلی، مکانیابی تسهیلات باتوجه به مسأله مطرح شده و محدودیتهای ایجاد شده به عمل آمدهاست. همچنین الگوریتمهای چندهدفهای که در این مقاله به کار گرفته شدهاست به طور عمومی معرفی و تشریح میشوند. باتوجه به اینکه سه الگوریتم از این الگوریتمها از مبحث ایمنی مصنوعی است، سعی شدهاست تا مروری مختصر بر این موضوع نیز انجام شود. در آخر نیز روشهاي اندازه گيري عملکرد الگوريتمهاي چندهدفه معرفی شدهاند.
در فصل سوم ابتدا درمورد مسئله مورد بررسی این تحقیق توضیحات کافی داده می شود و اهداف و محدودیت های فراروی آن شرح داده می شود. سپس، در قسمت طراحی الگوریتمها، الگوریتمهای درنظر گرفته شده را با مسئله مورد بررسی تطبیق می دهیم.
در فصل چهارم پس از اینکه درمورد تولید مسائل نمونه صحبت کردیم، به تجزیه و تحلیل و مقایسه الگوریتمها خواهیم پرداخت که این کار را به این صورت انجام میدهیم که ابتدا معیارهای مختلف را برای تمامی الگوریتمها اندازه گیری کرده و سپس این نتایج را باتوجه به روشهای موجود درزمینه تحلیل واریانس، مورد تجزیه و تحلیل قرارمیدهیم.
در فصل پنجم نیز پس از مروری کلّی بر تحقیقی که انجام شده، چند زمینه تحقیق برای مطالعات آتی به خوانندگان پیشنهاد میشود.
مرور ادبیات
2-1- مقدمه
در این فصل، ابتدا به بحث درباره موضوع مکانیابی تسهیلات می پردازیم. در ابتدا، به مروری بر ادبیات این موضوع می پردازیم. در ادامه، مسائل پوشش که مهمترین و پرکاربردترین مباحث در این حوزه است را توضیح داده و مدل های دیگر مکانیابی تسهیلات را معرفی می نمائیم. سپس باتوجه به اینکه مسئله ما در حیطه مسائل مکانیابی تسهیلات با تقاضای تصادفی و تراکم می باشد، به مرور ادبیات این حیطه و خصوصیات این نوع مدل ها می پردازیم. سپس سیستم صف و مسائلی که در این حوزه و ادامه تحقیق، موردنیاز است، شرح داده می شود. همچنین الگوریتمهای چندهدفهای که در این مقاله به کار گرفته شدهاست به طور عمومی معرفی و تشریح میشوند. باتوجه به اینکه سه الگوریتم از این الگوریتمها از مبحث ایمنی مصنوعی است، سعی شدهاست تا مروری مختصر بر این موضوع نیز انجام شود. در آخر نیز روشهاي اندازه گيري عملکرد الگوريتمهاي چندهدفه معرفی شدهاند.
2-2- مکانیابی تسهیلات
2-2-1- مرور ادبیات در موضوع مکانیابی تسهیلات [5]
میتوان استدلال نمود که تحلیلهای مکانیابی در قرن هفدهم و با مسأله پيِر دِ فِرمَت12 شروع شد: فرض کنید که سه نقطه در یک صفحه وجود دارد، نقطه چهارمی را پیداکنید به صورتی که مجموع فواصلش تا سه نقطه فرض شده مینیمم گردد. اِوانجليستا توريچلي13 نیز یکی از کسانی است که ساختارهای فضایی که نیاز به یافتن یک چنین میانههای فاصلهای یا «نقاط توریچلی» دارند، به آن نسبت داده شدهاست. به هر حال در قرن اخیر، با «مسأله وِبِر» از آلفرد وِبِر14 و بعضی از گسترشهای بعدی اش در مسئله درِزنر15 و همکارانش دوران جدید تحلیلهای مکانیابی با کاربردش در مکانیابی صنعتی شروع میشود. مسأله وِبِر نقاطی را در یک سطح پیدا میکند که مجموع فواصل اقلیدسی وزندهی شده آن تا یک مجموعه نقاط ثابت مینیمم گردد. این مسأله به این صورت تفسیر میشود که مکان یک کارخانه را به گونهای پیداکنیم که کل مسافت وزن دهی شده آن از تأمین کنندگان و مشتریان مینیمم گردد، که وزنها بیانگر حجم مبادلات میباشد، مثل وزن موادی که باید از یک تأمینکننده منتقل شود یا حجم محصولات نهایی که برای یک مشتری ارسال میشود.
تنها در دهه 60 و 70، با فراهم بودن گسترده قدرت محاسبات برای پردازش و تحلیل مقادیر بزرگی از دادهها بود که ما شروع واقعی بهینه سازی جدید و به همراه آن، تحقیق در مسائل مکانیابی را مشاهده میکنیم. این دوره را به این دلیل دوره بلوغ تحلیلهای مکانیابی مینامند که گرایش زیادی به مطالعه p-median کلاسیک، p-center، پوشش مجموعه، مکانیابی تأسیسات ساده و مسائل تخصیص درجه دوم و گسترش آنها پیدا شد.
در این دوره، کوپر16 مسأله تک تسهیلی وِبِر را گسترش داد تا مسأله تخصیص-مکانیابی چندتسهیلی را ایجاد کند. سپس مارانزانا17 این مسأله را از فضای پیوسته به شبکه گسترش داد. به هر حال حکيمي18 است که شالوده تحقیق در p-median و مسائل دیگر در یک شبکه را کامل میکند. مسأله p-median شبیه مسأله وِبِر در یک سطح، مکان p نقطه را در یک شبکه به گونهای پیدا میکند که کل مسافت وزن دهی شده با تقاضا را تا نزدیکترین تسهیل مینیمم میکند. به علاوه حکيمي مسأل
