2-4- مسائل بهینه سازی چندهدفه40
2-4-1- فرمول بندی مسائل بهینه سازی چندهدفه40
2-4-2- الگوریتم‌های تکاملی برای بهینه سازی مسائل چندهدفه بر مبنای الگوریتم ژنتیک41
2-4-2-1- الگوریتم ژنتیک مرتب سازی نامغلوب42
2-4-2-2- الگوریتم NSGA-II محدود شده45
2-4-2-3- الگوریتم ژنتیک رتبه بندی نامغلوب46
2-4-3- الگوریتم‌های تکاملی برای بهینه سازی مسائل چندهدفه بر مبنای سیستم ایمنی مصنوعی49

2-4-3-1- سیستم ایمنی مصنوعی49
2-4-3-1-1- مفاهیم ایمنی49
2-4-3-1-2- ایمنی ذاتی51
2-4-3-1-3- ایمنی اکتسابی51
2-4-3-1-4- تئوری شبکه ایمنی52
2-4-3-1-5- الگوریتم ایمنی مصنوعی53
2-4-3-1-6- سیستم ایمنی مصنوعی و مسائل بهینه سازی چندهدفه54
2-4-3-2- الگوریتم MISA56
2-4-3-3- الگوریتم VIS61
2-4-3-4- الگوریتم NNIA64
2-5- روش‌های اندازه گیری عملکرد الگوریتم‌های چندهدفه67
2-5-1- فاصله نسلی68
2-5-2- درجه توازن در رسیدن همزمان به اهداف69
2-5-3- مساحت زیر خط رگرسیون70
2-5-4- تعداد جواب‌های غیرمغلوب نهائی71
2-5-5- فاصله گذاری71
2-5-6- گسترش72
2-5-7- سرعت همگرائی73
2-5-8- منطقه زیر پوشش دو مجموعه73
2-6- جمع بندی74
فصل سوم: مدل سازی مسأله و توسعه الگوریتم‌ها76
3-1- مسأله موردتحقیق77
3-2- طراحی الگوریتم‌ها81
3-2-1- تطبیق الگوریتم‌ها با مسئله موردبررسی81
3-2-1-1- ساختار حل‌ها81
3-2-1-2- معیار توقف82
3-2-2- تطبیق الگوریتم NSGA-II برای مسئله موردبررسی83
3-2-3- تطبیق الگوریتم CNSGA-II برای مسئله موردبررسی84
3-2-4- تطبیق الگوریتم NRGA برای مسئله موردبررسی85
3-2-5- تطبیق الگوریتم MISA برای مسئله موردبررسی85
3-2-6- تطبیق الگوریتم VIS برای مسئله موردبررسی85
3-2-7- تطبیق الگوریتم NNIA برای مسئله موردبررسی86
فصل چهارم: تجزیه و تحلیل داده‌ها87
4-1- تولید مسأله نمونه88
4-2- اندازه گیری عملکرد الگوریتم‌ها براساس معیارها89
4-3- تجزیه و تحلیل نتایج92
فصل پنجم: نتیجه گیری و مطالعات آتی100
5-1- نتیجه گیری101
5-2- مطالعات آتی102
فهرست منابع و مراجع103
پیوست الف: محاسبه معیارهای هشت گانه برای الگوریتم های استفاده شده105
پیوست ب: نمودارهای بدست آمده از تجزیه و تحلیل نتایج113
پیوست ج: یک نمونه مسئله حل شده توسط الگوریتم NSGA-II118
پیوست د: کد برنامه نویسی الگوریتم NSGA-II در محیط MATLAB123

فهرست اشکال
شکل 2-1- مدل پایه‌ای صف36
شکل 2-2- مجموعه حل‌های غیرمغلوب41
شکل 2-3- نمایشی از نحوه عملکرد NSGA-II43
شکل2-4- الگوریتم NRGA47
شکل 2-5- سلول B، آنتی ژن، آنتی بادی، اپیتوپ، پاراتوپ و ادیوتوپ50
شکل 2-6- فلوچارت الگوریتم MISA57
شکل 2-7- یک شبکه تطبیقی برای رسیدگی به حافظه ثانویه60
شکل 2-8- فلوچارت الگوریتم VIS62
شکل 2-9- تکامل جمعیت NNIA65
شکل 2-10- نمایش حل‌های مناسب69
شکل 2-11- مساحت زیر خط رگرسیون70
شکل 2-12- بیشترین گسترش73
شکل 3-1- مکانیسم عملگر تقاطع83
شکل 4-1- نمودار همگرایی الگوریتم‌ها براساس شاخص MID90
شکل 4-2- نتیجه بدست آمده از آنالیز واریانس برای معیار تعداد جواب‌های غیرمغلوب94
شکل 4-3- نتیجه بدست آمده از آزمون توکی برای معیار تعداد جواب‌های غیرمغلوب95
شکل 4-4- نتیجه به دست آمده از آنالیز واریانس برای تعداد جواب‌های غیرمغلوب97

فهرست جداول
جدول 4-1- مشخصات هر نمونه88
جدول 4-2- گروه بندی الگوریتم‌ها براساس معیار تعداد جواب‌های غیرمغلوب96
جدول 4-3- مقایسه الگوریتم‌ها ازنظر معیارهای مختلف و در حالت‌های گوناگون98
جدول 4-4- متوسط معیارهای الگوریتم‌ها و رتبه بندی الگوریتم‌ها براساس آن99

تعریف مسأله

1-1- مقدمه
با رشد روز افزون معاملات تجاری در سطح جهان و در سال‌های اخیر، ظهور پدیده تجارت الکترونیک3 و بانکداری الکترونیک4 به عنوان بخش تفکیک ناپذیر از تجارت الکترونیک مطرح شد. بانکداری الکترونیک اوج استفاده از فناوری انفورماتیک و ارتباطات و اطلاعات برای حذف دو قید زمان و مکان از خدمات بانکی است. ضرورت یک نظام بانکی کارامد برای حضور در بازارهای داخلی و خارجی ایجاب می‌کند تا بانکداری الکترونیک نه به عنوان یک انتخاب، بلکه ضرورت مطرح شود. امروزه پایانه فروش، پایانه شعب، دستگاه‌های خودپرداز و … نماد بانکداری الکترونیک است و یافتن مکان بهینه برای این پایانه‌ها و دستگاه‌ها می‌تواند نقش مهمی در حضور یک بانک یا مؤسسه در بازارهای داخلی و خارجی داشته باشد [1].
1-2- مکانیابی تسهیلات5
فرض کنید که یک شرکت رسانه‌ای می‌خواهد که ایستگاه‌های روزنامه را در یک شهر ایجاد کند. این شرکت در حال حاضر جایگاه‌هایی را به صورت بالقوه در شهرهای همسایه اش مشخص کرده‌است و هزینه ایجاد و نگهداری یک جایگاه را می‌داند. همچنین فرض کنید که تقاضای روزنامه در هر شهر همسایه مشخص است. اگر این شرکت بخواهد تعدادی از این ایستگاه‌ها را ایجاد کند، باتوجه به مینیمم کردن کل هزینه‌های ایجاد و نگهداری این ایستگاه‌ها و همچنین متوسط مسافت سفر مشتریان، این ایستگاه‌ها در کجا باید واقع شوند؟
سؤال قبل یک مثال از مسأله مکانیابی تسهیلات بود. مکانیابی تسهیلات یعنی اینکه مجموعه‌ای از تسهیلات (منابع) را به صورت فیزیکی به گونه‌ای در یک مکان قراردهیم که مجموع هزینه برآورده کردن نیازها (مشتریان) باتوجه به محدودیت‌هایی که سر راه این مکانیابی قرار دارد، مینیمم گردد.
از سالهای 1960 به این طرف مسائل مکانیابی یک جایگاه ویژه‌ای را در حیطه تحقیق در عملیات اشغال کرده‌اند. آنها وضعیت‌های مختلفی را درنظر گرفته‌اند که می‌توان به موارد ذیل اشاره کرد: تصمیم گیری در مورد مکان کارخانجات، انبارها، ایستگاه‌های آتش نشانی و بیمارستان‌ها.
به طور اساسی، یک مسأله مکانیابی بوسیله چهار عنصر زیر توصیف می‌شود:
* مجموعه‌ای از مکانها که در آن‌ها، تسهیلات ممکن است ایجاد یا باز شوند. برای هر مکان نیز بعضی اطلاعات درمورد هزینه ساخت یا باز نمودن یک تسهیل در آن مکان مشخص می‌شود.
* مجموعه‌ای از نقاط تقاضا (مشتریان) که برای سرویس دهی به بعضی از تسهیلات اختصاص داده شوند. برای هر مشتری، اگر بوسیله یک تسهیل معینی خدمت‌رسانی شود، بعضی اطلاعات راجع به تقاضایش و درمورد هزینه یا سودش بدست می‌آید.
* لیستی از احتیاجات که باید بوسیله تسهیلات بازشده و بوسیله تخصیص نقاط تقاضا به تسهیلات برآورده شود.
* تابعی از هزینه یا سودهایی که به هر مجموعه از تسهیلات اختصاص پیدا می‌کند.
پس هدف این نوع مسائل، پیدا کردن مجموعه‌ای از تسهیلات است که باید باتوجه به بهینه کردن تابع مشخصی باز شوند.
مدل‌های مکانیابی در یک زمینه گسترده از کاربردها استفاده می‌شود. بعضی از این موارد شامل موارد ذیل است: مکانیابی انبار در زنجیره تأمین برای مینیمم کردن متوسط زمان فاصله تا بازار؛ مکانیابی سایت‌های مواد خطرناک برای مینیمم کردن درمعرض عموم قرار گرفتن؛ مکانیابی ایستگاه‌های راه آهن برای مینیمم کردن تغییرپذیری زمان بندی‌های تحویل بار؛ مکانیابی دستگاه‌های خودپرداز برای بهترین سرویس دهی به مشتریان بانک و مکانیابی ایستگاه‌های عملیات تجسس و نجات ساحلی برای مینیمم کردن ماکزیمم زمان پاسخ به حادثه‌های ناوگان دریایی. با اینکه این پنج مسأله توابع هدف مختلفی دارند، همه این مسائل در حوزه مکانیابی تسهیلات واقع می‌شوند. درواقع، مدل‌های مکان‌یابی تسهیلات می‌توانند در موارد ذیل متفاوت باشند: توابع هدفشان، معیارهای فاصله‌ای که به کار می‌برند، تعداد و اندازه تسهیلاتی که قرار است مکانیابی شوند و چندین معیار تصمیم گیری مختلف دیگر. بسته به کاربرد خاص هر مسأله، درنظرگرفتن این معیارهای مختلف در فرموله کردن مسأله، منتهی به مدل‌های مکانیابی بسیار متفاوتی خواهدشد.
1-3- بیان مسأله
هدف از اجرای این تحقیق، مکان‌یابی سیستم‌های خدمات رسانی ثابت با ظرفیت خدمت محدود می‌باشد. یعنی دستگاه‌های خدمت‌رسان به چه تعداد و در چه محل‌هایی استقرار یابند و چه مراکز تقاضایی به این دستگاههای خدمت‌رسان تخصیص یابند. در چنین سیستم‌هایی، زمانی که برای انجام سرویس موردنیاز است تصادفی است و همچنین تقاضای انجام خدمت در نقاط تصادفی از زمان می‌رسند که این تقاضا از جمعیت بزرگی از مشتریان سرچشمه می‌گیرد و معمولاً این سرویس‌دهی در نزدیک ترین تسهیل انجام می‌شود. چنین سیستم‌های خدمت‌رسانی، سیستم‌های صف را تشکیل می‌دهند. مدل‌های مختلفی برای حل این مسائل مکان‌یابی سیستم صف ارائه شده‌است.
دو ناحیه کاربردی وجود دارد که ما با این مدل‌ها روبه رو می‌شویم [4]: اولی در طراحی سیستم ارتباط کامپیوتری مانند اینترنت می‌باشد. در یک سیستم ارتباط کامپیوتری، ترمینال‌های مشتری (کاربران اینترنت) به کامپیوترهای میزبان (سرورهای پروکسی، سرورهای آینه) وصل می‌شوند که قابلیت پردازش بالا و/یا پایگاه داده‌های بزرگ میزبان دارند. زمانی که طول می‌کشد تا سرور درخواست را پردازش کند بستگی به سرعت پردازش سرور و و نوع درخواست دارد که آن هم تصادفی است. زمانی که مشتری برای پاسخ سرور منتظر می‌ماند نیز بستگی به تعداد و اندازه درخواست‌های داده‌ای است که در حال حاضر در صف هستند. به طور کلی، درخواست‌های مشتری‌ها به نزدیکترین سرور وصل می‌شود. این مکان و ظرفیت سرورها، پارامترهای طراحی بحرانی هستند. این انتخاب پارامترها تأثیری قابل توجه روی کیفیت خدمات دارد، به طوری که بوسیله یک مشتری درک می‌شود.
کاربرد دوم شامل طراحی یک سیستم دستگاه خودپرداز برای بانک است. مشتری‌ها به صورت تصادفی به یک دستگاه خودپرداز می‌رسند. اگر هنگامی‌که آن‌ها می‌رسند، دستگاه آزاد باشد، آن‌ها بلافاصله سرویس دهی می‌شوند. در غیر این صورت ، آن‌ها به صف می‌پیوندند یا آن جا را ترک می‌کنند. زمان تصادفی که یک مشتری در یک دستگاه سپری می‌کند بستگی به تعداد و نوع تراکنشی (مثلاً مانده حساب، دریافت وجه، انتقال وجه و غیره) دارد که او انجام می‌دهد. منبع قابل توجه دیگر زمان مشتری در یک دستگاه، شامل تأخیر ارسال در مدت شبکه ارتباط بانک است. از آن جا که دستگاه‌ها ثابت هستند، مشتری‌ها باید به یک مکان خودپرداز مراجعه کنند تا یک تراکنش را انجام دهند. گاهی اوقات، مردم در طول مسیر خود (مثلاً از خانه به محل کار) برای استفاده از یک دستگاه خودپرداز به آن مراجعه می‌کنند؛ گاهی اوقات هم، آن‌ها آن را طبق یک مسیر از پیش برنامه‌ریزی‌شده (مثلاً مسیر روزانه بین خانه و کار) استفاده می‌کنند. به طور کلی، آن‌ها از تسهیل با کمترین هزینه قابل‌دسترس استفاده می‌کنند. برای مثال، هنگامی‌که هزینه‌ها بوسیله مسافت سفر تعیین می‌شود، مشتری‌ها نزدیکترین تسهیل به محل کار/خانه یا نزدیکترین مسیر روزانه شان را انتخاب می‌کنند. ما فرض می‌کنیم که مشتری‌ها هیچ اطلاعی از تأخیرات دستگاه‌های خودپرداز ندارند و از این رو نزدیکترین تسهیل را برای درخواست سرویسشان انتخاب می‌کنند.
فرضیاتی که برای این مسأله درنظر گرفته می‌شود به شرح زیر می‌باشد:
1) گره مشتری وجود دارد که هر یک درخواستی را برای سرویس ایجادمی‌کند؛
2) تعداد درخواست‌ها در واحد زمان، یک جریان پوآسن مستقل را تشکیل می‌دهند؛
3) گره خدمت‌رسان بالقوه وجود دارد؛
4) مشتریان از مراکز تقاضا به سمت مکان این دستگاه‌ها حرکت می‌کنند؛
5) هر جایگاه خدمت فقط یک خدمت دهنده دارد؛
6) زمان سرویس یک دستگاه به صورت تصادفی و توزیع نمایی دارد؛
7) مکان دستگاه‌ها ثابت هستند؛
8) مشتری‌ها بوسیله نزدیکترین دستگاه خودپرداز خدمت‌رسانی می‌شوند؛
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 نقطه را در یک شبکه به گونه‌ای پیدا می‌کند که کل مسافت وزن دهی شده با تقاضا را تا نزدیکترین تسهیل مینیمم می‌کند. به علاوه حکیمی مسأله p-center اصلی را ارائه می‌کند که مکان p نقطه را در یک شبکه به گونه‌ای پیدا می‌کند که ماکزیمم مسافت تقاضا تا نزدیکترین تسهیل مینیمم گردد. نتیجه مهم قضیه حکیمی نیز مشخص است، یعنی اینکه یک حل در مسأله p-median، همیشه در گره‌های یک شبکه در مسأله واقع می‌شود، درحالیکه یک حل در مسأله p-center لزومی ندارد که در گره‌ها واقع شود. کاریف19 و حکیمی اثبات می‌کنند که مسائل p-center و p-median، NP-Hard هستند.
مدلهای پوشش، مسائلی را درنظر می‌گیرند که تقاضاها باید در یک مسافت مطمئنی از زمان سفر پوشش داده شوند. تورِگاس20 و همکارانش روش حلی را برای اینگونه مسائل که در کاربرد با نام مسأله پوشش مجموعه (LSCP)21 شناخته می‌شود را فرمول بندی و ارائه کردند. مکان تسهیلات برای خدمات اورژانسی از این مسأله الهام می‌شوند. چِرچ و رِوِله22، مسأله مکانیابی حداکثر پوشش (MCLP)23 را ارائه کردند. این مسأله، مکانهای بهینه‌ای را برای تعداد معیّنی از تسهیلات پیدا می‌کند که جمعیّتی که درون یک فاصله خدمت‌رسانی مشخص، پوشش داده می‌شوند، حداکثر گردد.
دیگر مسأله بنیادی با مفهوم پوشش، مسأله تخصیص درجه دوم (QAP)24 می‌باشد که به دلیل طبیعت درجه دوّم فرموله کردن تابع هدفش به این نام خوانده می‌شود. تعدادی (N) تسهیل که در همان تعداد جایگاه (N) به گونه‌ای واقع می‌شوند که کل هزینه انتقال مواد درمیان آنها مینیمم گردد. هزینه حرکت مواد بین هر دو مکان بوسیله ضرب یک وزن یا جریان در فاصله بین مکان‌ها بدست می‌آید. مدل خطی آن بوسیله کوپمنس و بِکمن25 ارائه شد که مورد خاصی از مسأله حمل و نقل شناخته شده‌است. این مسأله NP-Hard علائق بسیاری را برای تحقیق ایجاد کرد و هنوز هم حل آن در هر اندازه ای، بسیار سخت به نظر می‌رسد.
دهه 80 و 90 تحقیقاتی را در تحلیل مکانیابی دید که به رشته‌های دیگر نیز گسترش پیدا کرد و نتایج سودمندی را از دیدگاه مدل سازی و کاربرد بدست آورد. این نوآوری‌ها تا به امروز نیز ادامه دارد.
از جمله این مدل‌ها می‌توان به مکان‌یابی رقابتی، مکان تسهیلات گسترده، مکانیابی تصادفی، مسیریابی، مکان‌یابی هاب26 و جلوگیری از جریان اشاره کرد. به عنوان کاربردهای جدید در این دوران می‌توان به ناحیه‌هایی ازجمله برنامه ریزی خدمات اورژانسی، کاربردهای محیط زیستی همچون تسهیلات زیان آور و ترکیب مکانیابی با مدیریت زنجیره تأمین اشاره کرد.

در این سایت فقط تکه هایی از این مطلب با شماره بندی انتهای صفحه درج می شود که ممکن است هنگام انتقال از فایل ورد به داخل سایت کلمات به هم بریزد یا شکل ها درج نشود

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

ولی برای دانلود فایل اصلی با فرمت ورد حاوی تمامی قسمت ها با منابع کامل

اینجا کلیک کنید

مدلهای مکانیابی رقابتی: حکیمی مدلهای رقابتی را درون تئوری مکانیابی وارد کرد. بیشتر نتایج در این زمینه یک فضای گسسته یا یک شبکه را درنظر می‌گیرند. اخیراً مدل‌های مکانیابی رقابتی پیوسته توسط داسکی و لاپورته27 ارائه شده‌است.
مدلهای مکانیابی تسهیلات گسترده: یک تسهیل اگر در مقایسه با محیطش، خیلی کوچکتر از یک نقطه به نظر برسد، گسترده نامیده می‌شود. چنین مدل‌هایی بارها در وضعیت‌های طراحی شبکه به کار گرفته شده‌است. مِسا و بوفی28 یک سیستم دسته بندی شامل مسائلی برای تعیین خط مسیر حمل و نقل مواد خطرناک ارائه کردند. اخیراً یک مثال بوسیله بریمبرگ29 و همکارانش آورده شده‌است که مسأله مکانیابی یک دایره درون یک کره را درنظر می‌گیرد، به صورتی که فاصله از تسهیلات موجود باید مینیمم گردد.
مکانیابی تصادفی: مدلهای مکانیابی تصادفی هنگامی رخ می‌دهند که داده‌های مسأله فقط به روشی احتمالی شناخته شوند. بِرمن30 و همکارانش مسائلی را درنظر گرفتند که ورود به تسهیلات به صورت تصادفی است و اثر تراکم نیز باید درنظر گرفته می‌شد. لوگندران و تِرِل31 یک مسأله LA با ظرفیت نامحدود را با تقاضاهای تصادفی حسّاس به قیمت درنظر گرفتند. بِرمن و کراس32 یک کلاس کلی از “مسائل مکانیابی با تقاضای تصادفی و تراکم” را ارائه کردند.
مسیریابی مکان: ترکیب تحلیلهای مکانیابی با زمینه‌های شناخته شده مسائل مسیریابی وسایل نقلیه، ناحیه جدید دیگری از مدل سازی، یعنی مسیریابی مکان را ایجاد می‌کند.
مکانیابی هاب: در چنین مسائل مکانیابی، هاب‌ها به عنوان متمرکزکننده‌ها یا نقاط سوئیچینگ33 ترافیک عمل می‌کنند، خواه برای مسافران خطوط هوایی باشد، خواه بسته‌های کوچک در سیستمهای سوئیچینگ. جریان بین منابع و مقاصد اساس مدل سازی این دسته از مسائل را تشکیل می‌دهد. اُکِلی34 اساس تحلیلهای مکانیابی هاب را بنانهاد. آن مدل‌ها به صورتی مدل سازی شد تا بهترین مکان‌ها برای متصل کردن ترمینال‌ها را باتوجه به مینیمم کردن هزینه‌های کل تراکنش‌ها، پیدا کند.
جلوگیری از جریان: در بسیاری از مسائل مکانیابی، تقاضاها فرض می‌شوند که در گره‌های یک شبکه رخ می‌دهند. یک تغییر جالب که بوسیله مسائل فرض می‌شود این است که تقاضا بوسیله جریانی از وسایل نقلیه یا پیاده‌هایی که از میان اتصالات شبکه عبور می‌کنند، ارائه می‌شوند. ازجمله کاربردهای این حیطه می‌توان به دستگاه‌های خودپرداز و ایستگاه‌های نفتی اشاره کرد. چنین مسائلی اولین بار توسط هاچسون35 و بِرمن و همکارانش ارائه شد.
مکانیابی یا جابجایی وسایل خدمات اورژانسی: مقدار شگرفی از تحقیقات در مطالعه مکانیابی وسایل خدمات اورژانسی ایجاد شده‌است. چَپمن و وایت36 اولین کار را برحسب محدودیت‌های کاربردی که در LSCP کاربرد دارد، ارائه کردند. مطالعه میرچندانی و اُدُنی37 زمان‌های سفر تصادفی را در مکانیابی تسهیلات اورژانس درنظر می‌گیرد. همچنین باتوجه به کاربردهای وسایل اورژانسی، مدل 38MEXCLP که توسط داسکین39 ارائه شده‌است، مدل MCLP را با محدودیت‌های احتمالی گسترش می‌دهد. رِپِده و برناردو40، مدل TIMEXCLP را ارائه کردند که MEXCLP را با تغییر تصادفی در تقاضا گسترش می‌دهد.
کاربردهای مرتبط با محیط زیست: تسهیلات زیان آور و مفاهیم دیگر: بعضی از تحلیلهای مکانیابی در موضوع محیط زیست، مربوط به مکان تسهیلاتی می‌شود که برای جمعیت مجاورشان مضر یا نامطبوع هستند. گُلدمن و دیِرینگ41 و همچنین چِرچ و گارفینکل42 جزء اولین افرادی بودند که مکانیابی برای تسهیلات زیان آور یا تسهیلاتی که ترجیح می‌دهیم دور از دسترس باشند را درنظر گرفتند.
تحلیلهای مکانیابی با مدیریت زنجیره تأمین: مدیریت زنجیره تأمین (SCM43) شامل تصمیمات درمورد تعداد و مکان تسهیلات و جریان شبکه در حیطه تأمین، تولید و توزیع می‌شود. در اولین کارها در برنامه ریزی پویا، بالُو44 از برنامه نویسی پویا برای جابجایی انبارها در طول دوره برنامه‌ریزی استفاده می‌کند. جئوفریون و پاورز45 محیطی یکپارچه را بین مکان و SCM درنظر می‌گیرد.
2-2-2- معیارهای دسته بندی مدلهای مکانیابی
مدلهای مکانیابی تسهیلات می‌توانند باتوجه به اهداف، محدودیتها، حل‌ها و دیگر خصوصیات دسته بندی شوند. در زیر، هشت معیار رایجی که برای دسته بندی مدل‌های مکانیابی تسهیلات سنتی استفاده می شود، آورده شده‌است ‍‍[6]:
1) مشخصات مکان: مشخصات مکان تسهیلات و جایگاه‌های تقاضا شامل مدل‌های مکانیابی پیوسته، مدل‌های شبکه گسسته، مدل‌های اتصال هاب و غیره می‌شود. در هر یک از این مدل‌ها، تسهیلات می‌توانند فقط در جایگاه‌هایی واقع شوند که توسط شرایط مکانی مجاز هستند.
2) اهداف: هدف یکی از معیارهای مهم برای دسته بندی مدل‌های مکانیابی است. هدف مدل‌های پوشش، مینیمم کردن تعداد تسهیلات برای پوشش همه نقاط تقاضا یا ماکزیمم کردن تعداد تسهیلاتی است که باید پوشش داده شوند. هدف مدل‌های p-center مینیمم کردن ماکزیمم فاصله (یا زمان سفر) بین نقاط تقاضا و تسهیلات است. آن‌ها اغلب برای بهینه کردن تسهیلات در بخش‌های عمومی همچون بیمارستان‌ها، اداره‌های پست و آتش‌نشانی‌ها استفاده می‌شوند. مدل‌های p-median سعی می‌کنند که جمع فاصله (یا متوسط فاصله) بین نقاط تقاضا و نزدیکترین تسهیلشان مینیمم گردد. شرکت‌هادر بخش‌های عمومی اغلب از مدل‌های p-median استفاده می‌کنند تا برنامه توزیع تسهیل را به گونه‌ای بریزند که مزایای رقابتشان را بهبود دهند.
3) روش‌های حل: روش‌های حل مختلف در مدل‌های مکانیابی مختلف همچون مدل‌های بهینه‌سازی و مدل‌های توصیفی بدست می‌آیند. مدل‌های توصیفی از رویکردهای ریاضی همچون برنامه نویسی ریاضی یا برنامه نویسی عددی استفاده می‌کنند تا حل‌های مختلف را برای سبک و سنگین کردن اکثر اهداف مهم در مقابل یکدیگر جستجو کنند. در مقابل، مدل‌های توصیفی، از شبیه سازی یا رویکردهای دیگری استفاده می‌کنند تا موفقیت دستیابی به الگوی مکانیابی را افزایش دهند تا حلی با درجه مطلوب بدست آید. روش‌های حل ترکیبی نیز بوسیله گسترش مدلهای توصیفی با تکنیک‌های بهینه سازی توسعه داده شده‌است تا مسائل مکانیابی تعاملی یا پویا (مثل سرورهای متحرک) را بسازند.
4) مشخصات تسهیلات: مشخصات تسهیلات نیز مدل‌های مکانیابی را به انواع مختلف تقسیم می‌کند. مثلاً، محدودیت تسهیل می‌تواند منجر به مدلی با یا بدون ظرفیت خدمت‌رسانی شود، و تکیه تسهیلات به یکدیگر می‌تواند به مدل‌هایی منجر شود که همکاری تسهیلات را به حساب آورند یا نیاورند.
5) الگوی تقاضا: همچنین مدل‌های مکانیابی می‌توانند براساس الگوهای تقاضا دسته بندی شوند. اگر یک مدل تقاضای انعطاف پذیر داشته باشد، پس آن تقاضا محیطی متفاوت با تصمیمات مکانیابی تسهیلات مختلف خواهد داشت؛ درحالیکه یک مدل با تقاضای غیرانعطاف پذیر، به علت تصمیمات مکانیابی تسهیلات، با آن الگوی تقاضا متفاوت نخواهد بود.
6) نوع زنجیره تأمین: مدل‌های مکانیابی می‌تواند بوسیله نوع زنجیره تأمینی که درنظر می‌گیرند تقسیم شوند (یعنی مدلهای تک مرحله‌ای درمقابل مدل‌های چند مرحله ای). مدل‌های تک‌مرحله‌ای بر روی سیستمهای توزیع خدمت تنها با یک مرحله تمرکز می‌کنند، درحالیکه مدل‌های چندمرحله ای، جریان خدمات را در طول چند سطح سلسله مراتبی درنظر می‌گیرند.
7) افق زمانی: افق زمانی، مدل‌های مکانیابی را به مدل‌های استاتیک و پویا دسته بندی می‌کند. مدل‌های استاتیک، کارایی سیستم را با درنظر گرفتن همزمان همه متغیرها بهینه می‌کند. درمقابل، مدل‌های پویا، دوره‌های زمانی مختلف را با تغییر داده‌ها درطول این دوره‌ها درنظر می‌گیرند و حل‌هایی را برای هر دوره زمانی با وفق دادن با شرایط مختلف ارائه می‌کند.
8) پارامترهای ورودی: روش دیگری برای دسته بندی مدل‌های مکانیابی براساس خصوصیت پارامترهای ورودی به مسأله است. در مدلهای قطعی، پارامترها با مقادیر مشخص پیش بینی می‌شوند و بنابراین، این مسأله، برای حل‌های ساده و سریع، ساده سازی می‌شود. به هر حال، برای بیشتر مسائل جهان واقعی، پارامترهای ورودی ناشناخته هستند و طبیعتاً ماهیت احتمالی/تصادفی دارند. مدل‌های مکانیابی احتمالی/تصادفی برای رسیدگی به ماهیت پیچیده مسائل جهان واقعی از توزیع احتمالی متغیرهای تصادقی استفاده می‌کنند یا مجموعه‌ای از طرحهای ممکن را برای پارامترهای نامعیّن درنظر می‌گیرند.
همچنین مدل‌های مکانیابی می‌توانند براساس مشخصات دیگری همچون مدل‌های تک محصولی درمقابل مدلهای چندمحصولی و یا مدلهای کششی درمقابل مدلهای فشاری متمایز شوند.
2-2-3- مسائل پوشش
ایده اصلی پشت مدلهای پوشش مکانیابی تسهیلات به گونه‌ای است که بعضی خدمات موردنیاز مشتریان فراهم شود. دو هدف برای مکانیابی تسهیلات وجود دارد که آیا همه مشتریان در شبکه با حداقل تسهیلات پوشش داده می‌شوند یا هر تعدادی از مشتریان که ممکن است با تعداد مشخصی از تسهیلات پوشش داده شوند. در اینجا به مسائل پوشش در شبکه می‌پردازیم [7]،[8].
2-2-3-1-مسأله پوشش مجموعه46
برای ساده سازی، فرض می‌کنیم که همه مشتریان و تسهیلات در گره‌های شبکه واقع می‌شوند. در ادامه، ما از اندیس i برای اشاره به مشتریان و از اندیس j برای اشاره به تسهیلات استفاده می‌کنیم. همچنین تقاضاها (یا وزن‌ها) در گره i را با و تعداد تسهیلاتی است که باید مکانیابی شوند را با p نمایش می‌دهیم. همچنین ما را به عنوان کوتاهترین مسیر (یا زمان، هزینه یا هر عدم مطلوبیت دیگری) بین گره تقاضای و جایگاه تسهیل در گره تعیین می‌کنیم. اگر گره i بتواند بوسیله تسهیل در مکان j پوشش داده شود، قرارمی‌دهیم، درغیر اینصورت . همچنین را مجموعه همه جایگاه‌های کاندیدشده‌ای قرار می‌دهیم که می‌توانند گره تقاضای i را پوشش دهند. اینکه p تسهیل در کجا واقع شوند و کدام تسهیل باید کدام گره تقاضا را سرویس دهد، تصمیمات کلیدی در اینگونه مسائل هستند.
مسائل پوشش مجموعه در ابتدای دهه 70 ایجاد شد. هدف LSCP مکانیابی حداقل تعداد تسهیلات به گونه‌ای است که هر گره تقاضا بوسیله یک یا چند تسهیل “پوشش” داده شود. به طور کلی، تقاضا در یک گره i توسط تسهیل j پوشش داده شده نامیده می‌شود اگر فاصله (یا زمان سفر) بین گره‌ها کمتر از فاصله بحرانی D باشد. به علاوه، D به ماکزیمم فاصله یا زمان خدمتی که تصمیم‌گیرنده مشخص می‌کند اشاره می‌کند.
با این توضیحات، می‌توان مدل مکان پوشش مجموعه را که اولین بار توسط تورِگاس و همکارانش ارائه شد، به صورت زیر فرموله کرد:

دسته بندی : پایان نامه ها

پاسخ دهید