Stochastic Vehicle Routing Problems

Vehicle routing problems (VRPs) have been the subject of numerous research studies since Dantzig and Ramser [16] first presented this general class of optimization problems in a practical setting. Since then, the operations research community has devoted collectively a large effort towards efficiently solving these problems, developing both exact and heuristic methods; see Laporte [40]. The majority of these studies have been conducted under the assumption that all the information necessary to formulate the problems is known and readily available (i.e., one is in a deterministic setting). In practical applications, this assumption is usually not verified given the presence of uncertainty affecting the parameters of the problem. Uncertainty may come from different sources, both from expected variations and unexpected events. Such variations can affect various aspects of the problem under study (e.g., stochastic parameters, which entail additional feasibility requirements and extra costs). This is particularly true in the case of VRP models, which are used both at the tactical level and at the operational level to plan and control logistical operations. In this case, uncertainty is present given the time lag separating the moments where routes are planned and executed, considering the informational flow that defines the problem. For example, if customer demands are uncertain and only revealed when customers are visited, a planned route performed by a vehicle on a given day may turn out to be infeasible if the total observed demand for the customers scheduled on the route exceeds the capacity of the vehicle. When such a situation occurs, additional costs often involving additional decisions must be taken to produce a feasible solution. The need to account for such extra costs when solving VRPs entails developing models that explicitly factor in all relevant uncertainty features of the problem.