فرم درخواست پروژه





















دانلود پایان نامه و شبیه سازی بهینه سازی مسیریابی وسائل نقلیه با استفاده از سیستم کلونی مورچگان

اطلاعات بیشتر

پروپوزال + پایان نامه + شبیه سازی متلب+ پاورپوینت

بهینه سازی مسیریابی وسائل نقلیه با استفاده از سیستم کلونی مورچگان

۶۸۰ هزار تومان

۰۹۱۷۷۳۶۱۸۴۵

==========================================

گزارش اول

فاز اول در این تحقیق استنتاجی و اکتشافی بوده و با تمرکز بر تحقیقات پیشین با هدف بدست آوردن تئوری های قبلی انجام می شود. در این مرحله یک مطالعه وسیع در حوزه مورد نظر بر روی تحقیقات پیشین صورت می گیرد. این موضوع در بدست آوردن یک بینش وسیع کمک کرده و نواقص موجود در زیر ساخت تئوری موجود را روشن می سازد. سپس توسعه تئوری انجام می شود. بعد از تعیین شدن و مشخص شدن دقیق نقصان موجود در تحقیقات قبلی، پیشنهاد لازم جهت توسعه چارجوب تئوریکی قبلی ارائه می شود. بدین منظور یک مطالعه وسیع جهت تکمیل مدل پیشنهادی صورت می پذیرد. این امر به محدود کردن تحقیق کمک می کند. هر گونه توسعه مدل باید بر مبنای اصل سادگی و اضافه شدن حداقل مراحل ممکن باشد.

در بررسی های انجام شده۶۰% از هزینه های لجستیک زنجیره های تأمین ناشی از  هزینه های حمل و نقل است. متأسفانه عدم برنامه ریزی کافی و بررسی همه جانبه فاکتور حمل و نقل، هزینه های بسیاری را به زنجیره های تأمین تحمیل می کند. این هزینه ها که شامل هزینه های مادی و غیر مادی از جمله اتلاف زمان، اعتبار، از دست دادن مشتریان و…  می باشد بیشترین هزینه های تحمیل شده به زنجیره های تأمین را تشکیل می دهد. بطور کلی می توان هزینه های ناشی از حمل و نقل را به هزینه های ناشی از انواع حمل از جمله ریلی، جاده ای، هوائی و…، هزینه  های انتخاب مسیر، هزینه های تخلیه و بارگیری و…، تقسیم بندی نمود. با بررسی و مطالعه بر روی عوامل ذکر شده می توان هزینه ها را کاهش داد. در لجستیک، هنر کاهش هزینه های حمل و نقل است تا جایی که صدمه ای به توزیع مطمئن و بموقع نزند. استفاده از تکنیک های مسائل حمل ونقل در برنامه ریزی های خطی و همچنین استفاده از الگوریتم های فرا ابتکاری از راه کارهای بهینه سازی در لجستیک زنجیره های تأمین می باشد. کاهش هزینه ها و در نتیجه بهینه سازی زنجیره های تأمین  نقشی حیاتی در بهبود و پیشبرد  اهداف تولید، افزایش مزیت رقابتی و افزایش رضایت مشتریان خواهد داشت.

در این پژوهش برآنیم تا با ارائه یک مدل حمل  و نقل بر اساس الگوریتم های فراابتکاری کلونی مورچگان، لجستيك زنجیره تأمین محصولات لبنی را در شبکه توزیع، بهینه نماییم. سیستم مورچگان یکی از روش های فرا ابتکاری است که با الهام از طبیعت به ساختن جواب مسائل بهینه یابی ترکیبی پیچیده می پردازد. این سیستم اولین بار توسط مارکو دوریگو در سال ۱۹۹۱ برای حل مسائل مذکور معرفی گردید و اولین کاربرد آن در مورد شناخته شده ترین مسئله بهینه یابی مسائل ترکیبی یعنی مسئله فروشنده دوره گرد بود.

زنجیره های تأمین فرآورده های لبني شامل شبکه توزیع بسیار گسترده در سرتاسر کشور  هستند که هزینه های لجستیک و حمل ونقل این زنجیره ها بطور قابل ملاحظه ای تأثیر مستقیمی بر روی قیمت تمام شده و كيفيت محصول دارند. زنجیره تأمین محصولات لبنی با توجه به لزوم استفاده از وسائل نقلیه خاص بمنظور توزیع محصولات تولید شده و هزینه بر بودن این تجهیزات نیاز به استفاده از حداقل وسائل نقلیه مورد نیاز جهت توزیع محصولاتش دارد بگونه ای که مدت زمان سرویس دهی به مشتریانش با تأخیر مواجه نشود.

برای رسیدن به این هدف، به بررسی یافتن حداقل تعداد وسائل نقلیه مورد نیاز و همچنین یافتن حداقل زمان مورد نیاز جهت سرویس دهی به مشتریان پایین زنجیره تأمین این زنجیره در شبکه توزیع آن، می پردازیم.

مسئله مطرح شده، یک مسئله مسیر یابی وسائل نقلیه است. مسئله مسیریابی وسائل نقلیه یکی از مسائل بهینه یابی ترکیبی سخت است که در آن ناوگانی متشکل از چندین وسیله نقلیه از یک یا چند قرار گاه به ارائه خدمت به مشتریان مستقر در نقاط مختلف جغرافیایی می پردازند و این امر را به نحوی انجام می دهند که هزینه های انجام کار به حداقل برسد. مسئله مسیریابی وسائل نقلیه، یک مسئله محوری در مدیریت توزیع بشمار می آید. و مسئله مسیریابی وسائل نقلیه با هدف حداقل کردن هزینه های حمل و نقل مورد بررسی قرار می گیرد.

ابتدا به ارائه مدل پیشنهادی بمنظور بهینه کردن لجستیک زنجیره های تأمین در قسمت توزیع زنجیره و بر روی حمل و نقل آن خواهیم پرداخت. مسئله مورد نظر، مسئله مسیریابی وسائل نقلیه می باشد که یک سری محدودیت هایی بر آن اعمال می شود. این محدودیت ها در راستای نزدیکتر شدن مدل به مسئله واقعی است. هدف این مدل مینیمم کردن تعداد وسائل نقلیه و یافتن کوتاهترین مدت زمان سرویس دهی به تمامی مشتریان است که بایستی سرویس دریافت دارند.

برای کاهش هزینه های حمل و نقل لجستیک زنجیره تأمین از الگوریتم های فراابتکاری کلونی مورچگان استفاده نمودیم.

در این الگوریتم از دو کلونی مورچه متفاوت که هرکدام رسیدن به هدف های تعریف شده را دنبال می کند، استفاده می نماییم. مدل پیشنهادی با عنوان “سیستم کلونی مورچه دوگانه جهت حل مسئله مسیریابی وسائل نقلیه با محدودیت های پنجره زمانی و مدت زمان  سرویس دهی به هر مشتری ” شروع به کار می کند و نسبت به مدل های پیشنهادی محققان دیگر علاوه بر محدودیت پنجره زمانی، محدودیت مدت زمان سرویس دهی به مشتریان را نیز لحاظ کرده و همچنین از الگوریتم جایگذاری کمبل که در سال ۲۰۰۴ ارائه گردید، استفاده  می نماید. این الگوریتم پیچیدگی زمانی مسئله را از O(n4) به O(n3) یا O(n3log( n)) تقلیل می دهد. این مدل مبنای خود را بر جواب اولیه ایجاد شده توسط الگوریتم ابتکاری نزدیکترین همسایه قرار می دهد و سپس کلونی های مورچه را فعال نموده و جواب حاصل از هر کلونی را با این جواب مقایسه می نماید، چنانچه جواب بهتری از کلونی ها بدست آمد، جواب یافت شده، جایگزین جواب بهینه فعلی می گردد. دراین پژوهش الگوریتم نزدیکترین همسایه کار خود را با یک وسیله نقلیه و از پایانه آغاز می نماید و با تعریف دو متغیر زمان جاری و گنجایش جاری به محاسبه لیست  گره هایی که شرایط لازم را هم از نظرپنجره زمانی و هم از نظر گنجایش وسیله نقلیه دارا هستند، می پردازد. این لیست به لیست منتخب مشهور است.

گزارش دوم

این شرکت محصولات متنوعی از فرآورده های لبنی را تولید می کند که پس از بسته بندی و تأیید کنترل کیفیت، محصولات به مرکز توزیع شرکت حمل و سپس به خودروهای مخصوص توزیع منتقل خواهند شد. (عملیات بارگیری) پس از آن، محصولات تولید شده از مرکز توزیع ( پایانه )، بین مشتریانی که متقاضی محصولات هستند توزیع می گردد. بدلیل ماهیت نگهداری محصولات لبنی در شرایط ویژه بایستی از وسائل نقلیه خاص بمنظور توزیع این محصولات استفاده شود که طبق برآورد شرکت استفاده از این نوع وسائل نقلیه ویژه که شامل تجهیزات سرمایشی است، باعث افزایش ۱۰% هزینه های حمل و نقل گردیده است.

خودروهای بارگیری شده رأس ساعت ۷ صبح با ظرفیت ۸۰۰ واحد،آماده حرکت به سوی مشتریان هستند و حداکثر زمان بازگشت وسائل نقلیه پس از سرویس دهی به مشتریان و بازگشت به پایانه ساعت ۱۵ می باشد. وسائل نقلیه شش روز هفته به سرویس دهی به مشتریان می پردازند. ماهیت تقاضاهای مشتریان در این مطالعه موردی قطعی است و محصولات از یک پایانه بین مشتریان توزیع می گردد. خودرو ها، همگن و با ظرفیت یکسان می باشند. تعداد مشتریان مورد نظر در این مطالعه موردی ۷۵ مشتری است که در اقصی نقاط مختلف شهر شیراز قرار دارند. ورودی های مورد نیاز جهت پیاده سازی مدل، مدت زمان مابین کلیه مشتریان و پایانه و همچنین مدت زمان مابین تمامی مشتریان می باشد. در ابتدا تمامی داده ها در یک ماتریس مربعی ۷۶۷۶ آرایه ای (۷۵ مشتری و یک پایانه) مدون گردید در مرحله بعد، این ماتریس با استفاده از برنامه ریزی پویا در نرم افزار WINQSB بهینه گردید. این بهینه سازی بمنظور حصول اطمینان از وجود کوتاه ترین فاصله زمانی بین تمامی ۷۵ مشتری مورد نظر می باشد. برای دستیابی به یک ماتریس بهینه شده ۷۶۷۶ آرایه ای، نرم افزارمورد نظر۲۸۵۰ بار اجرا گردید. در این نرم افزار پس از مشخص شدن دو نقطه مورد نظر، کوتاه ترین فاصله بین دو نقطه بر اساس برنامه ریزی پویا محاسبه می گردد. برنامه ریزی پویا برای مسائلی استفاده می شود که شامل تصمیم گیری هایی در طول زمان و بطور متوالی هستند.

سپس داده های ورودی مسئله با استفاده از الگوریتم نزدیکترین همسایه مورد ارزیابی قرار گرفت. الگوریتم نزدیکترین همسایه توانست با ۳۳ وسیله نقلیه و در ۸۲/۱۱۵ساعت (مجموع کل زمان های ۳۳ وسیله نقلیه) محصولات را بین مشتریان مورد نظر(۷۵ مشتری) با توجه به محدودیت های تعریف شده برای مسئله از جمله : محدودیت ظرفیت وسیله نقلیه، مدت زمان سرویس دهی ومحدودیت پنجره زمانی تعریف شده برای مشتریان،  توزیع نماید.

بمنظور ارزیابی مدل پیشنهادی و سنجش اعتبار آن از شیوه مقایسه نتایج بدست آمده از الگوریتم پیشنهادی با نتایج حاصل ازالگوریتم ابتکاری نزدیکترین همسایه، استفاده شده است.

فصل اول:مقدمه

  • کليات تحقيق                                                   ۲       

۱-۲- خواستگاه اولیه تحقیق                                                                ۲

۱-۳- ضرورت انجام تحقیق                                                                  ۵  

۱-۳-۱- حمل و نقل در ايران                                                               ۵

۱-۴- ساختار گزارش تحقیق                                                                ۶

۱-۵- چشم انداز کلی تحقیق                                                                ۸ ۱-۶- اهداف تحقیق                                                                           ۸

۱-۷- دامنه تحقیق                                                                            ۸        

۱-۸- سؤال تحقیق                                                                            ۸

۱-۹- متدولوژی تحقیق                                                                      ۸

۱-۱۰-نوع تحقیق                                                                             ۹

۱-۱۱- اعتبار تحقیق                                                                        ۱۰

۱-۱۲- تعریف واژه ها                                                                       ۱۰

فصل دوم: مروری بر تحقيقات پيشين و مبانی نظری تحقيق

۲-۱- مقدمه                                                                                  ۱۳

۲-۲- مروری بر تحقیقات پیشین                                                         ۱۳

۲-۳- مباحث نظری تحقیق                                                                ۱۶

۲-۳-۱- لجستیک                                                                           ۱۶

۲-۳-۲- مسئله مسیریابی وسائل نقلیه                                                   ۲۱

۲-۳-۳- مسائل بهینه سازی  ترکیبی                                                    ۳۳

۲-۳-۴- روش های حل مسائل بهینه سازی ترکیبی                                  ۳۴

۲-۳-۵- الگوریتم های دقیق                                                               ۳۴

۲-۳-۶- الگوریتم های تخمینی                                                           ۳۴

۲-۳-۷- الگوریتم های سازنده                                                             ۳۴

۲-۳-۸- الگوریتم  ابتکاری نزدیکترین همسایه                                         ۳۵

۲-۳-۹- الگوریتم ابتکاری جایگذاری                                                     ۳۶

۲-۳-۱۰- الگوریتم های جستجوی محلی                                               ۳۷

۲-۳-۱۱- الگوریتم k-opt                                                                 ۳۸

۲-۳-۱۲- ۲-o                                                                               ۳۹

۲-۳-۱۳- ۳-opt                                                                            ۳۹

۲-۳-۱۴- ۲٫۵-opt                                                                        ۴۱

۲-۳-۱۵- الگوریتم ابتکاری لین – کرنیگان                                             ۴۱

۲-۳-۱۶- الگورتیم ابتکاری تبادلی لاندا                                                 ۸۴

۲-۳-۱۷- الگوریتم ابتکاری تبادلی متقاطع                                             ۴۲

۲-۳-۱۸- فراابتکاری ها                                                                    ۴۳

۲-۳-۱۹- معیار های عمومی توقف فرا ابتکاری                                        ۴۴

۲-۳-۲۰- الگوریتم مورچگان                                                              ۴۵

۲-۳-۲۱- ساختار مسائل قابل مدلسازي براي حل با الگوريتم هاي مورچگان     ۴۷                                                        

۲-۳-۲۲- رفتار مورچه ها                                                                  ۴۸

۲-۴- کليات الگوريتم هاي مورچگان                                                     ۵۱

فصل سوم: چارچوب الگوريتم پيشنهادی

۳-۱- مقدمه                                                                                  ۵۶

  • الگوريتم پيشنهادی: الگوريتم سيستم کلونی مورچه دوگانه جهت حل

 مسئله مسيريابی وسائل نقليه با محدوديت های پنجره زمانی و مدت-            ۵۶

زمان سرويس دهی به هر مشتری                                                           

۳-۲-۱- کلونی  ACS-VEI                                                    ۶۱               ۳-۲-۲- کلونی  ACS-TIME                                                             ۶۲

۳-۲-۳- رويه ساخت جواب                                                                ۶۲

۳-۲-۴- الگوريتم ابتکاری جايگذاری                                                     ۶۶

۳-۲-۵- جستجوی محلی                                                                  ۶۸

فصل چهارم: پياده سازی مدل پيشنهادی

۴-۱- مقدمه                                                                                  ۷۲

۴-۲- پیاده سازی مدل                                                                               ۷۲

۴-۲-۱- الگوريتم ابتکاری نزديکترين همسايه                                          ۷۳

۴-۲-۲- الگوريتم DACS-VRPTWS                                                   ۷۴

 ۴-۳- ارزيابی مدل پيشنهادی                                                            ۷۹

فصل پنجم: نتيجه گيری و پيشنهادات ارائه شده

۵-۱- مقدمه                                                                                  ۸۲

۵-۲- نتیجه گیری                                                                           ۸۲

۵-۳- پیشنهادات                                                                            ۸۳

۵-۳-۱- پیشنهادات تئوریک                                                               ۸۳

۵-۳-۲- پيشنهادات مربوط به توسعه مدل در پايين زنجيره تأمين                 ۸۳

  • فهرست منابع ۸۶

  • پيوست ها

پیوست شماره۱: الگوریتم نزدیکترین همسایه                                           ۹۷

پیوست شماره۲: ساختار کلی الگوریتم DACS-VRPTWS                          ۹۸

پيوست شماره۳-۱: الگوریتم ACS-VEI برای یک مورچه                            ۹۹

پيوست شماره ۳-۲: الگوریتمACS-VEI  برای یک Itration                     ۱۰۰

پيوست شماره۴- ۱: الگوريتم ACS –Time برای یک مورچه                     ۱۰۱

پيوست شماره ۳-۲: الگوریتم ACS –Time برای یک Itration                ۱۰۲

پيوست شماره ۵: الگوریتم جایگذاری                                                   ۱۰۳

پيوست شماره ۶: الگوریتم جستجوی محلی تبادلی متقاطع                        ۱۰۴

پیوست شماره ۷: داده های اولیه مدت زمان بین پایانه و مشتریان               ۱۷۹

پیوست شماره ۸: داده های بهینه شده مدت زمان بین پایانه و مشتریان        ۱۰۵

پیوست شماره ۹: محدودیت های پنجره زمانی، مدت زمان سرویس دهی       ۱۰۶       و تقاضای هر مشتری                                                      

پيوست شماره ۱۰: گراف های تولید شده توسط ۱۰ مورچه در یک              ۱۰۷