ترجمه مقاله یک روش جستجوی محلی تکراری برای مسئله‌ زمان ‌بندی خودرویی چند انباره

ترجمه مقاله یک روش جستجوی محلی تکراری برای مسئله‌ زمان ‌بندی خودرویی چند انباره

ترجمه مقاله Iterated local search for the multiple depot vehicle scheduling problem

چکیده فارسی:

زمان ‌بندی خودرویی چند انباره multiple depot vehicle scheduling problem – MDVSP یک مسئله‌ ی مهم در حمل و نقل عمومی است. با توجه به این موضوع که راه ‌حل ‌های بساری برای حل این مسئله بیان ‌شده است، اما الگوریتم ‌هایی که از روش ‌های فراابتکاری یا متاهیروستیک استفاده می‌ کنند، به تازگی به میان آمده ‌اند. در مقاله پیش رو، یک الگوریتم جستجوی محلی تکراری را برای مسئله‌ ی MDVSP یا زمان ‌بندی خودرویی چند انباره ارائه داده ایم که از یک شمایی تحت عنوان جابجایی بلاک بهره گرفته ‌شده است که بر مبنای زنجیره ‌ی جهشی می باشد. با استفاده از مجموعه‌ از بنچ مارک ‌ها، به طور تجربی نشان داده شده است که الگوریتم پیشنهادی ما عملکرد بهتری را نسبت به روش‌ های فرا هیروستیکی داشته است که تا به حال پیاده ‌سازی شده اند و از این ‌رو توانسته نتایجی با کیفیت بهتری را در کمترین زمان محاسباتی به دست آورد.

توضیحات بیشتر و دانلود مقاله اصلی در ادامه مطلب …

با توجه به مجموعه ‌ای از سفرها و مجموعه ‌ای از خودروهایی که در چندین انبار با ظرفیت محدود هستند، مسئله ‌ی مسیریابی خودرویی چند انباره یا MDVSP با هدف زمان ندی خودروها ارائه شده است تا به وسیله آن بتوان تمام سفرها را پوشش داد، به صورتی ‌که زمان‌ بندی حاصله بتواند مجموعه‌ ای از محدودیت ‌ها را ارضا کرده و تابع هزینه را نیز کمینه کند.

می توان MDVSP را یک گام کلیدی در پروسه ‌ی برنامه ‌ریزی عملیاتی مربوط به شرکت‌ های حمل ‌و نقل عنوان کرد. اگر چه این موضوع، یک مسئله ‌ی چالش‌ برانگیز است، اما در زمانی که حداقل دو انبار را در نظر بگیریم، این مسئله به یک مسئله ‌ی ان پی سخت مبدل خواهد شد. در این خصوص، متدهای راه ‌حل بسیاری در سه دهه ‌ی اخیر توسعه ‌یافته ‌اند. فعالیت ‌های اولیه در رابطه با این مسئله، بر روی الگوریتم ‌های هیروستیک متمرکز بوده ‌اند.

.

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

.

از انتهای دهه ‌ی 80 میلادی، چندین الگوریتم دقیق در این خصوص پیشنهاد شده است. مدل ‌هایی که بکار گرفته‌ شده است، متعلق به یکی از سه دسته‌ بندی زیر هست:

• فرمولاسیون جریان تک کالایی(مثلا کارپانت، دل آمیکو، توت 1989، فیسچتی ، لودی و مارلتو 2001)
• فرمولاسیون جریان چند کالایی(مثلا فوبر، هالت، واتس 1994، لوبیل1979، کلیویر ، ملولی 2006)
• فرمولاسیون بخش بندی مجموعه(مثلا ریبرو ، سومیس 1994، هاجار، مورکاتو و سومیس 2006)

 چکیده انگلیسی:

The multiple depot vehicle scheduling problem (MDVSP) is a well-known and important problem arising in public transport. Although many solution approaches have been published in the literature, algorithms using metaheuristics appeared only very recently (large neighborhood search and Tabu search). In this paper, we introduce an iterated local search algorithm for the MDVSP, incorporating a neighborhood schema called ‘‘block moves”, based on the notion of ejection chains. Using a set of benchmark instances, we show empirically that the proposed algorithm performs better than the best metaheuristics implemented so far and obtains high quality results within short computational times.