تشکر و قدردانی:
به پاس محبت های بی دریغشان که هرگز فروکش نمی کند…
اساتید راهنمایم
دکتر جواد رضاییان
و دكتر حسین محمديان
چکیده
در این تحقیق، مسئله مسیریابی ویزیتورها با در نظر گرفتن مهارت ویزیتورها و زمانهای ویزیت متفاوت و زمانهای حمل و نقل بین سوپر مارکتها به منظور ایجاد بهترین تعادل بار کاری بین ویزیتورها با توجه به مهارت و تجربه آنها در نظر گرفته شده است. در این پایان نامه برای حل این مسئله از دو رویکرد استفاده شده است. در رویکرد اول یک مدل برنامهریزی عدد صحیح مختلط برای مسئله یاد شده اردئه شده است. اما از آنجاییکه که مدل ریاضی ارائه شده تنها قادر به حل مسائل با ابعاد کوچک میباشد، که این موضوع کاربرد الگوریتمهای فراابتکاری را اجتناب ناپذیر میسازد. دو رویکرد دوم برای مسئله فوق دو الگوریتم فراابتکاری شامل « الگوریتم ژنتیک » و « الگوریتم بهینه سازی کلونی مورچگان » به منظور حل مدل در مقیاسهای کاربردی ارائه شده است. نتایج محاسباتی نشان دهنده برتری الگوریتم مورچگان نسبت به الگوریتم ژنتیک در حل مسائل با ابعاد واقعی را دارد. در ادامه مسئلهی فوق را در بخش فروش شرکت تولیدی بریان گوشت پیاده سازی کرده ایم.
واژههای کلیدی : مسئله مسیریابی ویزیتورها، تعادل بار کاری، الگوریتم ژنتیک، الگوریتم کلونی مورچگان
عنوان فهرست مطالب صفحه
فهرست جداول …………………………………………………………………………………………………………….. ث
فهرست اشکال ……………………………………………………………………………………………………………… ج
فصل اول: مقدمه و کلیات پژوهش………………………………………………………………………. 1
1-1- مقدمه …………………………………………………………………………………………………………………… 2
1-2- تعریف موضوع ……………………………………………………………………………………………………… 3
1-3- بیان مساله……………………………………………………………………………………………………………….. 5
1-4- ضرورت انجام تحقيق………………………………………………………………………………………………. 6
1-5- اهداف تحقیق………………………………………………………………………………………………………….. 6
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- جمع بندی

دسته‌ها: No category

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

background