جستجو در سایت

تماس با ما: 09361509687  ایمیل: royalproje.ir[ at ]gmail.com

Get Started

مسئله مسیریابی خودرو (وسیله نقلیه) ( از حالا به بعد VRP)، یک مسئله کلاسیک می باشد که ابتداعاً در سال 1959 توسط Danrzig و Ramser توصیف گردید و برگرفته از مسئله فروشنده دوره گرد یا مسئله مسیریابی قوس می باشد. مسئله مسیریابی قوسی اصولاً مسئله ای است که در آن سعی می کنیم راهی بهینه برای ساخت مسیر پیدا کنیم به شیوه ای که مسیر کوتاهترین مسیر ممکن باشد. VRP این مسئله را به شیوه ای توسعه می دهد که مجموعه ای از مشتریان یا ایستگاهها وجود دارد و وسیله نقلیه باید از آنها بازدید به عمل بیاورد و این وسیله نقلیه باید سفرش (حرکت) را در ایستگاه انبار خانگی شروع و به پایان برساند. این مسئله اصولاً بازتابی از مسائل توزیع زندگی واقعی مثلاً تحویل و سوار کردن مسافرین، بسته های پستی، بسته ها و انواع مختلف کالاها می باشد.

از زمان پیشنهاد آن توسط Danzig، در جامعه علمی مورد توجه واقع شده و روشهای درست و ابتکاری زیادی برای حل آن پیشنهاد شده است. تحقیق حاضر بر کاربردی ترین تغییرات این مسئله یعنی VRP چند انباری (MDVRP) تاکید می کند. آن مسئله کلاسیکی را با معرفی ظرفیت وسایل نقلیه و تقاضا برای مشتریان و اضافه کردن انبارهای متعدد، توسعه می دهد. MDVRP مثل VRP، یک مسئله بهینه سازی ترکیبی از نوع NP-hard می باشد و به همین خاطر یافتن راه حل بهینه برای آن سخت و دشوار می باشد. در حالیکه روشهای درست مسائل کوچک را به شکلی کاملاً کارا حل می کنند، اما برای مسائل بزرگتر یا انواع خاصی از گونه های VRP، مسائلی به قوت خود وجود دارد. از طرف دیگر، روشهای فراابتکاری در مدت زمان کمتر به راه حل ها دست یافته و یکی از این نوع روشها، الگوریتم ژنتیک (GA) می باشد- الگوریتمی که از فرایند طبیعی تکامل تقلید می کند. شیوه های فراابتکاری مختلفی برای حل VRP و مسائل حمل و نقل متغیرش وجود دارد. راه حل های پیشرفته عبارتنداز: شیوه بهینه سازی ازدحام ذرات، بهینه سازی کلونی مورچگان، شیوه ژنتیکی، تبرید شبیه سازی شده و جستجوی ممنوع.

این شیوه ها در انواع و اقسام مسائل حمل ونقل شبیه به VRP، نظیر مسئله مکان یابی تسهیلات مفید واقع می شوند که هدف اصلی، یافتن مکان بهینه انبار مرکزی با در نظر گرفتن مکان ایستگاهها می باشد. موضوع مسئله مکان یابی تسهیلات قبلاً در مقالات پژوهشی به طور جامع مورد تحقیق و پژوهش قرار گرفته است.در [18] و [19]، مولفین شیوه های فراابتکاری در مورد این مسئله مکان یابی تسهیلات و برنامه ریزی مکانی را باهم مقایسه کردند. نتایج بدست آمده از این مقالات نشان می دهد مزیت اصلی GA در مقایسه با سایر الگوریتم های فراابتکاری عملکردو نتیجه نهایی محدودیت های زمانی و توان محدود کامپیوتر می باشد، در حالیکه به راه حل های رقابتی نیز منتج می شود. هرچند برخی از روشهای فراابتکاری دیگر توانایی یافتن راه حل های بهتری نسبت به GA را دارند، اما GA به طور کلی راه حل های کافی ( به اندازه کافی خوب) در چارچوب زمانی کوتاهتر بدست می آورد. یکی از دلایل کاربرد GA در حل مسائل مسیریابی، مکانیابی و سایر مسائل سخت، همین مسئله می باشد. تحقیقات زیادی در مورد حل مسئله VRP با GA انجام شده است که محققین بر کاربرد عملی GA در مسائل VRP و دنیای واقعی تاکید کردند.

شکل 1. تعداد مقالات منتشر شده در سال پیرامون کاربرد GA در حل VRP ( با استفاده از رشته جستجو: الگوریتم های ژنتیک مسائل مسیریابی خودرو) طی 20 سال گذشته

تحقیق سیستماتیک پیرامون تاثیر جنبه های مختلف، عملگرها، گونه ها ( متغیرها) و تنظیمات GA بر فرایند جستجو و راه حل های بدست آمده وجود ندارد.

بنابراین اهداف این تحقیق عبارتنداز کشف زمینه یا پیشینه حل MD VRP با GA، نگاه کردن، ارزیابی و مقایسه شیوه های مختلف بکاررفته، بحث راجع به نحوه ساخت این نوع GA برای حل کارای MD VRP. اگرچه MD VRP و کاربرد GA برای حل آن طی سالیان دراز شناخته شده است، اما تعداد GAها برای حل MD VRP رو به رشد می باشد ( شکل 1). یعنی، ادبیات پژوهشی راه حل های خوب GA برای MD VRP را گزارش می کند که دور از حد بهینه نیستند و در عین حال، منابع محاسباتی مورد نیاز برای یافتن راه حل در مرزهای بسیار مطلوب را حفظ می نماید. در این زمینه، کاربرد GA برای حل MD VRP را به طور مفصل مورد بررسی قرار می دهیم. به علاوه، نتایج استفاده از کاربردی ترین عملگرها و یا تنظیمات درادبیات پژوهشی روی مجموعه ای از مسائل محک استاندارد، را مطرح کرده و راجع به آنها به طور مفصل بحث می کنیم. رئوس این مقاله به شرح ذیل می باشد. مقاله را با کلیاتی از VRP و تغییراتش شروع می کنیم. سپس فراوان ترین تغییرات را شرح داده و MDVRP را فرمول نویسی می کنیم چراکه نقطه تاکید اصلی تحقیق حاضر می باشد. با اصول GA کار را ادامه داده و کل فرایند را از تهیه و آماده سازی داده ها تا حلقه تکاملی اصلی الگوریتم توصیف نموده و با بینش هایی در مورد عملگرهای ژنتیک کارمان را به پایان می رسانیم.

سپس با موضوع اصلی این مقاله، یعنی حل مسئله MDVRP با GA ادامه می دهیم که با کلیاتی در مورد پیشینه این شیوه شروع می شود. سپس معمول ترین روش نمایش مجدد این مسئله به شکل ژنتیک فهرست بندی می شود. در ادامه به عملگرهای ژنتیکی بکاررفته برای این مسئله خاص نگاه می کنیم- در این رابطه عملیات های کراس اور، جهش، انتخاب و سایر عملگرهای بکاررفته را توصیف می نماییم. برای بخش دوم مقاله، نمونه کاری اولیه ای از GA برای حل مسئله MD VRP توسعه داده و آن را شدیداً مورد آزمون قرار می دهیم. ابتدا، با مقایسه برخی از کاربردی ترین عملگرها شروع کرده و سعی می کنیم در مورد مناسب ترین اینها برای این نوع مسئله تصمیم گیری نماییم. در پایان، راه حل های مبتنی بر GA را با برخی از راه حل های موجود دیگر، درست و ابتکاری، روی مجموعه ای از مسائل محک استاندارد مقایسه می نماییم.

2. مسئله مسیریابی خودرو (وسیله نقلیه).VRP یک مسئله کلاسیک است که نمایانگر موقعیت های زندگی واقعی از فیلد توزیع می باشد. در تئوری، برگرفته از دو مسئله بهینه سازی پایه می باشد: مسئله فروشنده دوره گرد (TSP) و مسئله مسیریابی قوسی. هدف TSP ، حل مسئله فروشنده ای است که مجبوراست از کلیه شهرها بازدید به عمل آورده و در همان زمان مسیر کل را تا حد امکان کوتاه نگه دارد- آن در واقع مسئله به حداقل رساندن را نشان می دهد. روشهایی برای حل آن توسعه یافته است که برخی از آنها درست بوده و دیگران سعی کردند به روش ابتکاری آن را حل کنند.

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

شکل 2. مسئله مسیریابی خودرو چند انباری 

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

[1]. multi depot capacitated vehicle routing problem

اشتراک برای
آپ دیت ودریافت خبرها