فهرست

 

فصل اول کلیات تحقیق.. 1

1-1. مقدمه. 2

1-2. تعریف مساله. 4

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-1. مقدمه

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

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

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

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

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

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

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

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

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