مساله مسیریابی وسیله نقلیه پویا DVRP

  

حل بهینه‌سازی مجدد دوره‌ای برای مسائل مسیریابی وسائل نقلیه پویا

مقدمه:

مساله مسیریابی وسیله نقلیه یکی از مسائل پیچیده و سطح بالای مسائل مسیریابی می‌باشد. یکی از انواع آن، مساله مسیریابی وسیله نقلیه پویا می‌باشد که در آن همه‌ی مشتری ها از قبل مشخص نیستند اما با گذشت زمان آشکار و مشخص می‌شوند. مساله مسیریابی وسیله نقلیه پویا یک مساله بهینه‌سازی پویا می‌باشد که در دو دهه اخیر، به یک موضوع تحقیقاتی داغ و چالش برانگیز تبدیل شده است. در مسائل بهینه‌سازی پویا، حداقل یک قسمت (عنصر) از مساله، با گذشت زمان تغییر می‌کند. کاربردهای مساله مسیریابی وسیله نقلیه پویا به وضوح در مسائل دنیای واقعی دیده می‌شوند. تا به امروز، از یک رویکرد ارزیابی بر مبنای زمان برای سیستم‌های مساله مسیریابی پویا دوره‌ای استفاده می‌شد اما در این مقاله، ما از الگوریتم پیشرفته شده ژنتیک استفاده می‌کنیم که سعی دارد هم واگرایی و هم توانایی دور شدن از جواب بهینه محلی را افزایش دهد. 

 

  چکیده:

مساله مسیریابی وسیله نقلیه یکی از مسائل پیچیده و سطح بالای مسائل مسیریابی می‌باشد. یکی از انواع آن، مساله مسیریابی وسیله نقلیه پویا می‌باشد که در آن همه‌ی مشتری ها از قبل مشخص نیستند اما با گذشت زمان آشکار و مشخص می‌شوند. مساله مسیریابی وسیله نقلیه پویا یک مساله بهینه‌سازی پویا می‌باشد که در دو دهه اخیر، به یک موضوع تحقیقاتی داغ و چالش برانگیز تبدیل شده است. در مسائل بهینه‌سازی پویا، حداقل یک قسمت (عنصر) از مساله، با گذشت زمان تغییر می‌کند. کاربردهای مساله مسیریابی وسیله نقلیه پویا به وضوح در مسائل دنیای واقعی دیده می‌شوند. تا به امروز، از یک رویکرد ارزیابی بر مبنای زمان برای سیستم‌های مساله مسیریابی پویا دوره‌ای استفاده می‌شد اما در این مقاله، ما از الگوریتم پیشرفته شده ژنتیک استفاده می‌کنیم که سعی دارد هم واگرایی و هم توانایی دور شدن از جواب بهینه محلی را افزایش دهد. بنابراین رویکرد ارزیابی برازندگی وزنی به عنوان گزینه‌ی جایگزینی برای رویکرد ارزیابی بر مبنای زمان، بدون توجه به قدرت و مشخصات سیستم اجرا کننده ارائه شده است. الگوریتم ژنتیک پیشرفته ارائه شده در این مقاله، در هر دو زمینه مبتنی بر زمان و ارزیابی برازندگی وزنی نسبت به الگوریتم های منتشر شده در گذشته برتری دارد.

1.      مقدمه:

در دهه‌های اخیر، زندگی ما به دلیل پیشرفت هایی که در حمل و نقل و لجستیک اتفاق افتاده است بهبود پیدا کرده است. بحث های حمل و نقل و لجستیکی درصد بسیار زیادی از هزینه کل هر محصولی را در برمی‌گیرند. در واقع یک شرکت چیزی در حدود 20 درصد ارزش محصول و کالا را در بخش حمل و نقل و لجستیکی هزینه و مصرف می‌کند. با این تفاسیر بخش حمل و نقل بخش بسیار مهمی می‌باشد اما دارای تاثیرات منفی نظیر سر وصدا، آلودگی و... می‌باشد.به هر حال سیستمهای مسیریابی حمل و نقل موثر و کارآمد با ابزار بهینه‌سازی کامپیوتری به کاهش تاثیرات منفی و هزینه‌ها کمک می‌کنند. این به این دلیل است که کاهش مسافت طی شده به بهبود کارایی راننده و وسیله‌ی نقلیه کمک می‌کند و می‌تواند منجر به کاهش هزینه های عملیاتی، کاهش انتشار گازهای گلخانه‌ای و همچنین افزایش سطح خدمت مشتری شود. مساله مسیریابی وسایل نقلیه از انواع مختلفی تشکیل شده است، نظیر مساله مسیریابی وسیله نقلیه با ظرفیت محدود، مساله مسیریابی وسیله نقلیه با چند انبار مرکزی، مساله مسیریابی وسیله نقلیه با پنجره زمانی. یکی از انواع مختلف آن، مساله مسیریابی وسیله نقلیه پویا می‌باشد که در آن همه‌ی مشتری ها از قبل مشخص نیستند اما با گذشت زمان آشکار و مشخص می‌شوند. مساله مسیریابی وسیله نقلیه پویا یک مساله بهینه‌سازی پویا می‌باشد که در دو دهه اخیر، به یک موضوع تحقیقاتی داغ و چالش برانگیز تبدیل شده است. در مسائل بهینه‌سازی پویا، حداقل یک قسمت (عنصر) از مساله، با گذشت زمان تغییر می‌کند. کاربردهای مساله مسیریابی وسیله نقلیه پویا به وضوح در مسائل دنیای واقعی دیده می‌شوند. مانند مساله مسیریابی وسیله نقلیه، مساله مسیریابی وسیله نقلیه پویا نیز جزو مسائل خیلی سخت (NP-Hard) می‌باشد. بنابراین  تکنیک‌های بهینه‌سازی که توانایی تولید جواب‌های غیر بهینه اما با کیفیت بالا را تحت محدودیت زمانی دارند، بسیار مفید می‌باشند. از جمله این تکنیک‌ها و روش ها می‌توان به الگوریتم های فراابتکاری نظیر سیستم کلونی مورچگان و الگوریتم ژنتیک اشاره کرد. این مقاله دارای دو نوآوری می‌باشد. نوآوری اولی، استفاده ‌از الگوریتم پیشرفته شده ژنتیک استفاده است که سعی دارد هم واگرایی و هم توانایی دور شدن از جواب بهینه محلی را افزایش دهد. برای الگوریتم ژنتیک پیشرفته، 5 اصلاح ارائه شده است. جمعیت اولیه بخش زمانی اول، جمعیت اولیه بخش های زمانی دیگر، فرآیند انتخاب، جهش از نوع مبادله و مدیریت/ کشف شرایط بهنیگی محلی. این مقاله مسائل کمینه سازی را در برمی‌گیرد.

نوآوری دوم این مقاله، ارائه یک رویکرد ارزیابی جدید و بهتر برای مسائل مسریابی وسایل نقلیه پویا می‌باشد. تا به امروز، از یک رویکرد ارزیابی زمان-محور برای سیستم‌های مساله مسیریابی پویا دوره‌ای استفاده می‌شد. در رویکرد ارزیابی زمان-محور، یک مساله مسیریابی پویا به ازای بخش‌های مختلف زمانی مساله حل می‌شود. بنابراین این روش تا حد زیادی بستگی به قدرت سیستم پردازنده دارد. بنابراین به عنوان جایگزین برای ارزیابی زمان-محور از 4 روش ارزیابی دیگر استفاده می‌شود که عبارتند از: نسلها، برازندگی خام، برازندگی وزنی و محاسبات مسافتی.

1.      مسائل بهینه سازی پویا:

در مسائل بهینه‌سازی پویا، حداقل یک قسمت (عنصر) از مساله، با گذشت زمان تغییر می‌کند. کاربردهای مساله مسیریابی وسیله نقلیه پویا به وضوح در مسائل دنیای واقعی دیده می‌شوند. این تغییرات ممکن است که بر روی تابع هدف و محدودیت‌ها اقر بگذارند. در ادامه تعدادی از روش های ارائه شده برای حل مسائل بهینه‌سازی پویا ارائه شده است:

·         استفاده از واگرایی هنگامی که تغییری اتفاق می‌افتد

·         استفاده مداوم از واگرایی در حین جستجو

·         رویکرد‌های پیش‌بینی

·         رویکرد‌های چند-جمعیتی

2.       مساله مسیریابی وسیله نقلیه پویا:

مونتمانی و همکاران مساله مسیریابی وسایل نقلیه پویا را به عنوان توسعه‌ای از مساله مسیریابی وسیله نقلیه کلاسیک می‌باشد و در واقع مساله پویا شامل تعداد زیادی از مساله ایستای پویا می‌باشد. مانند مساله ایستا، هدف در این مساله کمینه کردن هزینه‌های کل در هر دوره‌ی زمانی است که از تعداد m وسیله نقلیه تحت فرضیات زیر استفاده می‌کند:

ü      هر وسیله نقلیه از انبار شروع به حرکت می‌کند و دوباره به انبار برمی‌گردد.

ü      هر مشتری تنها توسط یک وسیله نقلیه ملاقات شود.

ü      هر وسیله دارای ظرفیت محدودی ،Q ، برای هر محصول می‌باشد. تقاضای مشتریانی که قرار است توسط این وسیله نقلیه برآورده شود نباید از ظرفیت وسیله نقلیه بیشتر شود.

فرق بین مساله مسیریابی وسیله نقلیه ایستا و پویا در این است که در مساله پویا، سفارشات جدید بعد از شروع شدن روز کاری به دست وسیله نقلیه می‌رسد، بنابراین نیاز است به طور پویا  فرآیند بهینه‌سازی تغییر کند. در مساله مسیریابی وسیله نقلیه پویا، پارامتری به نام درجه پویایی، dod، وجود دارد که نسبت مشتریان شناخته شده به مشتریان شناخته نشده در زمان شروع به کار سیستم می‌باشد که عددی بین 0 و1 می‌باشد.

برای مساله مسیریابی وسیله نقلیه پویا داده‌های زیر وجود دارند:

v     روز کاری، T، زمان موجود برای سرویس دادن به همه‌ی مشتریان را نشان می‌دهد.

v     زمان در دسترس، که تعیین می‌کند زمانی که یک مشتری وارد یک سیستم می‌شود، تا زمانی که زمان در درسترس بودنش فرا برسد هیچ اطلاعاتی از آن مشتریان و سفارش آنها نداریم.

v     یک دوره از زمان، که برابر زمان خدمت دادن به مشتری می‌باشد.

در این مدل، یک وسیله باید درزمان مقرر اعزام شود و پیش از اینکه انبار بسته شود دوباره به انبار برگردد. وسیله نقلیه ممکن است پیش آخرین مشتری که باید سرویس دهد باقی بماند مگر اینکه قانون " برگشت به خانه (انبار) "به دو دلیل زیر اتفاق بیافتد:

Ø      همه‌ی مشتریان سرویس داده شوند، یا

Ø      یک وسیله از حداکثر ظرفیت خود استفاده کند

برای حل مساله مسیریابی وسیله نقلیه پویا، هر روز کاری (T) به تعداد n_ts  بازه زمانی کوچک تقسیم می‌شود (T/ n_ts). اگر سفارش هر مشتری در وسط یک دوره زمانی برسد به انتهای آن دوره زمانی معوق می‌شود.

برای حل مساله مسیریابی وسیله نقلیه پویا، از دو زمان استفاده می‌شود. زمان اول به نام زمان برش، T_co، می‌باشد که این پارامتر توسط استفاده کننده تعیین می‌شود. زمان برش نسبتی از زمان کاری می‌باشد. اگر هر مشتری زمان در دسترس بودن بیشتری از زمان برش داشت باید قبل از اینکه سیستم شروع به کار کند شناسایی شود. زمان دوم معروف به تعهد پیشرفته، T_ac، به عنوان نسبتی از روز کاری بیان می‌شود. از این زمان استفاده می‌شود چون در عمل، یک سفارش باید حداقل T_ac ثانیه قبل از عزیمت از آخرین محل سرویس داده شده، به راننده اطلاع رسانی گردد. بنابراین T_acبرابر با صفر این مفهوم را می‌رساند که تمامی تصمیمات باید در لحظه آخر اخذ شود. بعد از هر برهه زمانی، بهترین جواب پیدا شده انتخاب می‌شود و مشتریان با زمان فعالیتی که در T/n_ts+T_ac ثانیه بعد شروع می‌شود به وسیله نقلیه مربوط به خود متصل می‌شوند. جوابهای حاصل از برهه‌های زمانی قبلی می‌توانند به عنوان جواب اولیه قسمت‌های بعدی به کار گرفته شوند.

1.      سیستم الگوریتم ژنتیک پیشرفته برای مساله مسیریابی وسیله نقلیه پویا

در این مقاله، الگوریتم ژنتیک توسعه داده شده برا اساس الگوریتم ژنتیک هانشار و اومبوکی-برمن می‌باشد اگرچه بهبودهایی در آن به منظور واگرایی بیشتر و فرار از بهینه محلی برای رسیدن به جواب های بهتر ارائه شده است. این اصلاحات عبارتند از :

·         جمعیت اولیه بخش زمانی اول

·          جمعیت اولیه بخش های زمانی دیگر

·          فرآیند انتخاب

·         جهش از نوع مبادله و

·          مدیریت/ کشف شرایط بهنیگی محلی

1.1. جمعیت اولیه بخش زمانی اول:

جمعیت اولیه برای الگوریتم ژنتیک می‌تواند به صورت تصادفی یا با استفاده از یک الگوریتم ابتکاری ایجاد شود. در این مقاله از هر دو روش تصادفی (در حدود 80 درصد) و الگوریتم ابتکاری برای تولید جواب اولیه استفاده شده است. 20 درصد باقی مانده از روش ابتکاری زیر برای تولید جواب اولیه استفاده شده است:

a)      تولید مجموعه ای از وسایل نقلیه =

b)      ایجاد مجموعه‌ای از جایگشت‌های تصادفی برای مشتریان شبیه مساله مسیریابی وسیله نقلیه

c)      جایگشت ایجاد شده در مرحله­ی قبل را یکی یکی در بهترین جاهای مجموعه وسایل نقلیه ایجاد شده خالی قرار دهید تا زمانی که برای انتخاب تصادفی در 90 درصد مواقع از ظرفیت وسیله نقلیه تجاوز نکند ( در 90 درصد مواقع محدودیت ظرفیت را در نظر بگیرید)  و در غیر اینصورت تخطی مجاز می‌باشد.

1.1. جواب اولیه برای برهه‌های زمانی دیگر:

80 درصد از جواب اولیه برهه‌های زمانی دیگر توسط روش تصادفی تولید می‌شود. 10 درصد از جمعیت اولیه توسط همان روشی تولید می‌شود که 20 درصد برهه زمانی اول در زیربخش قبلی ایجاد شد. 10 درصد دیگر از طریق استفاده از بهترین کروموزوم از برهه زمانی قبلی به شکل زیر ایجاد می‌شود:

a)      یک مجموعه جایگشت تصادفی از مشتریان جدید برهه زمانی فعلی را ایجاد کنید و

b)      یکی یکی جایگشت‌های ایجاد شده را در بهترین مکان‌ها وارد کنید و دوباره، در 90درصد از مواقع ظرفیت را در نظر بگیرید در غیر اینصورت آنها را نادیده بگیرید.

1.2. انتخاب

فرآیند انتخاب مشخص می‌کند که کدام کروموزم‌ها برای فرایند تولید مجدد ( جهش و تقاطع) انتخاب می‌شوند. در این مقاله، انتخاب تورنمتی با اصلاحاتی استفاده می‌شود تا به غیر از بهترین کروموزوم شانس بیشتری برای انتخاب داده شود. نسخه اصلاح شده در شکل 1 نشان داده شده است. 

که در آن مقدار تصادفی rبرای مقایسه با آستانه انتخاب pایجاد شده است تا واگرایی را افزایش دهد.

1.1. جهش

فرایند جهش تعیین می‌کند که چگونه فرزندان در الگوریتم ژنتیک خود-اصلاح می‌شوند. دو روش جهش در این مقاله استفاده شده است که عبارتند از:

·         معکوس (وارونگی) در طول کروموزوم دو نقطه برای قطع شدن را انتخاب می‌کند و سپس ژن های بین این دو نقطه را معکوس می‌کند

·         مبادله، دو ژن را انتخاب می‌کند وجایگاههای آنان را با هم تعویض می‌کند. در این مقاله یکبار دیگر با هدف افزایش واگرایی، یک جابجایی اصلاح شده به منظور تولید مشتقات دیگر طبق گام های زیر استفاده می‌شود:

گام 1: دو عدد صحیح تصادفی تولید کنید و تفاضل آنها را به دست آورید ()

گام 2: برای  بار، دو ژن را انتخاب کنید و با هم جایگزین کنید

1.1. تقاطع و کشف شرط بهینه محلی

فرایند تقاطع تعیین می‌کند که چگونه والدین با هم ترکیب می‌شوند تا فرزندان به وجود آیند. در این مقاله، یک نسخه اصلاح شده از تقاطع مسیر با بهترین هزینه استفاده شده است که در شکل 2 نمایش داده شده است:

در این رویکرد، هزینه‌ی وارد کردن مشتری Cبین دو مشتری متوالی a,bطبق رابطه زیر محاسبه می‌شود:

Cost_{c, ab}=Dist (c, a) + Dist(c, b) – Dist (a, b)

برای استفاده از این استراتژی، الگوریتم ژنتیک با یک حد آستانه برابر با یک. اگر در ده نسل متوالی، همان بهترین کروموزوم را به دست آورد، در شرایط بهینه محلی گیر می‌کند. هنگامی که سیستم این بهینه محلی را کشف می‌کند، تلاش می‌کند تا از آن رهایی پیدا کند تا به بهینه کلی برسد، سپس آستانه تقاطع را به اندازه‌ی 10 درصد کاهش می‌دهد و دوباره شروع می‌کند تا برای ده نسل متوالی چک کند. حد آستانه تقاطع باید در نهایت به کمتر از 0.1 برسد و دوباره به 1 برمی‌گردد.

در نهایت یک استراتژی نخبه‌گرا استفاده می‌شود. بدین ترتیب، همیشه مجموعه ای از بهترین جوابها به نسل بعد منتقل می‌شود که تضمین می‌کند بهترین جوابها در طول زمان باقی‌ می‌مانند.

نتایج:

برای ارزیابی اصلاحات انجام شده برای الگوریتم ژنتیک، از 6 سیستم به شرح زیر استفاده شده است:

1.       اولین سیستم همان الگوریتم ژنتیک می­باشد که در آن اصلاحی صورت نگرفته است و در آن جمعیت اولیه در همه­ی مقاطع زمانی به­صورت تصادفی تولید می­شود و از مکانیزم­های انتخاب ترنمنتی و جهش معکوس استفاده می­شود.

2.       سیستم دوم همان سیستم اول می­باشد با این تفاوت که در دوره­ی زمانی اول، جمعیت اولیه با روشی که در بخش 4.1 توضیح داده شد ساخته می­شود.

3.       سیستم سوم همان سیستم دوم می­باشد با این تفاوت که برای ایجاد جمعیت تصادفی در برهه­های زمانی متفاوت از روش های شرح داده شده در زیر بخش های 4.1 و 4.2 استفاده می­ شود.

4.       سیستم چهارم همان سیستم سوم می باشد، فقط برای فرایند انتخاب اصلاح شده زیر بخش 4.3 اضافه می شود.

5.       سیستم پنجم همان چهارمی می باشد، فقط جهش تعویض اصلاح شده در زیر بخش 4.4 به آن اضافه می شود.

6.       سیستم ششم همان پنجمی می باشد، فقط فرآیند کشف شرایط بهینه محلی موجود که در زیر بخش 4.5 توضیح داده شده است، به آن اضافه شده است.  

مقادیر پارامترهای مربوط به الگوریتم ژنتیک در ادامه آمده است:

جدول زیر نشان می دهد که هر سیستم با سیستم قبلی تا چه اندازه متفاوت و بهتر می باشد:

برای ارزیابی عملکرد الگوریتم ارائه شده در این مقاله، با توجه به کیفیت جواب حاصله بر مبنای کمینه نمودن فواصل پیموده شده، مقایسه ای بین این نتایج این مقاله و کارهای قبلی صورت گرفته است. برای مقایسه از الگوریتم مورچگان مونتمانی، جستجوی ممنوعه ی  هانشار و اومبوکی-برمن و از الگوریتم های جستجوی همسایگی متغیر و بهینه سازی ازدحام ذرات استفاده شده است:

رویکرد ارزیابی جدید:

در این بخش، ما دومین نوآوری مقاله را ارائه می دهیم که رویکردی جدید برای ارزیابی سیستمهای مساله مسیریابی وسیله نقلیه پویا می باشد. تا به امروز از روش ارزیابی مبتی برزمان استفاده می شد که وابستگی زیادی به سیستم مورد استفاده داشت. اما در این مقاله از روشی عادلانه که مبتنی بر قدرت سیستم پردازنده نمی باشد استفاده می کنیم. به همین دلیل از 4 رویکرد ارزیابی استفاده می شود:

·         نسل ها: از این رویکررد در بسیاری از کاربردهای GA به عنوان یک شرط توقف استفاده می شود. بدون توجه به ابعاد مساله، تعداد نسل ها در هر بازه­ی زمانی را می­شمارد. تعداد متوسط نسلهای مورد نیاز در هر بازه­ ی زمانی از طریق متغیر generationsum محاسبه می شود.

·         ارزیابی برازندگی خام: با استفاده از متغیری به نام rawFitnessEvalSum تعداد ارزیابی برازندگی در هر بازه­ ی زمانی را می شمارد و هر بار که برازندگی ارزیابی می شود یکی به آن اضافه می شود.

·         ارزیابی برازندگی وزنی: با استفاده از متغیری به نام WeightedFitnessEvalSum هم تعداد ارزیابی برازندگی کامل و ارزیابی وزنی را می شمارد.

·         محاسبات مسافت: تعداد محاسبات مربوط به مسافت را می شمارد که ابعاد مساله را در هر بازه ی زمانی منعکس می کند. برای مثال برای دو مشتری سه فاصله وجود دارد، از انبار به مشتری اول، از مشتری اول به مشتری دوم و از مشتری دوم به انبار. از متغیری به نام distanceCalcSum که تعداد کل محاسبات مربوط به مسافت را نشان می دهد استقاده می شود.

جدول زیر اطلاعات مربوط به هر یک از رویکردها را نشان می دهد: