مقاله حل مسئله مسیریابی وسایل نقلیه
این مقاله یک الگوریتم تقریبی مبتنی بر آتاماتای یادگیر توزیع شده برای حل مسئله مسیریابی وسایل نقلیه با ظرفیت ارائه می دهد.مسئله مسیریابی وسایل نقلیه (VRP) جز مسائل NP-Hard می باشد و مسئله مسیریابی وسایل نقلیه با ظرفیت (CVRP) نوعی از این در نظر گرفته شده است. این مسئله یکی از مسائل NP-Hard است و به همین دلیل الگوریتم های تقریبی فراوانی برای حل آن طراحی شده اند.
آتاماتای یادگیر توزیع شده یک ابزار جستجوی عمومی و یک ابزار حل برای انواع مسائل NP-Complete است، که برای حل این مسئله استفاده شده است و روی چهارده مسئله بنچمارک آزمایش شده است. نتایج ما با بهترین نتایج شناخته شده مقایسه شد. نتایج حاصل از مقایسه، کارایی الگوریتم پیشنهادی را نشان می دهد.
مسئله مسیریابی وسایل نقلیه، مسئله مسیریابی وسایل نقلیه با ظرفیت، آتاماتای یادگیر توزیع شده، جستجوی اکتشافی محلی دو انتخابه، لیست کاندید، عمل جهش.
پیدا کردن مسیر وسایل نقلیه کارآمد یک مسئله مهم تدارکاتی است که برای چندین دهه مورد مطالعه قرار گرفته شده است. هنگامی که یک شرکت قادر به کاهش طول مسیرهای انتقال یا قادر به کاهش تعداد وسایل نقلیه می شود، آن قادر می سازد که خدمات بهتری به مشتریان خود ارائه دهد، و در روشی کارآمدتر عمل کند و احتمالا سهام بازار افزایش یابد. یک مسئله مسیریابی وسایل نقلیه معمولی عبارت است از تعیین همزمان مسیر برای وسایل نقلیه مختلف از یک انبار عرضه مرکزی به تعدادی از مشتریان و بازگشت به انبار بدون تجاوز از محدودیت ظرفیت هر خودرو.
روند انتخاب مسیرهای خودرو اجازه می دهد تا انتخاب از هر ترکیبی از مشتریان در تعیین مسیر برای تحویل هر خودرو باشد. بنابراین، مسئله مسیریابی وسایل نقلیه یک مسئله بهینه سازی ترکیبی است که در آن تعدادی از راه حل های عملی برای مسئله را به صورت نمایی با تعدادی از مشتریان سرویس گرفته را افزایش می دهد.
علاوه بر این، مسئله مسیریابی وسیله نقلیه تا حدودی شبیه مسئله فروشنده دوره گرد است به صورتی که یک رفت و برگشت از یک مکان مرکزی برای هر وسیله نقلیه تعیین شده است. از آنجا که الگوریتمی با پیچیدگی زمانی چند جمله ای یافته نشده است که راه حل بهینه در هر نمونه پیدا کند،مسئله مسیریابی وسایل نقلیه جز مسائل NP-Hard در نظر گرفته شده است [1].
از آنجا که این مسئله برگرفته از طبیعت است، استفاده از روش های دقیق برای حل نمونه های زیادی از مسئله واقع بینانه نیست. چندین روش ترکیبی اکتشافی برای حل مسئله VRP پیاده سازی شده است. برخی از آنها عبارتند از: یک روش جستجوی ترکیبی آمیخته با شبیه سازی حرارتی غیر یکنواخت تپه نوردی و راه اندازی مجدد تصادفی [2]، روش ترکیبی گسسته الگوریتم بهینه سازی گروه ذرات (DPSO) [3]، روش بهبود یافته ی بهینه سازی کلونی مورچه ها (IACO) [4]، الگوریتم بهینه سازی جفت گیری زنبور عسل [5]، الگوریتم بهینه سازی شده ی ترکیب ژنتیک[6].
در این مقاله از یک الگوریتم کارآمد آتاماتای یادگیر توزیع شده (DLA) برای پیدا کردن راه حلهای مسئله مسیریابی وسایل نقلیه با ظرفیت استفاده می شود. به منظور تست الگوریتم پیشنهادی ما از چهارده مسئله بنچمارک استفاده کرده ایم. این مقاله به شرح زیر سازماندهی شده است. بخش 2 مسئله مسیریابی وسایل نقلیه با ظرفیت را ارائه می دهد. بخش 3 آتاماتای یادگیر و آتاماتای یادگیر توزیع شده را توصیف می کند. بخش 4 سه استراتژی بهبود را توصیف می کند. در بخش 5 جزئیات پیاده سازی از الگوریتم DLA برای مسئله CVRP شرح داده شده است. بخش 6 تجربیات و نتایج را ارائه می کند. نتیجه گیری و برخی از طرح های احتمالی برای آینده در بخش 7 هستند.
نقد و بررسیها
هیچ دیدگاهی برای این محصول نوشته نشده است.