بخشی از پاورپوینت
اسلاید 1 :
مسیریابی وسایل نقلیه (VRP)
اسلاید 2 :
مقدمه
یکی دیگر از مسائل مهم مکان یابی تسهیلات، که در چند دهه اخیر کاربرد بسیار بالایی در عمل داشته و برای افزایش کارایی و بهره وری سیستم های حمل و نقل مطرح شده است بحث مساله مسیریابی وسایل نقلیه (VRP) است. مساله مسیر یابی وسایل نقلیه به مجموعه ای از مسایل اطلاق می گردد که در آن تعدادی خودرو متمرکز در یک یا چند قرار گاه بایستی به مجموعه ای از مشتریان مراجعه نموده و خدمتی را ارایه دهند که هر یک دارای تقاضای معینی می باشند.
این مساله درصدد است تا با مدل های ریاضی و بهینه سازی به گونه ای عمل کند که مسافت طی شده، زمان کل سفر، تعداد وسایل حمل و نقل، جریمه های دیرکرد و در نهایت تابع هزینه حمل و نقل حداقل گردد و در نهایت رضایت مشتریان به حداکثر برسد. مسیریابی خودرو (VRP) نامی کلی است که به تمامی کلاس مسائلی که شامل ملاقات مشتریها با خودروهاست، اطلاق میشود. VRP در نوشتهها، بهصورت زمانبندی خودروها و توزیع خودرو یا بهطور سادهتر به صورت مسئله تحویل نیز شناخته شده است.
اسلاید 4 :
موضوع مسیریابی وسیلهنقلیه، یکی از مفاهیم آشنا در زمینه تحقیق در عملیات است که در دو دهه اخیر تلاشها و به دنبال آن پیشرفتهای بزرگی در این زمینه انجام گرفته است. مسأله مسیریابی وسایل نقلیه به مجموعهای از مسائل اطلاق میشود که در آن ناوگانی متشکل از چندین وسیله نقلیه از یک یا چند انبار به ارائه خدمت به مشتریان مستقر در نقاط مختلف جغرافیایی میپردازند و این امر را به نحوی انجام میدهند که هزینههای انجام این کار به حداقل برسد. در طول این مسیرها مشتریان تنها و تنها یک بار ملاقات میشوند و تمام تقاضاهای آنها تنها توسط یک وسیله نقلیه دریافت میگردد، هر وسیله دارای ظرفیت معینی است و از سویی تمام مسیرها از یک نقطه مشخص (مبدأ بارگیری) آغاز میشوند و پس از آنکه وسیله نقلیه یک سلسله از مشتریان را ملاقات نمود به همان نقطه اولیه باز میگردد و مسیر در همان مکان پایان مییابد.
اسلاید 5 :
اینگونه مسائل به طور کلی به عنوان مسائل مسیریابی وسایل نقلیه ( VRP) یا مسائل برنامهریزی حملونقل، شناخته شدهاند. مدلها و الگوریتمهای معرفی شده برای حل مسائل برنامهریزی و مسیریابی ارائه شده را، نه تنها برای استفاده در مسائل مربوط به پخش و جمعآوری کالاها بلکه برای بسیاری از مسائل مختلف صنعت حملونقل در دنیای واقعی، نیز میتوان استفاده نمود و به طور عمده مورد استفاده از این دست مسائل به عنوان مثال، در جمعآوری زبالههای خشک، پاکیزه سازی خیابانها، مسیریابی اتوبوس مدرسه، سیستمهای جابهجایی معلولین، مسیریابی فروشنده دورهگرد و واحدهای نگهداری و تعمیرات میباشد. پخش کالاها در برگیرنده خدمتدهی به دستهای از مشتریان، در یک بازه زمانی داده شده توسط دستهایی از وسایلنقلیه میشود که در یک یا چند مرکز قرار دادند و توسط دستهایی از رانندگان هدایت میشوند و جابجاییها در یک شبکه مسیر مناسب انجام میشود.
اسلاید 6 :
مدل های VRP در حالتهای کاربردی که در برخی موارد حتی مستقیما با توزیع فیزیکی کالاها مرتبط نیستند، بسیار به تناوب ظاهر میشود. سوارکردن کودکان به اتوبوسهای مدرسه، تحویل تولیدات بین سوپرمارکتها و فروشگاههای بزرگ، توزیع روزنامه، تورهای بازرسی و تعمیر بازدارنده، توزیع لباسشویی و غیره، همگی VRPهایی هستند که در آن، کالاها و خودروها میتوانند فرمهای متنوعی بگیرند.
اغلب مسائل مسیریابی وسایل نقلیه (VRP)، NP-hard هستند و به نظر میرسد که قابل حل در زمانی چندجملهای نباشند. الگوریتمهای تحقیقاتی ارائه شده برای VRP عموماً شامل روشهای دقیق و الگوریتمهای بهینهسازی هوشمند است. الگوریتمهای دقیق شامل روشهای شاخه و کران، متدهای برنامهریزی پویا و مانند اینها هستند. مثلا، Nobert روشهای پیشرو شاخه و کران چندگانه پیشرو را ابداع کرد. در مقابل، الگوریتمهای تقریبی عمدتاً شامل روشهای جستوجوی ممنوع و شبیهسازی حرارتی ، الگوریتمهای ژنتیک بهینهسازی مورچگان و غیره است.
اسلاید 7 :
ضرورت مسایل مسیریابی وسایل نقلیه
در مسیریابی وسایل نقلیه، بحث کلیدی مربوط به مدیریت ناوگانی از وسایل می باشد که خدمات تحویل یا جمع آوری و یا ترکیبی از آن دو را به مجموعه ای از مشتریان انجام می دهد. مدیر برنامه ریزی علاوه بر این که در مورد تعداد و نوع وسایل باید تصمیم گیری نماید، هم چنین بایستی مشخص نماید که مشتریان با چه وسیله و با چه ترتیبی دنبال شوند تا هزینه حمل و نقل کاهش یابد. بنابر این پژوهشگران در تلاش هستند روش هایی که منجر به کاهش هزینه حمل و نقل در این سیستم می گردد را ارائه نمایند.
یکی از بخش های عمده تشکیل دهنده قیمت تمام شده محصولات، هزینه های مربوط به حمل و نقل می باشد. تحقیقات انجام شده در دهه ۱۹۷۰ میزان هزینه های حمل و نقل در آمریکا را بیش از ۱۶٪ ارزش فروش یک محصول نشان می دهد. مقدار هزینه های فوق در دهه ۱۹۸۰ حدود ۱۰٫۳ ٪ قیمت تمام شده محصولات تخمین زده شده است هزینه های حمل ونقل شرکتهای تولیدی از سه بخش اصلی تأمین مواد اولیه و قطعات مورد نیاز از تأمین کنندگان، جابه جایی مواد و قطعات نیمه ساخته در درون کارخانه و توزیع محصولات تشکیل می شوند.
اسلاید 8 :
ضرورت مسایل مسیریابی وسایل نقلیه
برنامه ریزی هر یک از حمل و نقل های فوق از جایگاه ویژه ای برخوردار بوده و تحقیقات زیادی نیز در مورد آنها انجام شده و در حال انجام می باشد. برنامه ریزی وسایل نقلیه به منظور جمع آوری قطعات از تأمین کنندگان و توزیع مواد اولیه به آنها به طور هم زمان را می توان به عنوان یک مسأله VRPSPD در نظر گرفت. در این مسأله سعی می شود که نحوه برنامه ریزی وسایل نقلیه به گونه ای صورت گیرد که هزینه های حمل ونقل کاهش داده شوند. از آن جا که مسأله مسیریابی وسایل نقلیه، جزء مسائل NP hard* است و جواب بهینه ای برای این گونه مسائل با | مقیاس بزرگ تا به حال شناخته شده نیست، لذا پژوهشگران زیادی با به کارگیری الگوریتم های ابتکاری برای رسیدن به جواب های بهتری در تلاش هستند
مسأله مسیریابی وسایل نقلیه با جمع آوری و تحویل همزمان کالا نیز یک مسأله NP - hard می باشد و در چندین سال اخیر از الگوریتم های فراابتکاری جهت حل این مسأله، بسیار بهره برده اند و تلاش برای توسعه و ارائه راه حل های بهتر هنوز باقی است. قابل توجه است که در تحقیقات انجام گرفته روی مسائل مسیریابی، تحقیقات اندکی روی مسأله مسیریابی وسایل نقلیه با در نظر گرفتن دو تقاضای همزمانی برای مشتریان انجام گرفته شده است و با این وجود جهت ارائه جوابهای بهتر و کارا باید تحقیقاتی صورت گیرد. به همین خاطر در این تحقیق سعی می شود با ارائه یک روش فوق ابتکاری جهت حل این نسخه از مسأله مسیریابی جواب های بهتری حاصل شود.
اسلاید 9 :
انواع مدل های VRP
مسأله مسیریابی وسایل نقلیه (VRP) نامی کلی است که به تمامی کلاس مسائلی که شامل ملاقات مشتری ها با وسیله نقلیه است، اطلاق می شود. VRP در مقالات، تحت عنوان زمان بندی وسیله نقلیه، توزیع وسیله نقلیه یا به بیان ساده تر به صورت مسأله تحویل نیز بیان شده است. با گذشت زمان انواع مسأله مسیریابی با محدودیت هایی که بیشتر در عالم واقعی کاربرد داشت، به وجود آمده که در شکل زیر نشان داده شده اند.
اسلاید 10 :
انواع مدل های VRP
در مسائل کلاسیک مسیریابی وسایل نقلیه، مجموعه ای از مشتریان با تقاضای مشخص برای هر مشتری، در مناطق جغرافیایی پخش شده اند که باید توسط ناوگانی از وسایل نقلیه که در یک پایانه مرکزی قرار دارند با ظرفیت های مشخص سرویس دهی شوند. هدف طراحی مسیرهایی است که با حداقل هزینه بتوان به همه تقاضای مشتریان خدمات داد. حداقل هزینه با به حداقل رساندن دو تابع طول مسافت طی شده و تعداد وسیله مورد نیاز برای انجام این خدمات امکان پذیر می باشد. مسأله کلاسیک مسیریابی وسایل نقلیه تحت عنوان مسأله مسیریابی وسایل نقلیه با محدودیت ظرفیت (CVRP) نیز بیان می شود. این مسأله به طور شماتیک در شکل زیر با یک پایانه نمایش داده شده است.
اسلاید 11 :
انواع مدل های VRP
اسلاید 12 :
مسیریابی وسیله نقلیه با محدودیت مسافت (DCVRP)
اولین نسخه مسأله مسیریابی، مسیریابی وسایل نقلیه با محدودیت مسافت نامیده شده است که در هر مسیر یک محدودیت حداکثر مسافت در نظر گرفته می شود. هزینه های حمل ونقل با زمان سفر رابطه مستقیم دارند و هرچه طول یا زمان سفر بزرگتر باشد علاوه بر هزینه های انرژی و استهلاک و زمان از دست رفته احتمال وقوع تصادف نیز بیشتر می شود. گاهی اوقات هم قوانین و مقررات خاصی جهت ملاحظات ایمنی برای محدود کردن طول سفر وضع می شود. در چنین حالاتی مسأله مسیریابی وسایل نقلیه با یک محدودیت کاربردی که طول سفر را تهدید می کند ترکیب می شود، یعنی اینکه حداکثر مسافتی که وسیله می تواند طی نماید مشخص شده و بیش از آن مجاز نیست.
اسلاید 13 :
مسأله مسیریابی وسایل نقلیه با پنجره های زمانی (VRPTW)
یکی از حالت های مسأله VRP، مسأله مسیریابی وسایل نقلیه با پنجره زمانی نامیده می شود که در این مسأله علاوه بر محدودیت ظرفیت، هر یک از مشتریان یا پایانه ها دارای فواصل زمانی جهت ارائه خدمات می باشند. در این مسأله زمان ارسال کالا از پایانه ممکن است در ساعات با فواصل زمانی خاصی صورت گیرد که در چنین حالاتی گفته می شود پایانه دارای پنجره زمانی می باشد. ولی اغلب اوقات این مشتریان هستند که برای دریافت کالا محدودیت زمانی را تعریف می نمایند و فقط در آن ساعات کالا دریافت نموده و یا برای ساعات ذکر شده اولویت در نظر می گیرند. با توجه به تعبیری که ارائه شد، دو نوع پنجره زمانی موضوعیت می یابد: یکی این که گاهی اوقات این محدودیت زمانی به گونه ای است که خارج از محدوده زمانی فوق، خدمات ارائه نمی شود، این پنجره زمانی را پنجره زمانی سخت می نامند. دیگر این که محدودیت زمانی یک اولویت ترجیح است و می توان خارج از آن زمان خدمات ارائه نمود، ولی از مطلوبیت کمتری برخوردار است. این نوع پنجره زمانی را پنجره زمانی نرم" می نامند.
اسلاید 14 :
مسأله مسیریابی وسایل نقلیه با جمع آوری و تحویل کالا(VRPPD)
یکی از توسعه های معروف و پرکاربرد VRP مسأله مسیریابی وسایل نقلیه با جمع آوری و تحویل کالا" (VRPPD) است که مورد توجه بسیاری از محققان تحقیق در عملیات قرار گرفته است. در حالت پایهای مسأله مسیریابی وسایل نقلیه با جمع آوری و تحویل کالا، هر مشتری با دو پارامتر به و p متناظر میشود که به ترتیب مقدار تقاضای تحویلی و جمع آوری را برای مشتری ام نمایش می دهند. گاهی اوقات فقط یک مقدار تقاضای d - D = 4 برای هر مشتری در نظر گرفته میشود که مقدار اختلاف بين تقاضای تحویلی و تقاضای جمع آوری ( که می تواند منفی هم باشد) را نشان می دهد. فرض کنید در هر موقعیت مشتری، تحویل قبل از جمع آوری انجام می گیرد، بنابراین مقدار بار موجود وسيله نقليه قبل از رسیدن به موقعیت داده شده به صورت مقدار بار اولیه منهای همه تقاضاهای تحویل شده به اضافه همه تقاضای جمع آوری شده میباشد.
اسلاید 15 :
مسأله مسیریابی وسیله نقلیه با چند پایانه
مسأله مسیریابی وسیله نقلیه با چند پایانه " (MDVRP) نوعی مسأله مسیریابی با محدودیت ظرفیت است که در آن چندین پایانه مرکزی جهت استقرار وسایل وجود دارد و هر وسیله با یکی از این چندین پایانه حرکت خود را آغاز نموده و پس از ارائه خدمات به مشتریان، به همان پایانه یا پایانه های مرکزی دیگر باز می گردد. در این مسأله بیش از یک پایانه وجود دارد که باعث پیچیده تر شدن مسأله می گردد. ممکن است که کالاها در این چند مرکز نگهداری شده و از این مراکز برای مشتریان ارسال شوند.
اسلاید 16 :
مسأله مسیریابی وسیله نقلیه با مقدار تقاضای احتمالی
چنانچه مقدار تقاضای هر مشتری بطور دقیق مشخص نباشد و صرفا براساس اطلاعات گذشته، تخمینی از تقاضا در دست باشد و یا به صورت آماری تابع توزیع مقدار تقاضای هر مشتری تعریف شده باشد، مسأله مسیریابی وسیله نقلیه شکل پیچیده تری به خود می گیرد که اصطلاحا به آن مسیریابی وسیله نقلیه با مقدار تقاضای احتمالی(SVRP) می گویند.
اسلاید 17 :
مسأله مسیریابی وسیله نقلیه با مقدار تقاضای احتمالی
