پایان نامه مسیریابی حمل و نقل کالا با استفاده از الگوریتم ژنتیک

مسیریابی حمل و نقل کالا در زنجیره تامین در شرایط عدم قطعیت با استفاده از الگوریتم ژنتیک

یکی از مسائلی که امروزه در زنجیره تأمین بسیار مطرح است و مطالعاتِ گسترده­ای در زمینه­ ی آن انجام شده، مسأله مسیریابی وسایل نقلیه حامل بار برای تحویل کالا به متقاضیان می­باشد. برای حل این مسأله باید تابع هدفی را بهینه سازی کرد به نحوی که معیارهایی از قبیل مسافتِ طی شده، زمان سفر و تعداد وسایل نقلیه کمینه شود و تابع هدف حداقل گردد و در نهایت رضایت مشتریان به حداکثر برسد. این مسأله از نوع NP-hard است و اغلب برای حل آن­ از روش­های فرا­ابتکاری استفاده می­شود. در دنیای واقعی، وجود برخی عوامل بـاعث می­شود که مسأله­ ی مسیریابی وسایل نقلیه، یک مسأله ی غیر قطعی باشد. یک نوع عدم قطعیت در این مسأله، وقوع تقاضایِ متغیرِ مشتریان می­باشد؛ یعنی میزان تقاضای برخی مشتریان، نامشخص است و تنها هنگامی که وسیله نقلیه به محل مشتری برسد، تقاضای او مشخص می­شود. در این مقاله، روشی بر اساس الگوریتم ژنتیکِ مقاوم برای حل مسأله مسیریابی وسایل نقلیه­ ی حامل بار با تقاضای متغیر ارائه شده است. در این روش، سعی بر یافتن جواب­های مقاوم برای این مسأله است که در مواجه شدن با تغییرات، بهینگی خود را حفظ کنند. ارزیابی­های انجام شده و مقایسه نتایج، کارایی روش پیشنهادی را نشان داده است.

[alert type=”info”]در این پژوهش هدف ما ارائه ی روشی برای حل VRP بر اساس الگوریتم ژنتیک (GA) است که بتواند به جواب های مقاومی برای این مسأله دست یابد که در شرایط عدم قطعیت نیز بتواند همچنان بهینگی خود را حفظ نمایند. [/alert]
همان طور که پیش تر اشاره کردیم، اضافه شدن یکسری از محدودیت ها باعث ایجاد انواع مختلف VRP می گردد؛ در مطالعه ی ما افزوده شدن عدم قطعیت به مسأله به صورت «نامعلوم بودن تقاضای مشتریان»، سبب ایجاد VRP با تقاضای تصادفی (VRPSD) گردیده است. به VRPSD، مسأله مسیریابی وسایل نقلیه احتمالی (PVRP) نیز گفته می شود.
یکی از مهم ترین عوامل ایجاد عدم قطعیت در VRP، عدم قطعيت در تقاضای مشتریان می باشد که در این پژوهش نیز تمرکز ما بر روی عدم قطعیت مشتریان می باشد. وقوع عدم قطعیت تقاضاي مشتریان به این صورت است که میزان تقاضا نامشخص است تا هنگامی که وسیله نقلیه به محل مشتری برسد؛ چنانچه میزان تقاضا کمتر از بار موجود در وسیله نقلیه باشد مشتری سرویس می گیرد و وسیله نقلیه برای خدمت، به مشتری بعدی می رود. در غیر این صورت برای مشتری کنونی یک هزینه منفی در نظر گرفته می شود و وسیله نقلیه پس از رفتن به انبار و بارگیریِ مجدد به مشتریِ بعد از مشتری کنونی می رود. تابع هدفِ روش پیشنهادی، علاوه بر هزینه ی منفیِ ناشی از عدم سرویس به مشتریان، شامل هزینه ی سفر بین مشتریان و همچنین انبار می باشد.
به منظور ارزیابی روش پیشنهادی، آن را با روش های «الگوریتم ژنتیک»، «بهینه سازی ازدحام ذرات» و «بهینه سازی ازدحام ذرات ترکیبی» مورد مقایسه قرار دادیم. نتایج بدست آمده، کارایی روش پیشنهادی را نسبت به روش های دیگر نشان می دهد.
ساختار این پایان نامه به صورت زیر می باشد:

1. فصل اول مسأله مسیریابی وسایل نقلیه در زنجیره تأمین را شرح می دهد.
2. فصل دوم عدم قطعیت در مسائل و مدیریت آن به کمک الگوریتم ژنتیک را ارائه می دهد
3. فصل سوم مروری بر مسأله مسیریابی وسایل نقلیه ی غیرقطعی دارد.
4. فصل چهارم و پنجم به ترتیـب، روش پیشنهادی و ارزیابی روش پیشنـهـادی را بیان می کنند
5. و در نهایت در فصل ششم نتیجه گیری و پیشنهادهای آینده ذکر می شود.

فهرست پایان نامه مسیریابی حمل و نقل کالا در زنجیره تامین در شرایط عدم قطعیت با استفاده از الگوریتم ژنتیک

• چکیده
• مقدمه

• فصل اول – مسأله مسیریابی وسایل نقلیه در زنجیره تامین

• مدیریت زنجیره تأمین (SCM)
• هدف زنجیره تأمین
• عوامل يا محرك هاي زنجيره تامين
• مسأله مسیریابی وسایل­نقلیه
• انواع VRP

• فصل دوم – عدم قطعیت در مسائل و مدیریت آن به کمک الگوریتم ژنتیک

• عدم قطعیت
• بهینه­سازی تکاملی در محیط­های عدم قطعیت
• پایدارکردن جواب­ها در شرایط عدم قطعیت
• الگوریتم ژنتیک
• مراحل الگوریتم ژنتیک
• کدگذاری
• محاسبه تابع برازندگي (تابع ارزش)
• اعمال عملگرهای ژنتیکی
• انواع الگوریتم ژنتیک
• الگوریتم ژنتیک گسسته
•  
• الگوریتم ژنتیک­پیوسته
• الگوریتم ژنتیک­جایگشتی

• فصل سوم – مروری بر مسأله مسیریابی وسایل نقلیه­ ی غیرقطعی

• عدم قطعیت در زمان توزیع
• عدم قطعیت در تقاضاهای آنلاین و زمان سفر نامعلوم
• عدم قطعیت در تقاضاي سفر و عرضه
• عدم قطعیت در تقاضاي متغیر
• عدم قطعیت در تقاضای تصادفی

• فصل چهارم – روش پیشنهادی

• طراحی صورت مسأله
• فرمول VRPSDپیشنهادی
• تشریح اجزای الگوریتم ژنتیک بر حسب روش پیشنهادی

• فصل پنجم – ارزیابی روش پیشنهادی

• روش­های فراابتکاری مورد مقایسه
• داده­های استفاده شده برای ارزیابی روش پیشنهادی
• نتایج حاصل از روش پیشنهادی
• مقایسه نتایج روش پیشنهادی با نتایج سه روش فراابتکاری دیگر
• نرخ بهبود

• فصل ششم – نتیجه­ گیری

• نتیجه ­گیری و پیشنهادهای آینده

• فصل هفتم – پیوست­ها

• کد برنامه مسیریابی وسایل­نقلیه

• کد مربوط به برنامه اصلی (gapermutation.m)

• تابع create_permutations.m

• تابع traveling_salesman_fitness.m

• تابع crossover_permutations.m

• تابع mutate_permutations.m

• تابع traveling_salesman_plot.m

• فصل هشتم – اختصارها

• فصل نهم – فهرست منابع

کد برنامه مسیریابی وسایل نقلیه

این کد مربوط به برنامه مسیریابی وسایل نقلیه با تقاضای تصادفی است که جواب های پایداری را با در نظر گرفتن تقاضای نامشخص مشتریان بدست می آورد. این کد در برنامهMatlab 7.12.0 (R2011a) نوشته و اجرا شده است.
برنامه اصلی با نام gapermutation.m می باشد که در داخل آن توابع زیر صدا زده می شود:

1. تابع create_permutations.m : این تابع وظیفه ایجاد جمعیت را بر عهده دارد.
2. تابع traveling_salesman_fitness.m : محاسبه میزان برازندگی هر کروموزوم بر عهده این تابع می باشد.
3. تابع crossover_permutations.m : انجام عمل ادغام در این تابع صورت می گیرد.
4. تابع mutate_permutations.m : عمل جهش کروموزوم ها بر عهده این تابع است.
5. تابع traveling_salesman_plot.m : در نهایت بهینه ترین مسیر توسط این تابع رسم می گردد.