عنوان پایان‌نامه
طراحی وحل مدل چند هدفه مسیریابی دورهای وسایل نقایه با استفاده از یک الگوریتم فرا ابتکاری کارامد
- رشته تحصیلی
- مهندسی صنایع
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس 2 فنی شماره ثبت: 1900;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 48147;کتابخانه پردیس 2 فنی شماره ثبت: 1900;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 48147
- تاریخ دفاع
- ۱۸ بهمن ۱۳۸۹
- دانشجو
- امیر محمد ظهره وند
- استاد راهنما
- رضا توکلی مقدم
- چکیده
- برنامهریزی حمل و نقل ، امروزه یکی از زمینههای اساسی در شاخه مختلف علوم همانند تحقیق در عملیات ، مهندسی صنایع ، مهندسی عمران ، مدیریت سلامت و غیره به شمار میرود. هدف عمده این رشته عبارت است از ، کمینهسازی هزینه حمل و نقل کالا و مواد بین دو سطح تولیدکننده و مصرف کننده به طوریکه تقاضای هر مصرف کننده برآورده گردد. مسأله حمل و نقل در صورتیکه بدنبال تولید یک تور یا مجموعه تورها بر روی شبکه با هدف بهینه ساختن یک یا چند تابع هدف باشد را مسأله مسیر یابی مینامند. اجزای یک مسأله مسیریابی عبارتند از شبکه ، تقاضا ، جریان ، هزینه و اهداف. مسأله فروشنده دورهگرد شناخته شدهترین مسأله مسیر یابی به شمار میرود. با تعمیم مسأله فروشنده دوره گرد ، در صورتیکه تعداد فروشنده(وسیله نقلیه ، ...) بیشتر از یک باشد ، مسألهای جدید به نام مسیریابی وسیله نقلیه ایجاد میشود. این مسأله ، یکی از چالش برانگیزترین مسایل بهینهسازی ترکیبیاتی به شمار میرود. بیان ساده این مسأله عبارتست از سرویس دهی مجموعهای از مشتریها با تقاضای ثابت و قطعی از انبار مرکزی توسط ناوگان وسائل نقلیه. مسأله VRP دامنه زیادی از مسایل را به واسطه حالات بسیار خود در بر میگیرد. مسأله مسیریابی دورهای وسائل نقلیه حالت خاصی از VRP محسوب میشود که در آن دوره برنامهریزی از یک روز به T روز افزایش مییابد. پیچیدگیهای مسایل واقعی عموما کاربرد مسایل تکهدفه را به چالش میکشد و با استناد به دانستههای ما ، تاکنون مسأله PVRP در حالت چندهدفه مورد بررسی قرار نگرفته است. با توجه به تعلق مسأله به کلاس NP-Hard ، حل آن توسط روشهای سنتی بسیار هزینه بر بوده و عملا در مسایل با اندازه بزرگ فاقد کارکرد میباشد. لذا استفاده از روشهای ابتکاری و فراابتکاری مورد استفاده قرار میگیرند.پیشنهاد و طراحی این پایان‌نامه با عنایت به موارد بالا و با هدف فائق آمدن به معضلات فوق صورت گرفته است. در این رساله ابتدا یک مدل سه هدفه طراحی گردیده است . از نکات حائز اهمیت مدل پیشنهادی به کارگیری محدودیت میلر- تاکر- زمیلین برای حذف زیر تورهاست. سپس یک الگوریتم جستجوی ممنوع برای حل مدل ارائه شده طراحی و اجرا گردیده است .
- Abstract
- Transportation Planning” is one of the hot major in different scientific areas such as Operations Research, Industrial Engineering, Civil Engineering, Healthcare Management and etc. The main objective is “minimizing the total transportation cost” among supplier to the client in the way that demand of each client must be satisfied. When the “Transportation Problem” tries to generate a tour or a set of sub tours aiming to optimize some objectives, then it is called “Routing Problem”. Routing Problem consists of 5 components as: Network, Demand, Fleet, Cost and the Objectives. One of the most famous examples of “Routing Problem” is “Traveling Salesman Problem” abbreviated as “TSP”. When there is more than one server (server such as vehicle), then “TSP” is converted to a new problem called “Vehicle Routing Problem” or “VRP”. This is one of the most challenging problems in the area of “Combinatorial Optimization”. A very simple definition of “VRP” is: Given a set of customers with known demands that must be satisfied by a fleet of vehicle based at a central depot”. In some distribution systems, planning is not a “one day” period rather there is a “T- day” period and also customer has a known delivery frequency through this “T-day” period. The recent problem is known as the “Periodic Vehicle Routing Problem” or “PVRP”. Since the real-world situation limits the ability of single objective optimization approach to model the events, the present thesis developed the concept of PVRP to the multi objective optimization. Regarding the complexity of this problem, classical optimization methods will not be useful in the medium to large size of the problem. So, the thesis introduced a new hybrid meta heuristic base on Tabu Search and Genetic Algorithm. The validity of both proposal model and algorithm studied in this thesis. To the best of the author’s knowledge this thesis is the first multi objective PVRP. Another contribution of the thesis is “applying Miller-Tucker Zemillin sub tour elimination constraint”.
