توضیحات
ABSTRACT
Rollout algorithms lead to effective heuristics for the single vehicle routing problem with stochastic demands (VRPSD), a prototypical model of logistics under uncertainty. However, they can be computationally intensive. To reduce their run time, we introduce a novel approach to approximate the expected cost of a route when executing any rollout algorithm for VRPSD with restocking. With a sufficiently large number of customers its theoretical speed-up factor is of big-o order 1/3. On a set of instances from the literature, our proposed technique applied to a known rollout algorithm and three variants thereof achieves speed-up factors that range from 0.26 to 0.34 when there are more than fifty customers, degrading only marginally the quality of the resulting routes. Our method also applies to the a priori case, in which case it is exact.
INTRODUCTION
Given a set of geographically dispersed customers, a quantity to deliver to each customer, and a fleet of capacitated vehicles located at a depot, the vehicle routing problem consists of determining a set of minimal cost routes, each starting and ending at the depot, such that the demand of all the customers is satisfied without exceeding the capacity of the vehicles. Since its introduction by Dantzig and Ramser (1959), this problem and variants thereof have been well studied (see Fisher, 1995; Laporte, 1992; Toth & Vigo, 2014; and Laporte, 2009 for reviews). In the vehicle routing problem with stochastic demands (VRPSD), given probability distributions describe the customer demands and the realization of the demand of a customer becomes known upon the first visit to this customer. If the realized demand of a customer exceeds the remaining capacity of a vehicle when this customer is visited then a route failure occurs and a recourse action must be taken. VRPSD is relevant in both strategic distribution planning, when only estimates of customer demands are typically available, and tactical and operational decision making, when there remains residual uncertainty about the demands of the customers.
چکیده
الگوریتم های تکامل یافته منجر به اکتشافی مؤثر برای مسائل مسیریابی یک خودرو با خواسته های تصادفی (VRPSD)، یک مدل نمونه اولیه از تدارکات تحت عدم اطمینان می شود. با این حال، آنها می توانند محاسباتی شدید باشند. برای کاهش زمان اجرا، ما یک رویکرد جدید برای تقریب هزینه مورد انتظار یک مسیر را در هنگام اجرای هر الگوریتم رولینگ برای VRPSD با استفاده از بازگردانی معرفی می کنیم. با توجه به تعداد کافی از مشتریان، عامل تسریع نظری آن از 1/3 بزرگتر است. در مجموعه ای از موارد از ادبیات، تکنیک پیشنهادی ما به یک الگوریتم شناخته شده شناخته شده و سه نوع آن، فاکتورهای سرعت بخشیدن را از 0.26 تا 0.34 به دست می آورند که بیش از پنجاه مشتری وجود دارد، و تنها کیفیت کیفیت راه های به دست آمده را تضعیف می کند . روش ما نیز برای یک پرونده پیشین کاربرد دارد، در این صورت دقیق است.
مقدمه
با توجه به مجموعه ای از مشتریان پراکنده جغرافیایی، مقدار برای ارائه به هر مشتری و یک ناوگان از وسایل نقلیه خالی که در انبار قرار دارد، مسائل مسیریابی خودرو شامل تعیین مجموعه ای از مسیرهای حداقل هزینه، هر شروع و پایان در انبار، مانند که تقاضای تمام مشتریان بدون بیش از ظرفیت وسایل نقلیه راضی است. از زمان معرفی آن توسط دانتسیگ و رامسر (1959)، این مشکل و انواع آن به خوبی مورد بررسی قرار گرفته است (نگاه کنید به Fisher، 1995؛ Laporte، 1992؛ Toth & Vigo، 2014؛ Laporte، 2009 برای بررسی). در مسير رانندگي خودرو با خواسته هاي تصادفي (VRPSD)، با توجه به توزيع احتمالات، نيازهاي مشتري را توصيف مي كند و تحقق تقاضاي مشتري بر اساس اولين بازديد از اين مشتري شناخته مي شود. اگر تقاضای متوجه یک مشتری بیش از ظرفیت باقی مانده یک وسیله نقلیه هنگامی که این مشتری بازدید می شود، یک خطای مسیر اتفاق می افتد و باید اقدام عملیاتی صورت گیرد. VRPSD در هر دو برنامه ریزی توزیع استراتژیک مرتبط است، زمانی که تنها برآوردهای تقاضای مشتری معمولا در دسترس است، و تصمیم گیری تاکتیکی و عملیاتی، زمانی که عدم اطمینان باقی مانده در مورد خواسته های مشتریان وجود دارد.
Year: 2018
Publisher : ELSEVIER
By : Luca Bertazzi , Nicola Secomandi
File Information: English Language/ 11 Page / size: 682 KB
سال : 1396
ناشر : ELSEVIER
کاری از : لوکا برتازی، نیکولا سیکومندی
اطلاعات فایل : زبان انگلیسی / 11 صفحه / حجم : KB 682
نقد و بررسیها
هنوز بررسیای ثبت نشده است.