دانلود مقالات

انواع اصلی مسأله مسیریابی وسیله نقلیه

همانگونه که در بخش قبلی بحث شده است، نسخه اصلی VRP تعدادی از مفروضات از جمله، استفاده از یک ناوگان یکسان از ماشین‌ها، وجود یک انبار مرکزی، وجود تنها یک مسیر برای هر ماشین و غیره را شامل می‌شود. این دسته از محدودیت‌ها با معرفی محدودیت‌های اضافی می‌تواند از مسأله حذف گردند و محدودیت‌های زیادی که مسأله را بیشتر به واقعیت نزدیک می‌کند به آن افزوده شد. این تغییر سبب افزایش پیچیدگی مسأله می‌گردد، همچنین با محدود ساختن سبب طبقه‌بندی اینگونه مسائل توسعه یافته تحت یک مسأله NP-hard می‌گردد. در این بخش این مسائل تعمیم داده شده را می توان در دسته‌های زیر مورد مطالعه قرار داد.

مسیریابی وسیله نقلیه باظرفیت محدود وسایل نقلیه
مسیریابی وسیله نقلیه با ناوگان ناهمگن
مسیریابی وسیله نقلیه با تقسیم تحویل
مسیریابی وسیله نقلیه باتحویل و جمع آوری
مسیریابی دوره‌ای وسیله نقلیه
مسیریابی وسیله نقلیه چند انبار
مسیریابی وسیله نقلیه بادر نظر گرفتن پنجره زمانی

2-8-1- مسیریابی وسیله نقلیه باظرفیت محدود وسایل نقلیه

در مسائل مسیریابی وسیله نقلیه باظرفیت محدود وسایل نقلیه[1] (CVRP) کلیه نقاط دارای تعداد مشخصی از میزان تقاضا هستند همچنین وسایل نقلیه‌ای که از نقطه مبدأ حرکت می‌کنند نیز دارای یک ظرفیت محدود برای سرویس‌دهی هستند، تابع هدف اینگونه مسائل مانند تابع هدف مسأله VRP کلاسیک به کمینه‌سازی کل هزینه‌ها، شامل هزینه‌های طی مسیر و وسایل نقلیه می باشد. در این نوع مسائل برای وسایل نقلیه حداکثر ظرفیتی به نام "C" تعریف می‌شود که جمع کل تقاضای هر گره نباید از آن بزرگتر شود.

با توجه به میزان ظرفیت هر وسیله نقلیه دو گونه CVRP تعریف می‌شود:

مسیریابی وسایل نقلیه با دیدگاه ظرفیت محدود یکسان برای تمامی وسایل نقلیه[2](SCVRP)  که در این حالت کلیه وسایل نقلیه باهم یکسان ومشابه خواهد بود.
مسیریابی وسایل نقلیه با دیدگاه ظرفیت محدود غیر‌یکسان برای وسایل نقلیه(ACVRP) [3] که در این حالت ظرفیت وسایل نقلیه غیر‌یکسان بوده و در نتیجه انتخاب خودرو برای مسیرهای مختلف تابع ظرفیت آن خواهد بود.(شریعت،2004).

2-8-2- مسأله مسیریابی وسایل نقلیه با ناوگان ناهمگن

مسأله مسیریابی وسایل نقلیه با ناوگان ناهمگن[4] (HFVRP) شکل دیگری از VRP است که در آن نیازی نیست که کلیه ماشین‌های ظرفیت، هزینه ثابت و متغیر برابری داشته باشند. ما می‌توانیم یک مجموعه از مشتری‌ها، N، و یک تعداد معین از انواع ماشین‌ها، M، را داشته باشیم؛ بطوریکه هر دسته از ماشین‌ها دارای یک ظرفیت ، یک هزینه ثابت ، و یک واحد هزینه متغیر  داشته باشند (m=1,…,M). در VRP کلاسیک، هر مشتری تنها می‌بایست توسط یک ماشین سرویس داده شود، هر ماشین می‌بایست سفر خود را از انبار مرکزی آغاز و به همانجا ختم کند و ظرفیت ماشین و حداکثر زمان هر سفر نمی‌بایست از حد خود تجاوز کنند. هدف HFVRP حداقل نمودن کلیه هزینه‌ها شامل هر دو هزینه‌های ثابت و متغیر بهره‌گیری از ماشین‌ها است. این ایده تنها مربوط به مسیریابی نمی‌شود، بلکه ترکیب ناوگان ماشین‌ها را نیز در نظر دارد. تحقیقات موجود در ادبیات موضوع برای حل انواع HFVRP بر روی توسعه الگوریتم‌های ابتکاری بجای روش‌های دقیق متمرکزند. آنها را می‌شود در دو دسته کلی قرار داد: روش‌های ابتکاری کلاسیک که اکثرا از الگوریتم‌های ابتکاری VRP ساده برگرفته شده‌اند، و روش‌های فراابتکاری.

گلدن و همکاران در سال 1984، برای نخستین بار یک الگوریتم ابتکاری را برای حل HFVRP معرفی کردند. آنها روش‌های ابتکاری مختلفی را بر اساس روش پس‌انداز[5] کلارک و رایت، بمانند الگوریتم تور اصلی ژیلت و میلر، ایجاد کردند. جدیدترین روش ابتکاری معرفی شده، عبارت است از الگوریتم رناد و باکتور، که تا به امروز یکی از برترین دستورالعمل‌ها حل است، با این حال زمان حل آن طولانی است. این روش با تولید یک مجموعه بزرگ از مسیرها آغاز بکار می‌کند؛ سپس از میان آنها، آنهایی را که محدودیت مسأله را با کمترین هزینه برآورده می‌سازد، با استفاده از روش دقیق ولی چندجمله‌ای الگوریتم تقسیم‌بندی مجموعه برمی‌گزیند (رفیعی،2010).

به تازگی، روش‌های فرابتکاری بیشتری برای حل HFVRP پیشنهاد شده‌اند. در سال 1996 عثمان و صالحی، در سال1999 گندرائو و همکاران، ودر سال 2002واسان و عثمان، روش‌هایی را که امروزه تحت نام OS، GLMT، و WO شناخته شده‌اند، معرفی کرده‌اند. تمامی این الگوریتم‌ها بر اساس روش جستجو ممنوعه استوارند. در الگوریتم OS یک جواب اولیه بر اساس روش ابتکاری صالحی و راند، تولید شده و سپس با استفاده از یک روش جستجو ممنوعه در حافظه کوتاه مدت بهبود می‌یابد (رفیعی،2010).

الگوریتم GLMT به مراتب پیچیده‌تر است و نیازمند استفاده از GENIUS، که توسط گندرائو و همکارانش، برای TSP، توسعه یافته است. الگوریتم WO، متغیر‌های گوناگونی را که از روش‌های مختلف جستجوی همسایگی بدست آمده، با یکدیگر مقایسه می‌کند (رفیعی،2010).

در سال 2008 پاراسکوپولوس و همکارانش، مسأله مسیریابی ناوگان غیریکسان به همراه پنجره زمانی را به منظور حداقل نمودن هزینه نهایی جابجایی، در نظر گرفته‌اند. برای حل مسأله یک الگوریتم دو مرحله‌ای بر اساس روش جستجو ممنوعه ترکیبی با الگوریتم جستجو همسایگی متغیرها[6] (VNS)، بکار گرفته شده است. در اولین مرحله، راه‌حل‌های اولیه گوناگونی بر اساس الگوریتم ساختاری نیمه‌موازی تولید می‌شود. سپس، یک دستورالعمل حذف مسیر برای کاهش تعداد خودروها مورد استفاده قرار می‌گیرد. سرانجام، یک زیرمجموعه از راه‌حل‌ها با کیفیت‌تر برای بهبود انتخاب می‌شوند. در مرحله بعدی، یک الگوریتم جستجوعه ممنوعه همسایگی برای کاهش هزینه کلی جابجایی مسیرهای انتخابی در اولین مرحله، مورد استفاده قرار می‌گیرد. ایمران و همکارانش در سال 2009، یک VNS را برای حل HFVRP ارائه دادند. جواب اولیه در سه مرحله ایجاد می‌شود. ابتدا یک تور اصلی بر اساس الگوریتم جاروب ایجاد می‌شود. سپس تور ایجاد شده توسط روش 2-opt ارائه شده توسط لین، بهبود می‌یابد. سرانجام، بر مبنای هزینه شبکه ایجاد شده با استفاده از الگوریتم دیجکسترا[7] اندازه ناوگان بهینه محاسبه می‌شود. یک روش بر مبنای دیجکسترا، و تنوع‌سازی بعد از مرحله جستجوی محلی برای بهبود کیفیت جواب‌های بدست آمده و بررسی سایر مناطق در ناحیه جواب بکار می‌روند. لیو و همکارانش در سال 2009، یک الگوریتم ژنتیک موثر را برای حل یک HFVRP ترکیبی ارائه کردند. در الگوریتم پیشنهادی آنها ابتدا، یک مجموعه از جواب‌های اولیه توسط دو روش ساختاری مختلف پس‌انداز، و جاروب ایجاد می‌شوند. هر جواب اولیه به شکل یک کروموزوم متناظر آن در می‌آید. سپس در یک تعداد از پیش مشخص تکرار، دو جواب به عنوان والدین برای تولید نسل‌های بعدی بر مبنای روش انتخاب مسابقه‌ای، به صورت تصادفی انتخاب می‌شوند. سپس تعداد مطلوبی از نسل بعدی در مرحله تولید مجدد بوسیله عملگر تقاطع ایجاد می‌شوند. نسل بعدی سپس جستجوهای محلی تغییر داده می‌شود تا کیفیت آنها بهبود یابد (رفیعی،2010).

.دانلود پایان نامه حل مسئله مسیریابی وسایل نقلیه چند انبار با پنجره زمانی با استفاده از یک الگوریتم فرابتکاری کارآمد

[1] Capacity Vehicle Routing Problem

[2] Symmetric CVRP

[3] Asymmetric CVRP

[4] Heterogeneous Fleet VRP(HFVRP)

[5] Saving Method (SM)

[6] Variable Neighborhood Search Algorithm(VNSA)

[7] Dijkstra Algorithm(DA)