1-6-1-تقسیم بندی نارولا…………………………………………………………………………………..

8

1-6-1-1- تسهیلات شامل متوالی…………………………………………………………………..

8

1-6-1-2- تسهیلات انحصار متوالی……………………………………………………………….

8

1-6-1-3- حالات دیگر………………………………………………………………………………..

8

1-6-1-4-شامل محلی………………………………………………………………………………….

9

1-6-1-5- شامل کلی…………………………………………………………………………………….

9

1-6-1-6- منحصر متوالی………………………………………………………………………………

9

1-6-2- تقسیم بندی شاهین، سورال……………………………………………………………………

9

1-6-2-1-الگوی جریان…………………………………………………………………………………

10

1-6-2-2- انواع خدمت…………………………………………………………………………………

10

1-6-2-3- ساختار فضایی……………………………………………………………………………..

11

1-6-2-4- تابع هدف…………………………………………………………………………………….

12

1-7- نواحی قابل کاربرد مکان یابی سلسله مراتبی……………………………………………………….

12

1-7-1- مراکز بهداشتی درمانی…………………………………………………………………………….

12

1-7-2- سیستم های جمع آوری و دفع زباله ………………………………………………………..

12

1-7-3- سیستم های تولید و توزیع……………………………………………………………………..

12

1-7-4- سیسستم های آموزشی……………………………………………………………………………

13

1-7-5- سیستم های خدمات رسانی اضطراری………………………………………………………

13

1-7-6- شبکه های ارتباطی…………………………………………………………………………………

13

 

فصل دوم:ادبیات و پیشینه تحقیق

 

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

15

2-2- فرموله کردن یک مدل میانه عمومی خدمات سلسله مراتبی شامل متوالی……………….

19

2-3- فرموله کردن یک مدل مکان یابی سلسله مراتبی منحصرا متوالی……………………………

21

2-4- مساله مکان یابی بیشترین پوشش سلسله مراتبی………………………………………………….

22

2-5- پوشش حداکثری سلسله مراتبی با پوشش همه ی سطوح تقاضا……………………………

22

 

فصل سوم:مدل ریاضیپیشنهادی و حل آن

 

3-1- مقدمه……………………………………………………………………………………………………………

29

3-2- تعریف مسأله و مدل ریاضی……………………………………………………………………………

30

3-3- مثال عددی……………………………………………………………………………………………………

34

3-4- حل فرابتکاری……………………………………………………………………………………………….

36

3-5- تضاد بین تابع های هدف………………………………………………………………………………..

37

3-6- بهینه سازیچند معیاره……………………………………………………………………………………

37

3-7- ارتباط غالب …………………………………………………………………………………………………

37

3-8- مرز بهینه ……………………………………………………………………………………………………..

38

3-9- الگوریتم بهینه سازی انبوه ذرات(PSO) ………………………………………………………..

39

3-10- پنج قانون میلوناس برای هوش گروهی…………………………………………………………..

39

3-11- اصطلاحات موجود در الگوریتم…………………………………………………………………….

40

3-12- مراحل الگوریتم…………………………………………………………………………………………..

41

3-13- بهینگی پارتو……………………………………………………………………………………………….

42

3-13-1- مفهوم آرشیو پارتو……………………………………………………………………………….

42

3-13-2- بروز رسانی آرشیو جوابهای پارتو………………………………………………………….

43

3-14- نحوه تخصیص تابع برازندگی………………………………………………………………………..

43

3-15- رویکردPSO چندهدفه………………………………………………………………………………

44

3-16- شاخص های مقایسه………………………………………………………………………………….

44

 

3-16-1- شاخص كیفیت……………………………………………………………………………………

45

3-16-2- شاخص پراكندگی………………………………………………………………………………..

45

3-17- مقدار دهی اولیه و نمایش جواب ها……………………………………………………………..

45

3-18- مراحل تکرار……………………………………………………………………………………………..

48

3-19- شرط توقف……………………………………………………………………………………………….

50

3-20- تئوری مجموعه فازی………………………………………………………………………………….

54

3-21- معرفی مسأله برنامه ریزی خطی فازی……………………………………………………………

56

3-22- مدل فازی………………………………………………………………………………………………….

60

3-23- دیفازی سازی…………………………………………………………………………………………….

60

3-24- مثال عددی برای مدل فازی………………………………………………………………………….

62

 

فصل چهارم: الگوریتم حل مسأله و نتایج محاسباتی

4-1- مقدمه……………………………………………………………………………………………………………

65

4-2- حل با استفاده از نرم افزار GAMS …………………………………………………………………….

66

4-3- تنظیم پارامترهای الگوریتم: روش سطح پاسخ (RSM) ……………………………………….

68

4-4- شاخص های اندازه گیری ………………………………………………………………………………

69

4-5- شاخص تعداد جواب های بهینه پارتو(NPS) …………………………………………………….

70

4-6- شاخص زمان حل بر حسب ثانیه (CPU Time) ………………………………………………….

73

 

فصل پنجم : نتیجه گیری و پیشنهادات برای تحقیقات آتی

 

5-1- مقدمه……………………………………………………………………………………………………………

76

5-2- نتیجه گیری……………………………………………………………………………………………………

76

5-3- پیشنهادات تحقیقات آتی…………………………………………………………………………………

77

منابع مآخذ……………………………………………………………………………………………………………..

79

پیوستها……………………………………………………………………………………………………………..

87

 

 

 

 

جدول 1-1 مثال برای سیستم خدمات بهداشتی و درمانی

5

جدول 2-1کلی بر روی مطالعات انجام شده

24

جدول 2-2کلی بر توابع هدف و محتوای مطالعات انجام شده

26

جدول 3-1 جدول تقاضای سطوح مختلف گره های تقاضا و تسهیلات موجود

35

جدول 3-2 جدول فواصل گره های تقاضا و تسهیلات موجود از نقاط کاندید

35

جدول 3-3 جدول هزینه ساخت و مطلوبیت تأسیس نقاط کاندید

35

جدول 3-4 جدول مقادیر متغیر ها

36

جدول 3-5 جدول مقادیر فازی تقاضا

62

جدول 4-1 جدول بازه های انتخابی برای تولید اعدادتصادفی هزینه ساخت برای سطوح مختلف

65

جدول 4-2 جدول نتایج از حل مسائل نمونه ای در نرم افزار GAMS

67

جدول 4-3 جدول پارامترها و سطوح آنها در الگوریتم MOPSO پیشنهادی

68

جدول 4-4 جدول پارامترهای تنظیم شده در الگوریتم MOPSO پیشنهادی

69

جدول 4-5 میانگین تعداد جوابهای نامغلوب در الگوریتم MOPSO پیشنهادی

70

جدول 4-6 زمان حل بر حسب ثانیه در نرم افزار GAMSو الگوریتم MOPSO پیشنهادی

73

ی نوشته‌ها

3-2-7 تشریح جزئیات و عملکرد مدل 22

3-3 خطی سازی مدل پیشنهادی 26

3-4 مثال 28

3-5 لزوم استفاده از رویكرد فرا ابتكاری و ابتکاری 31

3-6 تشریح الگوریتم ژنتیک 32

3-7 مفاهیم كلیدی الگوریتم ژنتیك 33

3-7-1 کدینگ 33

3-7-2 ایجاد جمعیت اولیه 34

3-7-3 عملگر های الگوریتم ژنتیک 34

3-7-4 تابع برازش 37

3-7-5 استراتژی برخورد با محدودیت ها 37

3-8 ساختار كلی الگوریتم ژنتیك 38

3-9 رویه انجام الگوریتم ژنتیک 40

3-9-1 نمایش كروموزوم 40

3-9-2 جمعیت اولیه 41

3-9-3 ارزیابی 42

3-9-4 معیار توقف 42

3-9-5 نخبه گرایی 42

3-9-6 عملگر 42

3-10 الگوریتم آزاد سازی لاگرانژ 48

3-10 -1 مراحل الگوریتم آزاد سازی لاگرانژ 50

3-10 -2 شرایط توقف الگوریتم آزاد سازی لاگرانژ 50

3-11 رویه انجام الگوریتم آزاد سازی لاگرانژ 51

فصل چهارم…………………………………………………………………………………………………………………….. 54

نتایج محاسباتی 54

4-1 نتایج محاسباتی 55

5-2 مسایل نمونه 55

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

5-1 نتیجه گیری 66

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

مراجع فارسی 68

مراجع لاتین 69

Abstract 72

فهرست جداول
فصل دوم

جدول (1- 1). خلاصه ادبیات موضوعی مساله مکان یابی- تخصیص…. 14

فصل سوم

جدول (3 – 1). تعداد متغیر های مسئله خطی و غیر خطی.. 28

جدول (3 – 2). تعداد متغیر های مسئله خطی و غیر خطی.. 28

جدول (3 – 3). مقادیر پارامتر . 29

جدول (3 – 4). مقادیر پارامتر برای تسهیلات i 29

جدول (3- 5). مقادیر پارامتر های انبار. 29

جدول (3- 6). مقادیر تابع هدف.. 30

جدول (3- 7). جواب بهینه مسئله. 30

جدول(3- 8). روند الگوریتم ژنتیك. 39

جدول(3- 9) مراحل بهینه سازی گرادیان. 53

فصل چهارم

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

جدول(4- 2). پارامترهای الگوریتم لاگرانژ. 56

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

جدول(4- 4). نتایج محاسباتی در مقیاس های بزرگ.. 61

جدول(4- 5). مقایسه جواب های B&B و الگوریتم GA.. 62
فهرست شکل ها
فصل اول

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

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

فصل سوم

شکل(3- 1). کروموزم. 41

شکل(3- 2). تقاطع نوع I. 43

شکل(3- 3(.تقاطع نوع II. 45

شکل(3- 4). جهش نوع I. 46

شکل(3- 5). جهش نوع II. 47

فصل چهارم

شکل (4- 1). نمودار همگرایی مقادیر تابع هدف در GA.. 63

شکل (4- 2). نمودار مقایسه زمان محاسباتی الگوریتم ژنتیك و الگوریتم آزاد سازی لاگرانژ و Lingo در اندازه های متفاوت.. 64

چکیده:

4-2-2 محاسبه فاصله انتظاری…………………………………………………………………………………….64

4-2-3 مدل ریاضی پیشنهادی……………………………………………………………………………………..83

4-2-3-1 مثال……………………………………………………………………………………………………………92

4-3 روش پیشنهادی حل……………………………………………………………………………………………………….94

4-4 مسائل نمونه…………………………………………………………………………………………………………………..99

4-4-1 روش کاروش- کاهن- تاکر……………………………………………………………………………..97

4-5 نتایج محاسباتی……………………………………………………………………………………………………………..99

فصل پنجم : نتیجه گیری و پیشنهادات آتی……………………………………………………………………………106

5-1 نتیجه گیری……………………………………………………………………………………………………..107

5-2 پیشنهادات آتی…………………………………………………………………………………………………108

مراجع………………………………………………………………………………………………………………………………….109

مراجع فارسی…………………………………………………………………………………………………………..110

مراجع لاتین…………………………………………………………………………………………………………….111

فهرست جداول

فصل دوم :

جدول (2-1).ی اجمالی بر مسایل مكان یابی تسهیلات در حضور موانع………………………………….8

فصل چهارم :

جدول (4-1). اطلاعات تسهیلات موجود………………………………………………………………………………….93

جدول (4-2). اوزان مابین تسهیل موجود و جدید……………………………………………………………………..3 9

جدول (4-3) . مختصات مکان بهینه تسهیل جدید در مثال نمونه………………………………………………….93

جدول (4-4). مختصات تسهیلات موجود…………………………………………………………………………………99

جدول (4-5). تسهیلات درون و بیرون مسیر دایره ای……………………………………………………………….100

جدول (4-6). نقاط پایداری حاصل ازK.K.T در ترکیب تکی ربع……………………………………………….101

جدول (4-7). نقاط پایداری حاصل ازK.K.T در ترکیب دو تایی ربع ها………………………………………101

جدول (4-8). نقاط پایداری حاصل ازK.K.T در ترکیب سه تایی ربع ها……………………………………..107

جدول (4-9). نقاط پایداری حاصل ازK.K.T در ترکیب چهار تایی ربع ها………………………………….102

جدول (4-10). نقاط پایداری حاصل ازمیانه در ترکیب تکی ربع ها……………………………………………102

جدول (4-11). نقاط پایداری حاصل ازمیانه در ترکیب دو تایی ربع ها……………………………………….102

جدول (4-12). نقاط پایداری حاصل ازمیانه در ترکیب سه تایی ربع ها………………………………………102

جدول (4-13). نقاط پایداری حاصل ازمیانه در ترکیب چهار تایی ربع ها…………………………………..103

جدول (4-14). نقاط با تابع هدف مینیمم حاصل ازدو روش در ترکیب تکی ربع ها……………………. 103

جدول (4-15). نقاط با تابع هدف مینیمم حاصل ازدو روش در ترکیب دو تایی ربع ها…………………103

جدول (4-16). نقاط با تابع هدف مینیمم حاصل ازدو روش در ترکیب سه تایی ربع ها………………..104

جدول (4-17). نقاط با تابع هدف مینیمم حاصل ازدو روش در ترکیب چهار تایی ربع ها…………….104

جدول (4-18). مقدار تابع هدف در نقاط حاصل از گام پنجم…………………………………………………..104

فهرست اشكال

فصل دوم :

شکل (2 -1- 1). نواحی با محدودیت در قرارگیری و یا حركت……………………………………………………..8

شکل (2-2-1) . نوع مانع در نظر گرفته شده توسط کاتز و کوپر……………………………………………………9

شکل( 2- 2- 2) رویکرد در نظر گرفته شده برای حل مسایل مکان یابی با مانع توسط بایشوف و کلامروس……………………………………………………………………………………………………………………………….10

شکل( 2- 2-3)0 رویکرد در نظر گرفته شده برای حل مسایل مکان یابی با مانع توسط کلامروس…….11

شکل (2-2-4) . نوع مانع در نظر گرفته شده توسط آنجا و پارلر…………………………………………………..12

فصل سوم :

شکل (3-1). دسته بندی مسایل برنامه ریزی تسهیلات…………………………………………………………………22

شکل(3-2). فاصله اقلیدسی بین دو نقطه……………………………………………………………………………………25

شکل(3-3). فاصله متعامد بین دو نقطه………………………………………………………………………………………26

فصل چهارم :

شکل (4-1). مانع آرکی شکل احتمالی در صفحه………………………………………………………………………..44

شکل (4-2). وضعیت دو تسهیل در حالت پدیدار نبودن………………………………………………………………46

شکل (4-3). وضعیت دو تسهیل در حالت پدیدار بودن……………………………………………………………….46

شکل (4-4). گام های شرایط پدیدار بودن دو تسهیل نسبت به هم………………………………………………..47

شکل (4-5). شرایط گام اول پدیداری……………………………………………………………………………………….49

شکل (4-6). شرایط گام سوم پدیداری………………………………………………………………………………………53

شکل (4-7) .حالت اول شرایط با مانع جهت آزمون برخورد راستای افق تسهیل جدید با مانع…………..56

شکل (4-8) .ترکیب اول از شرایط با مانع…………………………………………………………………………………..59

شکل (4-9) .ترکیب دوم از شرایط با مانع………………………………………………………………………………….60

شکل (4-10) .ترکیب سوم از شرایط با مانع……………………………………………………………………………….60

شکل (4-12) .ترکیب چهارم از شرایط با مانع…………………………………………………………………………….63

شکل (4-13) .ترسیم خطوط متناظر در حالت تک ریشه………………………………………………………………65

شکل (4-14).نمای تصویری جهت محاسبه پاره خط T……………………………………………………………….70

شکل (4-15).مسیرهای جابجایی بین دو تسهیل در زمان وجود مانع……………………………………………..74

شکل (4-16).ترسیم رابطه بین خطوط ابتدای مانع و انتهای مانع……………………………………………………76

شکل (4-17) . مکان تسهیلات موجود و تسهیل جدید در شرایط با مانع و بدون مانع……………………..90

شکل (4-18) . ارائه الگوریتم پیشنهادی حل مساله………………………………………………………………………93

چکیده

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

برای درک مدل ارائه شده و اثبات کارایی آن مثال کوچک ارائه شده است و همچنین به علت پیچیدگی حل مدل در ابعاد بزرگ الگوریتم ابتکاری نیز ارائه شده است.

مقدمه

برنامه ریزی تسهیلات دو بخش عمده جایابی و طراحی را شامل می­شود که مهمترین بخش طراحی، استقرار یا جا­نمایی تسهیلات می­باشد.منظور از تسهیلات،هر مجموعه، شامل کارخانه، بیمارستان، دانشگاه … است. با افزایش میزان هزینه حمل و نقل و هزینه­های تحویل­،مساله مکان­یابی تسهیلات نقش مهمی در محیط­های صنعتی ایفا می­کند.نظریه مکان­یابی به عنوان شاخه­ای از تحقیق در عملیات از یک سو در جایابی تسهیلات و از سوی دیگر در تصمیم گیری های مدیریتی ،اقتصادی و برنامه ریزی تولید تاثیرگذار است و فواید بسیاری برای واحد های صنعتی از جمله سرمایه کمتر و بازدهی بیشتر، زمان بازگشت سرمایه کمتر و سود بیشتر به دنبال خواهد داشت.انتخاب مکان بهینه و متعاقبا مسیر بهینه کاری پیچیده و دارای فرایند تکراری می باشد.مکان بهینه همچنین باید بتواند پاسخگوی حجم تردد در محیط صنعتی باشد.مطالعه پیرامون مکان بهینه از دیدگاه جغرافی دانان و علمای اقتصادی هموراه دارای اهمیت بوده و در محاسبات خود مد نظر قرار می دهند [1].مراکز صنعتی و کارخانجات برای تعیین مکان احداث کارخانه، استقرار تجهیزات و دپارتمان­های خود در کارخانه، استقرار دفاترشان در سطح شهر، تعیین مراکز توزیع محصولات و … با چنین مسائلی سر و کار دارند.

• فرآیند تحقیق ………………………………………………………………………………………………. 34

  • تعریف ساده ای از مساله ……………………………………………………………………………… 34
  • وضعیت دو نقطه نسبت به هم در حضور مانع ………………………………………………… 35

  • کوتاهترین فاصله بین دو نقطه در حضور مانع ………………………………………………… 38

    • مانع به صورت ثابت …………………………………………………………………………….. 38
    • مانع به صورت متحرک …………………………………………………………………………. 40

فصل چهارم- محاسبات و یافته های تحقیق

• مقدمه …………………………………………………………………………………………………….. 44

• محاسبه امید فاصله بین دو نقطه در حالت shadow ……………………………………. 45

• محاسبه امید فاصله بین دو نقطه در حضور مانع احتمالی در حالت کلی …………. 48

• متغییر های واسط ……………………………………………………………………………………. 51

• مدل ریاضیمسئله ………………………………………………………………………………….. 54

• محدوده امید فاصله بین دو نقطه در مدل …………………………………………………… 55

• وارد نمودن انتگرال به لینگو ……………………………………………………………………. 57

• الگوریتم ژنتیک ……………………………………………………………………………………… 59

  • تعریف الگوریتم ژنتیک …………………………………………………………………….. 59
  • مزایا و برتریهای الگوریتم ژنتیک ……………………………………………………….. 61
  • معایب الگوریتم ژنتیک …………………………………………………………………….. 64
  • گذری بر ژنتیک طبیعی …………………………………………………………………….. 65
  • واژگان الگوریتم ژنتیک …………………………………………………………………….. 70
  • ساختار کلی الگوریتم ژنتیک ……………………………………………………………… 71
  • کروموزوم ……………………………………………………………………………………….. 73
  • ایجاد جمعیت اولیه …………………………………………………………………………… 75

  • اعمال ژنتیک ……………………………………………………………………………………. 76

    • عملگر جهشی …………………………………………………………………………… 77
    • عملگر تقاطعی ……………………………………………………………………………79
  • انتخاب چرخه رولت ……………………………………………………………………….. 81
  • استراتژی برخورد با محدودیت ها …………………………………………………….. 82

• مثال ………………………………………………………………………………………………….. 83

فصل پنجم- نتیجه گیری و پیشنهادات

• نتیجه گیری …………………………………………………………………………………………. 87

• پیشنهادات آتی …………………………………………………………………………………….. 88

پیوست – فهرست منابع و مواخذ ………………………………………………………………………. 89

چکیده انگلیسی ……………………………………………………………………………………………….. 91

• فهرست جداول

جدول 1-1 روند تحقیقات علمی و مقالات انجام شده در زمینه مکانیابی در حضور مانع …….21

جدول 4-1 مختصات تسهیلات موجود …………………………………………………………. 83

جدول 4-2 وزن بین تسهیلات موجود با جدید ………………………………………………..83

جدول 3-4 وزن بین تسهیلات جدید با جدید …………………………………………………83

جدول 4-4 داده های مانع خطی ………………………………………………………………….. 83

جدول 4-5 مقایسه نتایج الگوریتم ژنتیک ……………………………………………………… 84

جدول 4-6 نتیجه حل مثال …………………………………………………………………………. 84

• فهرست تصاویر و نمودارها

شکل 3-1 فاصله اقلیدسی در صفحه ……………………………………………………………….26

شکل 3-2 مسیر های مختلف متعامد بین x و xi ……………………………………………. 29

شکل 3-3 وضعیت های مختلف دو نقطه نسبت به هم در حضور مانع خطی ………36

شکل 3-4 فاصله بین دو نقطه در حالت shadow …………………………………………… 39

شکل 3-5 تابع فاصله در حضور مانع خطی در حالت xj > xi …………………………. 42

شکل 3-6 تابع فاصله در حضور مانع خطی در حالت xj < xi …………………………. 42

شکل 4-1 دو نقطه در حالت shadow …………………………………………………………… 47

شکل 4-2 مدل تئوری داروین ……………………………………………………………………… 71

شکل 4-3 ساختار کروموزوم ……………………………………………………………………….. 76

شکل 4-4 عملگر Mutation …………………………………………………………………………..81

شکل 4-5 عملگر Crossover …………………………………………………………………………82

شکل 4-6 مکان استقرار تسهیلات مثال 4-9 ………………………………………………….. 87

چکیده

مسائل مکانیابی بر روی سطح, در حضور یک مانع خطی یا چند مانع, مساله ای می باشد که هم استقرار تسهیل جدید و هم تردد از میان این موانع, ممنوع می باشد. مسئله بررسی شده در این تحقیق, از نوع مکانیابی پیوسته با ظرفیت نامحدود می باشد. یعنی هدف یافتن مکان چند تسهیل نقطه ای در میان یک تعداد متناهی تسهیلات موجود با وزن معین, قطعی و دارای وزن غیر منفی می باشد.

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

استقرار تسهیلات موجود در سیستم به گونه ای می باشد که امکان استقرار مولفه محور yها بر روی مسیر مانع خطی وجود ندارد و به صورت مشابه امکان استقرار تسهیلات جدید بر روی مسیر مانع خطی امکان پذیر نمی باشد.

همچنین تعریفی از فاصله بین دو نقطه در حضور مانع ارائه شده و برای مسئله مورد بحث با توزیع نرمال, فاصله بین دو نقطه مفروض را فرموله نمودیم. با توجه به پیچیده بودن مسئله مدل بدست آمده, از الگوریتم فراابتکاری ژنتیک در این مسئله استفاده شده و نتایج این روش با روش دقیق مقایسه گشته است.

مقدمه

مسالة مكان یابی (جایابی) و استقرار تسهیلات یکی از مسائل مهمی می باشد که در طراحی سیستم های صنعتی مورد توجه قرار فراوان می گیرد. در ادبیات موضوعی، معمولاً چند حالت از مسایل مكانیابی پیوسته، مورد بحث قرار گرفتند، مانند مساله میانه، مساله مركز و مساله مركز-میانه. در مساله میانه هدف، پیدا کردن مکان وسیله (تسهیل) جدید می­باشد، بطوریکه مجموع فواصل وزن­دهی شده بین تسهیل جدید و تسهیلات موجود، حداقل گردد. این مساله، در تئوری مکان­یابی به مساله وِبِر[5] و مساله کمینه مجموع[6] نیز شهرت دارد. مسایل مکان­یابی بر اساس نوع تابع فاصله نیز تقسیم­بندی می­شوند، مانند فاصله اقلیدسی و متعامد. مساله میانه با فواصل اقلیدسی یکی از قدیمی ترین مسایل مکان­یابی تسهیلات می­باشد. برای حل بهینه این نوع مساله، روش­های حل مختلفی پیشنهاد شده­است که مشهورترین آن روش تکراریی می­باشد.

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

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

فرضیاتی که برای مسئله تعریف می نماییم به قرار زیر می باشد:

• مسئله از نوع مکان یابی پیوسته با ظرفیت نامحدود می باشد. یعنی هدف یافتن مکان چند تسهیل نقطه­ای در میان یک تعداد متناهی تسهیلات موجود متناهی می­باشد، بطوریکه ظرفیت تسهیلات جدید برای خدمت­دهی نامحدود می­باشد.

• مسئله از نوع مکان یابی پیوسته میانه متعامد در حالت چند تسهیله می باشد.

• هر تسهیل موجود دارای مکان ثابت با مختصات معین، قطعی و دارای وزن غیرمنفی می­باشد.

• مساله برای کل افق برنامه­ریزی در ابتدای دوره، سیاست­گذاری می­کند، یعنی مساله مکان­یابی ایستا می­باشد.

• با مساله مکان­یابی محدود با یک مانع خطی سر و کار داریم، بطوریکه از عرض مانع صرفنظر می­شود.

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

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

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

جدول( 3- 6). نتایج محاسباتی مثال نوعی.. 45

جدول( 3- 7). روش بهینه سازی گرادیان.. 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

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

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

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