دانلود فایل پایان نامه : پایان نامه ارشد رشته صنایع: بهینه سازی چندهدفی مدل جانمایی تسهیلات با سرویس دهندگان ثابت و تقاضای تصادفی مشتریان با استفاده از الگوریتم های فراابتکاری

!–more–

وزارت علوم، تحقیقات و فناوری

دانشگاه علوم و فنون مازندران

پایان نامه مقطع کارشناسی ارشد

رشته مهندسی صنایع- صنایع

عنوان:

بهینه سازی چندهدفی مدل جانمایی تسهیلات با سرویس دهندگان ثابت و تقاضای تصادفی مشتریان، با بهره گیری از الگوریتم های فراابتکاری

استاد راهنما:

دکتر مصطفی زندیه

استاد مشاور:

دکتر نیکبخش جوادیان

برای رعایت حریم خصوصی نام نگارنده درج نمی گردد

تکه هایی از متن به عنوان نمونه :

فهرست مطالب:

فصل اول: تعریف مسأله………………………………………………………………………………………….. 1

1-1- مقدمه…………………………………………………………………………………………………………. 2

1-2- مکانیابی تسهیلات…………………………………………………………………………………………. 2

1-3- اظهار مسأله……………………………………………………………………………………………………. 4

1-4- روش حل……………………………………………………………………………………………………. 7

1-5- اهمیت و ضرورت پژوهش………………………………………………………………………………… 8

1-6- اهداف پژوهش……………………………………………………………………………………………….. 9

1-7- جمع بندی…………………………………………………………………………………………………… 9

فصل دوم: مرور ادبیات  …………………………………………………………………………………….. 11

2-1- مقدمه……………………………………………………………………………………………………….. 12

2-2- مکانیابی تسهیلات……………………………………………………………………………………….. 12

2-2-1- مرور ادبیات در موضوع مکانیابی تسهیلات………………………………………………… 12

2-2-2- معیارهای دسته بندی مدلهای مکانیابی……………………………………………………….. 17

2-2-3- مسائل پوشش……………………………………………………………………………………… 19

2-2-3-1-مسأله پوشش مجموعه…………………………………………………………………….. 19

2-2-3-2- مسأله مکانیابی حداکثر پوشش…………………………………………………………. 21

2-2-3-3- مسائل p-center………………………………………………………………………………

2-2-3-4- مسائل p-median…………………………………………………………………………….

2-2-4- مسائل دیگر مکانیابی…………………………………………………………………………….. 24

2-2-5- مسائل مکانیابی تسهیلات با تقاضای تصادفی و تراکم…………………………………… 25

2-2-5-1- مرور ادبیات مسائل مکانیابی تسهیلات با تقاضای تصادفی و تراکم…………… 26

2-2-5-2- مکانیابی تسهیلات با تقاضای تصادفی و تراکم…………………………………….. 29

2-3- نظریه صف…………………………………………………………………………………………….. 35

2-3-1- مشخصات صف………………………………………………………………………………….. 36

2-3-2- قانون ليتِل………………………………………………………………………………………….. 38

2-3-3- صف M/M/1…………………………………………………………………………………….

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- الگوریتم MISA………………………………………………………………………….

2-4-3-3- الگوریتم VIS……………………………………………………………………………..

2-4-3-4- الگوریتم NNIA………………………………………………………………………….

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-II …………………………………

پیوست د: کد برنامه نویسی الگوریتم NSGA-II در محیط MATLAB…………………………….

چکیده:

مسأله مورد مطالعه در این پایان نامه، مسأله‌ی جانمایی تسهیلات با فرض ثابت بودن سرویس‌دهندگان و تصادفی بودن تقاضای مشتریان می‌باشد.

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

سه هدف برای مسأله فوق درنظر گرفته شده‌می باشد که هدف اول، مینیمم کردن متوسط تعداد مشتریان درحال سفر، هدف دوم، مینیمم کردن متوسط تعداد مشتریان در حال انتظار و هدف سوم، ماکزیمم کردن مجموع کارکرد دستگاه‌ها در واحد زمان می‌باشد. باتوجه به اینکه این مسأله، در حالت تک‌هدفه بودن نیز NP-Hard می‌باشد، حل آن در حالت چندهدفه، بسیار مشکل تر خواهدبود. به‌همین خاطر، چندین روش فراابتکاری برای حل آن ارائه می گردد. در این پژوهش کوشش شده‌می باشد که از سه الگوریتم چندهدفه مبتنی بر الگوریتم ژنتیک و همچنین از سه الگوریتم چندهدفه مبتنی بر سیستم ایمنی مصنوعی بهره گیری گردد. این الگوریتم‌ها با بهره گیری از روش‌های اندازه گیری عملکرد الگوریتم‌های چندهدفه، مورد مطالعه و تجزیه و تحلیل قرار می‌گیرند.

فصل اول: تعریف مسئله

1-1- مقدمه

با رشد روز افزون معاملات تجاری در سطح جهان و در سال‌های اخیر، ظهور پدیده تجارت الکترونیک[1] و بانکداری الکترونیک[2] به عنوان بخش تفکیک ناپذیر از تجارت الکترونیک مطرح گردید. بانکداری الکترونیک اوج بهره گیری از فناوری انفورماتیک و ارتباطات و اطلاعات برای حذف دو قید زمان و مکان از خدمات بانکی می باشد. ضرورت یک نظام بانکی کارامد برای حضور در بازارهای داخلی و خارجی ایجاب می کند تا بانکداری الکترونیک نه به عنوان یک انتخاب، بلکه ضرورت مطرح گردد. امروزه پایانه فروش، پایانه شعب، دستگاه‌های خودپرداز و … نماد بانکداری الکترونیک می باشد و یافتن مکان بهینه برای این پایانه‌ها و دستگاه‌ها می‌تواند تأثیر مهمی در حضور یک بانک یا مؤسسه در بازارهای داخلی و خارجی داشته باشد [1].

1-2- مکانیابی تسهیلات[3]

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

سؤال قبل یک مثال از مسأله مکانیابی تسهیلات بود. مکانیابی تسهیلات یعنی اینکه مجموعه‌ای از تسهیلات (منابع) را به صورت فیزیکی به گونه‌ای در یک مکان قراردهیم که مجموع هزینه برآورده کردن نیازها (مشتریان) باتوجه به محدودیت‌هایی که سر راه این مکانیابی قرار دارد، مینیمم گردد.

از سالهای 1960 به این طرف مسائل مکانیابی یک جایگاه ویژه‌ای را در حیطه پژوهش در عملیات اشغال کرده‌اند. آنها وضعیت‌های مختلفی را درنظر گرفته‌اند که می‌توان به موارد ذیل تصریح نمود: تصمیم گیری در مورد مکان کارخانجات، انبارها، ایستگاه‌های آتش نشانی و بیمارستان‌ها.

به گونه اساسی، یک مسأله مکانیابی بوسیله چهار عنصر زیر توصیف می گردد:

– مجموعه‌ای از مکانها که در آن‌ها، تسهیلات ممکن می باشد ایجاد یا باز شوند. برای هر مکان نیز بعضی اطلاعات در ارتباط با هزینه ساخت یا باز کردن یک تسهیل در آن مکان مشخص می گردد.

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

– لیستی از احتیاجات که بایستی بوسیله تسهیلات بازشده و بوسیله تخصیص نقاط تقاضا به تسهیلات برآورده گردد.

– تابعی از هزینه یا سودهایی که به هر مجموعه از تسهیلات اختصاص پیدا می کند.

پس هدف این نوع مسائل، یافتن مجموعه‌ای از تسهیلات می باشد که بایستی باتوجه به بهینه کردن تابع مشخصی باز شوند.

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

1-3- اظهار مسأله

هدف از اجرای این پژوهش، مکان‌یابی سیستم‌های خدمات رسانی ثابت با ظرفیت خدمت محدود می‌باشد. یعنی دستگاه‌های خدمت‌رسان به چه تعداد و در چه محل‌هایی استقرار یابند و چه مراکز تقاضایی به این

• 1
• 2