مقاله حل مسأله مسیریابی وسایل نقلیه های پویا با الگوریتم جستجوی ممنوعه

بخشی از مقاله

چکیده

قالات بسیاري درباره مسأله مسیریابی خودرو در دسترس است اما تقریباً تمام فعالیت هاي صورت گرفته در این زمینه ، مسائل استاتیک بوده اند که تمامی این اطلاعات به صورت پیشرفته بررسی شده و شناخته شده اند. پیشرفت هاي تکنولوژیکی سالهاي اخیر سبب طلوع مسائل جدیدي چون مسائل مسیریابی پویاي خودرو شده است. به این صورت که سفارش هاي جدیدي با گذشت زمان دریافت می شود و باید به صورت پویا با یک برنامه زمان بندي قبلی همراه شود. در این مقاله مسأله مسیریابی پویاي خودرو بررسی شده و یک استرتژي حل مسأله بر پایه ي الگوریتم فراابتکاري جستجوي ممنوعه پییشنهاد شده است. این شیوه ، براي مسائل موجود بسیاري تست شده است. نتایج محاسباتی ، اثربخشی و بهره وري استرتژي مدل پیشنهاد شده ما را تأیید می کند.

کلمات کلیدي: مسیریابی پویاي وسایل نقلیه ، الگوریتم جستجوي ممنوعه ، مسیریابی وسایل نقلیه ، مسیریابی وسایل نقلیه چندانباره .

1,1مقدمه

مسیریابی کارآمد براي وسایل نقلیه به لحاظ اقتصادي هم براي بخشهاي خصوصی و هم براي بخشهاي عمومی از اهمیت بالایی برخوردار است . [1] مسأله ي مسیریابی وسایل نقلیه - VRP - به عنوان یک زمینه ي گسترده ي مطالعاتی تعریف شده است. در مسأله مسیریابی وسایل نقلیه - VRP - یک ناوگان وسایل نقلیه با ظرفیت محدود جهت سرویس دهی به یک مجموعه از مشتري ها باید مسیردهی شوند . در VRP ایستا تمامی سفارشات مشتري ها از قبل مشخص هستند. مسائل مسیریابی وسایل نقلیه - VRP - دسته جدیدي از مسائل هستند که باعث افزایش استفاده کنندگان از پیشرفت هاي اخیر در زمینه حمل و نقل و تکنولوژي اطلاعات شده است که استفاده از اطلاعات را جهت فراهم کردن و به انجام رساندن زمانبندي در هر زمانی منجر می شود.

در این مسائل سفارشات جدید زمانی که یک زمانبندي صورت گرفته است ، دریافت می شوند. بنابراین زمانبندي ما باید تا زمان برگشتن تمامی وسایل نقلیه به انبار به روز رسانی شود. در مسأله اي که ما در این مقاله بررسی می کنیم ، برخی از سفارشات قبل از حرکت وسایل نقلیه از انبار دریافت شده اند و یک زمانبندي اولیه جهت پوشش دادن مسیرها ایجاد شده است. با گذشت زمان، سفارشات جدید وارد سیستم شده و باید با برنامه زمانبندي قبلی همراه شوند. در این مقاله مسأله مربوطه به این صورت است که وسایل نقلیه برنامه زمانبندي اولیه را به انجام رسانده اند، پس از دریافت سفارشات جدید زمانبندي ثانویه را براي هریک از وسایل نقلیه مشخص می کنند که در ادامه به تشریح کامل مسأله خواهیم پرداخت.

مسأله مسیریابی وسایل نقلیه پویا - DVRP - جز مسائل کلاسیک NP-hard به شمار می آید و یافتن جواب بهینه در این حوزه حتی در ابعاد نسبتا کوچک نیز دشوار است بنابراین کاربرد روشهاي ابتکاري و فراابتکاري در این حوزه رشد چشمگیري داشته است. قابل ذکر است که براي حل مسأله مسیریابی پویاي خودرو از استراتژي حلی بر پایه ي الگوریتم فرا ابتکاري جستجوي ممنوعه استفاده شده است. به این صورت که ابتدا مسأله VRP ایستا را با اندکی تفاوت با این الگوریتم حل کرده و سپس به حل مسأله VRP چند انباره با اندکی تفاوت پرداخته ایم. در نهایت با ادغام این دو مسأله ، مسأله مسیریابی پویاي وسایل نقلیه حل می شود. این مقاله برگرفته از مقاله ي مونتمانی و همکاران[2] می باشد با این تفاوت که تابع هدف این مقاله براساس کوتاهترین مسیر می باشد.

1,2شرح مسأله

در این بخش ابتدا VRP ایستا توصیف شده و در بخش بعدي به توصیف VRP چند انباره می پردازیم. در نهایت مسیریابی پویاي وسایل نقلیه را شرح می دهیم.

1,2,1مسأله مسیریابی ایستاي وسایل نقلیه

مسأله مسیریابی ایستاي وسایل نقلیه می تواند به این صورت توصیف شود : n مشتري باید از یک انبار سرویس دهی شوند. مشتري iام درخواستی به مقدار دارد. یک ناوگان داراي v وسایل نقلیه که هر وسایل نقلیه aام با ظرفیت محدود   جهت تحویل کالاها در دسترس است. یک مسافتی به طول    براي سرویس دهی به هر مشتري وجود دارد که این مسیر نشانگر مسافتی است که وسیله نقلیه براي حرکت از مشتري iام و رسیدن به مشتري jام باید بپیماید.بنابراین ، بعد از حل VRP یک مجموعه اي از تورهامشخص می شوند.

VRP می تواند به صورت ریاضی مدله شود و گراف G= - V,A -   کهV={0,1,…,n} یک مجموعه از گره ها است که V=0    نشانگر انبار بوده و مشتري ها {1,2,…,n} ،A= { - i,j - /i,j   V} یک مجموعه از یال ها می باشند که این یال ها کوتاهترین مسیر از گره iام به گره jام را محاسبه می کند. مقدار کالاي سفارش داده شده ي∈ هر مشتري iام - i>0 - ، با نشان داده می شود و هر وسیله نقلیه داراي ظرفیت بخصوص  ,…, می باشد که در نهایت به انبار برمی گردد. هدف ما یافتن یک مجموعه ي موجه از تورها با کوتاه ترین مسیر می باشد. یک مجموعه تور زمانی موجه می شود که از هر گره - مشتري - فقط یکبار عبور شود. هر تور aام شروع و پایانش در انبار صورت می گیرد. باید توجه شود که مجموع مقادیر سفارشات هرگز از ظرفیت وسایل نقلیه ها بیشتر نشود.

1,2,2مسأله مسیریابی وسایل نقلیه چند انباره

مسأله مسیریابی وسایل نقلیه چندانباره می تواند به این صورت توصیف شود: n مشتري تقاضاي کالا دارد. مشتري iام درخواستی به مقدار    دارد و ما داراي p انبار هستیم که با استفاده از آنها به سفارشات مشتري هایمان جواب می دهیم. یک ناوگان داراي v وسایل نقلیه که هر وسایل نقلیه a ام با ظرفیت محدود   جهت تحویل کالاها در دسترس است. یک مسافتی به طول   براي سرویس دهی به هر مشتري وجود دارد که این مسیر نشانگر مسافتی است که وسایل نقلیه براي حرکت از مشتري iام و رسیدن به مشتري jام باید بپیماید. بنابراین ، بعد از حل MDVRP یک مجموعه اي از تورها مشخص می شوند.MDVRP می تواند به صورت ریاضی مدله شود. در MDVRP فرض می شود که تعداد و مکان هر انبار و مشتري از ابتدا معلوم است و تقاضاي هر مشتري و تعد اد و نوع هر وسیله نقلیه مشخص است.

براي توضیح این مورد از مدل پذیرفته شده ي ریناد و همکاران استفاده میکنیم .[3] با این تغییر که در این مقاله تابع هدف ما بر حسب کوتاه ترین مسیر می باشد. G= - V,A - یک گراف است که V مجموعه گره ها است که تعداد مشتري ها و انبارها را نشان می دهد و A نشان دهنده مجموعه یال ها است و مسیرها را نشان میدهد. هدف در اینجا تعیین مشتري هایی است که به هر انبار تخصیص می دهیم به نحوي که مسافت طی شده توسط هر وسیله نقلیه حداقل شود. محدودیتهاي مسأله از این قرار است: هر مشتري تنها توسط یک انبار خدمت دریافت کند، شروع و پایان مسیر هر وسیله نقلیه یک انبار باشد، کل تقاضاي هر مسیر کمتر یا مساوي ظرفیت وسایل نقلیه باشد، کل تقاضاي مشتري هایی که به هر انبار تخصیص داده می شود کمتر و یا مساوي ظرفیت انبار باشد.

1,2,3مسأله مسیریابی وسایل نقلیه پویاي

در مسأله مسیریابی وسایل نقلیه پویا ، سفارشات جدید زمانی که روز کاري وسایل نقلیه جهت سرویس دهی به مشتریان شروع شده است ، دریافت می شوند. در مسیریابی وسایل نقلیه پویا ابتدا زمانبندي اولیه براي مشتري هاي قبلی صورت می گیرد یعنی یک VRP ایستا حل می شود با این تفاوت که وسایل نقلیه اي که ظرفیت محدود آن هنوز تمام نشده است به انبار اولیه برنمی گردد . حال سفارشات جدیدي که دریافت شده است باید زمانبندي شوند. در این صورت مکان نهایی وسایل نقلیه در زمانبندي اولیه به عنوان انبارهاي ثانویه عمل می کنند ]در واقع قسمت دوم مثال به صورت MDVRP می باشد..[ یعنی از آن مکان نهایی که هر کدام طی کرده اند ، زمانبندي ثانویه را انجام می دهیم و وسایل نقلیه هاي ما باید به مشتري هاي جدید سفارش دهند. باید توجه داشت که اگر سفارش مشتري خاصی بیشتر از ظرفیت وسایل نقلیه باشد باید تا برگشت به انبار اولیه و زمان بندي بعدي منتظر بماند.

2,1الگوریتم جستجوي ممنوعه

اگرچه ریشه بحث جستجوي ممنوعه به اواخر دهه 1960 و اوایل دهه 1970 بر می گردد ولی شکل فعلی این روش تنها چندین سال پیش توسط گلوور[•] ارائه شد. این روش در حال حاضر به عنوان یک روش بهینه یابی که به سرعت در بسیاري از زمینه هاي جدید به کار گرفته می شود مطرح است . ایده اصلی جسجوي ممنوعه توسط هانسن نیز مطرح شده است

2,1,1روش جستجوي ممنوعه

روش جستجوي ممنوعه، یکی از روش هاي بهینه یابی فرا ابتکاري از نوع بهبود دهنده براي حل مسایل بهینه سازي ترکیبی است که بر پایه الگوریتم هاي جستجوي محلی بنا نهاده شده است، و به نحوي سعی در بر طرف نمودن عیوب آنها دارد . این روش در حقیقت یک روش جستجوي محلی هدایت شده است که از ساختارهاي حافظه اي انعطاف پذیري استفاده می کند - حافظه انطباقی - و می توان از آن به عنوان یک چارچوب کلی براي روش هاي نوین جستجوي فراابتکاري استفاده نمود . همچنین اخیرا هم گرایی این روش به سمت جواب بهینه، در صورت زیاد شدن تکرارها به اثبات رسیده است یک الگوریتم جستجوي ممنوعه تقریبا مانند الگوریتم هاي جستجوي محلی کار می کند .

با این تفاوت که براي جلوگیري از دور و تسلسل در جواب ها و افتادن در دام جواب هاي بهینه محلی، از مفهومی به نام فهرست ممنوعه استفاده می کند . فهرست ممنوعه حاوي تعدادي محدود از جواب هاي مسأله است که در هر مرحله حرکت به سوي آنها ممنوع است . حتی اگر بهترین جواب در همسایگی جواب فعلی باشد . این فهرست ممنوعه، در هر مرحله بروز می شود . حافظه انطباقی روش جستجوي ممنوعه از دو جز کوتاه مدت و بلند مدت تشکیل شده است که در این جا بیشتر روي جنبه هاي کوتاه مدت آن تأکید می کنیم . ولی در عین حال به منظور دست یابی به نتایج محاسباتی بهتر، بر اهمیت حافظه هاي بلند مدت نیز تأکید خواهیم کرد .

از دید کوتاه مدت استراتژي گریز از مینیمم هاي به جاي آن V - x -   به جواب مرحله بعد، با توجه به بهترین جواب ممکن موجود در همسایگ - انجام محلی بصورت زیر است: حرکت از جواب فعلی خواهد شد. در مواقعی که بسیارx همسایگی بزرگتر از آن باشد که بتوان تمام آن را موردکاوش قرار داد، از زیرV - x ′ - - - استفاده می شود . - حتی اگر هیچ جوابی بهتر ازجواب فعلی در -      - موجود نباشد . هرگاه ساختار - همسایگی⊂متقارن باشد، - یعنی اگر    متعلق به همسایگی V - x -  باشد، آنگاه -     ∈ -    نیز باشدxخطر افتادن در دور وجود دارد . درواقع ممکن است بهترین جواب در V - x - باشد! که در این صورت بطور پشت سر هم میان و نوسان خواهیم نمود .

براي اجتناب ازاین حالت و سایر حالتx    هایی که ایجاد دور می نمایند فهرست ممنوع را به صورت - - که در واقع شامل l جواب اخیر بدست آمده می باشد، تشکیل می دهیم - درحقیقت نحوه ورود و خروج جواب ها به فهرست ممنوعه به صورت    FIFO  است.   -  اگر x دفهرست ممنوعه باشد، آنگاه حرکت از به x ممنوع خواهد بود . البته این کار باعث بوجود آمدن بعضی مشکلات نیز می شود . چرا که ثبت ونگهداري تمام اطلاعات جواب هایی که اخیرا بازدید شده اند، و بررسی هر یک از جواب هاي کاندیدا در فهرست موجود، فرایندي زمان بر است . بنابراین به جاي ثبت تمامی اطلاعات مربوط به جواب ها، یک خاصیت یا ویژگی بخصوص از آنها ثبت می شود .

مثلأ تبدیلی که با استفاده از آن، جواب مربوطه بدست آمده است . اما از طرفی این کار - یعنی ثبت یک ویژگی از جواب ها به جاي خود آنها - ، بسیار محدود کننده تر از ثبت خود جواب ها است . چرا که ممکن است جواب هاي دیگري نیز که جز جواب هاي اخیر بازدید شده نیستند، داراي خاصیت مذکور باشند . از طرف دیگر ممکن است فهرست ممنوعی که شامل خواص جواب ها است، نتواند به خوبی از ایجاد " دور " جلوگیري کند . البته این مشکلات، معضلات اساسی و مهمی به شمار نمی آیند. زیرا نقش اساسی فهرست ممنوعه، ایجاد تنوع در جستجو است.

یعنی در واقع هدف فهرست ممنوعه این است که از جواب فعلی به سمت جواب هایی از مکان هایی از فضاي جواب حرکت شود که تاکنون مورد جستجو قرار نگرفته اند و بطور اخص از دام مینیمم هاي محلی فرار شود . در تأیید این مورد می توان به تجارب محققانی چون پیریلات اشاره نمود. استفاده از فهرست هاي ممنوعی که شامل خود جواب ها هستند، حتی با صرف نظر از زمان محاسباتی بالا، معمولا منجر به جواب هاي ضعیفی نیز می شود و وظیفه متنوع سازي را به خوبی انجام نمی دهد . بنابراین علی رغم مطالبی که گفته شد، فهرست هاي ممنوعه اغلب شامل یک یا چندویژگی از جواب هاي اخیر بازدید شده یا حرکت هاي اخیر انجام شده هستند . اما در عین حال باید در انتخاب این ویژگی ها دقت کافی به خرج داد.

همان طور که بیان شد، ممنوع کردن جواب هایی که داراي یک خاصیت ویژه هستند، محدود کننده تر از ایجاد ممنوعیت براي جواب هایی است که اخیرا بازدید شده اند . براي اصلاح تبعات نامطلوب این امر - دقت کنید که تمام تبعات آن نامطلوب نیستند - پیشنهاد شده است که وقتی یک حرکت منجر به جوابی شد که به حد کافی خوب است، باید در ممنوع بودن آن تجدید نظر کرد . در واقع براي این منظور، یک »سطح رضایت « تعیین می شود که مشخص می کند منظور از یک جواب به حد کافی خوب چگونه جوابی است . در این جا دو نوع معیار رضایت توضیح داده می شود:

معیار رضایت :1 یک جواب از حد رضایت بالاتر است، اگر مقدار تابع هدف آن از هر جواب بدست آمده قبلی بهتر باشد.
معیار رضایت :2 هرگاه ساختار روش و فهرست ممنوعه در یک تکرار از الگوریتم جستجوي ممنوعه به گونه اي باشد که امکان هیچ حرکتی وجود نداشته باشد، در این صورت آن حرکت یا جوابی از فهرست ممنوعه که در صف خروج از فهرست ممنوعه از سایر جواب ها به خروج نزدیک تر است، انتخاب می شود و ممنوعیت آن برداشته می شود. در جستجوي ممنوعه به منظور ایجاد یک توازن میان کیفیت S و تلاش جهت دست یابی به آن از استراتژي لیست کاندید استفاده می شود جستجوي ممنوعه در هنگام انجام جستجو با اصلاح همسایگی -      -   که آن را بطور مؤثري با همسایگی دیگر بصورت -    ′ -   جایگزین می کند، خود را از بهینه موضعی خارج می کند .

همان طور که xذکر شدیک جنبه مهم جستجوي ممنوعه استفاده از حافظه است که جهت تعیین -    ′ -   بکار می رود.  با وجود سادگی طرح کلی، این روش خصوصیات مفیدي دارد . در صورتی که x مجموعه اي از نقاط حدي قابل قبول براي یک برنامه ریزي خطی و -   -  مجموعه اي از حرکات باشد که از نقطه   به یک نقطه حدي مجاور حرکت می کند، آنگاه می توان روش سیمپلکس را از آن نتیجه گرفت . محدودیت اصلی این روش در مسایل ترکیباتی این است که زمانی که در نقطه توقف بهینه موضعی بدست می آید و انجام حرکت بهبودي دیگر امکان ندارد، نقطه بدست آمده می تواند بهینه کلی نباشد.

جستجوي ممنوعه چنین روش هیوریستیکی را به ادامه جستجو در حالیکه حرکت بهبودي وجود ندارد فرا می خواند، بدون اینکه به بهینه موضعی که قبلا یافته شده بازگشت داشته باشد . روش جستجوي ممنوعه در حالت ساده می تواند به صورت زیر مطرح شود:یک زیر مجموعه T از -   -  تولید می شود که عضوهاي آن حرکات ممنوع نام دارند . این حرکات می توانند تا t تکرار ممنوع باقی بمانند که t می تواند بابت یا متغیر باشد . عضویت در مجموعه T می تواند به شکل یک لیست یا مجموعه اي از شرایط ممنوعه بیان شود - به عنوان