دانشکده فنی – مهندسی
گروه مهندسی صنایع
پایان‌نامه جهت اخذ درجه کارشناسی ارشد مهندسی صنایع
عنوان:
حل مسئله مسیریابی وسایل نقلیه چند انبار با پنجره زمانی با استفاده از یک الگوریتم فرابتکاری کارآمد
دانشجو:
نصیبه شکری خوشرودی
استاد راهنما:
آقاي دکترمحمد میرابی
استاد مشاور:
آقاي دکتر احمد صادقیه
پائیز 1392
تقدیم به خدایی که در این نزدیکی است…
واز من به من نزدیک‌تر است
خدایی که همیشه و همه جا دستانم را گرفته است.
تقدیم به پدر و مادر عزیزم
که حضرت دوست آنان را برای حفاظتم در زمین گمارد
تا راهنمایم باشند و یاریم کنند در آنچه امروز هستم
و می‌خواستم باشم.
و
تقدیم به پاکانی از جنس دیگر
که وقتی در قهقرای زندگی گم شدم
شفاعتم کردند
تا خداوند دستانم را محکم‌تر بفشارد…
تقدیر و سپاس از اساتید بزرگوار و ارجمند
جناب آقای دکتر محمد میرابی، استاد راهنما
وجناب آقای دکتر احمد صادقیه، استاد مشاورم
به پاس همه همفکری‌ها و حمایت‌های بی‌دریغ و صمیمانه‌اشان.
چکیده
در طی سال‌های گذشته، تلاش‌های زیادی به جهت کاهش هزینه حمل و نقل با استفاده از مدل‌های متفاوت مسأله مسیریابی وسیله نقلیه صورت گرفت. در واقع افزایش در هزینه های حمل و نقل بسیاری را تشویق کرد که هزینه حمل و نقل مرتبط با حرفه خود را با بهره‌گیری از سیستم مسیریابی وسیله نقلیه کاهش دهند. در این تحقیق ما مسأله مسیریابی وسیله نقلیه چند انبار با پنجره زمانی را مورد بررسی قرار می‌دهیم.
مسأله مسیریابی وسایل نقلیه چند انبار با پنجره زمانی شامل ناوگانی از وسایل نقلیه می‌باشد که از انبارها حرکت نموده، دسته‌ای از مشتریان را ملاقات کرده و به انبار بر می‌گردند. ما در این تحقیق حالتی را در نظر گرفته ایم که دیگر نیازی نمی‌باشد هر وسیله نقلیه بعد از ملاقات مشتریان به انبار شروع حرکت برگردد بلکه ممکن است انبار ابتدای مسیر با انبار انتهای مسیر متفاوت از یکدیگر باشند. هر وسیله نقلیه دارای یک ظرفیت ثابت است، و هر مشتری دارای تقاضای مشخص است که باید کاملا ارضا شود. مسأله شامل ترکیب انتخاب ملاقات برای هر مشتری و تعیین مسیرهای وسایل نقلیه براساس قوانین مسأله مسیریابی وسیله نقلیه است؛ بطوریکه کل مسافت طی شده توسط هر وسیله نقلیه و کل زمان‌های زودکرد و دیرکرد و در مجموع کل هزینه کمینه شود.
از آنجائیکه مسأله مسیریابی وسیله نقلیه یک مسأله متعلق به کلاس NP-Hard است مسأله مسیریابی وسیله نقلیه چند انباره با پنجره زمانی نیز به عنوان تعمیمی از VRP جزء مسائل پیچیده و متعلق به کلاس NP-Hard است و برای حل آن از رویکردهای فراابتکاری استفاده می‌شود. در این پایان‌نامه الگوریتم ژنتیک برای حل مسأله مسیریابی وسیله نقلیه چند انباره با پنجره زمانی پیشنهاد شده است. وسعی شده است با استفاده از روش خوشه بندی ژنتیک، مشتریان را دسته‌بندی کرده تا فضای جستجوی مسأله را کاهش داده و سپس با استفاده از الگوریتم ژنتیک مجموعه جواب و تابع هدف مسأله را بدست می‌آ‌وریم.
کلمات کلیدی: مسیریابی وسایل نقلیه، چند‌انبار، پنجره زمانی، خوشه‌بندی، الگوریتم ژنتیک
فهرست مطالب
عنوان صفحه
فصل اول:کلیات تحقیق1
1-1مقدمه2
1-2- ضرورت و اهمیت برنامه ریزی حمل‌ونقل3
1-3- حمل‌ونقل در ایران4
1-4- هدف از انجام مطالعه5
1-5- تعریف مسأله6
1-6- جمع‌بندی و ساختار ارائه مطالب7
فصل دوم:ادبیات تحقیق9
2-1-مقدمه10
2-2- مسأله مسیریابی10
2-3- مسأله فروشنده دوره‌گرد10
2-4- مسأله مسیریابی وسایل نقلیه13
2-5- اجزای مسأله VRP14
2-5-1- خصوصیات کلی مشتریان14
2-5-2 خصوصیات وسایل نقلیه15
2-5-4- انواع توابع هدف در VRP16
2-5-6 برخی مشکلات مدل‌سازی VRP در شرایط واقعی16
2-6- تعریف ریاضی مسأله مسیریابی وسیله نقلیه در حالت کلی17
2-6-1 مدل عمومی مسأله VRP18
2-7-روشهای حل مسأله مسیریابی وسایل نقلیه کلاسیک20
2-7-1-روش‌های دقیق20
2-7-2-روشهای ابتکاری22
2-7-3-روشهای فراابتکاری24
2-8- انواع اصلی مسأله مسیریابی وسیله نقلیه26
2-8-1 مسیریابی وسیله نقلیه باظرفیت محدود وسایل نقلیه27
2-8-2-مسأله مسیریابی وسایل نقلیه با ناوگان ناهمگن28
2-8-3-مسأله مسیریابی وسایل نقلیه با تقسیم تحویل30
2-8-4- مسیریابی وسیله نقلیه با تحویل و جمع آوری33
2-8-5- مسأله مسیریابی دورهای وسایل نقلیه34
2-8-5-1 تعریف ریاضی مسأله مسیریابی دوره ای وسایل نقلیه (PVRP)35
2-8-5-2- مدل ریاضی PVRP37
2-8-6- مسأله مسیریابی وسایل نقلیه با چند انبار41
2-8-6-1-تعریف ریاضی مسأله MDVRP42
2-8-7- مسأله مسیریابی وسایل نقلیه با پنجره زمانی44
2-8-7-1 تقسیم بندی مسأله VRPTW45
2-8-7 -1-1 مدل های پنجره‌‌هاي زمانی سخت46
2-8-7-1-2- مدل های پنجره‌هاي زمانی نرم46
2-9- جمع‌‌بندی53
فصل سوم:روش تحقیق55
3-1 مقدمه56
3-2 خصوصیات و فرضهای مدل56
3-2-1-فرضیات56
3-2-2 تعریف علائم و پارامترها56
3-2-2-1 اندیسها57
3-2-2-2 پارامترها57
3-2-2-3 متغیرهای تصمیم‌گیری58
3-2-2-4 مدل ریاضی58
3-3 مروری بر الگوریتم ژنتیک (GA)60
3-3-1 تعریف60
3-3-2 گذری بر ژنتیک طبیعی61
3-3-3 واژگان الگوریتم ژنتیک66
3-3-4 ساختار کلی الگوریتم ژنتیک67
3-3-5 مفاهیم کلیدی الگوریتم ژنتیک68
3-3-6 کدینگ69
3-3-7 ایجاد جمعیت اولیه71
3-3-8 اعمال ژنتیک71
3-3-8 -1 عمل تحول72
3-3-8 -1 -1فضای نمونه گیری72
3-3-8 -1 -2مکانیسم نمونه‌گیری73
3-3-8 -1-4 نخبه گرایی75
3-3-8 -2 عملگرهای ترکیبی75
3-3-8 -2 -1 انواع عملگرهای ترکیبی75
3-3-8 -2 -2 احتمال ترکیب78
3-3-8 -3 عملگرهای جهشی79
3-3-8 -3 -1 انواع عملگرهای جهشی80
3-3-9 تابع برازش81
3-3-10 روش اجرای الگوریتم ژنتیک82
3-4 ساختار پیشنهادی الگوریتم ژنتیک84
3-4 -1خوشه بندی ژنتیک84
3-4 -1-1 نمایش رشته(کروموزوم)84
3-4-1 -2 ساخت جمعيت اوليه85
3-4-1 -3 محاسبه تابع برازش85
3-4 -1-3 انتخاب85
3-4 -1-4 ترکیب86
3-4 -1-5 جهش86
3-4 -1-6 شرط توقف87
3-4-2 الگوریتم ژنتیک87
3-4-2 -1 نحوه نمایش جواب‌ها87
3-4-2 -2 تعریف میزان برازندگی88
3-4-2 -3 مکانیزم انتخاب89
3-4-2 -3 عملگر ترکیب89
3-4-2 -4 عملگر جهش91
3-5 الگوریتم K-Mean92
3-6 الگوریتم خوشه‌بندی فازی (FCM) Fuzzy c-mean92
فصل چهارم:جمع‌آوری و تحلیل داده‌ها95
4-1 مقدمه96
4-2 ویژگی های نرم افزار96
4-3 مشخصات مسائل نمونه96
4-4 تعیین پارامترها97
4-5 نتایج محاسباتی97
4-6 جمع بندی102
فصل پنجم:نتیجه گیری103
5-1 نتیجه گیری104
5-2 تحقیقات آتی104
منابع ومآخذ106
فهرست جداول
جدول 1-1- مقایسه ارزش بخش حمل‌ونقل در تولید ناخالص ملی کشور در فاصله سال های 1370 و 1386 به قیمت های ثابت (میلیارد ریال)4
جدول 2-1 مروری بر ادبیات مسأله مسیریابی وسیله نقلیه با پنجره زمانی51
جدول 3-1 مقایسه الگوریتم ژنتیک با فرآیند تکامل طبیعی (ژن و همکاران،1997)65
جدول 4-1-مقادیرپارامترهای الگوریتم ژنتیک97
جدول 4-2 جوابهای بدست آمده از روش های خوشه بندی K-Means و FCM و GA98
جدول 4-3- جواب های بدست آمده در حالتهای با برگشت به انبار اولیه و بدون برگشت به انبار اولیه101
فهرست اشکال
شکل 1-2- شبکه حمل‌ونقل چند هدفه و مثال های اساسی آن (ظهرهوند،2011)5
شکل 2-1- نمایی از مسأله فروشنده دوره گرد TSP(ظهره وند،2011)11
شکل 2-2- نمایی ساده از مسأله MTSP(ظهره وند،2011)11
شکل 2-3- مسأله VRP(ظهره وند،2011)12
2-5-3- خصوصیات مسیرها15
شکل 2-4- مسأله PVRP( ظهره وند،2011)36
شکل 2-5-سرویس دهی در حالت TW سخت46
شکل 2-6- سرویس دهی در حالت TW نرم47
شکل2-7 ساختار کلی کار انجام شده53
شکل 3-1 تئوری داروین (ژن و همکاران،1997)63
شکل 3-2- فضای کدینگ و فضای جواب (ژن و همکاران،1997).70
شکل 3-3- قانونمند و موجه بودن(ژن،1997)70
شکل 3-4-ماتریس نمایش جواب88
شکل 3-5-شکل دیگر ازماتریس نمایش جواب88
شکل 4-1مسیربهینه به روشGA در p0399
شکل 4-2 مسیربهینه به روشK-means در p0399
شکل 4-3 مسیربهینه به روشFCMدر p03100
فصل اول
کلیات تحقیق
1-1- مقدمه
توسعه روز‌افزون شهر نشینی، صنایع و بخصوص صنایع پشتیبانی، جابجایی انسان و کالا را به صورت مسأله‌ای در آورده است که پیچیدگی آن دائماً در حال افزایش می‌باشد. رشد شهری باعث افزایش تقاضا در صنعت حمل و نقل شده که به تبع آن شهرها و صنایع بزرگ را دست به گریبان مشکلات زیادی در زمینه‌های تراکم ترافیکی، آلودگی هوا، اتلاف وقت‌های طولانی در مسیر سفرهای روزانه افراد، افزایش مصرف سوخت و استهلاک وسایل نقلیه و غیره کرده است.
برای حل مشکلات ترافیکی و مسایل اقتصادی، اجتماعی و زیست محیطی ناشی از آن در شهرهای بزرگ، صنایع تولیدی و بخش خدمات نیاز به یک سیستم مجهز و کارآمد حمل و نقل می‌باشد. در نتیجه تقاضای رو به افزایش برای راه‌حل‌هایی که اجرایی باشند و بتوانند تمامی منافع پیش‌بینی شده از جمله صرفه‌جویی در هزینه‌ها را با در نظر گرفتن حداکثر سرویس و استفاده بهینه از سرمایه و تجهیزات را حاصل نمایند وجود دارد. حمل و نقل داخل سازمانی، مسیر حرکت اتوبوس‌ها، سرویس‌های مدارس، سیستم‌های توزیع و نگهداری پخش پول و سرویس‌های بانکی و جمع‌آوری ضایعات صنعتی و غیره از جمله مسایلی هستند که می‌توان به آنها اشاره کرد.
برنامه ریزی حمل و نقل، امروزه یکی از زمینه‌های اساسی و مطرح در شاخه‌های مختلف علوم همانند تحقیق در عملیات، مهندسی صنایع و مهندسی عمران می‌باشد. هدف عمده این رشته، کمینه‌سازی هزینه حمل و نقل کالا و مواد بین دو سطح تولیدکننده و مصرف کننده می‌باشد، به طوری که تقاضای هر مصرف‌کننده باید توسط تولیدکنندگان ارضاء گردد. در این حالت با توجه به نوع مسأله مورد نظر عواملی همانند طول مسیر، کیفیت مسیر از لحاظ ساختاری و محیطی، ترافیک مسیر، گنجایش وسایل نقلیه و غیره مد نظر قرار می‌گیرند. چنانچه علاوه بر دو سطح تولید کننده و مصرف کننده، سطوح میانی نیز وجود داشته باشند، به آن شبکه حمل و نقل گفته می‌شود. به عنوان نمونه مسیریابی اتوبوس‌های داخل شهری حالت خاصی از شبکه حمل و نقل می‌باشد.
1-2- ضرورت و اهمیت برنامه‌ریزی حمل‌ونقل
حمل و نقل یکی از بخش‌های عمده و مهم، از اقتصاد هر کشوری به شمار می‌رود و همچنین یکی از مهمترین بخش‌های تشکیل دهنده هزینه تمام شده محصولات نهایی است. توسعه روز افزون شهر‌نشینی، صنایع و بخصوص صنایع پشتیبانی، جابجایی انسان و کالا را بصورت مسأله‌ای در آورده‌است که پیچیدگی آن دائماً در حال افزایش است. رشد شهری باعث افزایش فزاینده تقاضا در صنعت حمل‌ونقل شده که به تبع آن شهرها و صنایع بزرگ را دست به گریبان مشکلات زیادی در زمینه‌های تراکم ترافیکی، آلودگی هوا، اتلاف وقت طولانی در مسیر سفرهای روزانه افراد، افزایش مصرف سوخت و استهلاک وسایل نقلیه و غیره کرده است. برای حل مشکلات ترافیکی و مسایل اقتصادی، اجتماعی و زیست محیطی ناشی از آن در شهرهای بزرگ، صنایع تولیدی و بخش خدمات نیاز به یک سیستم مجهز و کارآمد حمل‌ونقل دارند. در نتیجه تقاضای رو به افزایش برای راه‌حل‌هایی که اجرایی بوده و بتواند تمامی منافع پیش‌بینی‌شده از جمله صرفه‌جویی در هزینه‌ها را با در نظر گرفتن حداکثر سرویس و استفاده بهینه از سرمایه و تجهیزات حاصل نماید، وجود دارد. نظافت خیابان‌ها، حمل‌ونقل داخل سازمانی، مسیرحرکت اتوبوس ها، سرویس مدارس، سیستم‌های توزیع و نگهداری پخش پول و سرویسهای بانکی و جمع آوری ضایعات صنعتی و غیره ازجمله مسایلی است که می توان به آن اشاره کرد.
در دهه‌های اخیر نتایج سودمندی در پروژه‌های بهینه‌سازی، بر مبنای روش‌های تحقیق در عملیات و برنامه‌ریزی ریاضی، در مدیریت موثر تدارک کالا و خدمت‌رسانی سیستم‌های توزیع دیده شده است. تعداد زیادی از کاربردهای واقعی جهانی، هم در آمریکای شمالی و هم در اروپا، بطور وسیع نشان داده که استفاده از روال‌های کامپیوتری برای برنامه‌ریزی فرآیند توزیع، صرفه‌جویی قابل توجهی را (معمولاً بین 5% تا 25%) در هزینه‌های عمومی حمل‌ونقل موجب می‌شود. در واقع، فرآیند حمل‌ونقل شامل همه مراحل سیستم‌های تولید و توزیع است. موفقیت بهره‌برداری از تکنیک‌های تحقیق در عملیات مدیون پیشرفت سیستم‌های کامپیوتری هم از نظر سخت‌افزار و هم از نظر نرم‌افزار و افزایش یکپارچگی سیستم‌های اطلاعاتی فرآیندهای تولید و تجاری است. فاکتور دیگر موفقیت که دارای اهمیت فوق العاده‌ای است، پیشرفت ابزارهای مدل‌سازی در سال‌های اخیر است. در واقع، مدل‌های پیشنهاد شده همه مشخصه‌های مسایل توزیع در کاربردهای واقعی، و الگوریتم‌های متناظر و اجراهای کامپیوتری را به حساب آورده و جواب‌های خوبی را برای نمونه‌های واقعی‌ جهانی در مدت زمان معقول پیدا می کند. (تاث وهمکاران،2002).
1-3- حمل‌ونقل در ایران
بخش حمل‌ونقل نیز به عنوان یکی از زیر بخش‌های مهم اقتصادی کشور که تولید آن به قیمت‌های ثابت دارای نرخ رشد بالاتری نسبت به نرخ رشد اقتصاد ملی بوده است، نیاز به توجه بیشتری در نظام مدیریتی کشور دارد. بررسی داده‌های آماری حساب های ملی در بازه ی بین دو مقطع زمانی 1370 تا 1386 نشان می دهد که در این دوره زمانی سهم فعالیت‌های حمل و نقل از تولید ناخالص ملی افزایش یافته است. افزایش سهم نسبی بخش حمل و نقل، انبارداری و ارتباطات از این عملکرد در سطح ملی 8/2 درصد بوده است. جدول (1-1)، مقایسه ارزش حمل و نقل در تولید ناخالص ملی در کشور در سال‌های 1370 تا 1386 را نشان می‌دهد. (شریعت،2004).
بدین ترتیب، در روند تحولات اقتصادی، بخش حمل‌و‌نقل در سال‌های پس از انقلاب، بخصوص حمل‌و‌نقل زمینی، برجستگی بیشتری یافته و تکیه‌گاه اصلی جابجایی بار و مسافر بوده است، لذا با توجه به حجم بالای ارزش افزوده این بخش، اهمیت بیش از پیش بررسی و برنامه‌ریزی حمل و نقل در ایران به منظور تقلیل بخشی از هزینه‌های مربوطه احساس شده و برخورد علمی و منطقی با این مبحث مهم، امری ضروری است.
جدول 1-1: مقایسه ارزش بخش حمل‌ونقل در تولید ناخالص ملی کشور در فاصله سال‌های 1370 و 1386 به قیمت های ثابت (میلیارد ریال)
سال13701375138013821383138413851386قیمت3441139435448584592112758130295169884217048
1-4- هدف از انجام مطالعه
برنامه‌ریزی حمل‌و نقل، امروزه یکی از رشته‌های اساسی و مطرح در شاخه‌های مختلف علوم همانند حمل و نقل در سیستمهای اقتصادی، تولیدی و خدماتی از جایگاه مهمی برخوردار است و بخش قابل‌توجهی از تولید ناخالص ملی هر کشوری را به خود اختصاص میدهد. مسأله مسیریابی وسیله‌نقلیه یکی از مهمترین مسائل برنامه‌ریزي حمل‌ونقل است که امروزه بسیار مورد توجه محققان و دانشمندان قرار گرفته است. هدف در این مسأله برآورده ساختن همه تقاضاها با حداقل هزینه می‌باشد. اگرچه اهداف فرعی تری از جمله حداقل کردن مسافت طی شده، متعادل ساختن مسیر از جهت زمان سفر و حجم بار وسیله نقلیه، حداقل کردن خسارت دیرکرد ارائه خدمت به مشتریان، حداقل کردن تعداد مسافرت‌های هر وسیله نقلیه وغیره می‌باشد. یکی از زیر‌مجموعه‌های برنامه‌ریزی حمل‌و‌نقل، مسأله مسیریابی خودرو1 است،شکل (1-2)، که از مسایل مهم و شناخته‌شده بهینه‌سازی ترکیبی2 است که به دلیل اهمیت و کاربرد زیاد آن، از سال‌ها قبل مورد توجه محققان و پژوهشگران قرار گرفته است.
شکل 1-2: شبکه حمل‌ونقل چند هدفه و مثال‌های اساسی آن (ظهره وند،2011)
در معمول‌ترین شکل این مسأله، هدف بهینه‌سازی نحوه سرویس‌دهی به مجموعه‌ای از مشتریان است که از نظر موقعیت جغرافیایی با هم متفاوت هستند. سرویس‌دهی توسط ناوگان حمل و نقلی که در یک مرکز مستقر هستند، انجام می‌پذیرد. با توجه با قابلیت مسأله مسیریابی خودرو در مدل‌کردن انواع مسایل مطرح در لجستیک سازمان‌ها و به طور اخص سیستم‌های توزیع و یا تأمین آنها توجه به بالا بردن قابلیت‌های مسأله در مدل‌کردن شرایط دنیای واقعی از اهمیت بالایی برخوردار است. به عنوان نمونه، مسیریابی اتوبوس‌های داخل شهری، جمع‌آوری ضایعات، مسیریابی فروشنده دوره‌گرد، و واحدهای تعمیر و نگهداری، حالات خاصی از شبکه حمل و نقل است که از آن می‌توان به عنوان مسأله مسیریابی وسایل نقلیه یاد کرد.
1-5- تعریف مسأله
VRP یک موضوع چالش برانگیز برای بسیاری از محققان از ابتدای معرفی آن توسط دانتزیگ و رامسر برای حل مسأله توزیع کامیون‌ها3 بوده است. انواع روش های بهینه سازی پیشنهاد و مطالعه شده است. همان طور که عنوان گردید، اهمیت و کاربرد زیاد مسأله VRP در دنیای واقعی موجب گردیده است که مطالعه زیادی روی چگونگی مدل کردن انواع مسأله، توسعه فرضیات مسأله برای تطبیق با شرایط کاربردی در دنیای واقعی و همچنین ایجاد یا توسعه روش های حل مسأله به منظور کسب نتایج بهتر انجام پذیرد. این مطالعه نیز با هدف توسعه و ایجاد مدلی برای مسأله VRP، به منظور افزایش قابلیت مسأله در کاربردهای واقعی انجام پذیرفته است.
در این پایان‌نامه، مسأله VRP در حالت چند انباره و با در نظر گرفتن محدودیت پنجره زمانی به منظور در نظر گرفتن کاربردهای واقعی بیشتر مورد بررسی قرار گرفته است که در آن به کارگیری حالتی که انبار اول و آخر مسیر ممکن است متفاوت از هم باشند در نظر گرفته‌شده است و سپس با استفاده از روش خوشه‌بندی ژنتیک برای گروه‌بندی مشتریان و از الگوریتم ژنتیکی برای محاسبه تابع هدف، الگوریتم ترکیبی کارا برای حل ارائه می‌شود. جواب این مسأله شامل یافتن کوتاهترین مسیری که در آن هزینه هر مسیر کمینه شود. در انتها حل مسائل نمونه با استفاده از الگوریتم پیشنهادی ارائه شده است، که با استفاده از نرم افزار متلب کدنویسی و اجرا شده است.
1-6- جمع‌بندی و ساختار ارائه مطالب
فصول پایان‌نامه به شرح زیر تدوین شده‌اند: فصل اول تحقیق به معرفی اجمالی آن اختصاص یافته است. در این فصل مقدمه‌ای بر آشنایی با مسأله مسیریابی خودرو، اهمیت آن، هدف از انجام مطالعه و روش‌های بکار گرفته شده در این مطالعه آورده شده است. در فصل دوم به تعریف مسأله مسیریابی خودرو، تعاریف و نیز سوابق تحقیقات انجام شده پیرامون آن پرداخته شده است. در این فصل ضمن بیان مفاهیم اصلی و ادبیات موضوع مربوط به مسأله VRP که شامل تشریح اجزای مسأله، اهداف و محدودیت‌های آن می‌باشد، انواع حالت‌های خاص مسأله و انواع روش‌های آن و تحقیقات انجام شده پیرامون آنها ارایه شده است. در فصل سوم تحقیق، مدل پیشنهادی برای نوع خاصی از مسأله VRP تشریح شده است. سپس در همین فصل، الگوریتم فراابتکاری ژنتیک، برای حل مسأله مورد نظر ارائه می‌گردد. نتایج محاسباتی الگوریتم پیشنهادی با استفاده از نرم افزار مربوطه، در فصل چهارم مورد بررسی قرار می گیرد. سر انجام در فصل پنجم، با جمع‌‌بندی مطالب ارائه شده در تحقیق و نتیجه گیری کلی، پیشنهادها و توصیه‌هایی برای انجام مطالعات بعدی روی موضوع تحقیق آورده ارائه خواهد شد.
فصل دوم
ادبیات تحقیق
2-1-مقدمه
هدف از این بخش آشنایی با مدل‌های پایه‌ای مسیریابی، همچون فروشنده دوره‌گرد، مروری بر مدل‌های متنوع مسیریابی وسایل نقلیه، عوامل تاثیرگذاردر مدل‌ها و توابع هدف مختلف مطرح شده در این حوزه می‌باشد. در ادامه این بخش به طور خاص به بررسی کارهای انجام گرفته در مسیریابی وسایل نقلیه با چندین انبار و مسیریابی وسایل نقلیه با پنجره زمانی و ترکیب این دو پرداخته خواهد شد. شناخت کامل مسأله مسیریابی و مشتقات آن تاثیر به سزایی در افزایش توانایی و همچنین سهولت در رویه مدل‌سازی موارد واقعی دارد.
2-2- مسأله مسیریابی
هر مسأله که بدنبال تولید یک تور یا مجموعه‌ای از تورها بر روی یک شبکه یا زیر‌شبکه با هدف بهینه ساختن یک یا چند تابع هدف می‌باشد را مسأله مسیریابی گویند. تمامی این مسائل به نوعی یک حالت خاص از مسأله فروشنده دوره‌گرد به شمار می‌روند. در حقیقت با استفاده از این مسأله بدنبال مدل‌سازی موارد حقیقی هستیم (تاث و همکاران،2002). اجزای یک مسأله مسیریابی عبارتند از: شبکه4، هزینه5، تقاضا6، ناوگان7 و اهداف8.
2-3- مسأله فروشنده دوره‌گرد
مسأله فروشنده دروه‌گرد (TSP)9 یکی از بنیادی‌ترین و مشهورترین مسائل در زمینه حمل و نقل و مسأله مسیریابی می‌باشد. در مسأله فروشنده دوره‌گرد هدف یافتن یک دور، مسیر کامل(تور) برای یک فروشنده دوره‌گرد است که در آن تمامی شهرها (مشتریان) با کمترین هزینه ممکن ملاقات شوند و فروشنده از هر کدام تنها و تنها یک بار عبور نماید، سپس این تور در همان شهر اولیه که سفر از آنجا آغاز شده بود پایان یابد (تاث و همکاران،2002). نمایی از مسأله فروشنده دورهگرد در شکل 2-1 نشان داده شده است.
شکل 2-1: نمایی از مسأله فروشنده دوره گرد TSP(ظهره وند،2011)
حال اگر همین مسأله را با چند فروشنده در نظر بگیریم، مسأله ما تبدیل به مسأله چندین فروشنده دوره گرد (MTSP)10 خواهد شد که در واقع چند فروشنده از یک شهر حرکت کرده و از ملاقات چندین شهر دوباره به همان شهر اولیه باز می‌گردند. در این حالت نیز هر کدام از شهرها باید فقط یکبار مورد ملاقات قرار گیرند (تاث و ویگو،2002). در شکل 2-2 نمایی از مسأله MTSP نشان داده می‌شود.
شکل 2-2: نمایی ساده از مسأله MTSP(ظهره وند،2011)
حال اگر پیچیدگی‌های دنیای واقعی در نظر گرفته شود در عمل با مسائل گسترده‌تری مواجه هستیم که از آن جمله می‌توان به مسائل مسیریابی وسایل نقلیه11VRP اشاره کنیم که در واقع تعمیم مسائل فروشنده دوره گرد TSP، مسأله چندگانه فروشنده دوره گرد MTSP می‌باشد با این تفاوت که در مسأله مسیریابی وسایل نقلیه مایک مبدأ مشخص داریم و برخلاف مسأله چندگانه فروشنده دوره‌گرد ظرفیت وسایل نقلیه بی‌نهایت نیست و همچنین در VRP مشتریان مشخص با میزان تقاضای مشخصی وجود دارد. در اینگونه مسائل هدف این است که تقاضای تمامی مشتریان تأمین شود و هزینه کل مسیر شامل هزینه وسایل نقلیه کمینه شود. بنابراین توضیحات مشخص می‌شود که بنیان مسأله مسیریابی وسایل نقلیه TSP و به طور دقیق تر بر MTSP استوار است. در شکل زیر نمایی از مسأله مسیریابی وسایل نقلیه VRP نشان داده شده است در این شکل qها میزان تقاضای مشتریان بوده و فلش‌های مسیر خودروهای مختلفی را نشان می‌دهند که از انبار مرکزی حرکت کرده و پس از سرویس‌دهی به آن باز می‌گردند.
شکل 2-3: مسأله VRP(ظهره وند،2011)
در ادبیات ثابت شده است که مسأله TSP مربوط به کلاس مسائل NP-Hard است و به این علت مسأله VRP نیز که تعمیمی از مسأله TSP می‌باشد نیز متعلق به همین کلاس مسائل می باشد از اینرو برای حل اینگونه مسائل از روشهای ابتکاری و فرابتکاری بهره جسته می‌شود و تاکنون روش‌های زیادی برای حل اینگونه مسائل توسعه داده شده است.
2-4- مسأله مسیریابی وسایل نقلیه
موضوع مسیریابی وسیله‌نقلیه، یکی از مفاهیم آشنا در زمینه تحقیق در عملیات است که در دو دهه اخیر تلاش‌ها و به دنبال آن پیشرفت‌های بزرگی در این زمینه انجام گرفته است. مسأله مسیریابی وسایل نقلیه به مجموعه‌ای از مسائل اطلاق می‌شود که در آن ناوگانی متشکل از چندین وسیله نقلیه از یک یا چند انبار به ارائه خدمت به مشتریان مستقر در نقاط مختلف جغرافیایی میپردازند و این امر را به نحوی انجام می‌دهند که هزینه‌های انجام این کار به حداقل برسد. در طول این مسیرها مشتریان تنها و تنها یک بار ملاقات می‌شوند و تمام تقاضاهای آنها تنها توسط یک وسیله نقلیه دریافت می‌گردد، هر وسیله دارای ظرفیت معینی است و از سویی تمام مسیرها از یک نقطه مشخص (مبدأ بارگیری) آغاز می‌شوند و پس از آنکه وسیله نقلیه یک سلسله از مشتریان را ملاقات نمود به همان نقطه اولیه باز می‌گردد و مسیر در همان مکان پایان می‌یابد. این‌گونه مسائل به طور کلی به عنوان مسائل مسیریابی وسایل نقلیه ( VRP) یا مسائل برنامه‌ریزی حمل‌ونقل، شناخته شده‌اند. مدل‌ها و الگوریتم‌های معرفی شده برای حل مسائل برنامه‌ریزی و مسیریابی ارائه شده را، نه تنها برای استفاده در مسائل مربوط به پخش و جمع‌آوری کالاها بلکه برای بسیاری از مسائل مختلف صنعت حمل‌ونقل در دنیای واقعی، نیز می‌توان استفاده نمود و به طور عمده مورد استفاده از این دست مسائل به عنوان مثال، در جمع‌آوری زباله‌های خشک، پاکیزه سازی خیابان‌ها، مسیریابی اتوبوس مدرسه، سیستم‌های جابه‌جایی معلولین، مسیریابی فروشنده دوره‌گرد و واحدهای نگهداری و تعمیرات می‌باشد. پخش کالاها در برگیرنده خدمت‌دهی به دسته‌ای از مشتریان، در یک بازه زمانی داده شده توسط دسته‌ایی از وسایل‌نقلیه می‌شود که در یک یا چند مرکز قرار دادند و توسط دسته‌ایی از رانندگان هدایت می‌شوند و جابجایی‌ها در یک شبکه مسیر مناسب انجام می‌شود. به طور خاص، یک حل مسأله مسیریابی وسایل نقلیه تعیین کننده دسته‌ای از مسیرهاست که هر کدام توسط یک واحد وسیله نقلیه انجام می‌شود و از مرکز مربوط به خودش شروع می‌شود و به آن پایان می‌پذیرد. به طوری که نیاز مشتریان برآورده شود، محدودیت‌های عملیاتی ارضا شود و هزینه‌های کلی حمل و نقل حداقل شود. شبکه مسیری است که برای انتقال کالاها استفاده می‌شود. معمولاً به صورت یک گراف معرفی می‌شود که کمانهای آن مسیرها را نمایش می‌دهند. کمانها بر اساس یک طرفه یا دو طرفه‌بودن به ترتیب به دو دسته مستقیم یا غیر‌مستقیم تقسیم می‌شوند به هر کمان هزینه‌ای مربوط است که معمولا بر اساس طول مسیر یا زمان طی‌کردن آن مسیر بیان می‌شود که می‌تواند به نوع وسیله نقلیه یا دوره زمانی که در آن مسیر طی می‌شود مربوط باشد.
2-5- اجزای مسأله VRP
اجزای مسأله VRP را در شکل معمول و شناخته شده آن می‌توان به مجموعه مشتریان، مجموعه وسیله نقلیه (ناوگان حمل و نقل)، و مسیرها تقسیم‌بندی کرد. هر یک از این اجزا دارای خصوصیاتی هستند که بعنوان فرضیات مسأله یا پارامترهای ورودی آن بایستی مورد توجه قرار گیرد. شرح این خصوصیات در زیر آورده شده است.
2-5-1- خصوصیات کلی مشتریان
مکان هر مشتری: با گره در گراف شبکه مسیرها نشان داده می‌شود. مختصات مکان مشتری در صورت لزوم برای محاسبه فاصله-زمان و یا هزینه سفر بین گره‌ها استفاده می‌شود.
مقدار تقاضای مشتری: معرف مقدار کالایی است که باید به مشتری تحویل داده شود، یا از محل مشتری جمع‌آوری گردد.
زمان خدمت به مشتری : مدت زمانی است که وسیله نقلیه در محل مشتری برای ارائه خدمت به آن توقف می کند. زمان خدمت را می‌توان بصورت تابعی از تقاضای مشتری هم تعریف کرد.
مجموعه وسایل نقلیه قابل استفاده برای مشتری: زیر مجموعه ای از وسایل نقلیه است که امکان خدمت‌دهی به مشتری را دارند.
بازه زمانی سرویس: بازه زمانی است که خدمت‌دهی به مشتری بایستی انجام پذیرد.
2-5-2- خصوصیات وسایل نقلیه
تعیین مبدا حرکت وسایل نقلیه: انبار محلی است که وسایل نقلیه از آنجا مسیر حرکت خود را آغاز کرده و در انتها نیز به انبار برمی‌گردند و امکان اینکه آیا در پایان به همان انبار یا به انبار دیگری بر‌می‌گردند.
ظرفیت وسیله نقلیه: بعنوان یکی از پارامترهای ورودی مسأله در محدودیت‌های مسأله مطرح می‌شود. ظرفیت خودروها می‌تواند یکسان یا متفاوت باشد (که به حداکثر وزن یا حجم یا تعداد دسته‌هایی که هر وسیله می‌تواند بارگیری نمایدمشخص می‌شود)
ابزار مورد نیاز برای عملیات بارگیری و تخلیه (بارگذاری) وسیله نقلیه
محدودیت‌های مربوط به میزان استفاده از خودرو (حداکثر زمان- مسافت استفاده)
زیر مجموعه‌ای از شبکه مسیرها که وسیله نقلیه می‌تواند آنها را طی می‌کند.
هزینه‌های مرتبط با استفاده از هر وسیله (بر اساس مسافت، واحد زمان، تعداد مسیرها،…)
2-5-3- خصوصیات مسیرها
هزینه (زمان – مسافت) مربوط به سفر در طول مسیر از ابتدا تا انتها.
یکسان بودن یا نبودن هزینه سفر رفت و برگشت مسیرها.
بعضی از مواقع، ممکن است که به طور کامل تقاضای هر مشتری برآورده نشود، در این مواقع، می‌توان مقداری که باید تحویل داده یا گرفته شود، را کاهش داد و یا اینکه تقاضای زیر مجموعه‌ای از مشتریان را بی‌پاسخ گذاشت برای رویارویی با این مسأله، اولویت‌ها و یا جریمه‌های متفاوتی به کمبودهای کلی و جزئی هر مشتری، تخصیص می‌یابد.
شروع و پایان مسیرهای طی‌شده برای خدمت‌دهی به مشتریان می‌تواند در یک یا چند مرکز باشد هر مرکز با تعداد انواع وسایلی که به آن تخصیص داده شده و مقدار کل کالایی که به آن مربوط است شناخته می‌شود. در بعضی مسائل دنیای واقعی مشتریان از قبل بین مراکز تقسیم می‌شوند و وسایل حمل و نقل باید در انتهای مسیرهایشان به مرکز مربوط به خود باز گردند در این موارد مسأله مسیریابی وسایل نقلیه را می‌توان به چند مسأله مستقل تقسیم نمود که هر کدام به یک مرکز متفاوت مربوط است. حمل و نقل کالاها با به کارگیری دسته‌ایی از وسایل انجام می‌شود که ترکیب و اندازه‌شان می‌تواند ثابت باشد و یا اینکه بر‌اساس نیاز مشتریان تعیین شود.
2-5-4- انواع توابع هدف در VRP
معمولی‌ترین و در عین حال مهم‌ترین هدف مسأله VRP حداقل‌کردن کل هزینه سیستم است. گاهی اوقات به جای حداقل‌کردن هزینه، از معادل‌های آن یعنی کل مسافت طی‌شده توسط وسایل نقلیه یا مجموع زمان استفاده از آنها در تابع هدف استفاده می‌شود. در عین حال در کاربردهای مختلف، اهداف دیگری نیز می‌توان برای مسأله در نظر گرفت. فهرست برخی اهداف مورد توجه برای مسأله در زیر آورده شده است:
حداقل‌کردن هزینه‌های مربوط به ناوگان و سرویس‌دهی شامل: هزینه مسافت کل طی‌شده توسط وسایل نقلیه، هزینه‌های ثابت و متغیر ناوگان مانند اجاره، حقوق، دستمزد، استهلاک،…
حداقل‌کردن تعداد وسایل نقلیه (یا رانندگان) مورد نیاز برای ارائه خدمت به همه‌ی مشتریان.
متعادل ساختن مسیر، از جهت زمان سفر و حجم بار وسیله نقلیه.
حداقل کردن خسارت دیر کرد یا زود کرد ارائه خدمت به مشتریان.
حداقل کردن زیان‌های ناشی از عدم برآورده شدن برخی خواسته‌های مشتریان.
حداقل کردن زیان ناشی از عدم استفاده از کل ظرفیت وسیله نقلیه.
حداقل کردن زیان‌های ناشی از اضافه‌کاری راننده – استفاده بیش از حد از وسیله نقلیه.
استفاده از حداقل تعداد وسایل نقلیه ممکن برای سرویس‌دهی به مشتریان.
توابع هدف می‌تواند ترکیب وزن داری از همه‌ی اهداف مذکور باشد.
2-5-6- برخی مشکلات مدل‌سازی VRP در شرایط واقعی
مسأله مسیریابی وسیله‌نقلیه وقتی در قیاس با دنیای واقعی قرار می‌گیرد با پیچیدگی‌ها و محدودیت‌هایی مواجه می‌شود که مدل‌سازی آن را بسیار متفاوت از مسأله ارائه شده خواهد نمود.
در ادامه نمونه‌ای از این محدودیت‌ها و مشکلات اشاره خواهد شد.
هزینه سفر بین نقاط در مسیرهای رفت و برگشت می‌تواند غیر یکسان (نامتقارن) باشد. (c_ij≠c_ji)
وسیله‌های نقلیه در ناوگان حمل‌ونقل می‌تواند ناهمگن و با ظرفیت‌های متفاوت باشد.
کل مسیرهای طی‌شده و یا زمان کل سرویس‌دهی ممکن است محدود باشد.
زمان سرویس‌دهی و طی مسیرها در ساعات مختلف شبانه روز (مثلا پیک‌های ترافیک) بایکدیگر متفاوت است.(هر کدام در یک بازه زمانی خاص صورت می گیرد).
سرویس‌دهی و توزیع برخی کالاها مانند محصولات فاسد شدنی شرایط خاصی را طلب می کند که باید در دوره‌های زمانی خاص صورت گیرد.
برخی سرویس‌ها باید در ساعات معینی ویا در یک بازه زمانی انجام شوند. مانند سرویس‌دهی سرویس‌های مدارس).
ممکن است انبارهای متعددی داشته باشیم.
زمان ارائه سرویس‌ها، حضور مشتریان و میزان تقاضای آنها می‌تواند احتمالی باشد.
اولویت‌های موجود در تقدم و تأخر بارگیری و تخلیه کالا و محصولات.
تعداد وسایل نقلیه در ناوگان حمل‌ونقل می‌تواند متغیر باشد و یا کل ناوگان اجاره‌ای باشد.
2-6- تعریف ریاضی مسأله مسیریابی وسیله نقلیه در حالت کلی
فرض کنیدG=(V,A) یک گراف کامل باشد به طوریکهV={1,2,…,n} مجموعه نقاط تقاضا و A نیز مبین مجموعه کمان‌ها یا مسیرهای شبکه است که نقاط را به هم متصل می‌کند. رأس i=1,2,…,n به مشتریان باز می‌گردد که هر کدام یک تقاضای مشخص غیر‌منفی دارند (q_i≥0). همچنین رأس 0 به مبدأ باز می‌گردد. یک هزینه غیر‌منفی مرتبط با هر کمان اندازه هزینه‌ی سفر از نقطه ی i به نقطه j را نشان می دهد (همچنین t_ij طول کمان یا فاصله زمانی بین رئوس i و j را نشان می دهد). اگر مقدار هزینه c_ij=c_ji را برای تمامی i و j ها را برقرار سازیم. آنگاه مسأله تبدیل به یک مسأله متقارن VRP تبدیل می‌شود و در غیر اینصورت مسأله نامتقارن است.
مسأله مسیریابی وسیله‌ نقلیه عبارتست از یافتن یک دسته k تایی مسیرهای ساده که هر کدام مرتبط است با مسیر یک وسیله با هدف کمینه‌کردن هزینه مجموعه مسیرها که نکات زیر را شامل می‌شود:
هر کدام از مسیرها از نقطه مبدأ آغاز و در نقطه مبدأ پایان می‌یابد.
هر کدام از مشتریان تنها توسط یک وسیله سرویس‌دهی می‌شوند.
مجموع تقاضای مشتریان که در یک مسیر قرار می‌گیرند نباید از ظرفیت وسیله نقلیه تجاوز کند.
2-6-1- مدل عمومی مسأله VRP
در اینجا به معرفی مدلی می‌پردازیم که توسط گلدن و همکاران در سال 1998 مطرح شد.
پارامترهای ورودی مدل را به این صورت تعریف می‌کنیم:
G=(E,A) گرافی است که شبکه مسیرهای وسایل نقلیه را بیان می‌کند بطوریکه E={1,2,…,n} کلیه نقاط موجود در مدل (مشتریان) A={(i,j):i ,j∈E,i>j} مجموعه کمان‌های اتصال‌دهنده نقاط
n: تعداد نقاط( گره‌ها) تقاضا. (قرار گاه مرکزی در گره i=1 قرار دارد.
V : تعدا وسایل نقلیه در دسترس
w : ظرفیت هر وسیله نقلیه
T_v : حداکثر زمانی که خودروی v می‌تواند طی مسیر کند.
Q_i : تقاضای گره i
C_ij : هزینه سفر(طول فاصله) بین گره‌های i ,j
X: ماتریس با درایه‌های بصورت X_ij= ∑_(v=1)^NV▒X_ij^v
S: زیر مجموعه‌ای از E که در آن E={i⁄i=1,2,…,n} است.
〖X_ij〗^v برابر 1 است که اگر مسیر ij به وسیله خودروی v طی شود درغیر اینصورت 0 است.
Min Z=∑_(i=1)^n▒∑_(j=1)^n▒∑_(v=1)^NV▒〖C_ij X_ij^V 〗
∑_(i=1)^n▒∑_(v=1)^NV▒〖X_ij^V=1〗 ∀j∈{1,2,…,n} (2-1)
∑_(j=1)^n▒∑_(v=1)^NV▒〖X_ij^V=1〗 ∀i∈{1,2,…,n} (2-2)
∑_(i=1)^n▒〖X_ip^v- ∑_(j=1)^n▒〖X_pj^v=0〗〗 p={1,…,n},∀v (2-3)
∑_(i=1)^n▒〖Q_i [∑_(j=1)^n▒X_ij^V ]≤W 〗 (v=1,2….,NV) (2-4)
∑_(j=1)^n▒〖X_1j^V≤1 (v=1,2….,NV)〗 (2-5)
∑_(i=1)^n▒〖X_i1^V≤1 (v=1,2….,NV)〗 (2-6)
∑_(v=1)^v▒∑_(i∈s)▒∑_(j∉s)▒〖X_ij^V≤|S|-r(S)〗 ∀s⊆A-{1},s≠∅ (2-7)
X_ij∈{0,1} , x∈S (2-8)

تابع هدف مسأله هزینه کل مسافت طی شده توسط خودروها را کمینه می کند.
محدودیت (2-1) و(2-2) تضمین می کند که هر گره یا نقطه تقاضا فقط و تنها فقط از یک وسیله سرویس دریافت کنند.
محدودیت (2-3) تضمین می‌کند که اگر خودرویی به گره‌ای وارد شود بایستی از آن خارج گردد و به این ترتیب پیوستگی مسیرها برقرار می‌شود.
محدودیت (2-4) مربوط به حداکثر ظرفیت خودروهاست
محدودیت (2-5) و (2-6) نیز تضمین می‌کند که هر خودرویی باید سرویس خود را از مبدا آغاز ودر همان مکان ختم کند و در غیر اینصورت مورد استفاده قرار نخواهد گرفت (غیرفعال محسوب میشود).
رابطه (2-7) مربوط به حذف زیر‌تورها می‌باشد. محدودیت (2-8) متغیر باینری را ارائه می‌کند.
2-7- روشهای حل مسأله مسیریابی وسایل نقلیه کلاسیک
مسأله مسیریابی وسایل نقلیه در شکل کلاسیک به مسأله مسیریابی وسیله نقلیه با محدودیت ظرفیت12 (CVRP) هم معروف است، سیستم توزیعی را مدل می‌کند که در آن به تعیین چگونگی توزیع کالا بین مشتریانی که از نظر موقعیت جغرافیایی با هم متمایزند توسط مجموعه مشخصی از وسایل نقلیه پرداخته می‌شود. جواب نهایی مسأله مسیرهایی را شامل می‌شود که هر یک ازآنها از یک انبار شروع شده، پس از گذشتن از تعدادی از مشتریان مجددا به مرکز باز می‌گردند. از آنجایی که هر یک از این مسیرها توسط یک وسیله نقلیه بایستی طی شود، لذا مجموعه تقاضاهای مشتریان در یک مسیر از ظرفیت وسیله نقلیه نبایستی تجاوز کند. هدف نهایی مسأله پیدا کردن مجموعه‌ای از مسیرهاست که در آن کلیه مشتریان بازدید شده و مجموع هزینه‌های سیستم توزیع حداقل گردد. گاهی اوقات به جای هزینه مسافت طی شده توسط خودروها، مجموع زمان صرف شده توسط آنها برای سرویس‌دهی به مشتریان لحاظ می‌شود. مقادیر بسیاری از نتایج تحقیقات که در آنها مسائل مسیریابی وسایل نقلیه با ظرفیت محدود بررسی شده‌اند، در قالب تئوری‌ها، روش‌ها، و الگوریتم‌ها ارائه شده‌اند. بطور کلی، روش‌های حل معرفی شده برای CVRP می‌تواند به در قالب روش‌های دقیق13، ابتکاری14، فراابتکاری15 تقسیم‌بندی شوند. مفهوم و موضوعات بحث برانگیز این سه دسته در ادامه بررسی خواهند شد.
2-7-1- روش‌های دقیق
از اصلی‌ترین روش‌های شناخته‌شده در دو دهه اخیر برای حل CVRP است، که در این قسمت معرفی خواهند شد. ابتدا، الگوریتم‌های بر مبنای شاخه و کران16 توضیح داده خواهند شد. سپس، الگوریتم‌های بر مبنای روش شاخه و برش17 بررسی می‌شوند. نهایتاً، الگوریتم‌های بر اساس روش شاخه و بها18 معرفی می‌شوند.
یکی از دیدگاه‌های دقیق به مسأله VRP که توسط فیشر در سال 1994 مطرح گردید الگوریتم شاخه و کران می‌باشد که موفق شده است مسأله‌ای با 71 مشتری را با موفقیت حل نماید. برای حل مسائلی با ابعاد بزرگتر و یا یافتن جواب بهینه در زمان سریع‌تر می‌بایست از الگوریتم‌های ابتکاری بهره گرفت که در ادامه توضیح داده خواهند شد.
منطق الگوریتم شاخه وکران بر این اساس است که از استراتژی تقسیم و غلبه برای تقسیم‌بندی فضای جواب به چند زیر مسأله بهره می‌جوید، و سپس عملیات بهینه‌سازی را روی این زیر مسأله‌ها اجرا می‌نماید. الگوریتم های مختلفی از شاخه و کران برای حل CVRP در دسترس است. تا اواخر دهه 1980، موثرترین الگوریتم شاخه و کران بر مبنای آزاد سازی ترکیبی19 بود، که شامل آن دسته از مسائل بر مبنای مسائل تخصیص20 (AP)، و کوتاهترین درخت جستجو با محدودیت درجه21 می باشند. در روش شاخه و کران بر مبنای مسائل تخصیص روش آزاد‌سازی با فرض حذف محدودیت‌های ظرفیتی صورت می‌پذیرد. مسأله حاصله را می‌توان یک مسأله تخصیص در نظر گرفت و نسبت به حل آن اقدام نمود. مسائل متقارن و نامتقارن را می‌توان با این روش حل کرد. لاپورته وهمکاران در سال 1986 و میلر در سال 1995 این روش را برای حل مسائل CVRP به کار گرفتند. در نوع دوم الگوریتم‌های شاخه و کران بر مبنای کوتاهترین درخت جستجو با محدودیت درجه با استفاده از تحدید شاخه و کران بعد از حذف محدودیت‌هایی که درجه آنها خارج از صورت مسأله است نسبت به حل مسأله اقدام نمود. کریستوفیدز در سال1981 این روش را برای حل مسائل CVRP به کار گرفت. آزاد سازی کیفیت پایینی در حل مسائل ترکیبی دارد به همین دلیل روش‌های آزاد‌سازی براساس مفاهیم لاگرانژ توسعه یافت. بوسیله این روش، مسائل بسیاری را می‌توان حل نمود. تاث و ویگو بر اساس مفاهیم لاگرانژ به حل دقیق مسأله CVRP نمودند (ظهره‌وند،2011) و (قصیری،2007).
روش شاخه و برش از ترکیب یک روش شاخه و کران با روش صفحات برشی ایجاد گردید. در حال حاضر این روش به عنوان بهترین روش دقیق برای حل مسائلVRP مطرح است. در این روش صفحات برش به ازای هر گره به فرمولبندی شاخه و کران اضافه می‌شوند. با این کار، آزاد سازی بهبود یافته و مسأله را می‌توان به کمک یک الگوریتم سیمپلکس به راحتی حل نمود. کاربرد این روش در حل مسائل VRP ابتدا توسط لاپورته و همکارانش در سال 1985 مطرح گردید. سپس در سال 1995 آئگرات و همکارانش نخستین روش شاخه و برش را برای حل چندین نمونه VRP تا حدی که شامل 134 مشتری می‌شد را به صورت کامل توسعه دادند. بالداچی و همکارانش در سال 2004 شکل دیگری از الگوریتم شاخه و برش را پیشنهاد دادند، که در آن آزادسازی برنامه‌ریزی خطی22 (LP) با بکارگیری قوانین گوناگون کاهش متغیر و شاخه‌بندی تقویت شده است.
روش شاخه و هزینه یک روش دیگر برای حل مسائل عدد صحیح بزرگ به شمار می‌رود. این روش بر اساس روش‌های تولید ستون23 ایجاد شده است. مهمترین و شناخته شده‌ترین روش شاخه و هزینه، الگوریتمی است که در سال 2006 توسط فوکوساوا و همکارانش برای حل مسائل مسیریابی وسایل نقلیه با ظرفیت محدود ارائه گردید. روش ارائه شده در حقیقت ترکیبی از روش‌های قبلی که آزاد‌سازی در آن بر اساس توسعه روشی بود که کریستوفیدز و همکارانش ارائه نمودند. این روش حدود کران بهتری نسبت به الگوریتم شاخه و برش ایجاد می‌نماید (ظهره‌وند،2011) و (قصیری،1007).
2-7-2-روش‌های ابتکاری
روش‌های ابتکاری با انجام جستجو نسبی و محدود در فضای جواب، جوابی با کیفیت خوب و در زمان حلی متوسط پیدا می‌نمایند. این الگوریتم‌ها در مسائل عملی بسیاری مورد استفاده قرار می‌گیرند. الگوریتم‌های ابتکاری برای حل مسائل به سه دسته کلی تقسیم می‌شوند:
الگوریتم‌های ابتکاری سازنده : این الگوریتم‌ها از قدیمی‌ترین این روش‌ها به شمار می‌روند. در قدم اول توجهی به هزینه جواب تولید نشده ندارند و به صورت تدریجی جواب موجه را ایجاد می‌کنند.
الگوریتم صرفه‌جویی مطرح شده توسط کلارک و رایت در سال 1964 یکی از الگوریتم‌های مشهور در زمینه VRPکه بر پایه مفهوم صرفه‌جویی عمل می‌کند. این الگوریتم به طور طبیعی در مسائلی کاربرد دارد که تعداد وسایل نقلیه در آنها متغیر بوده و برای هر دو نوع مسائل جهت‌دار و غیر‌جهت‌دار استفاده می‌شود (قصیری،2007).
الگوریتم‌های ابتکاری دومرحله‌ای :این الگوریتم‌ها خود به دو فاز مهم تقسیم می‌گردند:
اول دسته‌بندی رئوس، سپس مسیریابی
اول مسیریابی و سپس دسته‌بندی
در نوع اول ابتدا با رئوس (مشتریان) به دسته‌ها یا گروه‌های موجه تقسیم می‌گردند سپس با تخصیص یک وسیله نقلیه به هر گروه مسیر بهینه برای آن ایجاد می‌کنیم. ژیلت و میلر در سال 1974 برای اولین بار این روش را ارئه نمودند. که به الگوریتم پیمایش نامیده می‌شود. منطق این الگوریتم بر پایه دسته‌بندی رئوس به گروه‌های موجه می‌باشد که توسط دوران یکنواخت یک شعاع چرخشی به مرکز دپو صورت می‌گیرد. سپس در هر دسته با حل یک مسأله TSP، مسیرهای وسایل نقلیه معین می‌گردند. روش بعدی در این فاز روشی است که توسط فیشر و جایکومار در سال 1981 ارائه شده است. در الگوریتم آنها به جای استفاده از روش‌های هندسی برای گروه‌بندی رئوس، از روش تخصیص یافته24(GAP) استفاده می‌نمایند. روش تخصیص بدنبال کمینه کردن هزینه تخصیص هر مورد به دسته است. سپس هر دسته را می‌توان توسط روش ابتکاری یا دقیق حل نمود. در نوع دوم ابتدا یک تور بزرگ برای تمامی رئوس تعیین می‌گردد (مانند تور TSP ) سپس این تور به بخش‌های کوچکتر و موجهی تجزیه می‌شود که هر کدام به منزله یک مسیر برای یک وسیله نقلیه می‌باشد(قصیری،2007).
روش‌های بهبود : این روش‌ها در تلاش هستند تا جواب بهینه یافت شده را بهبود و ارتقا بخشند که این کار توسط تبادل پی در پی رئوس یا کناره‌ها در یک مسیر و یا بین دو مسیر وسیله به طور همزمان می‌گیرد.
بیشتر روش‌های بهبود برای مسأله TSP توسط لین در سال 1965 تحت عنوان مکانیزم λ-opt مطرح گردیده است. در این روش λ کناره از تور حذف شده و سپس مجددا این λ بخش را در تمامی حالت‌های ممکن به هم متصل می‌نماییم (قصیری،2007).
2-7-3-روش‌های فراابتکاری
روش‌های فراابتکاری ابزاری قدرتمند برای حل مسائل بهینه‌سازی به شمار می‌روند. حسن این روش‌ها در مقایسه با روش‌های ابتکاری اینست که فضای جواب بهتر مورد جستجو قرار می‌گیرد و احتمال توقف در بهینه‌های موضعی کاهش می‌یابد. این روش‌ها به سه دسته عمده تقسیم می‌شوند: روش‌های فراابتکاری بر اساس جستجوی همسایگی، روش‌های فراابتکاری براساس جستجوی جمعیت، و روش‌های فراابتکاری براساس شبکه‌های عصبی.
الگوریتم‌های جستجوی همسایگی به صورت متناوب اقدام به جستجوی در فضای جواب می‌کنند تا شرط خاتمه رخ دهد. در دهه گذشته تلاش‌های بسیاری در زمینه استفاده از نگرش جستجوی همسایگی برای حل VRP صورت گرفته است و الگوریتم‌های متنوعی ارائه گردیده است.
اولین الگوریتم‌های ارائه شده، الگوریتم شبیه‌سازی ذوب25 است. استفاده از این الگوریتم در ابتدای دهه 90 بسیار رایج بود. معروفترین روش شبیه‌سازی ذوب توسط عثمان در سال 1993 توسعه یافت. عثمان در الگوریتم خود از الگوریتم ذخیره که توسط کلارک و رایت معرفی شد، برای تولید جواب ‌های اولیه استفاده نمود. این الگوریتم جواب‌های خوبی تولید می‌کرد ولی جواب‌های بدست‌آمده قابل رقابت با جواب‌های حاصله از روش



قیمت: تومان

دسته بندی : پایان نامه ارشد

پاسخ دهید