جستجو در سایت

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

Get Started

MDVRP را می توان در مدل ریاضی به صورت زیر فرمول نویسی نمود.  فرض کنید G=(VCU VD,R) گراف جهت داری است که VC مجموعه متشکل از مشتریان و VD مجموعه متشکل از انبارها می باشد. فرض می شود مختصات همه مشتریان و انبارها معلوم می باشد. VC= {c1,c2,. . .,cn}، که n تعداد مشتریان را نشان می دهد و{d1,d2,. . .,dm} vd= که m تعداد انبارها را نشان می دهد. مجموعه R، مجموعه کلیه مسیرها بین انبارها و مشتریان می باشد. هر مسیر دارای هزینه های مختص خود می باشد و همچنین فرض می شود هزینه های هر مسیر معلوم است. به عنوان استاندارد این نوع مسئله، هزینه ها در طول مسیر نشان داده می شوند. راهکار جایگزین، نشان دادن زمان رانندگی روی مسیر خواهد بود.  Riis مسیری برای یک خودرو (وسیله نقلیه) می باشد: /= j}, R = {(ri, rj) : ri, rj VC∪ VD, I ، که در این رابطه lijis فاصله مسیر (ri,rj) را نشان می دهد. تعریف مسئله کلاسیک آن است که lijis متقارن است و به همین خاطر نامساوی مثلثی را بدست می آورد: lij= ljiبرای هر i,j. Riis مسیر یک خودرو است که در انبار شروع شده، از برخی مشتریان بازدید به عمل آورده و در انبار اولیه کارش را به پایان می رساند: Ri= {d, c1, . . ., cl, d}، که d ∈ VD، di تقاضای مشتری و mk ظرفیت خودرو را نشان می دهد. محدودیت ها به شرح ذیل می باشد: جمع تقاضاهای مشتری روی یک مسیر نبایستی بیشتر از ظرفیت خودرویی باشد که سرویس دهی را در مسیر انجام می دهد، خودروها درست یکبار به مشتری سرویس دهی می کنند، هر خودرو باید در یک انبار کارش را شروع کرده و به پایان برساند و هیچ مشتری تقاضای بیشتر از ظرفیت خودرو ندارد.

هدف  مسئله MDVRP به حداقل رساندن مجموع کل مسیرها،  VD) _(j VC VD))lij  in( _(i VC و به حداقل رساندن تعداد خودروهای مورد نیاز می باشد.

3. استفاده از الگوریتم ژنتیک برای حل مسئله MDVRPA. GA کلاسی از الگوریتم های بهینه سازی تصادفی تطبیقی است که از اصول تکامل طبیعی برای اجرای جستجو و بهینه سازی استفاده می کند. از آن به عنوان یک تکنیک بهینه سازی برای محاسبه راه حل های بهینه یا نزدیک به بهینه برای مسائل جستجو استفاده می شود. GA زیرمجموعه ای از الگوریتم های تکاملی است که از فرایند طبیعی فیلد بیولوژی یا زیست شناسی تقلید می شود.  فرایند طبیعی پایه در اصل توسط داروین با سه اصل پایه تشریح گردید: تولید مثل، انتخاب طبیعی و تنوع افراد. از این اصول پایه در GA استفاده شده است. فرایندهای تکامل و انتخاب طبیعی روی جمعیتی از راه حل های انتخابی ( افراد) محاسبه می شوند. هر فرد در جمعیت نمایانگر راه حلی خاص برای مسئله می باشد و این فرد با مجموعه ای از خصوصیات نمایش داده می شود که در کروموزوم یا ژنوتیپ فرد درست مثل طبیعت، نوشته شده اند.

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

مثل طبیعت، در GA، جمعیت با گذشت زمان تکامل می یابد. تکامل با تشکیل نسل جدیدی از افراد با فرایند جفت گیری رخ می دهد ( تولید مثل). شرکای جفتگیری با استفاده از عملگر انتخاب براساس برازششان انتخاب می شوند. از جهش ( تغییر تصادفی کوچک) نیز در الگوریتم تقلید می شود، اما کار متفاوتی انجام می دهد- آن فضای جستجو را عریض می نماید. تا جایی که می دانیم GA توسط Holland در سال 1975 توسعه یافت و با De Jong و Goldberg به تکامل خود ادامه داد، آنها روش استفاده از آن برای حل مسائل بهینه سازی پیچیده را نشان دادند. انواع دیگر الگوریتم های تکاملی عبارتنداز: استراتژیهای برنامه ریزی ژنتیک و تکامل ژنتیک، اما خارج از حیطه این مقاله هستند. GA یک فرایند تکراری است و تکرارها نسل ها نامیده می شوند.

فرایند اصلی GA در شکل 3 نشان داده شده است. بعد از مقدار دهی اولیه جمعیت اولیه، حلقه تکاملی اصلی با ارزیابی هر فرد طبق تابع برازش شروع به کار می کند.براساس نمرات برازش افراد از جمعیت با استفاده از یکی از روشهای انتخاب بعداً تشریح شده انتخاب می شوند. به طور کلی، هرچه برازش یک فرد بیشتر باشد، به همان نسبت شانس انتخاب او بیشتر می باشد. مجدداً از طبیعت تقلید می شود، زمانی که افراد انتخاب شده برای طی کردن فرایند جفت گیری باهم جفت می شوند ( کراس اور) و یک یا چند فرزند از هر جفت تولید می شود. فرایند کراس اور به شیوه ای پیاده می شود که فرزندان بایستی دارای ویژگیهای والدینشان باشند.معمولاً این فراینداز کپی کردن بخشی از ژنوتیپ از یک والد و پرکردن ژنهای گم شده از والد دیگر تشکیل می شود. تکنیک های متفاوت زیادی از کراس اور با گذشت زمان پیشنهاد گردید، اما همان گونه که در قسمت های بعدی خواهیم دید، هیچ تکنیک عمومی نمی تواند روی انواع و اقسام مسائل عملکرد کاملی به معرض نمایش بگذارد.

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

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