چكیده

در این تحقیق یک مسئله مکان­ یابی- تخصیص چندتسهیله ظرفیت دهی شده در محیط گسسته که با تقاضای برنولی مشتریان روبرو است، مورد بررسی قرار می­گیرد. هدف این مسئله احتمالی مکان­ یابی- تخصیص تعیین مکان بهینه تسهیلات از میان مکان‌های بالقوه و تخصیص تمامی مشتریان به تسهیلاتی که مستقر شده ­اند می­باشد، بطوریکه هزینه های ثابت برای استقرار تسهیلات و کل هزینه ارزش انتظاری استراتژی­ها کمینه شود. در این مسئله برای تصمیم گیری در مورد تقاضای مشتریان، با در نظر گرفتن دو استراتژی متفاوت فرمولبندی و مورد بررسی قرار گرفته است و در ادامه برای درک مسئله مذکور یک مثال عددی ارائه شده است.

نتایج محاسباتی این تحقیق، نشان می­دهدکه مسئله توسط نرم افزار بهینه سازی LINGO در اندازه­ های بزرگ در زمان معقول به حل بهینه دست پیدا نمی­ کند. به منظور نشان دادن کارائی مسئله در مقیاس­های بزرگ، یک الگوریتم فراابتکاری (الگوریتم ژنتیک) پیشنهاد شد. الگوریتم فرا ابیکاری پیشنهادی با یک حد پایین کارا (آزاد سازی لاگرانژ) مقایسه می­ شود.

 

كلمات كلیدی

مکانیابی- تخصیص تسهیلات؛ تقاضای برنولی؛ برنامه ریزی احتمالی؛ الگوریتم ژنتیک؛ آزاد سازی لاگرانژ.

 

 

 

 

 

 

فهرست مطالب

عنوان                                                                                                                                   صفحه

تقدیم به. ت‌

تشکر و قدردانی… ث‌

چكیده. ج‌

فهرست مطالب… ح‌

فهرست جداول.. ر‌

فهرست شکل ها ز‌

فصل اول

کلیات تحقیق و ساختار پایان نامه. 1

1-1-مقدمه. 2

1-2- ساختار پایان نامه. 4

فصل دوم

ادبیات موضوعی و زمینه های علمی تحقیق… 6

2-1- ابیادت موضوع. 7

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

2-1-2- مسائل با تقاضای احتمالی در ادبیات موضوعی.. 8

2-1-3- مسائل با تقاضای احتمالی برنولی در ادبیات موضوعی.. 12

2-2- زمینه های علمی تحقیق.. 15

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

2-2-2- مسائل مکانیابی.. 16

2-2-3- مسائل مکانیابی-  تخصیص…. 20

2-2-4- دسته بندی كلی مسایل برنامه ریزی تسهیلات… 24

2-2-5- دسته بندی مسائل مکانیابی با نگرش سنتی.. 25

2-2-6- دسته بندی مسائل مکانیابی با نگرش نوین.. 26

فصل سوم

ارائه مدل ریاضی و الگوریتم های پیشنهادی… 28

3-1- مقدمه. 29

3-2- تعریف مساله. 30

3-2-1-  فرضیات مساله. 31

3-2-2-  پارامترهای مساله. 32

3-2-3- متغیر های تصمیم مساله. 33

3-2-4- استراتژی های موجود مساله. 35

3-2-5- همگن سازی.. 37

3-2-6- خطی سازی مدل ریاضی.. 41

3-2-7- مثال.. 44

3-3- الگوریتم ژنتیک… 46

3-3-1- نمایش کروموزوم. 47

3-3-2- آغاز سازی.. 47

3-3-3- ارزیابی.. 49

3-3-4- معیار توقف… 49

3-3-5- نخبه گرایی.. 50

3-3-6- عملگر تقاطع.. 50

3-3-6-1- عملگر تقاطع نوع 1. 50

3-3-6-2- عملگر تقاطع نوع 2. 51

3-3-7- عملگر جهش…. 52

3-3-7-1- عملگرجهش نوع 1. 53

3-3-7-2- عملگرجهش نوع 2. 53

3-3-8- انتخاب… 54

3-3-9- معیار توقف… 54

3-4- آزادسازی لاگرانژ. 56

3-4-1- مقدمه. 56

3-4-2- مراحل الگوریتم آزاد سازی لاگرانژ. 56

3-4-3- شرط توقف… 57

3-4-4- رویه انجام الگوریتم آزاد سازی لاگرانژ. 57

فصل چهارم

نتایج محاسباتی… 60

4-1- مقدمه. 61

4-2- مسائل نمونه. 62

فصل پنجم

 

نتیجه گیری و پیشنهادات آتی… 71

5-1- نتیجه گیری.. 72

5-2- پیشنهادات آتی.. 72

مراجع فارسی… 73

مراجع لاتین.. 74

پیوست الف… 78

تشریح الگوریتم ژنتیک…. 78

1- ویژگی های الگوریتم ژنتیك… 79

2- واژگان الگوریتم ژنتیك… 80

3- ساختار كلی الگوریتم ژنتیك… 81

4- مفاهیم کلیدی الگوریتم ژنتیک… 83

4-1- كدینگ… 84

4-2- ایجاد جمعیت اولیه. 84

4-3- عملگرهای الگوریتم ژنتیك… 85

4-3-1- عملیات تقاطع.. 85

4-3-2- عملیات جهش…. 86

4-3-3- مکانیسم نمونه‌گیری.. 86

4-4- تابع برازش…. 88

4-5- استراتژی برخورد با محدودیتها 88

4-5-1- استراتژی ردی.. 88

4-5-2- استراتژی اصلاحی.. 88

4-5-3- استراتژی جریمه‌ای.. 89

Abstract. 90

 

 

 

 

 

 

 

فهرست جداول

 

 

عنوان

صفحه

فصل دوم:

جدول( 2- 1). خلاصهای از ادبیات موضوع. 7

جدول( 2- 2). عوامل موثر در تصمیمات مکان یابی.. 17

 

فصل سوم:

جدول (3- 1) . تعداد متغیر در مدل خطی و غیر خطی.. 43

جدول( 3- 2). تعداد محدودیت در مدل خطی و غیر خطی.. 43

جدول( 3- 3). مقادیر پارامتر برای . 44

….. 44

…. 44

.. 45

.. 59

 

 فصل چهارم:

جدول(4- 1). مقادیر پارامترهای الگوریتم ژنتیک… 62

جدول(4- 2). نتایج محاسبات برای اندازه کوچک… 65

جدول(4- 3).  نتایج محاسبات برای اندازه کوچک… 66

جدول(4- 4). مقایسه نتایج مثال نوعی.. 69

 

فهرست شکل­ها

 

 

عنوان

صفحه

فصل دوم:

شکل( 2- 1). دسته بندی کلی مسائل برنامه ریزی تسهیلات[1]. 25

شکل( 2- 2). دسته بندی نوین مسائل مکان یابی [1]. 27

 

فصل سوم:

شکل( 3- 1). روند آغازسازی.. 48

شکل( 3- 2). روند ارزیابی.. 49

شکل( 3- 3). فلوچارت الگوریت ژنتیک… 55

 

فصل چهارم:

شکل(4- 1).  نمودار Gapهای بدست آمده از الگوریتم ژنتیک و الگوریتم آزاد سازی لاگرانژ. 68

شکل(4- 2).  نمودار سرعت همگرای الگوریتم ژنتیک… 70

 

 

فصل اول:
کلیات تحقیق و ساختار پایان نامه

 

 

1-1-مقدمه

یکی از مسایلی که باید در مراحل اولیه طراحی سیستم­های صنعتی مورد توجه قرار گیرد مسئله مکان­ یابی- تخصیص[1]، که استقرار تسهیلات و تخصیص مشتریان به تسهیلات مستقر شده می­باشد، است. مطالعه پیرامون مکان بهینه از دیدگاه جغرافی­دانان و علمای علم اقتصادی همواره دارای اهمیت و الویت بوده است[1]. در ادبیات موضوع، مسایل مکان­ یابی[2] و مکان­ یابی – تخصیص مورد بحث قرار گرفتند و چند حالت از از این مسائل معرفی می­شوند. مانند مسئله ظرفیت­دهی[3] شده، مسئله بدون محدودیت ظرفیت[4] ، مسئله احتمالی[5] و مسائلی که تقاضایشان دارای توزیع برنولی[6] می­باشند. منظور از مکان­ یابی، مجموعه ­ای از اصول است که با توسل به آن مکان بهینه فعالیت­های (نقطه منطبق بر حداکثر سود یا حداقل هزینه) تعیین می­ شود. تصمیم گیری در مورد مکان تسهیلات از اجزاء بحرانی در برنامه ­ریزی استراتژیک شرکت­های بزرگ خصوصی و عمومی محسوب می­ شود. مطالعه و تحقیق پیرامون مکان بهینه صنعتی همواره دارای اهمیت و الویت بسیار بوده است [2].

مسائل مکانیابی در فضای گسسته[7] شامل تعیین مکان یک یا چندین تسهیلات در یک یا چند مکان بالقوه است تا هزینه تأمین نیاز های مشتریان را کمینه کند. در­مسائل مکانیابی- تخصیص استقرار مجموعه ­ای از تسهیلات جدید در بین تسهیلات موجود و تخصیص تسهیلات موجود به این تسهیلات جدید به صورتی که تقاضای موجود برآوردشود است مورد بحث قرار می­گیرد. در دنیای واقعی بسیاری از مسائل را می توان با بهره گرفتن از مدل­های مسائل مکان­ یابی- تخصیص حل نمود­و به جواب بهینه ومعقولی دست یافت که با اجرای این مدل­ها از صرف هزینه­ های اضافی می­توان جلوگیری کردو سود فراوانی بدست آورد [2].

در گونه­ای از مسائل مکان­ یابی- تخصیص محدودیت در ظرفیت برای تسهیلاتی که وظیفه خدمت رسانی را  دارند وجود دارد. این محدودیت می ­تواند ناشی از محدودیت فضا، محدودیت نیروی انسانی و یا حتی محدودیت­های از قبیل ظرفیت معابر جهت دستیابی به تسهیلات موجود باشد. تقاضای مشتریان را می­توان در مسائل مکان­ یابی- تخصیص بصورت احتمالی[8] و یا قطعی[9] در نظر گرفت. البته بدیهی است اگر بخواهیم خیلی دقیق با مسائل برخورد کنیم می­بابستی تمامی مسائل را بصورت احتمالی در نظر بگیریم که به خاطر پیچیدگی و گران بودن روش­های حل مسائل احتمالی و به فراخور نیاز های مسئله را بصورت قطعی در نظر می گیریم. در حالی که مسائل مکان­ یابی- تخصیص با تقاضای احتمالی در مقایسه با مسائل مکان­ یابی- تخصیص کلاسیک خیلی عملی­تر و نزدیک­تر به دنیای واقعی می­باشند، اما به علت پیچیدگی محاسباتی که این نوع مسائل دارند، تنها در چند دهه اخیر مورد بررسی قرار گرفتند. در این تحقیق مساله مکان یابی تسهیلات با تقاضای برنولی مورد بررسی قرار می گیرد. این تحقیق  شامل مسئله احتمالی مکان یابی گسسته است که هدف آن مکان یابی بهینه تسهیلات بین مکان های کاندید وتخصیص مشتریان به تسهیلات باز می باشد. تابع هدف مینییم کردن جمع هزینه ثابت تسهیلات باز،  بعلاوه  ارزش انتظاری دیگر هزینه ها که شامل هزینه سرویس دهی، هزینه منابع برونسپاری وهزینه تقاضای برآورده نشده می­باشد. هدف از این تحقیق مکانیابی بهینه تسهیلات بین مکان های کاندید وتخصیص مشتریان به تسهیلات می­باشد. در تحقیقات اخیر این مطلب مد نظر بوده  که اگر تسهیلی بیش از ظرفیت خود تقاضا داشته باشد از منابع برون سپار برای تامین تقاضای خود استفاده می کند. در حالی که ما در این تحقیق علاوه بر این حالت، حالت تقاضای برآورد نشده را در نظر می گیریم.

 

مفروضات مساله پیشنهادی بقرار زیر در نظر گرفته می­شوند:

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

 

 

1-2- ساختار پایان نامه

در ادامه در فصل2 ، ادبیات موضوعی و زمینه ­های علمی تحقیق را مورد بررسی خواهیم داد. ادبیات موضوع شامل مسئله مکان­ یابی، مکان­ یابی- تخصیص، مسئله مکان­ یابی- تخصیص ظرفیت­دهی شده ، مسئله مکان­ یابی- تخصیص احتمالی و مسائلی که تقاضا مشتریان دارای توزیع احتمالی برنولی هستند، می­باشد. در زمینه ­های علمی تحقیق دسته­بندی مسایل مكانیابی و مسایل مكانیابی- تخصیص، انواع این مسائل، مساله مكانیابی كلاسیک مورد بررسی قرار می­گیرد.  در فصل 3 به تشریح مساله و مدل پیشنهادی می پردازیم. در ادامه این فصل به منظور درك بهتر رفتار مدل، یک مثال نمونهای ارائه خواهیم داد، اما با توجه به پیچیدگیهای مدل پیشنهادی در مقیاس های بزرگ، یک الگوریتم فراابتكاری (الگوریتم ژنتیك) و یک حد پایین (ساده سازی لاگرانژ) معرفی خواهیم کرد. نتایج محاسبات مربوط به  الگوریتم­ها  پیشنهادی در فصل 4 مورد بررسی و مقایسه قرار خواهیم داد. در نهایت، تعدادی از توسعه­های آتی به همراه نتیجه ­گیری در فصل 5 مورد بررسی قرار گرفتند.

 

 

 

 

فصل دوم:
ادبیات موضوعی و زمینه ­های علمی تحقیق

 

 

 

2-1- ابیادت موضوع

 

2-1-1-  مقدمه