بخشی از مقاله
چکیده
مسئله مسیریابی وسایل حملونقل با ظرفیت محدود - CVRP - یک مسئله NP - Hard است که براساس این تعریف هیچ راه حل قطعی برای آن وجود ندارد. به همین جهت محققان و پژوهشگران برای حل مسائل اینچنینی سعی میکنند با استفاده از روشهای فراابتکاری، جوابهایی نزدیک به جواب بهینه را بیابند. هدف مسئله مسیریابی وسایل حملونقل با ظرفیت محدود یافتن مسیر بهینه برای هر وسیله است به طوری که وسیله مذکور باید به تعدادی از مشتریان موجود در مسئله سرویس ارائه دهد. در این تحقیق برای حل این مسئله از الگوریتم کلونی زنبورهای مصنوعی - ABC - استفاده شده است. در ادامه این مقاله نحوه تطابق الگوریتم زنبورهای عسل مصنوعی برای فضای مسئله گسستهای مانند CVRP و فرآیند بهبود جوابها آورده شده است. در آخر نیز برای ارزیابی روشارائه شده، نتایج حاصل از اجرای الگوریتم مذکور روی نمونه مسائلی با اندازههای متفاوت نشان داده شده است.
کلمات کلیدی: مسئله مسیریابی وسایل حملونقل، الگوریتم کلونی زنبورهای عسل، مسئله فروشنده دوره گرد، فاصله اقلیدسی.
-1 مقدمه
مسئله مسیریابی وسایل حملونقل - VRP1 - نخستین بار در سال 1959 توسط Dantzig و Ramser مطرح شد. این مسئله با نمونههای متفاوتی که از آن وجود دارد یکی از مسائل مورد علاقه محققان در میان مسائل بهینهسازی ترکیبی طی سالهای اخیر بوده است [1] و .[2] در مسئله مسیریابی وسایل حملونقل به تعیین مسیرهای بهینه با استفاده از ناوگان وسایل حملونقل کالا مانند کامیونها که توسط یک یا چند منبع دپو بارگیری شدهاند، جهت پاسخگویی به نیازهای مشتریان پرداخته میشود. الزامات و محدودیتهای زیادی در فرآیند اجرای VRP در دنیای واقعی وجود دارند. به عنوان مثال ممکن است سرویسدهی شامل هر دو مرحله تحویل کالا و جمعآوری باشد، بار حمل شده در طول هر مسیر نبایستی از ظرفیت وسایل حملونقل تجاوز کند، طول کلی هر مسیر نباید از مقدار پیش فرض بیشتر باشد، سرویسدهی به مشتریان باید در فاصله زمانی معینی انجام پذیرد، ممکن است ساختار ناوگان ناهمگون باشد، در میان مشتریان اولویتبندی وجود داشته باشد، تقاضای مشتریان کاملاً مشخص نباشد، سرویسدهی به مشتری در میان خودروهای مختلف تقسیم شود و بعضی از ویژگیهای مسئله مانند تقاضاها و زمانهای سفر به صورت دینامیکی تغییر کنند.
در این تحقیق حالت استاتیکی و قطعی مسئله، تحت عنوان مسئله مسیریابی وسایل حملونقل با ظرفیت محدود - CVRP2 - مورد مطالعه قرار گرفته است [3] و .[4] در حل مسئله CVRP تمامی مشتریان باید سرویسدهی شوند، تقاضاها مقدار قطعی دارند، تمامی وسایل حملونقل ظرفیت یکسانی دارند و همگی از یک منبع دپوی مرکزی عملیات بارگیری کالا را انجام میدهند و تنها پارامتر دارای محدودیت ظرفیت میباشد. هدف، بهینهسازی هزینه کل تمام شده جهت سرویسدهی به مشتریان میباشد. هزینه در قالب تعداد مسیرها، طول آنها و یا زمان سفر بیان میشود. در حالت کلی هزینه سفر بین هر زوج مشتری در دو جهت یکسان میباشد. در نتیجه ماتریس هزینه متقارن خواهد بود. در حالیکه در بعضی حالات مثل توزیع در مناطق شهری با خیابانهای یکطرفه، الزاماً ماتریس هزینه نامتقارن به دست میآید.
در واقع مسئله مسیریابی وسایل حملونقل، تعمیم کلاسی از مسائلی است که در آنها تعداد مسیرهای ممکن جهت سرویسدهی به مشتریان پراکنده، توسط خودروهای حملونقل کالا تعیین میشود. اساساً در اینگونه مسائل بایستی مسیرهای مورد نیاز با هزینه کمینه و دارای قابلیت تأمین تقاضاهای موجود، پیدا شوند. از سوی دیگر مسئله مسیریابی وسایل حملونقل با ظرفیت محدود، یکی از معروفترین گونههای مسئله VRP میباشد. در این حالت ناوگان وسایل حملونقل کالا، واقع در انبار واحد، باید تقاضاهای مختلف گروهی از مصرفکنندگان محصولات را تأمین کرده و کالا را بین آنها پخش کنند. محدودیتهای اصلی مطرح شده در CVRP عبارتند از:
. تمامی مسیرها از منبع دپو - انبار کالا - آغاز و به آن ختم میشوند.
. هر مشتری - مصرفکننده - بایدقیقاً یک بار در یک مسیر قرار گیرد.
. کل تقاضای مصرفکنندگان یا مشتریان یک مسیر نباید از ظرفیت وسیله حملونقل تجاوز کند. در شکل 1 نمایی از فضای مسئله مسیریابی وسایل حملونقل و گروه مسیرهای مربوط به هر وسیله حملونقل نشان داده شده است. همان طور که مشاهده میکنید، مستطیل قرمز رنگ مرکز شکل، دپو یا انبار است که در اطراف آن مشتریان موجود نشان داده شدهاند.
معادله شماره 1 تابع هدف مسئله است که قصد کمینه کردن آن را داریم، در واقع میخواهیم هزینه نهایی را که مجموع مسافت طی شده بوسیله تمام وسایل حملونقل است را کمینه کنیم. مسافت طی شده برای هر وسیله برابر با جمع فاصله اقلیدسی جفت مشتریانی است که در مسیر آن وسیله قرار دارند و بوسیله آن سرویس دریافت کردهاند. معادلات 2 و 3 نشانگر این محدودیت هستند که هر مشتری بایددقیقاً یکبار توسط یکی از وسایل حملونقل سرویس دریافت کند. معادله شماره 4 برای اطمینان از متصل بودن مسیر است. معادله شماره 5 بیانگر محدودیت روی طول نهایی هر مسیر است. معادله شماره 6 برای اطمینان از این است که مجموع تقاضاهای مشتریان موجود در مسیر یک وسیله حملونقل از ظرفیت آن وسیله فراتر نرود. معادلات 7 و 8 نشان میدهند که هر وسیله بیش از یکبار استفاده نشده است، و در نهایت معادله شماره 9 اطمینان حاصل میکند که متغیر فقط مقادیر صحیح 0 و 1 را می پذیرد.
-2 پیشینه تحقیق
در حالت کلی میتوان روشهای حل مسئله مسیریابی وسایلنقلیه را به دو دسته روشهای دقیق و روشهای فراابتکاری تقسیم کرد. از جمله روشهای دقیق حل مسئله میتوان به روش شاخه و حد و برنامه ریزی پویا اشاره کرد که توسط Christofides در سال 1981 ارائه شد .[6] همچنین Fisher و Jaikumar نیز با استفاده از روش برنامهنویسی ریاضی به حل مستقیم مسئله پرداختند .[7] از آنجایی که در مسائل با ابعاد وسیعتر استفاده از چنین روشهایی بسیار زمانبر بوده و خارج از توانایی محاسباتی کامپیوترها میباشد، محققین روشهای فراابتکاری را جهت حل مسئله بهکاربردند .[8] از جمله این روش ها میتوان به الگوریتم صرفهجویی هزینه، روش 2 مرحلهای، روش مسیر ممنوع و روشهای جدیدتر مانند الگوریتم ژنتیک و الگوریتم هوش جمعی ذرات اشاره کرد.
آقایان Clarck و Wright نخستین افرادی بودند که از روش فراابتکاری الگوریتم صرفهجویی هزینه بهمنظور حل مسئله VRP استفاده کردند .[9] شرط اولیه این الگوریتم این است که هر وسیله حملونقل تنها به یک مشتری سرویس میدهد. بعدها تعدادی دیگر از محققین از الگوریتم بهبود یافته صرفهجویی هزینه جهت حل مسئله استفاده کردند [10] و .[11] Miller و Gillet الگوریتم رفت و برگشتی را برای حل مسئله VRP به کار بردند .[12] نتایج حاصل نشان دادند، کیفیت جوابهای این الگوریتم در حالات گوناگون ناپایدار است، به عبارت دیگر الگوریتم رفت و برگشتیغالباً در مسائل تصادفی جوابهای مناسبی ارائه میدهد. تعدادی دیگر از محققین از روش 2 مرحلهای استفاده کردند [13] و .[14] در این روش فراابتکاری، ابتدا دستهبندی مشتریان انجام میشود و سپس به یافتن مسیر مناسب بین هر وسیله حملونقل و مشتری هدف بهمنظور دستیابی به حداقل هزینه در هر مسیر پرداخته میشود. این در حالی است که، در برخی از روشهای دیگر ابتدا به یافتن مسیر و سپس دستهبندی مشتریان پرداخته میشود [15] و .[16] Mold و Jameson روش ابتکاری درجی را معرفی کردند .[17] آنها دو پارامتر و ʽ را جهت ساخت مسیر تعریف کرده و روش تبادل -3 انتخابی را برای بهبود کیفیت جوابهای مسئله به کار بردند.
ترکیب روش شبیهسازی گداختگی و جستوجوی محلی در الگوریتم صرفهجویی توسط Osman جهت تولید جواب اولیه اتخاذ شد .[18] در سال Gendreau 1994 و همکارانش از الگوریتم جستوجوی ممنوع با استفاده از روش مسیر ممنوع برای حل مسئله VRP استفاده کردند .[19] روش GTS توسط Toth و Vigo بهمنظور دستیابی به جواب بهینه در مسئله VRP استفاده شد .[20] بهعلاوه در سال Toth 2001 از ترکیب الگوریتم صرفهجویی هزینه با روش -3 انتخابی جهت جستوجوی همسایگی استفاده کرد .[21] نتایج این روش باعث بهبود جوابهای الگوریتم سنتی صرفهجویی در حل مسئله VRP شد.
نخستین افرادی که از الگوریتم ژنتیک بهمنظور ساخت مسیر در روند حل مسئله استفاده کردند، Baker و Ayechew بودند .[22] همچنین Bullnheimer و همکارانش از روش فراابتکاری نزدیکترین همسایه برای حل مسئله VRP در سیستم الگوریتم اجتماع مورچگان استفاده کردند .[23] در سال Szlachcic 2009 و Gwozdz روشی فراابتکاری بر پایه یک سیر تکاملی جهت حل مسئله مسیریابی وسایل حملونقل با ظرفیت محدود ارائه دادند .[24] روش آنها مشتمل بر اصلاح فرآیند انتخاب در مسئله و ارائه دو ابتکار در زمینه اپراتورهای متقاطع بود. در سال Venkatesan 2011 و همکارانش در مقاله خود به حل مسئله مسیریابی وسایل حملونقل با استفاده از الگوریتم هوش جمعی ذرات پرداختند .[25] این روش شامل یک الگوریتم رفت و برگشتی هوشمند جهت دستهبندی مجموعه مشتریان و سرویس دادن به آنها بهوسیله وسایل حملونقل میباشد.
-3 روش تحقیق
در علم کامپیوتر و تحقیق در عملیات، الگوریتم زنبورهای عسل یک الگوریتم بر پایه جمعیت است و از رفتار دسته زنبورهای عسل برای یافتن منابع غذایی تقلید میکند. در نسخه اصلی این الگوریتم یک نوع جستوجوی تصادفی در ترکیب با یک جستوجوی محلی استفاده میشود که میتوان از آن برای حل مسائل بهینهسازی ترکیبی استفاده کرد. این الگوریتم یکی از جدیدترین الگوریتمهای شناخته شده برای حل مسائل بهینهسازی است که از کارایی بالایی در میان سایر الگوریتمهای مبتنی بر هوش جمعی برخوردار است.
-1-3 الگوریتم کلونی زنبورهای مصنوعی - ABC3 -
الگوریتم کلونی زنبورهای مصنوعی برای اولین بار توسط Karaboga و در سال 2005 ارائه شد .[26] آقایان Karaboga و Basturk نشان دادند که در مسئله بهینهسازی توابع چند متغیره، کلونی زنبورهای عسل مصنوعی از الگوریتم ژنتیک و الگوریتم بهینهسازی بر پایه هوش جمعی ذرات بهتر عمل میکند و نتایج بهتری بدست میآورد .[27] همان طور که اشاره شد الگوریتم کلونی زنبورهای عسل بر پایه رفتار جستوجو گرانه زنبورهای عسل واقعی در پیدا کردن شهد گلها و به اشتراک گذاشتن اطلاعات مربوط به منابع غذایی در کندو گسترش مییابد.
