عنوان پایان‌نامه
طراحی و حل یک مدل فراگیر مسیر یابی وسایل نقلیه با استفاده از یک الگوریتم فراابتکاری کارآمد
- رشته تحصیلی
- مهندسی صنایع
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس 2 فنی شماره ثبت: 1776;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 44978
- تاریخ دفاع
- ۲۶ تیر ۱۳۸۹
- دانشجو
- کوشا رفیعی درمیان
- استاد راهنما
- رضا توکلی مقدم
- چکیده
- مسیریابی وسایل نقلیه یک مسئله بهینه سازی ترکیبیاتی مهم و از نظر محاسباتی دشوار است. نسخه اصلی آن به شکل زیر تعریف می شود: یک مجموعه از مشتری ها با تقاضاهای ثابت و قطعی که می بایست از انبار مرکزی توسط یک ناوگان از ماشین های انتقال دهنده مشابه با ظرفیت مشخص براورده شوند. به طور معمول هدف VRP حداقل نمودن کل مسافت طی شده توسط ناوگان است، اما حداقل نمودن سایر اهداف از جمله کل هزینه حمل و نقل و یا کل تعداد ماشین های مورد استفاده نیز رایج است. اما تحقیقات انجام گرفته در زمینه VRP به برای تمرکز بر روی مدل های ایده آلگرا با مفروضات غیر واقعی در کاربردهای عملی، مورد انتقاد قرار گرفته اند. در نتیجه، محققان به متغیرهایی روی آورده اند که پیش از این توجه به آن سبب دشواری حل مسئله شده است. این دسته از متغیرها شامل جنبه هایی است که برای مسئله مسیریابی وسایل نقلیه در دنیای واقعی ضروری است. هدف اصلی این پایان نامه بررسی جنبه های تئوری و عملی مسئله فراگیر مسیریابی وسایل نقلیه که به برخی از پیچیدگی های کاربردی آن در ادبیات موضوع بدان ها کمتر پرداخته شده است، می باشد. که عبارتند از دوره های چندگانه، محدودیت های پنجره زمانی، یک ناوگان غیر یکسان از ماشین ها، سفارشات همراه با تجدید و تحویل، و تقسیم تحویل است. از آنجاییکه تطبیق هر چه بیشتر یک مدل ریاضی با شرایط واقعی مستلزم فزونی متغیرها و محدودیت ها است، حل این مدل توسط روش های سنتی بهینه سازی نیازمند صرف زمان، حافظه و قدرت پردازش بالا بوده و تنها می توان مسائلی با ابعاد کوچک را به این شیوه حل نمود. لذا بکارگیری روش های فراابتکاری نه تنها امکان حل مسائلی با ابعاد بزرگ را فراهم می کند بلکه یافتن جواب های نزدیک بهینه را نیز در زمان بسیار کوتاه میسر می نماید. در این پایان نامه یک الگوریتم بهینه سازی انبوه اجزا برای حل مدل ریاضی پیشنهادی، طراحی شده و مسائلی بصورت نمونه و با ابعاد مختلف با الگوریتم فوق الذکر حل شده و نتایج بدست آمده مورد تحلیل قرار گرفتند.
- Abstract
- The Vehicle Routing Problem is a combinatorial optimization problem that has some difficulties to solve it. It defines originally in this way: a set of costumers with definite demand which should be met form depot with a homogenous fleet. The most interesting objective for VRP is minimizing the total distance that traveled by vehicles. Moreover, other kind of objectives such as minimizing total cost of system, the number of used vehicle considered. This thesis presents a new mathematical model for a Rich Vehicle Routing Problem (RVRP) considering several assumptions that minimizes vehicle travel costs. We incorporate four problems in periodic planning (PVRP), namely a capacitated vehicle routing problem (CVRP), a vehicle routing problem with time windows (VRPTW), Heterogeneous Fleet VRP (HFVRP), vehicle routing problem with simultaneously pickup and delivery (VRPSPD), and vehicle routing problem with split service (VRPSS). As it is a unified model, we impose its computational complexity and are not able to solve such a hard problem by any optimization software in a reasonably computational time, especially for large-sized problems. Thus, we propose a meta-heuristic method based on particle swarm optimization (PSO). A number of instances are solved by this proposed PSO. Finally, the related results are illustrated.
