بخشی از مقاله
چکیده
مساله مسیریابی وسایل نقلیه یکی از مسایل بسیار مهم در شاخه بهینه سازی است که تاکنون الگوریتمهای زیادی برای حل آن پیشنهاد شده است. چگونگی انتخاب مسیر مناسب از مجموعه مسیرها و غلبه بر محدودیتهای مسیریابی، اهمیت پارامترهای مختلف مسیریابی وسائل نقلیه را تعیین میکند. در این مقاله پس از بررسی انواع مختلف مسیریابی وسائل نقلیه، یک مدل ریاضی برای مساله ارایه گردیده و با استفاده از ترکیب رویکرد نظریه آشوب و الگوریتم ازدحام ذرات در محیط نرم افزار متلب حل شده است . نتایج حاصل از شبیهسازی نشان و اجرای مدل برای مسایلی در ابعاد کوچک و بزرگ میدهد که خروجی روش پیشنهادی نسبت به روش PSO و الگوریتم ژنتیک بهتر بوده و همچنین این روش، از درجه همگرایی و پایداری خوبی برخوردار است.
کلمات کلیدی: وسائل نقلیه، مسیریابی، الگوریتم بهینهسازی ازدحام ذرات، تئوری آشوب.-1 مقدمه
از مباحث مهم که در چند دهه اخیر کاربرد بسیار بالایی در عمل داشته و برای افزایش کارایی و بهرهوری سیستمهای حملونقل مطرح شده است بحث مسئله مسیریابی وسایل نقلیه است. مسئله مسیریابی وسایل نقلیه به مجموعه ای از مسایل اطلاق میگردد که در آن تعدادی خودرو متمرکز در یک یا چند قرارگاه بایستی به مجموع های از مشتریان مراجعه نموده و خدمتی را ارائه دهند که هر یک دارای تقاضای معینی میباشند - چنگ و دوران، . - 2009 این مسئله درصدد است تا با مدل-های ریاضی و بهینهسازی به گونهای عمل کند که مسافت طیشده، زمان کل سفر، تعداد وسایل حملونقل، جریمههای دیرکرد و در نهایت تابع هزینه حمل و نقل حداقل گردد و در نهایت رضایت مشتریان به حداکثر برسد.
وجود محدودیتهای مختلف در اینگونه مسایل انواع مختلفی از مسایل کلاسیکی تشکیل میدهد که یکی از آنها بحث وجود پنجرههای زمانی نرم در سرویس به مشتریان میباشد. در اینگونه مسایل اجازه سرویس به مشتریان در خارج از بازه زمانی سخت نیز داده شده و برای هر واحد عدم سرویس به موقع جریمهای در نظر گرفته میشود - لی و همکاران، . - 2010مسیریابی مربوط به پیداکردن یک مسیر ایدهآلی است که اهداف مدل را تامین کرده و از مشتری تبعیت کند در حالی که برنامهریزی وسایل نقلیه، زمانی که باید به هر مشتری خدمت داده شود را معین میکند - اندرسون و همکاران، . - 2010
لذا در مبحث زمان هزینه کلی مسیر نه تنها شامل هزینه مسافت کل و زمانهای خدمت و سایر هزینههای وابسته میشود بلکه هزینه کلی توقفها و انتظارها نیز محاسبه میگردد. در این مقاله، یک مدل ریاضی برای حل مسئله مسیریابی وسایل نقلیه ارائه گردیده و روشی فراابتکاری مبتنی بر ترکیب نظریه آشوب و بهینهسازی ازدحام ذرات ارائه شده است. بدین صورت که در ابتدا، بررسی سوابق آورده شده است. در قسمت بعد، رویکرد پیشنهادی با نظریه آشوب و بهینهسازی ازدحام ذرات مسئله، در ادامه عملکرد روش پیشنهادی با الگوریتم ژنتیک مورد مقایسه قرار گرفته شده است.
-2 کارهای پیشین
تاکنون روشهای مختلفی برای حل مسأله مسیریابی وسایل نقلیه براساس ویژگیهای مختلف پیشنهاد شده است، از آن جمله میتوان به موارد زیر اشاره کرد. در تحقیقی بررسی تحلیلی استراتژی ارسال مستقیم انجام شد و کارایی ارسال مستقیم را در شرایط مختلف محاسبه شد - لی و همکاران ، . - 2010 همچنین مسأله مسیریابی-موجودی را در حالتی در نظر گرفتهاند که تأمینکننده تنها یک وسیله حمل در اختیار داشته و در هر دوره تنها میتواند برای یک مشتری موجودی ارسال کند. نویسندگان الگوریتمی ابتکاری برای یافتن توالی شدنی ارائه کردهاند - لی و همکاران ، . - 2008 مسأله در حالت چند محصولی، چند دورهای با چند تأمینکننده و یک کارخانه مونتاژ و با هدف کمینهسازی مجموع هزینههای حمل و نگهداری موجودی بررسی شد و با بررسی دو نحوه نمایش مختلف جواب، یک الگوریتم ژنتیک ترکیبی بر اساس رویکرد نخست تخصیص و سپس مسیریابی ارائه شد - عزیز و معین ،. - 2007
در تحقیق مشابهای، الگوریتم ژنتیک ترکیبی بهبودیافتهای ارائه شد - معین و همکاران،. - 2010 در تحقیق دیگر با بررسی یک مسأله مسیریابی-موجودی که در آن برنامهریزی تولید نیز لحاظ شده است، الگوریتمهای حل مبتنی بر رویه جستجوی انطباقی حریصانه تصادفی توسعه دادهشد - بودیا و همکاران، . - 2007 در تحقیق مشابهای، ساختاری مبتنی بر الگوریتم ممتیک1 با مدیریت جمعیت جوابها توسعه شد - بودیا و پرینز ، . - 2009 در روش دیگر مدل یکپارچهای برای مسأله مسیریابی-موجودی در زنجیره تأمین سه ردهای ارائه شد و برای حل آن الگوریتم جستجوی همسایگی بزرگ متغیری2 توسعه دادهاند - ژائو و همکاران، . - 2008
در مقاله ای رویکرد جدیدی بر اساس الگوریتم فراابتکاری جستجوی ممنوع برای حل مسأله مسیریابی-موجودی در یک زنجیره تأمین دو ردهای توسعه داده شد - ژائو و همکاران ، . - 2007 در تحقیقی با پیادهسازی الگوریتم ژنتیک برای حل مسأله مسیریابی-موجودی با چند محصول، تأثیر مقادیر مختلف پارامترهای ورودی الگوریتم ژنتیک را ارزیابی کردهاند تا بهترین مجموع مقادیر پارامترهای الگوریتم بدست آید - اسپارچی و همکاران ،. - 2007 با توسعه مدلی برای مسأله مسیریابی-موجودی ماشینهای سکهای، به ارائه الگوریتمی دومرحلهای مبتنی بر الگوریتمهای الحاق و جستجوی ممنوع پرداختهاند - کوردئا و همکاران ، . - 2010 در مقاله دیگر از الگوریتم کرم شبتاپ برای حل مساله مسیریابی وسایل نقلیه استفاده کردند. در این روش .به دلیل ماهیت پیوسته الگوریتم، نحوه تولید و رمزگشایی، جواب جدیدی طراحی شده است که منجر به کاهش زمان حل نیز می شود - مارنیکا و مارنیکا ، . - 2016
-3 مدلسازی مساله
مسیریابی مسالهای است که در آن می بایست یک مجموعه ای از مسیرها برای جریانی از وسایل نقلیه که مستقر در یک یا چند انبار هستند تعیین گردد تا به مجموعه ای از مشتریان و یا شهرهایی که به صورت جغرافیایی پراکنده شده اند، خدمت دهند. هدف از این مسئله ارائه خدمت به این مجموعه از مشتریان یا شهرها می باشد که می بایست در حداقل هزینه، مسافت و یا زمان سفر صورت پذیرد در ضمن هرکدام از این جریانات می بایست از انبار شروع شده و به آن نیز ختم گردد.مسأله VRPیکی از مسائلی است که در حوزه سیستم های توزیع و پشتیبانی زنجیره تأمین مورد توجه قرار می گیرد.مسیرهای وسیله نقلیه بایستی به گونه ای طراحی شوند که هر مشتری تنها یک بار با وسیله نقلیه ارتباط داشته و سرویس دریافت کند.
این مسأله جزو مسائل بهینه سازی ترکیبی محسوب می شود و از دسته مسائل پیچیده Np-hard میباشد - ژئو و همکاران، . - 2007 هر یک از مشتریان/تامینکنندگان دارای تقاضای مشخصی هستند و میتوانند، دارای محدودیت زمان دریافت سرویس باشند. در این تحقیق تابع اصلی هدف به صورت رابطه - 1 - تعریف میشود:پارامتر های تابع هدف در ادامه آورده شده است. در تمامی روابط - 1 - الی - 5 - ، نشان دهنده مشتری،نشان دهنده وسیله نقلیه، برابر ظرفیت وسایل نقلیه و و به ترتیب نشان دهنده مبدا و مقصد مسیر مورد نظر می باشد.رابطه - - 2 تضمین میکند که هر مشتری فقط توسط یک وسیله سرویس بگیرد.
در رابطه - 3 - ظرفیت ماشینها اعمال میگردد و نشان دهنده این مطلب است که مجموع حجم تقاضای مشتریانی که به یک ماشین تخصیص داده میشود بایستی حداکثر برابر با ظرفیت ماشین باشد.رابطه - 4 - تضمین میکند که مسیرها پیوسته باشند. در این روابط موازنه جریان ورود و خروج وسایل نشان داده شده است. به عبارت دیگر تعداد ماشینهایی که به هر گره وارد میشود برابر با تعداد ماشینهایی است که از آنها خارج میشوند. در حالت خاص میتوان جواب حاصل از مساله مسیریابی را به صورت زیر بیان نمود: تعیین مجموعهای از مسیرها که هر کدام توسط یک وسیله نقلیه مورد استفاده قرار میگیرند. البته وسایل نقلیه از مراکز توزیعی که اعزام میشوند در نهایت به همان مرکز توزیع نیز بر میگردند، به نحوی که نیاز مشتری برآورده شود و تمام محدودیتهای عملیاتی نیز ارضا شده و نتیجه به حداقل شدن هزینه کل منجر شود.
-4 رویکرد پیشنهادی
در روش پیشنهادی ابتدا دادهها از مجموعه دادهها، به عنوان ورودی الگوریتم خوانده میشوند. در این مرحله جمعیت اولیه با استفاده از تئوری آشوب تولید میگردد . بعد دادهها بر اساس تابع برازندگی که برای الگوریتم بهینهسازی ازدحام ذرات اعمال شده و مقدار شایستگی مراکز خوشهها را محاسبه میکند. اگر مراکز مسیرها برازنده نباشند، دوباره به جمعیت اولیه اضافه شده و با انتخاب مرکز جدیدی وارد سیستم میگردد. بعد با اعمال الگوریتم بهینهسازی ازدحام ذرات به جستجوی جوابهای بهینه یا دادههایی که ارزش برازندگی آنها مناسب است، میپردازد. در نهایت مسیر برازنده را به عنوان خروجی به ما میدهد. در این قسمت چارچوب روش پیشنهادی که در شکل - 1 - نشان داده شده است. در ادامه به تشریح این موضوع پرداخته شده است.
