۱- Introduction

۲- Optimal restocking recourse policy under the a priori approach

۳- An integer L-shaped algorithm to solve the VRPSD under an optimal restocking policy

۴- Numerical Results

۵- Conclusions

References

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 L-shaped 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.

Introduction

Following the seminal paper of Dantzig & Ramser (1959), the Vehicle Routing Problem (VRP) has been the subject of considerable research efforts over the last decades, see Laporte (2009). The aim in VRP is to find a set of routes serving a given set of customers at a minimal cost (the least travel cost, minimum number of vehicles, etc.). The routes should start and end at the depot, and are designed to be performed by a fleet of vehicles with homogeneous capacity. In the deterministic version of VRP in which all problem parameters are known precisely, each customer is only visited once by one vehicle. In real-life problems, however, various parameters of the VRP can be uncertain. Uncertainty is more likely to appear in demands, travel and service times, and customer presence. It is usually dealt with by using probability distributions to describe the uncertain parameters, which are then stochastic. The VRPs in which some parameters are stochastic are called Stochastic VRPs (SVRPs). Although SVRPs have received much less attention in comparison to the deterministic VRP, several efforts have been devoted to investigate various versions of the SVRP; for a thorough exposition of the SVRP context, we refer the reader to Gendreau et al. (2014), Oyola et al. (2016), and Oyola et al. (2017). One way to deal with stochastic parameters in stochastic routing models is to use their deterministic approximated counterparts, in which the stochastic parameters are roughly replaced by their forecasted equivalents. Such models can sometimes lead to arbitrarily bad quality solutions at execution time when stochasticity reveals itself, see Louveaux (1998). Thus, there is a need to model SVRPs using specialized optimization frameworks in which stochastic parameters are explicitly modeled through random variables.