مسیریابی وسایل نقلیه با دیدگاه ظرفیت محدود یکسان برای تمامی وسایل نقلیه[۳۴](SCVRP) که در این حالت کلیه وسایل نقلیه باهم یکسان ومشابه خواهد بود.
مسیریابی وسایل نقلیه با دیدگاه ظرفیت محدود غیریکسان برای وسایل نقلیه(ACVRP) [۳۵] که در این حالت ظرفیت وسایل نقلیه غیریکسان بوده و در نتیجه انتخاب خودرو برای مسیرهای مختلف تابع ظرفیت آن خواهد بود.(شریعت،۲۰۰۴).
۲-۸-۲- مسأله مسیریابی وسایل نقلیه با ناوگان ناهمگن
مسأله مسیریابی وسایل نقلیه با ناوگان ناهمگن[۳۶] (HFVRP) شکل دیگری از VRP است که در آن نیازی نیست که کلیه ماشینهای ظرفیت، هزینه ثابت و متغیر برابری داشته باشند. ما میتوانیم یک مجموعه از مشتریها، N، و یک تعداد معین از انواع ماشینها، M، را داشته باشیم؛ بطوریکه هر دسته از ماشینها دارای یک ظرفیت ، یک هزینه ثابت ، و یک واحد هزینه متغیر داشته باشند (m=1,…,M). در VRP کلاسیک، هر مشتری تنها میبایست توسط یک ماشین سرویس داده شود، هر ماشین میبایست سفر خود را از انبار مرکزی آغاز و به همانجا ختم کند و ظرفیت ماشین و حداکثر زمان هر سفر نمیبایست از حد خود تجاوز کنند. هدف HFVRP حداقل نمودن کلیه هزینهها شامل هر دو هزینههای ثابت و متغیر بهرهگیری از ماشینها است. این ایده تنها مربوط به مسیریابی نمیشود، بلکه ترکیب ناوگان ماشینها را نیز در نظر دارد. تحقیقات موجود در ادبیات موضوع برای حل انواع HFVRP بر روی توسعه الگوریتمهای ابتکاری بجای روشهای دقیق متمرکزند. آنها را میشود در دو دسته کلی قرار داد: روشهای ابتکاری کلاسیک که اکثرا از الگوریتمهای ابتکاری VRP ساده برگرفته شدهاند، و روشهای فراابتکاری.
گلدن و همکاران در سال ۱۹۸۴، برای نخستین بار یک الگوریتم ابتکاری را برای حل HFVRP معرفی کردند. آنها روشهای ابتکاری مختلفی را بر اساس روش پسانداز[۳۷] کلارک و رایت، بمانند الگوریتم تور اصلی ژیلت و میلر، ایجاد کردند. جدیدترین روش ابتکاری معرفی شده، عبارت است از الگوریتم رناد و باکتور، که تا به امروز یکی از برترین دستورالعملها حل است، با این حال زمان حل آن طولانی است. این روش با تولید یک مجموعه بزرگ از مسیرها آغاز بکار میکند؛ سپس از میان آنها، آنهایی را که محدودیت مسأله را با کمترین هزینه برآورده میسازد، با استفاده از روش دقیق ولی چندجملهای الگوریتم تقسیمبندی مجموعه برمیگزیند (رفیعی،۲۰۱۰).
به تازگی، روشهای فرابتکاری بیشتری برای حل HFVRP پیشنهاد شدهاند. در سال ۱۹۹۶ عثمان و صالحی، در سال۱۹۹۹ گندرائو و همکاران، ودر سال ۲۰۰۲واسان و عثمان، روشهایی را که امروزه تحت نام OS، GLMT، و WO شناخته شدهاند، معرفی کردهاند. تمامی این الگوریتمها بر اساس روش جستجو ممنوعه استوارند. در الگوریتم OS یک جواب اولیه بر اساس روش ابتکاری صالحی و راند، تولید شده و سپس با استفاده از یک روش جستجو ممنوعه در حافظه کوتاه مدت بهبود مییابد (رفیعی،۲۰۱۰).
الگوریتم GLMT به مراتب پیچیدهتر است و نیازمند استفاده از GENIUS، که توسط گندرائو و همکارانش، برای TSP، توسعه یافته است. الگوریتم WO، متغیرهای گوناگونی را که از روشهای مختلف جستجوی همسایگی بدست آمده، با یکدیگر مقایسه میکند (رفیعی،۲۰۱۰).
در سال ۲۰۰۸ پاراسکوپولوس و همکارانش، مسأله مسیریابی ناوگان غیریکسان به همراه پنجره زمانی را به منظور حداقل نمودن هزینه نهایی جابجایی، در نظر گرفتهاند. برای حل مسأله یک الگوریتم دو مرحلهای بر اساس روش جستجو ممنوعه ترکیبی با الگوریتم جستجو همسایگی متغیرها[۳۸] (VNS)، بکار گرفته شده است. در اولین مرحله، راهحلهای اولیه گوناگونی بر اساس الگوریتم ساختاری نیمهموازی تولید میشود. سپس، یک دستورالعمل حذف مسیر برای کاهش تعداد خودروها مورد استفاده قرار میگیرد. سرانجام، یک زیرمجموعه از راهحلها با کیفیتتر برای بهبود انتخاب میشوند. در مرحله بعدی، یک الگوریتم جستجوعه ممنوعه همسایگی برای کاهش هزینه کلی جابجایی مسیرهای انتخابی در اولین مرحله، مورد استفاده قرار میگیرد. ایمران و همکارانش در سال ۲۰۰۹، یک VNS را برای حل HFVRP ارائه دادند. جواب اولیه در سه مرحله ایجاد میشود. ابتدا یک تور اصلی بر اساس الگوریتم جاروب ایجاد میشود. سپس تور ایجاد شده توسط روش ۲-opt ارائه شده توسط لین، بهبود مییابد. سرانجام، بر مبنای هزینه شبکه ایجاد شده با استفاده از الگوریتم دیجکسترا[۳۹] اندازه ناوگان بهینه محاسبه میشود. یک روش بر مبنای دیجکسترا، و تنوعسازی بعد از مرحله جستجوی محلی برای بهبود کیفیت جوابهای بدست آمده و بررسی سایر مناطق در ناحیه جواب بکار میروند. لیو و همکارانش در سال ۲۰۰۹، یک الگوریتم ژنتیک موثر را برای حل یک HFVRP ترکیبی ارائه کردند. در الگوریتم پیشنهادی آنها ابتدا، یک مجموعه از جوابهای اولیه توسط دو روش ساختاری مختلف پسانداز، و جاروب ایجاد میشوند. هر جواب اولیه به شکل یک کروموزوم متناظر آن در میآید. سپس در یک تعداد از پیش مشخص تکرار، دو جواب به عنوان والدین برای تولید نسلهای بعدی بر مبنای روش انتخاب مسابقهای، به صورت تصادفی انتخاب میشوند. سپس تعداد مطلوبی از نسل بعدی در مرحله تولید مجدد بوسیله عملگر تقاطع ایجاد میشوند. نسل بعدی سپس جستجوهای محلی تغییر داده میشود تا کیفیت آنها بهبود یابد (رفیعی،۲۰۱۰).
۲-۸-۳- مسأله مسیریابی وسایل نقلیه با تقسیم تحویل
منبع فایل کامل این پایان نامه این سایت pipaf.ir است |
/>بسط دیگری از VRP عبارت است از مسیریابی وسایل نقلیه با تقسیم تحویل[۴۰] (SDVRP) است، در جاییکه یک ناوگان از ماشینهای یکسان با ظرفیت محدود میبایست به یک مجموعه از مشتریها سرویس دهند، هر مشتری میتواند بیش از یک بار ملاقات شود؛ برخلاف آنچه که به طور رایج در VRP کلاسیک مفروض بوده است، و تقاضای هر مشتری میتواند از ظرفیت ماشینها بیشتر باشد. تنها یک انبار برای کلیه ماشینها موجود است و کلیه آنها میبایست مسیر خود را از آن آغاز و به آن ختم کنند. مسأله شامل یافتن یک مجموعه از مسیرهای ماشین است که به تمامی مشتریها سرویس داده شود، بشرطی که مجموع مقادیر انتقال در هر تور از ظرفیت ماشین تجاوز نکند، تقاضای تمامی مشتریان به طور کامل برآورده شود، و کل مسافت پیموده شده حداقل گردد. به عبارت دیگر، در SDVRP محدودیت ملاقات یک باره هر مشتری برداشته شده است. SDVRP یک مسأله NP-Hard است، تا زمانیکه شرایط محدودکننده هزینهها برقرار باشد، و تمامی ماشینها دارای ظرفیتی بزرگتر از دو باشند، در حالیکه اگر کلیه ماشینها دارای حداکثر ظرفیت دو باشند در یک زمان چندجملهای قابل حل است (ظهرهوند،۲۰۱۱).
روشهای موجود برای حل SDVRP به سه دسته : روشهای دقیق، روشهای ابتکاری، و روشهای فراابتکاری تقسیمبندی میشوند.
الگوریتمهای محدودی در ادبیات موضوع یافت میشود، که بطور دقیق SDVRP را حل کرده باشند. یافتن جواب بهینه در مسائل مسیریابی، اغلب به علت نیاز به امکانات محاسباتی فراوان، عملی نیست. بطوریکه تنها سه روش حل دقیق برای SDVRP موجود است. درور و همکارانش در سال۱۹۹۴یک الگوریتم شاخه و کران را برای یک فرمولبندی خطی و عددصحیح SDVRP توسعه دادند، که در آن دستههای جدیدی از نابرابریهای معتبر به مسأله افزوده شدهاند. دستورالعمل آنها بر روی سه مثال در اندازه کوچک همراه با حداکثر ۲۰ مشتری و تقاضاهای متفاوت برای هر یک بررسی شده است. در سال ۲۰۰۰ بلنگوئر و همکارانش یک کران پایین را برای SDVRP بر مبنای مطالعه چند وجهی مسأله ارائه دادند. این مطالعه نابرابریهای مجاز جدیدی را در بر میگرفت. آنها یک الگوریتم صفحات برشی را برای حل مثالهای اندازه کوچک توسعه دادند. برای مثالهای با اندازه بزرگتر، مقادیر عددصحیح از روش شاخه و کران بدست میآید. لی و همکارانش در سال ۲۰۰۶ یک روش کاملا جدید را برای مسأله مسیریابی وسایل نقلیه چندگانه با تقسیم برداشت (MSDVRP)، بر مبنای مدل برنامه ریزی پویای قطعی و الگوریتم جستجو کوتاهترین مسیر معرفی کردند. بر مبنای چند ویژگی جوابهای بهینه MSDVRP، آنها مدل پویای اولیه را برای یافتن یک مدل معادل، مجدد فرمولبندی کردند. این مدل کوچک شده، با یک شبکه برایدار مرتبط است، که سپس توسط الگوریتم کوتاهترین مسیر حل خواهد شد(ظهرهوند،۲۰۱۱).
به مانند سایر گونههای VRP، روشهای ابتکاری بطور وسیعی در حل SDVRP مورد استفادهاند. درور و ترودئو در سال ۱۹۸۹یک روش جستجو محلی را برای حل SDVRP پیشنهاد کردند. روش آنها یک الگوریتم دو مرحلهای است، در مرحله اول یک جواب شدنی را برای VRP تولید میکند و سپس از روی آن یک حل شدنی را برای SDVRP ایجاد میکند. در مرحله اول از سه روال استفاده میشود: (i) یک تولید کننده اولیه مسیر برمبنای الگوریتم کلارک و رایت، (ii)یک تعویض گره بر مبنای جابجایی تک گره و دو گره، (iii) یک بهبود مسیر بر مبنای یک دستورالعمل ۲-opt. مرحله بعدی از، (i) یک تعویض ۲-split، و (ii) یک روال افزایش مسیر، بهره میجوید. برای هر نقطه تقاضا داده شده، ۲-split یک همسایگی را ایجاد میکند با تمام جایگزینها که نقطه تقاضا را حذف کرده، و آنها را در دو مسیر دیگر که ترکیب ظرفیت آنها برای برآوردهسازی تقاضا کافیست وارد میکند. در هر تکرار، داوطلب با بیشترین صرفهجویی انتخاب میشود و جستجو زمانی پایان میپذیرد، که دیگر بهبودی حاصل نشود. پس از اینکه جستجو محلی به اتمام رسید، یک روال افزایش مسیر، مسیرهای جدیدی را برای حذف تقسیم تحویلها برای کاهش هزینه کلی مسیرها، به جریان میافتد(ظهرهوند،۲۰۱۱).
روشهای فراابتکاری نیز برای حل SDVRP توصیه میشوند. در سال ۲۰۰۴ هو و هاگلند یک روش جستجو ممنوعه را برای حل مثالهایی از SDVRP همراه با پنجره زمانی توسعه دادند. آنها یک جواب اولیه را با بررسی مشتریها در یک توالی مشخص و افزودن نزدیکترین مشتری مسیر داده نشده به آخرین مشتری مسیر داده شده در راههای ممکن، ایجاد میکنند. اگر تقاضای مشتری از مجموع ظرفیت ماشین تجاوز کند، تقاضا مابین ماشینها تقسیم خواهد شد، و مسیر جدیدی برای برآوردهسازی این تقاضا ایجاد میشود. هنگامیکه برنامه مسیرها ایجاد شد، یک الگوریتم جستجو ممنوعه شروع بکار میکند. در هر تکرار بهترین گزینه در میان چهار همسایگی انتخاب میشود، و جوابهای همسایگی برای بهبود ارزیابی میشوند. همسایگیهای ارزیابی شده جایگزین یک مشتری در مسیر میشوند، تقسیم تحویل بین دو مسیر را حذف میکنند و یک تحویل جدید با دو مسیر مشابه را ایجاد میکنند، دو مشتری را مابین دو مسیر معاوضه میکنند، و یک دستوالعمل ۲-opt را بین دو مسیر به اجرا میگذارند. آرچتی و همکارانش در سال۲۰۰۶ یک الگوریتم جستجو ممنوعه را برای حل SDVRP ارائه کردند، در جاییکه یک مشتری از یک مجموعه از مسیرهای سرویسدهی حذف میشود و در مسیر جدید یا مسیر موجودی که ظرفیت استفاده نشده دارد، وارد میشود (ظهرهوند،۲۰۱۱).
۲-۸-۴- مسیریابی وسیله
نقلیه با تحویل و جمع آوری
مسأله مسیریابی وسیله نقلیه با تحویل و جمع آوری[۴۱] (VRPPD) بسیار شبیه به مسیریابی وسایل نقلیه با حمل در بازگشت میباشد؛ در این مسأله نیز مقداری کالا به مشتریان تحویل داده میشود، از مشتریانی نیز کالا دریافت میشود. تفاوت اصلی این مسأله در آن است که کالاهایی که از مشتریان دریافت میشود به مشتریان دیگری در مسیری تحویل میشود و موادی به محل دپو برگردانده نمیشود. هدف از ارائه این مدل حداقل نمودن جریان وسایل نقلیه و مجموع زمان سفر میباشد. شرط موجه بودن این مسأله آن است که کل کالایی که به مسیر تخصیص داده شده از ظرفیت وسیله نقلیه مفروض تجاوز ننماید و وسیله نقلیه ظرفیت کافی برای تحویل کالا از مشتریان را داشته باشد(ظهرهوند،۲۰۱۱).
ادبیات موضوع در بخش VRPPD، به دو دسته کلی: VRP با تجدید و تحویل همزمان[۴۲] (VRPSPD)، و VRP با ترکیب تجدید و تحویل[۴۳] (VRPMPD)، تقسیم میشوند. در حالت VRPSPD، تمامی مشتریها نه فقط به تحویل کالا، همچنین بطور همزمان به تجدید کالا نیز نیازمندند. یک فرض اصلی در این مسائل عبارت است از اینکه کلیه کالاهای تحویل داده شده از انبار آمدهاند، و همچنین تمامی کالاهای تجدید شده به انبار باز گردانده میشوند. در حالت VRPMPD، بعضی از مشتریها نیازمند تحویل کالا، و برخی دیگر نیازمند تجدید کالا میباشند. به عبارت دیگر، VRPMPD بعنوان یک حالتی خاص از VRPSPDمیتواند در نظر گرفته شود، که در آن یکی از موارد تجدید یا تحویل برای هر مشتری برابر صفر است.
مین در سال۱۹۸۹، اولین فردی بود که به بررسی VRP بشکل تحویل و تجدید همزمان پرداخت. او یک مسأله عملی را که یک کتابخانه عمومی شامل یک انبار مرکزی، دو وسیله نقلیه، و ۲۲ مشتری میشد، را در نظر گرفت. در الگوریتم پیشنهادی او، ابتدا مشتریها در گروههایی طبقه بندی میشدند و سپس در هر گروه یک مسأله فروشنده دوره گرد حل میشد. در سال ۱۹۹۲ هالس، گونههایی از VRP را مورد مطالعه قرار داد که شامل حمل در بازگشت[۴۴] و تجدید و تحویل میشدند. او مسأله دوم را ابتدا با استفاده از الگوریتم ابتدا خوشهبندی سپس مسیریابی حل کرد. در مرحله اول، مشتریها به وسایل نقلیه تخصیص مییابند، سپس یک دستورالعمل مسیریابی بر اساس روش بهبود ۳-opt مورد استفاده قرار میگیرد. در سال ۱۹۹۹، گندرائو و همکارانش مسأله فروشنده دورهگرد همراه با تجدید و تحویل (TSPPD) را بسط دادهاند. درابتدا مسأله TSP بدون در نظر گرفتن تجدید و تحویل حل خواهد شد، سپس سفارشات مربوط به تجدید و تحویل روی مسیر مشخص میشود(ظهرهوند،۲۰۱۱).
تحقیقات اندکی بر روی مسأله VRPMPD صورت گرفته است. گلدن و همکارانش در سال ۱۹۸۵، روشی را بر اساس تقسیم مشتریها به دو دسته تحویل در بازگشت (تجدید) و تحویل در مسیر (تحویل)، معرفی کردند. در فرمول الحاقی آنها از یک فاکتور جریمه ای استفاده میشد، که تعداد مشتریهای تحویلی را در سمت چپ مسیر در نظر میگرفت. کاسکو و همکارانش در سال۱۹۸۸، یک دستوالعمل تعبیه بر اساس حجم بار را توسعه دادند. هزینه الحاق برای مشتریها با تجدید برابر با باری است که میبایست، در ادامه مسیر تحویل داده شود. صالحی و ناگی در سال ۱۹۹۹، روش الحاقی کاسکو و همکارانش، ورود تحویلهای در بازگشت به خوشهبندی را برخلاف روشهای قبلی که بصورت تک به تک بود، آزاد کردند. این روش تنها نیاز به اندکی محاسبات بیشتر داشت، ولی قابلیت حل مسائل همراه به تجدید و تحویل همزمان را دارا بود. (ظهرهوند،۲۰۱۱).
۲-۸-۵- مسأله مسیریابی دورهای وسایل نقلیه
دسته دیگر از انواع مسایل VRP که آنرا در این بخش معرفی میکنیم عبارت است از مسأله مسیریابی دورهای وسایل نقلیه (PVRP). همانند VRP عمومی، موقعیت تک تک مشتریها به همراه تابع تقاضای قطعی آنها کاملا مشخص است. مسأله PVRP دارای یک افق برنامهریزی مشتمل بر T روز است، و تواتر بازدید برای هر مشتری مشخص میکند که در این T-روزه هر چند وقت یکبار میبایست بازدید شود. یک جواب برای PVRP مشتمل بر T مجموعه از مسیرها است که در مجموع محدودیتهای تقاضا و تواتر بازدید را برآورده میسازند. در این مسأله، تابع هدف معمولا حداقل نمودن مجموع هزینههای تمامی مسیرها در طول دوره برنامهریزی است. واضح است که این دسته از مسایل حداقل به دشواری VRP است. انواع گوناگونی از PVRP در ادبیات موضوع معرفی شده است. یک طبقهبندی از انواع گوناگون PVRP را میتوان در تحقیق که توسط مورگای و وندربک انجام گرفته است، یافت. تابع هدفهای مختلف از یکدیگر متمایزند، به طور مثال حداقلسازی مسافت پیموده شده، زمان انتقال، و یا مجموع هزینه حمل و نقل؛ بنابراین منطقهبندی مسیرها، تقسیم یک بار کاری یکسان بر روی ماشینها، و کیفیت سرویسدهی میتواند بخشی از تابع بهینهسازی باشد. تفاوتها اغلب در محدودیتها که میتوانند به سه دسته کلی تقسیم شوند، رخ میدهد: محدودیتهایی که شامل (۱) برنامهریزی ملاقاتها (تواترهای مختلف، محدودیت در روزهای ویژه، و غیره)، (۲) نوع تقاضا (ثابت و یا متغیر)، و (۳) ناوگان ماشینها (یکسان و یا غیریکسان) میشوند (مورگای و وندربک،۲۰۰۶).
۲-۸-۵-۱- تعریف ریاضی مسأله مسیریابی دوره ای وسایل نقلیه (PVRP)
مسأله مسیریابی دوره ای وسایل نقلیه، مسأله VRP را با توسعه دوره روزهای منفرد به دوره M-روزه تعمیم میدهد. اگر زیر مجموعه رئوس I={1,…,i,…,n} مطابق بامشتریان در نظر گرفته شود، در طول پریود، هر مشتری
بار ملاقات میشود (که تکرار ملاقات نامیده میشود). هر مشتری با تکرار ملاقاتش مشخص میشود. این ملاقاتها باید از ترکیبهای روز ملاقات مجموعه مجاز پیروی کند. برای نمونه، اگر یک مشتری باید سه بار در یک دوره ۶-روزه ملاقات شود، و ترکیبهای مجاز روز-ملاقات (۵،۳،۲) و (۶،۴،۱) باشند، بنابراین این مشتری فقط میتواند در روزهای مرتبط با یکی از این ترکیبات ملاقات شود.
مسأله PVRP شامل یافتن همزمان مجموعهای از V تور برای هر روز از پریود و تخصیص بهترین ترکیب روز-ملاقات به هر مشتری است بطوریکه همه نیازها تأمین شود و همه هزینههای سفر دوره M-روزه حداقل شود. مسأله PVRP همه محدودیتهای VRP را رعایت میکند، و برخی محدودیتهای اضافی عبارتند از:
هر مشتری باید یک ترکیب مجاز روز-ملاقات انتخاب نماید.
به هر مشتری فقط در روزهای مربوط به ترکیب روز-ملاقات سرویس داده میشود.
هر وسیله نقلیه میتواند بین دو مشتری در یک روز تردد کند اگر و تنها اگر هر دو مشتری برای ملاقات در آن روز زمانبندی شده باشند.
هر مشتری یک تقاضای مشخص روزانه دارد که باید در یک روز ملاقات روزانه با یک خودرو پاسخ داده شود. اگر دوره برنامهریزی M=1 شود، سپس PVRP به یک مسأله کلاسیک VRP بدل میگردد. در مدل کلاسیک PVRP تقاضای روزانه همواره ثابت است. PVRP میتواند به عنوان یک مسأله تخصیص گروهی مسیرها برای هر روز تلقی شود، به گونهای که محدودیتهای موجود رعایت شده و هزینه کل کاسته شود. در شکل (۲-۴)، مجموعهای از گرهها به وسیله دو خودرو از یک انبار مرکزی خدمترسانی میشوند.
ملاقات روزانه
ملاقات شنبه، دوشنبه، چهارشنبه
ملاقات یکشنبه و سه شنبه
تور شنبه، دوشنبه، چهارشنبه
تور یکشنبه و سه شنبه
خودروی ۱
گره ۱ خودروی۲
گره ۲
شکل ۲-۴: مسأله PVRP( ظهرهوند،۲۰۱۱)
۲-۸-۵-۲- مدل ریاضی PVRP
پارامترهای ورودی
Q =: مجموعه نقاط تقاضا، نقطه تقاضای شماره ۱ معرف انبار مرکزی است.
A = مجموعه یال یا اتصالات بین نقاط تقاضا.
N: تعداد نقاط تقاضا.