1-6- مفروضات مساله ……………………………………………………………………………………………………… 7

1-7- روش پژوهش …………………………………………………………………………………………………………. 7

1-7-1- مطالعات مورد کاوی و تجربی ………………………………………………………………………. 8

1-7-2- چهار چوب­ها ، دسته بندی و مرور ادبیات ……………………………………………………… 8

1-7-3- مدل­های کمی ……………………………………………………………………………………………… 8

1-8- مراحل اجرای تحقیق و روش های گرد آوری اطلاعات ………………………………………………… 8

1-9- جامعه آماری و روش های گرد آوری اطلاعات …………………………………………………………… 9

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

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

2-2- مروری بر مسائل VRP …………………………………………………………………………………………… 12

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

2-4- تقسیم بندی مساله VRP کلاسیک ……………………………………………………………………………. 13

2-4-1- مسیریابی وسیله ی نقلیه با دیدگاه ظرفیت (CVRP) ………………………………………… 14

2-4-2- مسیریابی وسیله ی نقلیه با حمل در بازگشت (VRPB) …………………………………… 15

2-4-3- مسیریابی وسیله ی نقلیه با چنجره ی زمانی(VRPTW) …………………………………… 15

2-4-4- مسیریابی وسیله ی نقلیه با تقاضای دریافت و تحویل (VRPPD) ……………………… 16

2-4-5- مسیریابی دوره ای وسیله ی نقلیه(PVRP) …………………………………………………….. 16

2-4-6- مسیریابی وسیله ی نقلیه با چهارچوب اتفاقی (SVRP) ……………………………………. 17

2-5- مرور ادبیات مسیریابی وسایل نقلیه با تقاضای تحویل و دریافت همزمان (VRPSPD) ……. 18

2-6- مروری بر تحقیقات انجام شده در مورد مساله مسیریابی وسایل نقلیه دارای چند مرکز تامین (MDVRP) …………………………………………………………………………………………………………………… 24

2-7- جمع بندی ……………………………………………………………………………………………………………. 27

فصل سوم: مدل ریاضی پیشنهادی …………………………………………………………………………….. 28

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

3-2- تعریف مسئله ………………………………………………………………………………………………………… 29

3-2-1- مفروضات مسئله ……………………………………………………………………………………….. 30

 
3-3- مدل ریاضی پیشنهادی ……………………………………………………………………………………………. 30

3-3-1- اندیس ها ………………………………………………………………………………………………….. 31

3-3-2- پارامترهای ورودی مدل ……………………………………………………………………………… 31

3-3-3- متغیر های تصمیم گیری …………………………………………………………………………….. 31

3-3-4- تابع هدف ………………………………………………………………………………………………… 32

3-3-5- محدودیت ها ……………………………………………………………………………………………. 32

3-4- اعتبارسنجی مدل ……………………………………………………………………………………………………. 35

3-5- پیچیدگی مدل مورد بررسی …………………………………………………………………………………….. 36

3-6- جمع بندی ……………………………………………………………………………………………………………. 39

فصل چهارم: الگوریتم فراابتکاری پیشنهادی ……………………………………………………………….. 40

4-1- مقدمه ای بر مسائل بهینه سازی ……………………………………………………………………………….. 41

4-1-1- تئوری پیچیدگی ………………………………………………………………………………………… 41

4-1-2- روش های بهینه سازی ……………………………………………………………………………….. 42

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

4-2-1- برخی از اصطلاحات الگوریتم ژنتیک …………………………………………………………… 48

4-2-2- روش های انتخاب کروموزوم ……………………………………………………………………… 50

4-2-3- تقاطع ……………………………………………………………………………………………………….. 52

4-2-4- جهش ………………………………………………………………………………………………………. 53

4-3- الگوریتم کلونی مورچگان ……………………………………………………………………………………….. 54

 
4-3-1- مزیت­های روش کلونی مورچگان ………………………………………………………………… 60

4-3-2- مراحل پیاده­سازی الگوریتم کلونی مورچگان …………………………………………………. 61

4-4- الگوریتم مورچگان پیشنهادی ………………………………………………………………………………….. 62

4-4-1- تبدیل مسئله به یک گراف جهت­دار ………………………………………………………………. 62

4-4-2- نحوه­ی ساختن پاسخ برای مسئله …………………………………………………………………… 62

4-4-3- بروزرسانی فرومون ها …………………………………………………………………………………. 63

4-5- ارزیابی الگوریتم ها ………………………………………………………………………………………………… 63

4-5-1- مجموعه داده ها ………………………………………………………………………………………… 64

4-5-2- مقایسه عملکرد الگوریتم ها برای مسائل با ابعاد کوچک …………………………………. 65

4-5-3- مقایسه عملکرد الگوریتم ها برای مسائل با ابعاد متوسط تا بزرگ ……………………… 67

4-6- مطالعه موردی ……………………………………………………………………………………………………….. 69

4-7- جمع بندی ……………………………………………………………………………………………………………. 72

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

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

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

5-3- پیشنهادات آتی ………………………………………………………………………………………………………. 75

فهرست منابع و مآخذ ………………………………………………………………………………………………………. 76

جدول 3-1 : داده های مسئله آزمایشی مربوط به هر گره ……………………………………………………   35

جدول 3-2: داده های مسئله آزمایشی مربوط به فواصل زمانی بین گره ها ……………………………   35

جدول 3-3 : زمان های تکمیل ویزیت هر گره در مسئله آزمایشی ………………………………………   36

جدول 4-1 : مقادیر داده های ورودی به مسائل آزمایشی ……………………………………………………   65

جدول 4-2 : نتایج محاسباتی حاصل از حل مسائل با ابعاد کوچک ……………………………………..   66

جدول 4-3 : زمان های محاسباتی و میانگین جواب های حاصل از حل مسائل با ابعاد کوچک… 66

جدول 4-4 : نتایج محاسباتی حاصل از حل مسائل با ابعاد متوسط تا بزرگ ………………………….. 68

جدول 4-5 : نتایج محاسباتی حاصل از حل مسئله کاربردی ……………………………………………….. 71

شکل 1-1 : مسأله فروشنده دوره گرد ………………………………………………………………………………… 4

شکل 1-2 : مسأله مسیریابی وسیله نقلیه …………………………………………………………………………….. 4

شکل 1-3 : نشان دهنده‌ی ارتباط بین نمونه‌های مختلف VRP …………………………………………….. 5

شکل 3-1 : سلسله مراتب پیچیدگی محیط های کارگاهی در مسائل زمانبندی ………………………. 38

شکل 3-2 : سلسله مراتب پیچیدگی توابع هدف در مسائل زمانبندی ……………………………………. 38

شکل 4-1 : انواع روش های بهینه سازی ………………………………………………………………………….. 43

شکل 4-2 : مکانیزم انجام عملگر تقاطع یک نقطه ای در مسائل جایگشتی ……………………………. 53

شکل 4-3 : نحوه انجام عملگر تعویض در مسائل جایگشتی ……………………………………………… 54

شکل 4-4 : رفت و برگشت مورچگان به آشیانه و منبع غذایی ……………………………………………. 56

شکل 4-5 : ایجاد یک مانع در مسیر آشیانه تا منبع غذایی مورچگان …………………………………….. 57

شکل 4-6 : ادامه حرکت مورچگان علی رغم حضور مانع ……………………………………………………. 57

شکل 4-7 : انتخاب مسیر کوتاهتر توسط همه­ی مورچه ها …………………………………………………… 58

شکل 4-8 : مقایسه زمان­های محاسباتی مورد نیاز نرم افزار لینگو و الگوریتم­های پیشنهادی ……… 67

شکل 4-9 : عکس هوایی از 161 سوپر مارکت مورد بررسی ……………………………………………….. 70