عنوان پایان‌نامه
حل مساله مسیریابس وسایل حملو نقل با سرعت وابسته به زمان سفر
- رشته تحصیلی
- مهندسی سیستم های اقتصادی - اجتماعی
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس 2 فنی شماره ثبت: 2187;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 55047
- تاریخ دفاع
- ۰۳ مهر ۱۳۹۱
- دانشجو
- ریحانه توکلی
- استاد راهنما
- فریبرز جولای
- چکیده
- امروزه برنامه‌ریزی حمل ونقل یکی از بخش‌های مهم و شناخته شده در لجستیک و سیستم‌های توزیع کالا می‌باشد که بهبود آن منجر به کاهش چشمگیری در بهای تمام شده کالاها می‌گردد، به همین دلیل از حدود نیم قرن پیش تاکنون محققان بسیاری مسئله مسیریابی وسایل حمل و نقل را مورد مطالعه قرار داده‌اند. مرور ادبیات انجام شده حاکی از این امر است که در اکثر تحقیقات، سرعت وسایل نقلیه میان مشتریان ثابت و هزینه‌های حمل و نقل تنها وابسته به مسافت پیموده شده و تعداد وسایل بکارگرفته شده، فرض شده است. دو فرض مذکور در اکثر موارد منجر به جواب‌هایی خواهد شد که با مسائل دنیای واقعی تطابق چندانی ندارند بنابراین در این پژوهش به بررسی دو مسئله در حوزه لجستیک معکوس پرداخته می‌شود که هدف آنها کمینه‌سازی وسایل بکارگرفته شده و هزینه‌های مربوط به مصرف سوخت وابسته به مسافت، بار و سرعت می‌باشد. در این مسائل دریافت و تحویل کالا به مجموعه‌ای از مشتریان باید در بازه‌های زمانی خاصی در مکان هر مشتری تنها در یک بازدید و توسط یک وسیله از ناوگان وسایل نقلیه صورت گیرد و در انتها کالاهای دریافت شده از مشتریان توسط وسایل به یک سایت خاص جهت بازیافت تحویل داده شوند. در یکی از دو مسئله مذکور سرعت وسایل ثابت و در دیگری وابسته به زمان سفر در نظرگرفته می‌شود. با توجه به پیچیدگی محاسباتی مسائل مسیریابی، فقط مسائل کوچک را می‌توان در یک زمان معقول با روش¬های دقیق حل کرد بنابراین برای حل مسائل در ابعاد بزرگ یک الگوریتم شبیه‌سازی تبرید جمعیت محور به همراه شیوه جدیدی برای نمایش جواب‌ها بکارگرفته شده است که در آن بمنظور افزایش پراکندگی و فرار از بهینه محلی در شروع الگوریتم، جمعیتی از جواب‌ها تولید و در هر تکرار به جستجوی همسایگی‌های چندین جواب پرداخته خواهد شد. آزمایش‌های صورت گرفته بر روی مسائل استاندارد موجود در ادبیات موضوع برای هر دو نوع مسئله نشان می‌دهد که رویکرد ارائه شده منجر به تولید جواب‌های باکیفیت‌تر نسبت به الگوریتم شبیه‌سازی تبرید کلاسیک می‌شود.
- Abstract
- Transportation programming is one of the significant and well known section in logistic and distribution systems that improving it have good effect on transportation cost so many researcher have studied vehicle routing problem about half decade. According to literature review, most research consider that speed of vehicles is constant and transportation cost depends on only distance traveled and number of used vehicles. These two consideration result in solutions that are not compatible for real world problems. Hence in this research, two problems that occur in reverse logistic have been studied that their objective is minimization of number of used vehicles and fuel consumption and fuel consumption depend on load, distance and speed. In these problems each customer must be visited only once and by only one vehicle for both delivery and pickup demands in a certain time interval (time window) and finally all pickup demands must be transported to the recycling or disposal site. In one of the problems, speed is constant and in other it depends on not only the departure time of vehicle from origin customer but also it can changes during traversing related route satisfying FIFO property. Because vehicle routing problems are NP-hard, exact algorithms can solve only small-scale problems in rational time. In this study a metaheuristic algorithm namely population based simulated annealing (PSA) and a new form for solution representation have been applied that starts with more than one solution and in every neighborhood search, it searches neighborhoods of some solutions to search wide solution space and escape from local optima. Finally a comparison between basic SA and PSA is done by test both of them on revised Solomon’s benchmark for both problems. The comparison shows that PSA could find better solution than basic SA.
