No category

پایان نامه رایگان درمورد الگوریتم ژنتیک، جستجوی محلی، برنامه ریزی

رسانی کرده اند. آنها لیستی از مقالات VRPPD و ویژگی های بارزشان را نیز منتشر کردند. سهلی و نگی روش های سازنده 29 خود را با افزودن عملگرهای گره که به پالایش جواب منتج می شوند بهبود دادند. آنها 3 روش ابتکاری جدید را معرفی کرده و کارایی آنها را با 3 روش از بهترین روش های قبلی خود مقایسه کردند.
چن و وو [40] مطالعه ای روی یک مساله مشابه انجام دادند. آنها دو الگوریتم را بسط دادند. اولین الگوریتم ، یک روش ابتکاری براساس جاسازی30 است که همچنین جواب اولیه را برای الگوریتم دوم ایجاد می کند. الگوریتم دوم یک روش فراابتکاری ترکیبی است که به مانند روش شبیه سازی تبرید عمل می کند اما آنها قوانین قطعی را با حرکت های احتمالی جایگزین کردند. همچنین الگوریتم جستجوی ممنوع را برای جلوگیری از تکرار بهینه محلی در نظر گرفته شده است و سرانجام اصلاح جواب ها با بکارگیری جانشینی گره ها31 و عملگرهای مبادله ای32 صورت گرفته است. الگوریتم بر روی 14 مثال سلهی و نگی اجرا شد و آنها مدعی شدند که نتایجی بهتر از نتایج سلهی و نگی در سال 1999 کسب کردند اما آنها هیچ مقایسه ای با نتایج بهبود یافته آنها در سال 2005 و نتایج دثلوف نداشتند. آنها همچنین با تغییر در مثال های سولومون با بکارگیری روش سلهی و نگی تولید مساله کردند.
دل آمیکو و همکاران [44] نیز در سال 2006 یک روش دقیق برای حل VRPSPD ارائه دادند که یک الگوریتم بهینه سازی مبتنی بر تولید ستونی33 ، برنامه ریزی پویا و روش Branch & Price بوده است اما روشآنها دارای پیچیدگی های محاسباتی بالایی است بطوریکه برای حل یک مساله اندازه کوچک با 40 مشتری حتی یک ساعت هم زمان مناسبی نیست.
مطالعات به عمل آمده توسط مونتانه و گالوائو [24] از حمل و نقل کارکنان بین ماینلند برزیل و سکوهای نفتی در آب های آزاد از طریق هلی کوپترها الهام گرفته شده است. در این مساله از آنجایی که هلیکوپتر ها می توانند بین دو نقطه پرواز کنند محدود به عواملی از قبیل سوخت می باشند لذا به مساله اصلی محدودیت اضافی حداکثر مسیر طی شده بین گره ها نیز افزوده شده است. از جابجایی کارکنان بین سکوهای مختلف جلوگیری شده که مساله را تبدیل به مثالی از VRPSPD کرده است. در مطالعه آنها از نسخه اصلاح شده روش های ابتکاری (sweep) و جدا سازی مسیر34 استفاده شده است. جواب های اولیه به عنوان ورودی در روش جستجوی ممنوع استفاده می شود، جستجوی ممنوع هنگامی پایان می یابد که دیگر بهبودی رخ ندهد و یا حداکثر تکرار بدست آمده باشد. نویسندگان مطالعات خود را با 87 مثال از دثلوف ، سلهی و نگی، مین و 18 مثال اصلاح شده از سولومون آزمایش کرده و نتایج را ارائه کردند.
بیانچسی و ریقینی[47] الگوریتم های جستجوی ممنوع و جستجوی محلی بر روی مساله VRPSPD خود به کار گرفتند. آنها ابتدا جواب های اولیه را با به کارگیری 4 قانون متفاوت انتخاب گره ها با توجه به تلرانس تخطی گنجایش و شدنی بودن کل مسیر به وجود آوردند، سپس جستجوی محلی در همسایگی های مختلف را با استفاده از معاوضه گره ها به کار بردند با این توضیح که رویه جستجوی به کار گرفته شده دقیقا همان روش VNS 35 که سیلور36 در سال 2004 ارائه کرده است. آنها همچنین الگوریتم خود را برای مثال های دثلوف به کار گرفته و بهبودهایی که نسبت به جواب های دثلوف داده بودند ارائه کردند اگرچه برای مثال های معیار سایر محققان چنین مقایسه ای را ارائه ندادند.
آی و همکاران [57] از روش فراابتکاری جدید برای حل VRPSPD استفاده کردند. مطالعه آنها دو ویژگی اصلی داشت ابتدا آنها VRPSPD را دوباره مدل سازی کردند بطوریکه نتایج بهتری از مدل مین و دثلوف حاصل شد و دومین ویژگی کار آنها نیز بهره گیری از روش فراابتکاری PSO 37 که نشان دهنده این مطلب است که چگونه نسخه با مقادیر حقیقی PSO برای حل VRPSPD کاربردی شده است. الگوریتمی که آنها استفاده کردند به جای مقادیر گسسته برای متغیر های جستجو از قادیر (پیوسته) استفاده کرده و همچنین از هیچ گونه روش جستجوی محلی بهرگیری نکرده است. نویسندگان نتایج مطالعه خود را با نتایج چند مطالعه دیگر مقایسه کردند، ابتدا برای مسائلی با کمتر از 40 مشتری از مثال های معیار دل آمیکو و روش دقیقی که دل آمیکو همکاران ارائه کردند به مقایسه پرداختند. همچنین برای مسائلی با 50 مشتری از مثال های معیار دثلوف نتایج مطالعات خود را با دثلوف، تانگ و گالوائو، بیانچسی و ریقینی مقایسه کرده و کارایی روش خود را به رخ کشیدند. در آخر برای مسائلی بین 50 تا 99 مشتری از مثال های معیار سلهی و نگی نتایج PSO را با نتایج روش های دثلوف، سلهی و نگی، تانگ و گالوائو مقایسه نموده و ارائه کردند.
یانگ و اربائو [42] روش فراابتکاری بهبود یافته تفاضل تکاملی را برای VRPSPD با در نظر گرفتن پنجره زمانی به کار گرفتند. آنها ابتدا یک مدل عدد صحیح مختلط برای VRPSPDTW ارائه کردند، آنها ابتدا از یک روش کدینگ ده دهی برای ایجاد جمعیت اولیه استفاده کرده و سپس عملگرهای روش تفاضل تکاملی بهبودیافته را بکار بردند. عملگر جهش مورد استفاده آنها براساس ترتیب صحیح اعداد طبیعی، عملگر تقاطعی آن یک روش خود وقف دهنده38 با تعداد تکرارهای متفاوت و همچنین برای ایجاد جواب های شدنی از یک روش جریمه دهی استفاده شده است. در انتها، آنها روش خود را با الگوریتم ژنتیک مقایسه کرده و کارایی مطالعات خودرا نشان دادند. در نهایت، جینگ فان [26] مسئله مسیریابی وسائل نقلیه با تحویل و دریافت همزمان برپایه طبقه بندی مشتریان (VRPSPDCS) مورد بررسی قرار داده است. او پس از ارائه یک مدل ریاضی، برای حل مسئله مورد مطالعه خود، الگوریتم فراابتکاری جستجوی ممنوع را بهبود داده و مود استفاده قرار داده است.
در ادبیات VRP توجه کمی نسبت به رانندگان صورت گرفته است، تنها در چند سال اخیر مطالعاتی در مورد زمان کاری رانندگان، قوانین ساعات کاری و زمان استراحت آن ها مورد توجه قرار گرفته است. در این زمینه یکی از اولین مطالعه ها را زو و همکاران [34] ارائه دادند که یک مسئله کاربردی دریافت و تحویل با چندین پنجره زمانی و محدودیت ساعات کاری رانندگان اعمال شده توسط دپارتمان حمل و نقل ایالات متحده را مورد مطالعه قرار دادند. آن ها برای حل مدل ارائه شده خود، رویکرد ترکیبی از تولید ستونی و یک روش ابتکاری سریع برای زیر مسئله هایی که در تولید ستونی ایجاد شده، بهره گرفتند و کارایی این روش را با مثال های تصادفی تولید شده توسط خود، نشان دادند.
جوئل و همکاران [6] در سال 2006 برای یک مسئله مسیریابی و زمانبندی وسائل نقلیه با توجه به قوانین ساعات کاری رانندگان در اتحادیه اروپا مطالعات خود را ارائه نمودند. در سال 2011 جوئل و همکاران[4] مسئله فوق را با در نظر گرفتن ساعات کاری قوانین کشور استرالیا مورد مطالعه قرار دادند و از روش های ابتکاری که خود ارائه نمودند، برای حل آن ها استفاده کردند. همچنین جوئل [5] در سال 2012 مسئله زمانبندی کامیون ها را با در نظر گرفتن قوانین ساعات کاری در کشور کانادا ارائه داد. او برای مسئله خود یک مدل مختلط صحیح ارائه نمود و از رویکرد برنامه ریزی پویا تکرار شونده برای حل آن استفاده نمود.
2-6- مروری بر تحقیقات انجام شده در مورد مساله مسیریابی وسایل نقلیه دارای چند مرکز تامین (MDVRP)39
مسیریابی وسایل نقلیه دارای چند مرکز تامین را می توان به مسائلی با مقصد ثابت و غیر ثابت دسته بندی کرد. در مدل MDVRP با مقصد ثابت هر وسیله مسیرش را از یک مرکز تامین آغاز کرده و در همان مرکز تامین پایان می دهد در حالی که در مدل مقصد نامعلوم مکان شروع و پایان حرکت وسایل می تواند متفاوت از یکدیگر باشند.
روش های زیادی برای VRP با یک مرکز تامین ارائه شده است اگر چه این روش ها را نمی توان به صورت مناسبی برای کار با مسائلی همراه با چند مرکز تامین به کار برد. در ابتدا 3 رویکرد کلی ابتکاری برای حل مسائل MDVRP به وجود آمد که دسته اول جواب های تصادفی به وجود آورده و با جابجایی گره ها جواب را بهبود می دهند تا جایی که دیگر نتوان در آنها بهبودی ایجاد کرد. این رویکرد توسط ورن و هالیدی [7] و همچنین توسط کاسیدی و بنت [48] ارائه شد. دسته دوم از این روش های ابتکاری توسط جیلت و جانسون [9] که بسطی از روش ابتکاری (sweep) جیلت و میلر بوده است و دسته سوم از روش های ابتکاری MDVRP توسط تیلمن و کینچ [25] که بهسازی از الگوریتم کلارک و رایت [27] بوده نیز برای حل مسائل به کار گرفته شده است.
لاپورته و همکارانش [29] اولین افرادی بودند که برای مسائلی با اندازه حداکثر 50 مشتری با استفاده از روش شاخه و کران جواب های بهینه ارائه دادند. رویکزد دقیق دیگر برای MDVRP توسط لاپورته و همکارانش [43] مطرح شد که در آن ابتدا مساله مورد نظر به یک مسئله تخصیص محدودیت هم ارز40 تغییر شکل داده و سپس با استفاده از روش شاخه و کران برای مسائل نمونه با حداکثر 80 مشتری و 3 مرکز تامین حل شده است.
رناود و همکاران [39] یک روش ابتکاری دیگر را برای حل MDVRP به کار گرفتند که در آن ابتدا جواب های اولیه شدنی ایجاد می شوند و در ادامه فرآیند بهبود با استفاده از جستجوی ممنوع حاصل می گردد. این مطالعه به عنوان یک مورد خاص همچنین برای PVRP نیز به کار گرفته شده است. سلهی و ساری [54] یک روش ابتکاری 3 سطحی را برای حل MDVRP ارائه دادند که سطح اول ساخت جواب اولیه شدنی با استفاده از روش خوشه بندی سازگار ژنتیک41 و سطوح دوم و سوم آن نیز به ترتیب بهبود مسیرها برای هر مرکز تامین و تمام مسیرهای آن و همچنین بهبود بین مراکز تامین مختلف بوده است.
گیوسا و همکاران [36] برای مسائل MDVRP با در نظر گرفتن محدودیت پنجره ی زمانی شش روش ابتکاری برای تخصیص مشتریان به هر مرکز تامین را طراحی کردند و برای هر مرکز تامین از یک روش ابتکاری یکسان برای رسیدن بهجواب استفاده کردند و به مقایسه این شش روش پرداخته اند. هاژیکونستانتینو و بالداچی [21] برای مساله ارائه خدمات نگهداری فرمولی به عنوان MDPVRP ارائه دادند. آنها مساله را به چهار سطح تجزیه کردند و سپس توسط روش های ابتکاری به حل آن پرداختند. در سطح اول تعیین می شود که کدام مشتری توسط کدام مرکز تامین خدمت دهی می شود، سطح دوم حل PVRP برای هر مرکز تامین و در سطح سوم VRP کلاسیک برای هر مرکز تامین و برای هر روز از دوره حل می شود و در سطح آخر نیز یک TSP کلاسیک برای هر مسیر به کار گرفته شده است.
نگی و سلهی[30] تعدادی از روش های ابتکاری را برای حل VRP با یک مرکز تامین ارائه دادند که آنها قابلیت اصلاح شدن و به کارگیری برای MDVRP نیز داشتند. مشتریان ابتدا به دو دسته مرزی و غیر مرزی تقسیم شده و مشتریان غیر مرزی ابتدا به نزدیکترین مرکز تامین تخصیص داده شده و جواب های شدنی ایجاد می شوند. سپس مشتریان مرزی به هر یک از مسیرهای مختلف اضافه شده و ارزیابی می شوند. آنها روش خود را با مثال های معیار جیلت و جانسون که 2 تا 5 مرکز تامین و 50 تا 249 مشتری دارند آزمایش نمودند.
هو و همکاران [59] برای حل MDVRP از یک الگوریتم ژنتیک ترکیبی استفاده کردند. در این روش برای ایجاد جواب های اولیه از روش کلارک و رایت و همچنین روش ابتکاری نزدیکترین همسایه استفاده شده است آن را با الگوریتم ژنتیکی که جواب های آن به صورت تصادفی ایجاد شده مقایسه شده است که حاصل این مقایسه بر دو مثال تصادفی ایجاد شده با 50 و 100 مشتری نشان دهنده زمان تحویل کمتر روش ترکیبی ارائه شده است.
میرآبی و همکاران[46] مدلی جدید برای MDVRP ارائه کرده و از یک استراتژی دو مرحله ای برای حل مساله استفاده کردند. آنها

دیدگاهتان را بنویسید

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