الگوریتم ژنتیک بهبود یافته برای حل مساله مسیریابی وسایل نقلیه

چکیده

 

چکیده
طراحی شبکه­‌های توزیع و جمع­آوری یکی از مهم­ترین مسائل مطرح در صنایع کنونی جهان است. در این صنایع، مسیر یابی وسایل حمل و نقل در نظر گرفته شده و مدل [۱]VRP را شکل دادهاند، به این معنا که مسیر بهینه­ی هر وسیله­ی نقلیه در مسیر مرتبط خود تعیین شود. یکی از کاربردهای این مساله در سیستم جمع­آوری زباله­های شهری است. اما مساله­ی اصلی در این سیستم­ها اینست که علاوه تعیین مکان­های استقرار وسایل نقلیه (وسایل حمل زباله)، بایستی مکان­های مراکز میانی تخلیه زباله­ها نیز تعیین شود و در عین حال وسایل نقلیه به صورت بهینه مسیریابی شوند. در این مقاله روشی یکپارچه برای حل این مساله با استفده از الگوریتم ژنتیک آمده است.
کلمات کلیدی: مسیریابی وسایل نقلیه، سیستم جمع­آوری زباله، الگوریتم ژنتیک
۱- مقدمه
مساله مسیریابی وسیله نقلیه یکی از مهمترین مسائل موجود در صنایع جهان است که امروزه به علت کاربردهای واقعی در مسائل صنعتی بسیار مورد توجه قرار گرفته است. در این مساله چندین وسیله نقلیه بطور همزمان از انبار (پارکینگ وسایل نقلیه) شروع به حرکت کرده و بعد از ملاقات کردن گره­های تقاضا (مشتریان) به انبار باز می­گردند، به شرط آن­که اولاً هر گره­ی تقاضا فقط توسط یکی از این وسایل نقلیه ملاقات شود و ثانیاً هر وسیله نقلیه بیشتر از ظرفیت خود در طول مسیر بارگذاری نکند. به کاربردن صحيح اين مساله حدود ۵ تا ۲۰ درصد در کل هزينه­ي حمل و نقل صرفه­جويي مي­کند.

از کاربردهای اصلی این مساله می­توان به جمع آوری زباله، توزیع و پخش مواد غذایی و دارو، مسیریابی سرویس مدارس و کارمندان، توزیع و پخش نامه­های پستی، برنامه­ریزی مسیر کشتی­ها، توزیع روزنامه، حرکت ربات­ها در کف کارخانه اشاره کرد.
اهدافی مختلفی تا به حال برای این مساله در نظر گرفته شده است که تعدادی از آن­ها عبارتند از:
· کمینه کردن مسیر پیموده شده توسط همه وسائل نقلیه
· کمینه کردن کل تعداد وسایل نقلیه
· کمینه کردن تابعی از زمان‌های دیرکرد یا زودکرد خدمت رسانی وسایل نقلیه به مشتریان
VRP میتواند دارای محدودیت­های متفاوتی باشد. برخی از این محدودیت­ها عبارتند از: تعداد مراکز سرویس دهی، محدود بودن یا نامحدود بودن ظرفیت خودروها، قطعی یا احتمالی بودن تقاضا، وجود یا عدم وجود محدودیت برای طول مسیر.
مساله VRPاز مسائل مشهور عدد صحيح است که در دسته مسائل NP-Hard قرار مي­گيرد. پيچيدگي اين مساله مربوط به دو مساله زير است:
۱-مساله فروشنده دوره گرد(Travel Salesman Problem)
اگر ظرفيت وسيله ي نقليه نامحدود در نظر گرفته شود VRP تبديل به مساله چند فروشنده دوره گرد([۲]MTSP) مي شود.
۲-مساله پوشش(Bin Packing Problem)
اين سوال که آيا يک جواب براي مساله VRP امکان پذير است يک مساله پوشش است.

انواع مسائل VRP
مساله VRP انواع مختلفي دارد که هر کدام شرايط مختلفي را در نظر مي­گيرند. هر يک از اين­ها داراي تابع هدف، فضاي امکان پذير و مدل رياضي خاص خود است. تعدادی از اين مسائل عبارتند از: CVRP،MDVRP، PVRP، SDVRP، SVRP، VRPTW و VRPPD
به عنوان مثال [۳]CVRPTWهمان مساله VRP است با اين تفاوت که هر وسيله نقليه ظرفيت يکنواختي از يک جنس خاص دارد. در مساله جمع­آوری زباله نیز ما به دلیل محدودیت در ظرفیت وسایل نقلیه با این مساله روبرو هستیم.
۲- ادبیات موضوع
با توجه به اهداف و محدودیت­های تعریف شده برای VRP و در نظر گرفتن عواملی مانند زمان و هزینه­های مورد نیاز جهت رسیدن به جواب و دقت مطلوب، روش­های مختلفی برای بدست آوردن جواب VRP وجود دارد که بطور کلی به سه دسته روش­های دقیق، ابتکاری و فراابتکاری تقسیم­بندی می­شوند.
روش­های دقیق:
در دهه­های ۱۹۶۰ و ۱۹۷۰ میلادی عمده تحقیقات انجام گرفته برای حل VRP بر روی روش­های دقیق متمرکز بود که برخی از آن­ها عبارتند از: برنامه­ریزی پویا، روش تبدیل VRP به TSP و فرمول­بندی دو اندیسی.
تبدیل VRP به :TSP
در این روش شبکه مورد نظر با اضافه کردن چند گره و یال مجازی تبدیل به شبکه دیگری می‌شود، که شبکه بدست آمده به صورت یک مساله TSP خواهد بود و با حل TSP می­توان مسیرهای مورد نظر و تعداد وسایل مورد نیاز را تعیین نمود.[۱[
برنامه ریزی پویا:
نمونه­ای از کاربرد برنامه ریزی پویا در حل VRP توسط ایلیون برای m خودرو که ظرفیت آن­ها مشخص می­باشد، ارائه شده است. در این تحقیق با تبدیل VRP به m مساله TSP جواب بهینه محاسبه گردیده است. [۱]
فرمول بندی سه اندیسی :
این فرمول بندی توسط فیشر ۳ و جی کومار ۴ ارائه گردیده است. فرمول بندی ارائه شده مساله تخصیص عمومی‌و مساله فروشنده دوره گرد با محدودیت زمانی را پوشش می­دهد. این روش ابتدا یک مساله اصلی GAP را برای تخصیص دادن نقاط به خودروها حل کرده و سپس بهترین مسیر برای هر خودرو از طریق حل یک TSPTW بدست می­آید. [ ۲ و ۳ و ۱[

روش­های ابتکاری:
VRP و TSP جزء مسائل Np- hard یا Np- complete می­باشند[ ۴ ] و با افزایش اندازه مساله حجم محاسباتی روش­های شناخته شده برای حل بهینه آنها دارای رشد نمایی است، بنابراین حل بهینه مسائل واقعی با اندازه بزرگ تقریبا غیر عملی است و به ناچار باید از روش­های ابتکاری و فراابتکاری برای محاسبه جواب قابل قبول و تقریباً بهینه استفاده شود. برخی از الگوریتم‌های ابتکاری VRP در ادامه آمده است.
الگوریتم صرفه جویی ( C& W)
این الگوریتم اولین بار توسط کلارک و رایت برای حل مسائل VRP با محدودیت ظرفیت و با تعداد نقاط محدود ارائه شد. این روش با ایجاد مسیرهایی که شامل مرکز و یک نقطه تقاضای دیگر است، شروع شده و در هر مرحله با توجه به بیشترین صرفه جویی ممکن دو مسیر با هم ترکیب می­شود.[۱,۲]
تعداد مسیرها( خودروها) توسط الگوریتم مشخص می­شود ولی در صورتی­که تعداد خودروها از قبل مشخص باشد، می­توان ترکیب مسیرها را تا جایی ادامه داد که تعداد مسیرهای موجود با تعداد مشخص شده برابر شود، حتی اگر میزان صرفه جویی منفی باشد.
الگوریتم جارو :
این الگوریتم توسط ژیلت و میلر ارائه گردیده و بر اساس روش­های دسته بندی مسیریابی عمل می­کند. در این روش به مراکز تقاضا مختصات قطبی تخصیص داده می­شود و بر اساس افزایش زاویه رتبه بندی می­شوند. از مرکزی که دارای کوچکترین زاویه بوده و به هیچ مسیری تعلق ندارد شروع و تا جایی که ظرفیت خودرو اجازه دهد، مراکز به خودرو اختصاص یافته و مسیر بهینه هر خودرو از طریق حل TSP بدست می­آید. در بین مسیرهای مجاور در صورتی که تغییر بعضی از نقاط بین دو مسیر، مسافت کل را کاهش دهد، تغییرات انجام و مجدداً مسیر بهینه هر خودرو محاسبه می­شود. کوچکترین مقدار بین جواب­های بدست آمده جواب VRP است.[۱,۲]
الگوریتم مسیر یابی کمانی:
این الگوریتم جزء طبقه مسیریابی دسته بندی بوده و توسط استرن و درور در مورد مسیر یابی متصدیان خواندن کنتور برق ارائه شده است. الگوریتم طی دو فاز مسیرهای بهینه را محاسبه می­کند. در فاز اول با استفاده از روش­های CPP یک مسیر اولر ایجاد می­شود و در فاز دوم با توجه به محدودیت­ها مراکز تقاضا دسته بندی می­شوند.[۵]
الگوریتم صرفه جویی برای مسیر یابی کمانی:
الگوریتم فوق مشابه الگوریتم صرفه جویی در مسیریابی گره­ای بوده و توسط گلدن و وانگ ارائه گردیده است. در این الگوریتم همه مراکز تقاضا در مسیرهای جداگانه قرار گرفته و با توجه به محدودیت­های موجود ترکیب زوج مسیر‌های ممکن بررسی و دو مسیری که بیشترین صرفه جویی را ایجاد می­کند، با یکدیگر ترکیب می­شوند.[۶]

روش­های فراابتکاری:
الگوریتم­های فراابتکاری بسیاری درحل مساله مسیریابی خودروها استفاده شده که از آن جمله می­توان به الگوریتم ژنتیک اشاره نمود. استفاده از این الگوریتم در حلVRP، توسط افراد مختلفی بررسی گردیده که به عنوان نمونه می‌توان به تحقیقات پریرا، تاوارس ، ماچادا و کاستا اشاره نمود. در این تحقیقات کاربرد الگوریتم ژنتیک در مسائل مسیریابی با محدودیت ظرفیت ( CVRP) و مسیریابی با محدودیت زمانی ( VRPTW) بررسی گردیده است. نتایج محاسباتی نشان دهنده کارائی بالای این روش است [۷,۸,۹]. نمونه­ای از تلاش­های انجام شده برای استفاده از الگوریتم جستجوی ممنوع و سیستم بهینه سازی مورچگان در مراجع ۱۰ و ۱۱ موجود است.
۳- مدل ریاضی
در این قسمت به بیان مدل ریاضی مساله CVRP پرداخته می­شود.

CVRP

محدودیت ۲ تضمین می­کند که هر مشتری فقط توسط یک وسیله سرویس بگیرد. در محدودیت ۳ قید ظرفیت ماشین­ها اعمال می­گردد. به عبارت دیگر مجموع حجم تقاضای مشتریانی که به یک ماشین تخصیص داده می­شود بایستی حداکثر برابر با ظرفیت ماشین باشد. معادلات ۴ و ۵ تضمین می­کند که مسیرها پیوسته باشند. در این معادلات موازنه جریان ورود و خروج وسایل نشان داده شده است. به عبارت دیگر تعداد ماشین­هایی که به هر گره وارد می­شود برابر با تعداد ماشین­هایی است که از آن­ها خارج می­شوند.
متدولوژی حل
برای حل این مساله در حالت جمع­آوری زباله از الگوریتم ژنتیک استفاده شده است. الگوريتم­هاي ژنتيک از اصول انتخاب طبيعي داروين براي يافتن فرمول بهينه جهت پيش بيني يا تطبيق الگو استفاده مي­کنند. قانون انتخاب طبيعي بدين صورت است كه تنها گونه‌هايي از يك جمعيت ادامه نسل مي‌دهند كه بهترين خصوصيات را داشته باشند و آن­هايي كه اين خصوصيات را نداشته باشند به تدريج و در طي زمان از بين مي‌روند. موتور الگوريتم ژنتيک يک جمعيت اوليه تصادفي از پاسخ‌هاي ممكن براي مسئله ايجاد مي­کند كه هريك از اين پاسخ­ها در قالب يك كروموزوم داراي تعدادي ژن ( هر ژن نماينده ي يك مجهول مسئله مي باشد) بوده و به صورت مناسبي كدگذاري شده­اند. در مرحله بعدي هر كروموزوم در برابر مجموعه­اي از معيارها مورد آزمايش قرار مي­گيرد. تابع برازش با توجه به ميزان موفقيت هر كروموزوم در حل مسئله ارزش آن­ها را معين مي­كند. سپس بر اساس اين ارزش­ها كروموزوم­ها به ترتيب صعودي به نزولي مرتب مي شوند تا x% از آنها حفظ شده و بقيه حذف شوند. براي جايگزيني اين كروموزوم­هاي حذف شده، كروموزوم­هاي باقي­مانده به نحوي دو به دو انتخاب شده و توليد فرزند مي­كنند. يك نحوه­ي اين انتخاب اينست كه مجموعه كوچكي از كروموزوم­ها به صورت تصادفي انتخاب شده و سپس از بين اين كروموزوم­ها، دو كروموزومي كه داراي ارزش بيشتري هستند به­عنوان والدين براي توليد فرزند انتخاب مي­شوند. شرايط خاتمه الگوريتم­هاي ژنتيک عبارتند از:
· بودجه اختصاص داده شده تمام شود(زمان محاسبه/پول).
· يک فرد(فرزند توليد شده) پيدا شود که مينيمم (کمترين)ملاک را برآورده کند.
· بيشترين درجه برازش فرزندان حاصل شود يا ديگر نتايج بهتري حاصل نشود.
· بازرسي دستي.
· ترکيب­هاي بالا.

روش­هاي نمايش
قبل از اين که يک الگوريتم ژنتيک براي يک مسئله اجرا شود، يک روش براي کد کردن ژنوم­ها به زبان کامپيوتر بايد به کار رود. يکي از روش­هاي معمول کد کردن به صورت رشته‌هاي باينري است(رشته‌هاي ۰و۱). يک راه حل مشابه ديگر کدکردن راه حل­ها در آرايه­اي از اعداد صحيح يا اعشاري است،که دوباره هر جايگاه يک جنبه از ويژگي­ها را نشان مي­دهد. الگوريتم­هاي ژنتيکي که براي آموزش شبکه­هاي عصبي استفاده مي­شوند، از اين روش بهره مي­گيرند. سومين روش براي نمايش صفات در يک GA يک رشته از حروف است که هر حرف دوباره نمايش دهنده يک خصوصيت از راه حل است. در این مساله ما از کدگذاری عدد صحیح استفاده کردیم، به این­صورت که هر کروموزوم توالی گره­های تقاضا در مسیرها را نشان می­دهد.
روش‌هاي انتخاب
روش‌هاي مختلفي براي الگوريتم­هاي ژنتيک وجود دارند که مي­توان براي انتخاب كروموزوم­هاي والد از آن­ها استفاده کرد. تعدادی از این روش­ها عبارتند از:
۱. انتخاب Elitist : مناسبترين عضو هر اجتماع انتخاب مي­شود.
۲. انتخاب Roulette : يک روش انتخاب است که در آن عنصري که عدد برازش(تناسب) بيشتري داشته باشد، انتخاب مي­شود.
۳. انتخاب Scaling : به موازات افزايش متوسط عدد برازش جامعه،سنگيني انتخاب هم بيشتر مي شود وجزئي­تر. اين روش وقتي کاربرد دارد که مجموعه داراي عناصري باشد که عدد برازش بزرگي دارند وفقط تفاوت­هاي کوچکي آن­ها را از هم تفکيک مي­کند.
۴. انتخاب Tournament : يک زير مجموعه از كروموزوم­هاي يک جامعه انتخاب مي­شوند و اعضاي آن مجموعه با هم رقابت مي­کنند و سرانجام فقط دو كروموزوم از هر زير گروه براي توليد انتخاب مي­شوند.
بعضي از روش­هاي ديگر عبارتند از:Rank Selection, Generational Selection, Steady-State Selection .Hierarchical Selection
عملگر تقاطع:
در این عملگر که Crossover نام دارد، ۲ کروموزوم براي معاوضه ژن­هایشان انتخاب مي­شوند. اين فرآيند بر اساس فرآيند ترکيب کروموزوم­ها در طول توليد مثل در موجودات زنده شبيه سازي شده است. اغلب روش­هاي معمول Crossover از نوع Single-point Crossover هستند، که نقطه تعويض در جايي تصادفي بين ژن­هاي كروموزوم­ها است. بخش اول قبل از نقطه و بخش دوم سگمنت بعد از آن ادامه پيدا مي­کند،که هر قسمت برگرفته از يک والد است.
عملگر جهش:
این عملگر دقیقاً مثل جهش در موجودات زنده است که عبارت است از تغيير يک ژن به ديگري. در الگوريتم ژنتيک جهش تغيير کوچکي در يک ژن از کد كروموزوم ايجاد مي­کند.

پیام بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

+ thirty five = thirty six