1-3. اهداف تحقیق. 5

1-4. جنبه­ های نوآوری و کاربردی تحقیق. 6

1-5. محتویات تحقیق. 7

فصل دوم ادبیات 8

2-1. مقدمه. 9

2-2. مساله مسیریابی وسایل حمل و نقل VRP. 11

2-2-1. تاریخچه VRP. 13

2-2-2. مشخصات کلی مساله مسیریابی وسایل حمل و نقل. 13

2-2-3. تعریف ریاضی مساله مسیریابی وسایل حمل و نقل. 18

2-2-4. مدل عمومی مساله مسیریابی وسایل حمل و نقل. 19

2-2-5. تقسیم بندی مساله مسیریابی وسایل حمل و نقل کلاسیک… 21

2-2-6. مشکل ایجاد زیر تور (عدم همبندی) 28

2-2-7. برخی مشکلات مدل سازی VRP در شرایط واقعی.. 29

2-3.  ادبیات مسائل CMVRP. 30

فصل سوم مدل ریاضی و الگوریتم ژنتیک پیشنهادی.. 35

3-1. مقدمه. 36

3-2. مدل پیشنهادی CMVRP. 37

3-2-1. فرض­های مدل. 37

3-2-2. خصوصیت مدل ارائه شده 38

3-2-3. تعریف علائم و پارامترها 39

3-2-4. مدل ریاضی CMVRP. 41

3-3. روش حل مدل پیشنهادی.. 43

3-4. الگوریتم ژنتیک (GA) 43

3-4-1. تعریف… 43

3-4-2. گذری بر ژنتیک طبیعی.. 45

3-4-3. واژگان الگوریتم ژنتیك… 51

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

3-4-5. مفاهیم کلیدی الگوریتم ژنتیک… 54

3-4-6. كدینگ… 55

3-4-7. ایجاد جمعیت اولیه. 57

3-4-8. اعمال ژنتیك… 58

3-4-9. تابع برازش… 63

3-4-10. روش اجرای الگوریتم ژنتیک… 64

3-4-11. استراتژی برخورد با محدودیتها 66

3-4-12. انواع عملگرهای تقاطعی.. 69

3-4-13. انواع عملگرهای جهشی.. 73

3-5. ساختار پیشنهادی الگوریتم ژنتیک… 76

3-5-1. نحوه نمایش جواب ها 76

3-5-2. نحوه شدنی کردن جواب ها 78

3-5-3. تعریف میزان برازندگی.. 80

3-5-4. مکانیزم نمونه گیری.. 81

3-5-5. عملگر تقاطعی.. 81

3-5-6. عملگر جهشی.. 82

3-6. جمع­بندی.. 84

فصل چهارم تحلیل و نتایج محاسباتی.. 85

4-1. مقدمه. 86

4-2. تولید مسائل نمونه. 86

4-3. تنظیم پارامتر. 87

4-3-1. تنظیم پارامترهای الگوریتم ژننیک… 88

4-4. نتایج محاسباتی.. 93

4-5. صحه­گذاری مدل ارائه شده 97

4-6. جمع­بندی.. 100

فصل پنجم نتیجه ­گیری و ارائه پیشنهادها……………………………………………………………………………………………101

5-1. نتیجه ­گیری.. 102

5-2. پیشنهادها 103

مراجع. 104
لیست جداول

جدول 3-1. مقایسه الگوریتم ژنتیک با فرایند تکامل طبیعی 49

جدول 4-1. سطوح فاکتورهای مسئله 87

جدول 4-2. فاکتورهای الگوریتم ژنتیک به همراه سطوحشان 89

جدول 4-3. آرایه متعامد 90

جدول 4-4. نتایج محاسباتی برای مسائل کوچک 94

جدول 4-5. نتایج محاسباتی برای مسائل بزرگ 95

جدول 4-6. اطلاعات مساله نمونه تولید شده 97

جدول 4-7. بهترین حل ریاضی دستی 98

لیست شکل­ها

شکل 2-1. نمایی از مسأله TSP 9

شکل 2-2. نمایی ساده از MTSP 10

شکل 2-3. نمایی ساده از VRP 11

شکل 2-4. نسخه های مختلف VRP کلاسیک و ارتباط بین آنها 22

شکل 2-5. مشکل عدم همبندی (زیرتور)28

شکل 3-1. مدل تئوری داروین 47

شکل 3-2. فضای کدینگ و فضای جواب 56

شکل 3-3. قانونمندی و موجه بودن 57

شکل 3-4. فضای جواب: ناحیه موجه و ناحیه غیرموجه 68

شکل 3-5. نمایش ماتریسی مسیرهای ایجاد شده 77

شکل 3-6. نمایش گرافیکی مسیرهای ایجاد شده 77

شکل 3-7. ماتریس اولیه نمایش دهنده جواب 78

شکل 3-8. ماتریس اصلاحی محدودیت تیم ها 79

شکل 3-9. ماتریس نمایش دهنده جواب 79

شکل 3-10. ماتریس اصلاحی مسیرها 80

شکل 3-11. ماتریس نمایش دهنده والدین 81

شکل 3-12. نمایش عملگر تقاطع 82

شکل 3-13. نمایش ماتریس اولیه انتخابی برای عملیات جهش 83

شکل 3-14. نمایش ماتریس در قدم دوم83

شکل 3-15. نمایش مسیر انتخابی 83

شکل 3-16. نمایش عملگر جهش 84

شکل 4-1. نمودار نرخ S/N توابع هدف در سطوح مختلف عامل ها 91

شکل 4-2. نمودار نرخ تاثیرات میانگین داده ها بر میانگین ها،در سطوح مختلف عامل ها 92

شکل 4-3. نمودار حرکت الگوریتم ژنتیک پیشنهادی93

شکل 4-4. نمایش مقادیر تابع هدف هر دو روش 96

شکل 4-5. نمایش زمان محاسباتی حاصل از هر دو روش 96

شکل 4-6. نمایش نحوه محاسبه تابع هدف 99

شکل 4-7. نمایش کروموزم بهینه مساله نمونه 99

چکیده

مساله ترکیبی نیروی انسانی- مسیریابی وسایل حمل و نقل[1] (CMVRP) به برنامه ­ریزی همزمان تیم‌هایی از نیروی انسانی برای خدمت­دهی به مشتریان و مسیریابی وسایل نقلیه جابجا کننده این تیم­ها می ­پردازد. تصمیم ­گیری در مورد تخصیص و نحوه انتقال این تیم‌ها به مشتریان در حوزه‌های مختلفی مانند مدیریت بحران، تیم­های بیمارستانی و تیم­های خدمات تعمیرات کاربرد دارد.

مساله ترکیبی نیروی انسانی- مسیریابی وسایل نقلیه CMVRP به عنوان تعمیمی از مساله کلاسیک VRP[2] جزء مسائل پیچیده و مربوط به رده مسائل NP-HARD است. جهت حل دقیق مدل ارائه شده، از برنامه CPLEX11 استفاده شده است. همچنین برای حل مسائل تولید شده در اندازه‌های بزرگ، روش فرا ابتکاری الگوریتم ژنتیک [3](GA) ارائه شده است. الگوریتم ژنتیک پیشنهادی کارایی مناسبی در حل مسائل تولید شده، در مقدار تابع هدف نشان می­دهد و همچنین پایین بودن زمان حل مسائل توسط این الگوریتم بسیار جالب توجه است.

مقدمه
یکی از حوزه‌هایی که سهم قابل توجهی در مصرف انرژی و به تبع آن پیامدهای زیست محیطی ناشی از مصرف سوخت را داراست، بخش حمل و نقل است که در سال ۱۳۸۵ سهمی در حدود ۲۶ درصد از مصرف انرژی و 3/49 درصد از مصرف فرآورده‌های نفتی کشور را به خودش اختصاص داده است. قطعا مصرف بهینه انرژی در این بخش که وابسته به زیر ساخت‌ها و همچنین ناوگان حمل و نقل کشور است، تاثیر قابل توجهی در جلوگیری از تضییع سرمایه‌های ملی خواهد داشت.

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

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

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

حمل و نقل به معنای جامع آن شامل مدیریت، زیربنا و روبنا ناوگان از نیازهای اساسی جوامع امروزی است بطوری که در هر کشور برای اعتلای توان اقتصادی، فرهنگی، امنیتی وسیاسی داشتن شبکه حمل و نقلی گسترده و قابل اطمینان از نیازهای اولیه محسوب می­گردد. حتی برخی بر این باور هستند که حمل و نقل از ابزارهای ابتدایی توسعه می‌باشد. در گذشته به دلیل اینکه حمل و نقل یک نیاز ثانویه برای تحقق نیازهای اولیه‌ای همچون تجارت، مسافرت، اشتغال و غیره به حساب می‌آمد، به نحو شایسته‌ای بدان پرداخته نمی‌شد. لیکن رشد و توسعه اقتصاد جهانی، تلاش کشور‌ها برای استفاده بهینه از توانمندی‌ها و فرصت‌های در اختیار، و فشرده شدن رقابت در عرصه‌های جهانی موجب گشت تا حمل و نقل بواسطه نقش مستقیمی که درکاهش هزینه‌های تمام شده تولید و دسترسی به بازار ودر ‌‌نهایت افزایش توان رقابت در عرصه تجارت بین الملل مخصوصاً برای کشورهایی که حجم تجارت خارجی صادرات و واردات آن‌ ها بالا می‌باشد، از جایگاه رفیعی در مدیریت، برنامه ریزی و سرمایه گذاری و حتی تحقیقات برخوردار گردد. تاثیر چنین ویژگی سبب گشته تا نگرش‌های گذشته نسبت به حمل و نقل تغییر یابد و به حمل ونقل به عنوان یک بخش اقتصادی- خدماتی مهم نگریسته شود [2].

در ادبیات اولین بار شخصی به نام هیچکوک[1] [3] در مقاله­ای مسأله حمل ونقل را مورد بهینه بررسی قرار داد. پس از آن افرادی چون کوپمنز[2] در مقاله­ای با عنوان « بهینه­سازی استفاده از شبکه های حمل و نقل» و کنتاروویچ[3] [4] که مقاله­ایی تحت عنوان « متد­های ریاضی سازماندهی و برنامه ریزی محصولات» را انجام داد، به بررسی موضوع حمل و نقل پرداخته و روش­های ریاضی را مورد استفاده قرار دادند. همچنین برای نخستین بار در سال ۱۹۹۶ دانتزیگ[4] از روش سیمپلکس بر اساس اصول برنامه ریزی خطی برای بدست آوردن جواب در مسائل حمل و نقل استفاده نمود. در سال‌های اخیر نیز افراد زیادی به بررسی مسأله حمل و نقل پرداخته و الگوریتم­های ریاضی متعددی برای حل اینگونه مسائل ارائه شده است.

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

متن کامل را می توانید دانلود نمائید