بخشی از مقاله
چکیده
مسئله ی مسیریابی خودرویی واجد شرایط با استفاده از پنجره های زمانی را میتوان یک مسئله ی توسعه یافته از مسئله ی مسیریابی خودرویی واجد شرایط با تقاضاهای تصادفی دانست، که در آن تقاضاها به صورت تصادفی بوده و یک پنجره ی زمانی نیز بر روی هر رأس اعمال میشود. خطای رأس که به دلیل فزونی یافتن تقاضای ادراک شده ایجاد می-شود، ممکن است یک واکنش زنجیری از خطاها را بر روی سایر خودروها و در همان مسیر به دلیل وجود پنجره ی زمانی، تحریک کند. این مقاله، به مدل سازی این مسئله به عنوان یک برنامه ی استوکاستیک یا تصادفی با منابع پرداخته و یک روش جستجوی هیروستیک را همسایگی انطباقی را به عنوان راه حل ارائه میدهد . در آزمایشات، از روش نمونه های بنچ مارک Solomon تغییر یافته استفاده شده است. نتایج محاسباتی به وضوح نشان میدهند که روش هیروستیک پیشنهادی ما نسبت به روش های دیگر، برتری هایی را به همراه دارد.
واژگان کلیدی: مسیریابی خودرویی1، جستجوی بزرگ همسایگی انطباقی، هیورستیک، پنجره ی زمانی
.1مقدمه
مسئله ی مطرح شده در این مقاله، مسئله ی مسیریابی خودرویی واجد شرایط با تقاضاهای تصادفی و پنجره های زمانی - CVRPSDTW - 1 میباشد که یک مسئله ی توسعه یافته از مسئله ی مسیر یابی خودرویی واجد شرایط با تقاضاهای استوکاستیک - - CVRPSD میباشد. CVRPSDTW را بر روی گراف تعریف می کنیم که در آن، مجموعه ی رئوس بوده و - { مجموعه یال ها را تشکیل می دهد. رأس یک نقطه ی شروعی بوده که بر مبنای خودروهای یکسان m با ظرفیت Q میباشد، در حالی که مابقی خودروها، نشان دهنده ی مشتریان هستند. یک ماتریس هزینه ی پیمایش متقارن2 نیز بر روی تعریف شده است. فرض میکنیم که تمامی خودروها با سرعت یکسانی حرکت کرده و هزینه ی پیمایشی نیز یکسان است. یک زمان سرویس نیز در زمان ملاقات یک رأس اعمال میشود. هر رأس مرتبط با یک تقاضای استوکاستیک و غیر منفی میباشد که باید جمع آوری گردد. تقاضاهای استوکاستیک نیز قابل تقسیم بوده و تا زمانی که خودروها به رئوس برسند، ناشناخته باقی میمانند. در نتیجه ممکن است در صورتی که کل تقاضاهای جمع آوری شده از ظرفیت خودرو فزونی یابد، خطایی روی دهد.
Ccvrpsd را میتوان به عنوان یک برنامه ی ریاضی تصادفی در نظر گرفت. دو راه حل اصلی برای برنامه نویسی استوکاستیک وجود دارد: برنامه نویسی محدود به شانس - CCP - 3 و برنامه نویسی تصادفی با استناد - . - SPR در CCP، مسئله به وسیله ی اعمال محدودیت هایی به منظور حصول اطمینان از احتمال محدود بودن بروز خطا به یک سری پارامتر، حل میشود. استوارت و گلدن[1] و همچنین لاپورت[2] نشان داده اند که CVRPSD را میتوان به یک مسئله ی قطعی هم ارز4 تبدیل کرد. این نتیجه، بر روی CVRPSDTW نیز اعمال میشود زیرا تنها مؤلفه ی تصادفی مسئله، تقاضا میباشد. در SPR، دو استراتژی راه حل اصلی وجود دارد: بهینه سازی قیاسی[3-10]5 و .re-optimization استراتژی بهینه سازی قیاسی، به وسیله ی بهینه سازی دوم، بر حسب کیفیت راه حل مشخص میشود، ولی استراتژی اول، بر حسب هزینه های محاسباتی مطلوب تر بوده و میتواند راه حل های قابل پیش بینی پایدارتری را ایجاد کند.[4] در بهینه سازی قیاسی، در ابتدا یک راه حل اول مرحله، که شامل مجموعه ای از m مسیر خودرویی میباشد، ایجاد میشود. ادراک متغیر های تصادفی نیز مشخص میشود. هر زمانی که خطایی رخ دهد، یک عملی برای ایجاد هزینه های بیشتر پیاده سازی میشود. یک سیاست منبع رایج به صورت زیر است:
در صورتی که ظرفیت خودرو بر روی مسیر برنامه ریزی شده فزونی یابد، خودرو برابر با ظرفیتش مسافر سوار کرده و به نقطه ی مقصد برای تخلیه ی مسافران برمیگردد، و سپس به آخرین رأس ملاقات شده باز میگردد؛ در صورتی که به ازای هر رأس، به ظرفیت دقیقی دست پیدا کنیم، خودرو به نقطه ی شروع بازگشته و سپس به سمت رأس بعدی در امتداد مسیرش حرکت میکند. هدف این مسئله، کمینه سازی جمع هزینه ی راه حل اول گام و هزینه ی مورد انتظار منابع میباشد.
CVRPSD شامل طراحی مسیرهای خودرویی اول گام میباشد به گونه ای که:
.I نقطه ی شروع و پایان هر مسیر به هم برسد.
.II هر خودرو فقط یکبار هر رأس را ملاقات کند.
.III در صورتی که در یک رأس، به ظرفیت خودرو دست پیدا کنیم، یک عمل ارجاع فراخوانی شده، و
.IV تابع هدف نیز کمینه گردد.
نقش اولیه ی CVRPSD توسط تیل مان[13] مطرح شد که در آن، متغیر چند نقطه ای با تقاضاهای توزیع شده ی پواسون در نظر گرفته شده است. این مدل، یک تعادلی را بین فزونی یافتن ظرفیت خودرو و اتمام مسیر با ظرفیتی دقیق در نظر میگیرد. راه حل مطرح شده نیز یک نسخه ی تغییر یافته از الگوریتمClark,Wright[14] بود. نقش عمده ی مرتبط با CVRPSD توسط برتیمایس[15] صورت گرفته است که به چندین کرانه را به همراه مشخصه های نظری و مجانبی بدست آورده است. در لاپورت[2]، توزیع تقاضای بیشتری در نظر گرفته شده است و محل نقطه ی شروع نیز یک متغیر تصمیم میباشد. الگوریتم های برش و انشعاب دقیق نیز برای نسخه ی محدود به شانس مسئله ارائه شده است. برتیماس[4]، مدارک تحلیلی کاملی را ارائه داده است که بسیار مشابه با استراتژی های بهینه سازی استقرایی میباشد.
لاپورت[5] نیز یک متد صحیح جنریک L-Shaped را برای برنامه های استوکاستیک توسعه داده است. این الگوریتم انشعاب و برش، امکان برش های احتمالاتی را بر روی یک فرمالیسم جریان از مسئله فراهم کرده تا اینکه یک راه حل صحیح ممکن بدست آید. یک جستجوی هیروستیک نیز توسط Gendreau[7] ارائه شده است تا به حل یک مسئله ی مسیریابی خودرویی استوکاستیک بپردازد. Gendreau[6] از یک الگوریتم صحیح L-Shaped برای مدل ارجاع از CVRPSD استفاده کرده است که در آن، تابع جریمه، هزینه ی سفرهای عقب و جلو به سمت نقطه ی شروع را به دلیل خطاهای مسیر ارائه میدهد. پژوهش صورت گرفته شده توسطDror[16] ، بر روی تأثیر سیاست های سرویس و عملیاتی ، مشخصه ها و مدل هایی برای CVRPSDتأکید دارد اخیراٌ، Secomandi[16] مسئله ی CVRPSD را با استفاده از دو الگوریتم تخمین حل کرده است: تکرار سیاست تخمین بهینه و یک الگوریتم تک مرحله ای. Yang[18]
نیز یم تابع هدف برنامه نویسی پویا را برای CVRPSD ارائه داد که با استفاده از محاسبات تخمین سریع، بر روی مورد استوکاستیک مورد انطباق قرار گرفت. لاپورت[8] نیز یک الگوریتم صحیح را به همراه تقاضاهای نرمال و پواسون برای CVRPSD توسعه داد. Haughland[19] نیز طراحی بخش های خودرو را برای CVRPSD در نظر گرفت. جستجوی Tabu و هیروستیک چند ستاره ای برای مسئله نیز توسعه یافته اند و مقایسه شده اند. Tan[9] نیز به مطالعه ی الگوریتم تکاملی چند هدفه و نوع چند مدلی از CVRPSD پرداخته است و یک الگوریتم تکاملی چند هدفه را برای استخراج محلی و همچنین یک متد شبیه سازی مسیر را برای ارزیابی تناسب راه حل ارائه داده است. Secomandi و Margot نیز یک متودولوژی راه حل بهینه سازی را در ترکیبی با عملگر های ژنتیک و رویه های جستجوی محلی برای CVRPSD ارائه داده است. در نهایت، Rei[20] نیز از روش نمونه گیری مونت کارلو1 و انشعاب محلی برای ارائه ی راه حلی برای مسئله ی مسیریابی تک خودرویی با تقاضاهای تصادفی استفاده کرده است. یک مطالعه ای از مسیریابی خودرویی استوکاستیک را میتوان در Cordeau[21] بدست آورد.
در CVRPSDTW، هر رأس دارای یک پنجره ی زمانی مربوطه بوده که در آن، سرویس باید شروع شود. پنجره ی زمانی مخزن به صورت مشخص میشود. بکار گیری پنجره هیا زمانی در CVRPSD بدین معنا بوده که در صورت بروز خطا، پنجره های زمانی مشتریان باقی مانده بر روی مسیر ممکن است نقض شود، زیرا زمانی به وسیله ی خودرو نیاز است تا به نقطه ی شروع برگردد و جمع آوری خود را از سر گیرد. در چنین شرایطی، مشتریان متأثر نیز به صورت مجزا و به وسیله ی سرویس های خاص ملاقات میشوند که هزینه ی زیادی را در بر دارد. با توجه به دانشی که داریم، رویکرد های موجود و مرتبط با CVRPSDTW محدود به مدلی برای حل مسیریابی خودرویی و مسئله ی استوکاستیک با پنجره های زمانی و تقاضاهای تصادفی میباشد. یک معیار انتخاب نیز پیشنهاد شده است و یک هیروستیک دنباله ای نیز ارائه شده است. Chang[23] یک مدل استوکاستیک را برای مسئله ی مسیریابی با
