تلفن: ۰۴۱۴۲۲۷۳۷۸۱
تلفن: ۰۹۲۱۶۴۲۶۳۸۴

دانلود رایگان مقاله انگلیسی یک الگوریتم دقیق برای حل مسئله مسیریابی خودرو با خواسته های تصادفی – الزویر ۲۰۱۹

عنوان فارسی: یک الگوریتم دقیق برای حل مسئله مسیریابی خودرو با خواسته های تصادفی تحت یک سیاست ذخیره سازی مطلوب
عنوان انگلیسی: An exact algorithm to solve the vehicle routing problem with stochastic demands under an optimal restocking policy
تعداد صفحات مقاله انگلیسی : 31 تعداد صفحات ترجمه فارسی : ترجمه نشده
سال انتشار : 2019 نشریه : الزویر - Elsevier
فرمت مقاله انگلیسی : PDF نوع مقاله : ISI
نوع نگارش : مقالات پژوهشی (تحقیقاتی) پایگاه : اسکوپوس
کد محصول : E10784 رفرنس : دارد
محتوای فایل : PDF حجم فایل : mb 1
رشته های مرتبط با این مقاله: مهندسی کامپیوتر
گرایش های مرتبط با این مقاله: الگوریتم ها و محاسبات
مجله: مجله اروپایی تحقیق در عملیات - European Journal of Operational Research
دانشگاه: Centre interuniversitaire de recherche sur les réseaux d’entreprise - la logistique et le transport (CIRRELT) - Canada
کلمات کلیدی: مسیریابی، خواسته های تصادفی، سیاست مطلوب، Restocking، مسیرهای جزئی، الگوریتم L-shaped عدد صحیح، مجاورت پایین
doi یا شناسه دیجیتال: https://doi.org/10.1016/j.ejor.2018.07.039
برای سفارش ترجمه این مقاله با کیفیت عالی و در کوتاه ترین زمان ممکن توسط مترجمین مجرب سایت ایران عرضه؛ روی دکمه سبز رنگ کلیک نمایید.
چکیده

Abstract

This paper examines the Vehicle Routing Problem with Stochastic Demands (VRPSD), in which the actual demand of customers can only be realized upon arriving at the customer location. Under demand uncertainty, a planned route may fail at a specific customer when the observed demand exceeds the residual capacity. There are two ways to face such failure events, a vehicle can either execute a return trip to the depot at the failure location and refill the capacity and complete the split service, or in anticipation of potential failures perform a preventive return to the depot whenever the residual capacity falls below a threshold; overall, these return trips are called recourse actions. In the context of VRPSD, a recourse policy which schedules various recourse actions based on the visits planned beforehand on the route must be designed. An optimal recourse policy prescribes the cost-effective returns based on a set of optimal customer-specific thresholds. We propose an exact solution method to solve the multi-VRPSD under an optimal restocking policy. The Integer Lshaped algorithm is adapted to solve the VRPSD in a branch-and-cut framework. To enhance the efficiency of the presented algorithm, several lower bounding schemes are developed to approximate the expected recourse cost.

نتیجه گیری

 Conclusions

In this paper, we developed an exact solution methodology to solve the VRPSD under an optimal restocking policy. To do so, the Integer L-shaped algorithm was adapted. To enhance the efficiency of the Integer L-shaped algorithm, various lower bounding schemes were developed. The key element for successfully employing such bounding procedures is to provide effective lower approximation of the expected recourse cost of partial routes. In addition, a general lower bound enhancing the Integer L-shaped algorithm was also developed. Using the exact method proposed in this paper, we were able to optimally solve problems with up to 60 customers and a fleet of four vehicles. It should be noted that the proposed exact method is the first to solve the VRPSD under an optimal restocking policy when considering instances where customer demands follow arbitrary discrete distributions. The numerical results presented in this paper show that the resulting routes from the optimal restocking policy yield a appreciable amount of savings when compared to executing the classical policy on the same routes. Further research in this area could focus on the exploration of the potential of applying column generation and branch and price to the considered problem. It would also be interesting to investigate how more collaborative recourse policies (where several vehicles coordinate to react to high demand situations) could be applied to the VRPSD.