دانلود رایگان مقاله انگلیسی یک الگوریتم دقیق برای حل مسئله مسیریابی خودرو با خواسته های تصادفی - الزویر 2019

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.