The stochastic vehicle routing problem, a literature review, part I: models

Abstract

Building on the work of Gendreau et al. (Eur J Oper Res 88(1):3–12; 1996), we review the past 20 years of scientific literature on stochastic vehicle routing problems. The numerous variants of the problem that have been studied in the literature are described and categorized.

1 Introduction

Vehicle routing problems concern the challenge of selecting a set of routes for a fleet of vehicles to serve the demands of a set of customers. Almost invariably, the vehicles have limitations on the amount of goods they can carry, and the primary goal of the decision-maker (DM) is most often to minimize the total transportation cost. It thus makes sense to use the formulation of the (deterministic) capacitated vehicle routing problem (CVRP) as a point of departure for this review of the literature for stochastic variants.

The CVRP is defined over an undirected graph G(V, E), where $V = {v_0,\ldots , v_N }$ is a set of vertices and $E={(v_i, v_j): v_i, v_j \in V, i < j}$ is a set of edges. There is a symmetric matrix $C=[c_{ij}]$ that corresponds to the travel costs along edge $(v_i,v_j)$. Vertex $v_0$ represents the depot where there is a homogeneous fleet of m vehicles with capacity Q. A set of customers $V\setminus {v_0}$ with a non-negative known demand $d_i$ must be served. A solution to the CVRP consists of m delivery routes starting and ending at the depot. Each customer must be visited once by exactly one vehicle. The sum of the demands of the customers in the same route, must be less than or equal to the vehicle’s capacity. A different approach where the demand corresponds to items that must be collected from the customers leads to an equivalent problem. The classic objective is minimization of total route cost (see, e.g., Toth and Vigo 2002) but some formulations minimize total route length, total travel time or total cost.

In the real world one or more of the elements of the CVRP are uncertain. In order to model this, one typically allows some parameters in the general formulation to be represented as stochastic. When stochastic data are included in the problem, we have a stochastic (capacitated) vehicle routing problem (SVRP or SCVRP). Gendreau et al. (2014) provides a tutorial with a synthesis of some recent literature. A thorough review of the early literature on the SVRP, including a concise description of relevant solution concepts is found in Gendreau et al. (1996). We provide a brief recap of some details here before launching into a thorough review of papers since then.

Although demand, the presence of customers, travel times, and service times are sometimes modeled as stochastic (Gendreau et al. 1996; Tan et al. 2007), the most studied version of SVRP is the capacitated vehicle routing problem with stochastic demand (CVRPSD) (Cordeau et al. 2007). This is a feature of many real-life problems (see, e.g., Yang et al. 2000).

There is a striking difference between deterministic and stochastic VRP formulations: for all SVRP variants, the DM must decide the solution (at least partially) before the exact values of all parameters are completely known. In some situations, constraints may be violated when the actual parameter values are realized, e.g., the total realized demand of a planned route may actually exceed the vehicle’s capacity. One can say that the solution (or the route) “fails” when it is exercised with the realized data. In a deterministic problem the DM has complete information when making the plans, so there is no similar concept of a solution “failing”. There are two common ways of modeling stochastic problems: as a chance constrained program (CCP) or as a stochastic program with recourse (SPR).

In the case of CCP, the problem is solved ensuring that the probability of route failure is below a certain level and the cost of failures is typically ignored (Gendreau et al. 1996; Tan et al. 2007). Although chance constrained problems can be formulated with an expected value objective, in the SVRP literature, the objective is typically deterministic. Consider a very abstract formulation where the objective function is f(x) for a decision vector x and constraints are summarized by a set $\mathcal {X}$. We can then write a chance constrained program as:

$$\begin{aligned} \min _{x} \quad f(x) \text{ subject } \text{ to } \text{ Prob } (x \in \mathcal {X}) \ge 1-\alpha \end{aligned},$$

where the DM provides a parameter value $\alpha$ giving the acceptable probability of failing to meet the constraints. Of course, in less abstract formulations, the specific constraints that are subject to failure are specified.

On the other hand, in SPR, one allows route failures, but the DM must define a recourse policy, describing what actions to take in order to repair the solution after a failure. The expected transportation cost (travel cost + recourse policies cost) is optimized. SPR is more difficult to solve, but objectives are more meaningful (Gendreau et al. 1996).

The recourse policy is a modeling choice leading to different variants of an SVRP formulation. For the CVRPSD, three common recourse policies are (Tan et al. 2007; Secomandi and Margot 2009):

• The vehicle returns to depot to restock when capacity is attained or exceeded. Service resumes at the customer where route failure occurred. This is known as detour to depot (DTD).

• A preventive restocking can be done before a route failure occurs. Obviously, it may be less costly to travel to the depot to restock from the actual location than waiting for a route failure at a location further from the depot.

• After failure or after each customer is served and its demand becomes known, the portion of a route that has not been served is re-optimized. A decision is taken regarding which customer must be visited next, either as part of the regular routing or on the way to replenishment at the depot.

In other SVRP formulations the recourse policy does not involve routing decisions (as above), but a penalty for late/early arrivals or the extra time cost of the driver can be part of the expected cost when time windows and/or stochastic service time are taken into consideration (see, e.g., Li et al. 2010; Taş et al. 2013).

In the presence of stochastic data, any function of the data, such as a classic total cost objective function, will be a random variable, so some choice must be made to form a well-posed objective function. Most of the problems found in the SVRP literature can be cast as two-stage stochastic programming problems that minimize expected value. An abstract formulation (Birge and Louveaux 1997) is as follows:

$$\begin{aligned} \min _{x} \quad f(x) + E[Q(x,\varvec{\xi })] \text{ subject } \text{ to } x \in \mathcal {X} \end{aligned},$$

where $Q(x,\xi )$ is the optimal value of the second-stage problem

$$\begin{aligned} \min _{y} \quad q(y;x,\xi ) \text{ subject } \text{ to } y \in \mathcal {Y}(x,\xi ) \end{aligned}$$

Here x represents the first stage decisions that must be taken initially, before all information is available. In most formulations these are routing decisions. The function $f(\cdot )$ evaluates the objective function for the first stage portion of the decisions. The random variables that make the problem stochastic are represented by $\varvec{\xi }$. These may be pickup quantities or travel times, etc. In general, $\varvec{\xi }$ and its realizations $\xi$ are vector-valued. The second stage, or recourse, decisions are represented by y, which is evaluated using the function $q(\cdot )$ that can be parameterized by x and $\xi$. For some problems, this is simply a calculation of cost but in other cases a significant minimization is required. In most of the literature $\varvec{\xi }$ is discrete, so the expectation is computed using a sum.

In this abstract formulation, we have summarized constraints using the sets $\mathcal {X}$ and $\mathcal {Y}$. Most of the formulations in the literature are constructed so that there is relatively complete recourse (Kall and Wallace 1994), which in this formulation means that $\mathcal {Y}(x,\xi )$ is non-empty for every $x \in \mathcal {X}$ and every $\xi$ with non-zero probability.

A focus of two-stage formulations is the need to compute the first stage decisions, x, with the second stage decisions y used to compute, or estimate, an appropriate second stage expected cost. However, we note that a few papers in the literature seek methods for finding a good policy (dynamic programming approaches) or to provide an algorithm for routing vehicles dynamically (rollout algorithms) in addition to a good first stage decision.

One should note that SVRP papers usually come in one of two standard forms. On one hand there are researchers who are mainly interested in the modeling of SVRPs. They will need to formulate precise mathematical models describing what is understood by a solution x, and algebraic expressions for objective functions and constraints. On the other hand, we see researchers who are most interested in algorithmic issues. In an “algorithmic” paper, the model formulation is often not given algebraically. While input parameters are usually defined, there is often no mathematical formulations of either objectives or constraints, and a “solution” can be defined as “a set of routes” without further precision.

Evaluating the quality (i.e., the objective value) of a solution to an SVRP is not straightforward. Several approaches have been used to tackle this issue. In some cases a simulation is performed to generate a large number of possible realizations (scenarios), and then the solution is evaluated on each realization, getting an estimation of the quality (see, e.g., Juan et al. 2011). The quality of the solution is sometimes possible to calculate analytically, given certain characteristics of the problem (see, e.g., Laporte et al. 2010). A dynamic programming recursion can also be sometimes used for evaluating solutions (see, e.g., Yang et al. 2000).

This survey proceeds in Sect. 2 with an overview of problem types found in the SVRP literature. A summary of the literature is presented in Sect. 3. The paper closes with some conclusions and connections with related literature. Part II of the paper (Oyola et al. 2016) describes the literature concerning solution methods.

2 Types of problems

The stochasticity can be incorporated into the problem through different aspects and, typically, one or two elements are considered as stochastic. This limitation is likely due to the difficulty of solving a problem where many different parameters are stochastic. A summary of the different problems that have been studied is presented here.

2.1 The CVRP with stochastic demand—CVRPSD

In this version of the SVRP, the customer demands are stochastic and become known only after the routes have been established. The problem is usually modeled as a two-stage SPR.

A study of the basic CVRPSD is found in Laporte et al. (2002) where an SPR formulation is used with recourse action DTD. Two types of demand distributions are considered theoretically, Poisson and normal. Computational tests are done for both cases. The same problem is found in Jabali et al. (2014) where theoretically the demands are treated as independent and identically distributed (IID); however, tests are done using a normal distribution truncated at zero.

In the multi-compartment VRP with stochastic demands (Mendoza et al. 2010, 2011), each customer has a stochastic demand for different products, which follows a known probability distribution. Such products need to be transported in independent compartments in the vehicles. The recourse action is to travel to the depot once the capacity of any of the compartments in the vehicle is reached. Although the problem does not assume a particular probability distribution for the demand, computational tests were performed on instances with demands following a normal probability distribution.

A more recent paper by Goodson (2015) deals with a similar problem, where each route is subject to a route duration limit L. A method for computing the expected cost of the solutions is proposed; however, it works only with discrete distributions. Due to this restriction a different method was used in Mendoza et al. (2010, 2011), since results available for comparison were obtained assuming demands with normal distribution.

The stochastic CVRP with restocking (Yang et al. 2000; Marinakis et al. 2013) gives the option after each visit to choose between visiting the next customer in the route or traveling back to the depot to restock, even if the vehicle capacity has not been reached. This problem was formulated as an SPR in Yang et al. (2000) where the recourse action was to travel to the depot and restock, continuing with the planned route afterwards. The demand was assumed to be discrete, test instances were generated using a discrete triangular distribution. In Secomandi (2003) the single vehicle CVRPSD is studied in two versions, allowing restocking and with no restocking. In both cases the demand is assumed to be discrete, having instances with uniform discrete distribution.

A policy-based solution approach was taken in Marinakis et al. (2013). In this work, route failures are not permitted, assuming that these can be avoided by selecting a threshold value, such that when the residual load in a vehicle is less than or equal to the threshold, the vehicle should go to the depot for preventive restocking. This will only work under bounding conditions on the probability distributions. The only additional assumption regarding the probability distribution of the demands is that they are known and independent. For the computational tests, the demands follow discrete uniform probability distributions.

A different approach to handling the dynamics uses re-optimization; after visiting a customer the driver decides which customer to visit next, either directly or after replenishing at the depot. The decision is taken on basis of the available capacity and the expected demand of the unvisited customers. This problem was studied for the particular case of a single vehicle (Secomandi 2000, 2001; Secomandi and Margot 2009), where the probability distributions of the demands are discrete and independent (discrete uniform in one of the cases; Secomandi 2000). The problem was modeled as SPR, the recourse action is DTD. The computational tests are performed over instances with demands following discrete uniform probability distributions.

The single vehicle VRP with stochastic demands was also studied in Novoa and Storer (2009). A dynamic solution approach is used, where routing decisions are taken depending on the current state of the system, which is updated every time the vehicle arrives to a customer and demand is revealed. A simulation is used to evaluate solutions. The demands are assumed to follow a known discrete distribution, a discrete uniform was used in the tests. Split deliveries are accepted when a failure occurs. If the vehicle capacity is exceeded, the service may be finished in a not-immediate visit.

The single vehicle case of the CVRPSD has also been studied using a regular recourse action DTD, involving two different types of stockout (Hjorring and Holt 1999). A normal stockout, means the vehicle does not have enough goods to serve a customer. After restocking at the depot, the route is resumed starting with the customer where the failure occurred. An exact stockout means the vehicle has just enough goods to satisfy the demand of a particular customer. After restocking it will resume the trip at the next customer in the route. The proposed approach may apply for several probability distributions, but tests are performed using a discrete distribution. The same problem was studied following a different approach (Rei et al. 2010), where the demands are considered to have a known probability distribution. The testing was performed on instances with demands that follow normal probability distributions. Another version of the single vehicle case, where demands are a normal random variable truncated at zero, was also studied (Rei et al. 2007). In the latter case, if a failure occurs, then partial delivery is performed and the vehicle returns to the depot to restore capacity. In the cases where demands follow a continuous probability distribution, exact stockouts are not considered.

An interesting variant of the single vehicle CVRPSD allows preventive restocking (Bianchi et al. 2005). In this case, the vehicle can travel to the depot before the next customer in the route to restock, even if a route failure has not occurred. The demands are modeled as random variables with integer uniform distribution. Two ways of evaluating the objective function are considered, a dynamic programming recursion (Yang et al. 2000) and an approximation with the length of the a priori tour, without considering the stockout cost and the preventive restocking cost.

Another variant of the single vehicle CVRPSD was modeled considering that after a failure, no action is taken, and unserved customers will not be serviced (Chepuri and Homem-de Mello 2005). A penalty must be paid to the customer where the failure occurs and to the other unserved customers in the route, since the vehicle will not resume the route. The authors claim that this is the situation in several industries, where failures may result in lost revenue or emergency deliveries. They were motivated by a liquid air distributor. Demands are considered to follow a gamma distribution. The methods can exploit the special situation where the parameters of the probability distribution are the same for all customers.

The VRP with time windows and stochastic demands (VRPTWSD) was also studied in Chang (2005). Two categories of route failures are used, exact stockout and excess of available capacity. In both cases the vehicle returns to depot. Demands are assumed to follow a discrete uniform distribution. The problem is modeled as SPR. In the first stage late arrivals are not allowed, but waiting times are. The objective is to minimize the routing cost of first stage, waiting times at fist stage and the expected cost of recourse (DTD).

Another problem that has been studied is the combination of routing plus clustering (designing delivery districts) (Haugland et al. 2007). In this case the solution to the problem will have m contiguous districts, where all customers in the same district are assigned to the same route. The clustering process is in the first stage; i.e., it is done before the demands are realized. Tests were conducted using data where it was assumed that each customer will order a known minimum demand $d_i$ plus a stochastic amount which follows a binomial probability distribution. The decisions regarding the order in which the customers must be visited in each cluster are taken after the demands become known. However, during the construction of the districts, a restriction for the expected tour length within each district is imposed, otherwise the solution will be a single district. The problem is modeled as SPR. The recourse action is to plan the routing in each district with as many subtours as needed so as to ensure that the total demand on every subtour is less than or equal to the vehicle capacity and the routing cost is minimized.

The basic CVRPSD was extended to include time windows in Lei et al. (2011). The problem is modeled as an SPR, and two types of failure are considered, the vehicle capacity and the time windows. When there is a violation of the time window for a particular customer, it must be served by an additional single trip, which generates an extra cost. In addition, the vehicle must travel to the depot for restoring capacity whenever it is exceeded. No specific assumption regarding the demand distribution is made and the analysis of the expected cost of the solutions is done for both continuous and discrete cases. For computational testing, demands are generated following Poisson distributions.

Another extension of the CVRPSD can be found in Erera et al. (2010), where each tour duration must be feasible for all demand realizations. The problem, named the vehicle routing problem with stochastic demands and duration constraints (VRPSD-DC), it is modeled as an SPR. The non-splittable detour-to-depot recourse is used, i.e., if the demand of customer i is greater than the remaining capacity, the vehicle must travel first to the depot to restock capacity before serving customer i. The demands are assumed to follow a discrete uniform probability distribution. Two alternatives are consider to handle the exact stockouts, either to travel back to the depot and restock capacity or to identify the stockout just after arriving to the next customer. The objective function of the VRPSD-DC is to minimize the sum of the a priori total travel time, the expected additional travel time due to recourse actions and a penalty term for using more than m vehicles (in case they are required).

A new recourse strategy for the CVRPSD was proposed in Ak and Erera (2007) called the “pair locally coordinated” (PLC) operating scheme and it is presented as extension of the DTD. The demands are assumed to follow discrete, independent and identical probability distributions. The idea behind PLC is that some (not necessarily all) routes are matched together to create a route pair and routes are in at most one route pair. If a vehicle exceeds its capacity, its partner adds any unserved customer to the end of its route, which operates using the DTD scheme. One of the routes in the pair is labeled “type I route” and the other is “type II”. Routes not in pairs, are also type II. A failure will occur when visiting a customer, if adding its demand, the capacity of the vehicle would be exceeded. Demand cannot be split, so if the capacity is exceeded, the demand is collected after the recourse action: if a vehicle is serving a type I route, once a failure occurs, the vehicle returns to depot and the unserved customers are added to end of the planned route of the vehicle serving its type II route pair. If the vehicle serving a type II route experiences a failure, then it returns to the depot to unload, and then resumes the route in the first unserved customer of its route. Paired vehicles serving type II routes should wait at the final customer of their route, until the vehicle serving their paired type I route is traveling to the depot. The testing was performed on instances with demands that follow a discrete probability distribution that is the same for all customers.

The concept of PLC (Ak and Erera 2007) was also used in Zhu et al. (2014) as part of a paired cooperative reoptimization (PCR) for the CVRPSD. This strategy is proposed to be used for a pair of vehicles. The demand is assumed to follow a uniform discrete probability distribution. The problem is modeled as an SPR with DTD as recourse action, in addition partial reoptimization of routes is applied as described in Secomandi and Margot (2009). The two vehicles can communicate and dynamically modify their routes and the information about locations, residual capacities and unvisited customers is available to both vehicles. The model considers three assumptions: the service time is ignored, vehicles travel at the same speed and do not have idle time. Even though the strategy is proposed for a pair of vehicles, the authors briefly mention that the multi-vehicle case is solved by clustering the customers into groups and serving every group by a pair of vehicles.

The CVRPSD was formulated as a set partitioning problem and the associated column generation subproblem is solved using a dynamic programming scheme in Christiansen and Lysgaard (2007). In principle the demands can follow any probability distribution with accumulative property (the sum of two or more independent variables follows the same distribution). However, the tests were performed on instances with Poisson demands. The recourse action for the vehicle is to return to depot when a customer’s demand is greater than the residual capacity. If the vehicle becomes exactly depleted, it will not go to depot. It continues the route until a customer with positive demand is found, then it goes to the depot to restock.

The same problem was later studied in Goodson et al. (2012), where after generating a set of routes, a set partitioning problem is solved. In that way the best solution that can be constructed using a subset of the routes is found. The problem is also modeled as an SPR and uses DTD as recourse action.

Mendoza and Villegas (2013) worked with the same type of problem with an unlimited fleet of vehicles with capacity Q. The demand follows a known probability distribution, in the tests Poisson is used. The problem is formulated as an SPR and the recourse action is DTD.

The same problem and formulation as in Christiansen and Lysgaard (2007) was recently considered in Gauvin et al. (2014), where the CVRPSD was also formulated as an SPR. The recourse action is DTD, with the particular feature that in case of exact stockout, the vehicle returns to the customer where the failure occurred, after restoring capacity at the depot. The demand is assumed to follow a Poisson distribution.

A different approach that includes a limit on the duration of the routes in the CVRPSD was presented in Mendoza et al. (2015). The problem is modeled as a CCP and as an SPR. In the first case, the probability of the total duration of a route being greater than the maximum duration must be lower than a given threshold. In the second case, the violations to the maximum duration are included as a penalty in the objective function (expected cost of overtime). The objective is to minimize the total expected duration of routes.

The CVRPSD was studied using a different approach in Sungur et al. (2008), as the robust vehicle routing problem (RVRP). A solution that is feasible for all demands that belong to a bounded uncertainty set is said to be robust. Constraints that depend on the uncertainty set replace the connectivity and capacity constraints in the original model. The solution for the RVRP is a route that optimizes the objective function when all uncertain parameters are assumed to have the worst case value. The resulting problem is reported to be not significantly more difficult than solving the deterministic counterpart. It is assumed that the bounded uncertainty set captures all uncertainty of interest and the a priori route is feasible for every demand realization within the bounded uncertainty set, so no recourse actions or costs are considered.

Another robust approach can be found in Lee et al. (2012), where the robust CVRP with deadlines and travel time/demand uncertainty is studied. In this version of the problem, there is a deadline assigned to every customer i. This can be seen as a specific case of time windows, where the earliest starting time is equal to zero. The objective is to minimize the total distance, which is deterministic since there is no uncertainty associated with the distances. The stochastic parameters are the travel time (which may include the service time) and the demand. There is no recourse action in case of failure, since the robustness of a solution is evaluated as the percentage of scenarios (from a set) in which the solution is feasible. This has some similarity with a CCP. Scenarios are generated assuming that demands follow a normal distribution and travel times follow a distribution based on truncated normal. Such scenarios are used just to evaluate and compare the robustness of found solutions. During the search a uniform distribution is assumed.

A more recent version of the robust CVRPSD can be found in Gounaris et al. (2013). The probability distribution of the demands is unknown. However, it is assumed that all possible realizations of the demands are known (i.e., the support is known). Several deterministic formulations of the CVRP are reformulated into robust CVRP: two-index vehicle flow (Laporte et al. 1985), Miller–Tucker–Zemlin (MTZ) (Kulkarni and Bhave 1985), precedence formulation obtained from MTZ (Gounaris et al. 2013), commodity flow (Gouveia 1995) and vehicle assignment formulation (Golden et al. 1977). Two demand supports are considered, budget and factor support. In the budget support, the customers are partitioned in four geographic areas. Customers’ demands can deviate from their nominal values at most $\alpha \%$, but the cumulative demand in each area cannot exceed the nominal value by more than $\beta \%$. In the factor model support, the demand of a customer depends on the nominal value and an additive disturbance that depends on several independent factors. As in the budget support, the cumulative demand in each area cannot exceed the nominal value by more than $\beta \%$.

The CVRP with stochastic demands and time windows was recently studied in Zhang et al. (2016). For each customer i there is a time window $[e_i, l_i]$. If the vehicle arrives before $e_i$, it should wait until $e_i$. If the time when the demand is fully served (a recourse may be needed) is later than $l_i$, a penalty proportional to the lateness must be paid. Service times are not considered. Three different models are presented. The objective in the first model is to minimize the expected total cost (total distance of the a priori solution + expected cost of recourse action, DTD + expected penalty cost for late and early arrivals). In the second model the goal is to maximize the sum of on-time delivery probabilities to customers, penalties and recourse costs are ignored. In the third model, the objective function of model one is modified by including the fixed cost of using the vehicles multiplied by a large number (hierarchical objective). A constraint specifying a minimum probability of on-time arrival for each customer is included. This last model has characteristics from both CCP and SPR. A stockout is considered to occur when a customer is visited and the capacity of the vehicle has been exceeded or the remaining capacity becomes zero. A preventive restocking policy is compared to the DTD. The preventive restocking policy allows a vehicle to return to the depot before a stockout occurs. After servicing a customer, if the remaining capacity of the vehicle is less than a given threshold, the vehicle returns to the depot to restock, otherwise it travels to the next customer in the route. If a stockout occurs, DTD applies. This policy is evaluated in all the models. A simple illustrative example is presented. Authors stated that further studies are required to assess the performance of the models and the preventive restocking policy.

2.2 The capacitated arc routing problem with stochastic demand—CARPSD

The CARPSD was introduced by Fleury et al. (2002), the problem was presented as the stochastic capacitated arc routing problem (SCARP). The problem is defined on an undirected graph, where a set of edges (not necessarily all the edges in the graph) have a non-negative stochastic demand of items that must be collected and a set of vehicles with identical limited capacity is based at the depot. The problem is modeled as SPR, if total demand of a route is greater than the vehicle capacity, a trip to the depot has to be performed. The objective of SCARP is to find a solution for which the variations due to the random event realizations in the number of trips (and the cost) are minimum. The problem is not solved directly, instead a deterministic model is used to find solutions that are subjected to a sensitivity study by computing estimators of the average total cost and the standard deviation of the total cost. These computations are done by generating different scenarios. Demands of edges that require service are assumed to follow a truncated normal distribution, in a way that demands are greater than zero and less than or equal to the vehicle capacity. A similar problem and models are presented in Fleury et al. (2005b). The SCARP was also studied in Fleury et al. (2004), where a few additional assumptions are considered: the average demand of an edge is small, compared to the vehicle capacity. A trip cannot be interrupted more than once. In a robust solution, route failures are not common, if they occur it is more likely to happen just before the last edge to be served. Demands are also assumed to follow a truncated normal distribution.

The same problem was studied in Fleury et al. (2005a). Some theoretical analysis is done on the problem and five variants are considered: the minimization of the average cost, C, of the solution to the stochastic problem, minimization of C with bounds on the number of vehicles, minimizing C plus a fixed constant multiplied by the standard deviation of C, minimizing C under the condition that its standard deviation be less than a fixed value, and minimizing C under the conditions that the probability of having a route failure is less than a fixed value, for every route.

In the capacitated arc routing problem with stochastic demands (Laporte et al. 2010) there is a subset of edges with a non-negative demand of items that must be collected, a depot with a set of trucks and a vertex (dump site) that may or may not be different from the depot. The edge demands follow a known probability distribution, it can be either discrete or continuous and it is distributed uniformly along the edge. The edges can be traversed any number of times, but must be served just once. The recourse action is to travel to the dump site when the capacity of any vehicle is reached and resume its route at the point of failure. Just one failure is allowed per route. Test instances are generated using demands that follow Poisson distributions.

A similar problem was studied in Christiansen et al. (2009), but in this case the demands on the edges are assumed to have a Poisson probability distribution. This implies that if the edge is divided in a number of segments, the demand on each segment will also have a Poisson distribution. The computation of an approximate expected number of failures, consider a range of segments from one to a sufficiently large integer number. The routes start and end at the depot. A failure occurs when the actual accumulated demand exceeds the capacity of the vehicle. It is assumed that the total demand is revealed gradually along the edge and in case of failure the vehicle returns to depot using the end point of the edge that gives it a shorter distance to the depot. Several failures are allowed per route.

The mixed capacitated general routing problem MCGRP with probabilistic demands was proposed in Beraldi et al. (2015). In this problem, a homogenous fleet of vehicles has to satisfy the demand of customers which can be located in the vertices or along the edges or arcs. The problem is modeled as a chance constraint programming (CCP). For each route, the probability of not exceeding the vehicle capacity should be greater than or equal to a given parameter $\alpha$. The objective is to minimize the total traveling cost. For a subset of arcs, edges and vertices the demand may be known with certainty, for the others, the demand follows a multivariate normal distribution. The problem is named MCGRP with probabilistic constraints (MCGRPPC). A deterministic equivalent formulation of the problem is obtained by replacing each probabilistic constraint (one for each route) with an additional set of variables and constraints.

2.3 The CVRP with stochastic customers (and demand)—CVRPSCD

The customers’ presence has also been modeled as stochastic in several variants. The most interesting formulations are as SPR, where the routing is done for a given set of possible customers (stage 1), and then the presence is revealed, meaning that some customers in the original set have demand 0, and do not need a visit. The recourse action is to modify routes (stage 2). The demand at the present customers can be deterministic, but even more interesting are the formulations where demands are also stochastic, giving the CVRPSCD problem class. Pioneering work on such problems is discussed in Gendreau et al. (1996), where the CVRPSCD problem is described as “exceedingly difficult”.

A further extension of the problem based on a case study, was solved as a dynamic and stochastic problem in Hvattum et al. (2006). It is the case of a distribution company, where the customers can call at any time of the day, in addition there is a stochastic demand associated with the customers. Some of the calls are received before the vehicles are dispatched. The problem was modeled as an SPR, where the recourse action is using new vehicles and/or rearranging the customers already planned in a route. This problem does not have relatively complete recourse since feasibility in the first stage, does not imply feasibility in the second stage due to the customers’ time windows. The number of customers that appear at each time interval follows a Poisson probability distribution. Every demand already registered in the historical database is assigned an equal probability of reappearing as the demand associated with a new customer.

Another problem dealing with package delivery was presented in Zhong et al. (2007) where strategic and operational (daily) routes are created. Customer requests and locations are not known with certainty when designing the strategic routes. However, this information is revealed before vehicles are routed for every operational route. The learning curve (and forgetting curve) of the drivers regarding the different areas is taken into consideration and the time used to serve a set of customers varies from driver to driver. Due to this, the operational routes are designed so that day-to-day variations are minimized. Even though there are no constraints regarding the capacity, there is a time constraint: the vehicle must return to depot within the driver’s work shift. Customers are grouped into cells, which are each served by a single driver. Some cells are grouped into core areas that are assigned to the same driver every day. The rest of the cells are not assigned during strategic routing and can be served by any driver in the operational routes. The number of customers in each cell is assumed to follow a normal distribution. The problem of designing the strategic routes is modeled as CCP and the result of it is a nonlinear generalized assignment problem.

A vehicle routing problem with stochastic customers was studied in Sörensen and Sevaux (2009) as an example of a stochastic version of the CVRP. In this case customers need to book the service ahead, and cancellations on short notice are allowed. This problem is used to test the flexibility of solutions, measured as the possibility of being adapted/repaired after cancellations are realized and still having a high performance. An option to deal with this problem is to include all customers in the route, and remove the customers that do not require service, once this information becomes known. Customers need service with 0.5 probability. Customers not requiring service are not visited.

A different version of the CVRPSD with time windows was proposed in Erera et al. (2009). Each day the customers to be visited are a subset of all the customers because the demand quantity, which is uncertain, can be zero. Customers may have one or two time windows. Each day, customers are assigned to two routes: primary and backup. The recourse action is to move customers to a backup route. Customers are visited in the order that they appear in the route and those that do not require a service that day are skipped. The research was motivated by a collaboration with a beer, wine, and spirits distributor. Here are the key ideas of the approach: customers are divided into two sets, regular (with a high probability of placing an order for that day) and irregular, the former are included into the planned routes and the latter are added dynamically to operational routes. Regular customers are assigned to two routes, for each weekday: primary and backup. Customers can be moved to a backup route to regain feasibility or improve costs, this is done every day after demand realizations and the result is the operational routes. Each customer i places an order a given day with probability $p_i$. The discrete random variable, that represents the quantity that must be delivered to customer i, if an order is placed is $q_i$. The probability mass function of $q_i$ is known. For each customer the service must start within its time window(s).

2.4 Probabilistic multi-vehicle pickup and delivery problem—MPDP

This problem is described as a fleet of vehicles that must serve a set of customers’ requests (Beraldi et al. 2010), where each request specifies an origin and a destination and the origin must be visited before the destination. At the depot there may be a cargo transfer between vehicles, so a request can be served by two routes, one for pickup and one for delivery. A fixed number of routes is designed. There are no restrictions on the capacity and the vehicles perform two routes per day. In a solution to the deterministic problem, each vertex $V \setminus 0$ is part of a single route, the pickup visit is done before delivery optimizing a given performance indicator. A customer may or may not require a service. A Bernoulli random variable is associated with every customer i, it takes value one with probability $p_i$, if i requires a service, and zero with probability $1-p_i$ otherwise. The problem is modeled as a two-stage SPR. In the first stage, m routes are designed, with m equal to twice the number of vehicles, since they perform two routes per day, satisfying that each vertex is visited once and precedence constraints (delivery performed after pickup). In the second stage, after information about the requests is available, the customers are served in the same order as in the a priori route. Customers with no service requirement are skipped, which is considered to be the recourse action.

2.5 The CVRP with stochastic travel times (and service times)

Travel time has also been considered as the element that brings stochasticity to the CVRP. A version of the CVRP with soft time windows and stochastic travel times is found in Ando and Taniguchi (2006). In this model, a vehicle is allowed to make several routes per day and all goods from each customer must be loaded at the vehicle at the same time. The total weight of the goods in one route must not exceed the capacity of the vehicle. In addition, there is a hard time window for the depot. A triangular distribution is estimated for the travel time using real data. The objective of the problem is to minimize the total cost, which is given by the fixed cost of using vehicles, the operational costs and penalties for arriving outside time windows. The penalty for late/early arrivals can be seen as a recourse. The service time is assumed to be deterministic. Tests are performed for the single vehicle case.

A multi-objective approach to the CVRP with soft time windows and stochastic travel times (SCVRPSTW) is found in Russell and Urban (2008). In SCVRPSTW the demand is known in advance, and there is a deterministic service time and a time window associated with each customer. Servicing outside the time window is allowed at a cost, either for earliness or lateness. Three objectives are taken into consideration, the minimization of the number of vehicles, the total distance traveled and the total expected penalties for earliness and lateness in the service. Travel times are assumed to follow a shifted gamma, but the analysis and the tests are performed using a special case of gamma, the Erlang distribution. Due to the additive property of the gamma distribution, minimizing the total distance traveled is equivalent to minimize the expected travel time. The problem is modeled as an SPR, the recourse being the cost for servicing outside the time windows. The authors indicate that the problem could be modeled as a CCP; however, no tests were conducted for that case.

Another version of CVRP with stochastic travel times includes simultaneous pick-ups and deliveries (Zhang et al. 2012), where each customer can have both pick-ups and delivery demands. The vehicle has a maximum travel time B. The problem is modeled as CCP, so in a feasible solution the probability that the vehicle travel time be less than or equal to B must be greater than or equal to a given parameter. Testing is performed on instances with travel time following a normal distribution.

A variant of the problem including soft time windows was modeled as SPR (Taş et al. 2013) with an extra cost for servicing the customers outside the time windows. In addition, there is an overtime cost when the route time is longer than a certain value. The recourse cost is given by these penalties. In this formulation, the demand is deterministic and the travel time is assumed to follow a Gamma probability distribution. The objective is to minimize the sum of transportation costs and service costs. Transportation costs are the total distance, the fixed cost of using the vehicles and the total expected cost of overtime. Service costs are incurred for early or late arrivals at customers’ locations. The same problem can be found in a more recent paper by Taş et al. (2014b).

A CVRP with time windows and stochastic travel and service times is studied in Li et al. (2010). Here the problem is modeled using both a CCP and an SPR model. In the CCP approach two aspects are considered, the probability of arriving at each customer within the time windows and the probability of finishing a route within a certain given time. In the second approach, the expected value of some extra costs is computed: the penalty for arriving after the deadline of the time windows and the cost of the driver overtime. The travel times and service times are assumed to follow a normal probability distribution.

In Kenyon and Morton (2003) an uncapacitated VRP with stochastic travel and service time is described and two different problems are studied. The minimization of the completion time, which is the duration of the longest route, is one of the problems. The second problem is the maximization of the probability of completing the operation within a predefined target time. In the second stage, no route reoptimizations or recourse actions are allowed after the times are realized. The two models are analyzed theoretically, including the computation of bounds and how they are connected to the deterministic model that uses the expected value of the parameters. In the tests reported, the travel times are assumed to follow a discrete distribution as well as a uniform distribution. Tests with stochastic service times were not reported.

An interesting queueing approach is used by Woensel et al. (2007) to model routing problems with time-dependent travel time. The travel time is assumed to depend on traffic congestion. There is a limit for the maximum length of every route L and a deterministic service time. The expected travel time is calculated analytically together with the variance. The variance enables the evaluation of the risk involved. Time-dependent speeds are obtained using queueing models. Assuming that traffic conditions are stationary, there is a relationship between flow (number of vehicles), density (number of cars on a road segment) and speed. The time horizon is divided into a certain number of discrete periods and a different travel speed is associated with each period. Each segment of the route is considered as a service station where the vehicles arrive at one rate $\lambda$ and get served at a rate $\mu$. The objective function is to minimize total travel time, subject to capacity and length constraints. A modification of the objective function is also considered by adding the variance of the travel times, multiplied by a factor.

A VRP with stochastic time-dependent travel times was studied in Lecluyse et al. (2009). The objective is to minimize the sum of the expected travel times plus the weighted standard deviation of the travel times. Travel times are assumed to follow a lognormal distribution. The traffic conditions are assumed to be the result of two aspects: the congestion (congested and rush-hours) and the road and /or weather conditions (good and bad).

A stochastic vehicle routing problem with soft time windows under travel and service time uncertainties was studied in Zhang et al. (2013). The objective is to minimize the summation of the fixed cost of vehicles (multiplied by a large number), expected travel times, cost of early arrivals, cost of late arrivals and cost of excess route duration. This is a hierarchical optimization objective, where the number of vehicles is minimized with a higher priority. A minimum probability of on-time arrival (CCP) is assured. Each customer can have a different customer service-level constraint. There is a time window $[e_i, l_i]$ assigned to every customer. If the vehicle arrives before $e_i$ it must wait, if arrives late (later than $l_i$) a penalty proportional to the lateness must be paid. Travel and service times are random variables with probability distributions that are assumed to be known and independent. Tests were performed with travel times following a lognormal distribution and service times a normal probability distribution.

The CVRP with deadlines under travel time uncertainty was modeled by Adulyasak and Jaillet (2016) using two different approaches: as a robust problem and as a stochastic problem. In the stochastic approach the probability distribution of travel time is assumed to be known (Normal in the tests). The objective is to minimize the sum of probability of deadline violations. In the robust approach, on the other hand, the exact probability distribution is unknown but it is described by an interval and a mean. The objective is to optimize a performance measure, the lateness index, which takes the value of zero if the travel time meets the deadline. Both approaches are extended using fixed service times, random service time and by replacing the deadline with a soft time window.

A time-dependent VRP with soft time windows and stochastic travel times was introduced in Taş et al. (2014a). In this problem, the travel times (speed of vehicles) are assumed to be different at different times of the day. The objective is to minimize the transportation costs (distance traveled, number of vehicles and expected overtime) and the service costs (penalty for early and late servicing). The problem is modeled as SPR, a penalty for servicing outside the time windows and the overtime cost must be paid as recourse action. Two versions of the model are studied, with and without service times. In the model without service times, the exact values of the mean and the variance of the arrival times are calculated. In the model with service times, these parameters are approximated. The travel times are assumed to follow a gamma distribution.

A cash transportation vehicle routing and scheduling problem under stochastic travel times was presented in Yan et al. (2014). In this problem, the variations in vehicle routes and schedules, together with the stochastic travel times are taken into consideration, with the goal of securing vehicles safety and reducing stochastic disturbances. It is desired to have variations on the planned daily routes, so the vehicles would be more difficult to track for robbers. There are no capacity constraints and multiple trips during the planning period are allowed. Each customer (demand point) has a soft time window. The potential movements of the vehicles are formulated using the time–space network flow technique. The idea is to formulate changes in time and space for routes and schedules. Changes in time mean that arrival times will vary day by day. Changes in space mean that the sequence of customers will vary day by day. The objective is to minimize the operating costs with an unanticipated penalty cost, while considering variations in vehicle routes and schedules. Unanticipated penalties are related to early and late arrival costs. The problem is modeled as SPR, and the recourse action is the unanticipated penalty cost for violating the planned operation time windows. The vehicles are often robbed while being held at a demand point or during the route. To minimize the holding time at customers, a risk cost of robbery is used, it increases with the amount of money in the vehicle and the number of customers visited. The schedules are changed as a mechanism to reduce the risk of being robbed during the route. A similarity concept is introduced, where the potential current planned route is compared to previously planned routes. There is a maximum allowed similarity with the planned routes of previous days, it is smaller when the preceding day is closer. Similarities in both time and space are considered. The travel times are simplified as a discrete distribution from a continuous truncated normal. The travel time range is divided into periods, each of them becomes associated with a discrete travel time and a probability, which is estimated using a truncated normal distribution.

A VRP with time windows and stochastic travel times was studied in Ehmke et al. (2015). The service must start at each customer i within the time window $[e_i, l_i]$. If the vehicle arrives earlier than $e_i$, it will have to wait. The problem is modeled as CCP. The probability of the vehicle arriving at customer i, before $l_i$, must be greater than or equal to a given level $\alpha$. The travel times are assumed to be normal, but it is shown by simulation that the analysis will hold even if the distributions are not normal. The number of vehicles and the total duration of the routes are minimized.

The distance-constrained CVRP with stochastic travel and service times (DCVRPSTT), which was originally introduced by Laporte et al. (1992), is modeled using a different approach in a recent paper by Gómez et al. (2016). This new approach is interesting since no assumptions are made on the probability distribution. The stochastic travel and service times are modeled with Phase-type (PH) distributions (Neuts 1981), where a random time interval is modeled as being composed of a number of exponentially distributed segments. There exists a PH distribution arbitrarily close to any positive distribution. The objective function is to minimize the total expected duration, subject to a service-level condition, where every route must finish before a threshold T with a probability greater than $\beta$.

The CVRP with stochastic travel times was studied using a different approach in Solano-Charris et al. (2015), as a robust CVRP. The travel times are modeled by discrete scenarios, which are not associated with probability distributions. The objective of this problem is to minimize the worst cost (total cost of the routes) over all scenarios. A lexicographic approach is used to break ties.

The CVRP with hard time windows and stochastic travel and service time, was studied in Miranda and Conceição (2016). In this case, for every customer i, the service has to start within the range $[e_i, l_i]$. If the vehicle arrives earlier than $e_i$, it must wait. The problem is modeled with hierarchical optimization objectives; first the number of vehicles is minimized, later the operating costs (mean travel time). This is achieved by multiplying the number of vehicles by a large number in the objective function. The problem is modeled as CCP, and the probability of arriving earlier than $l_i$ for every customer i must be greater than $\alpha _i.$ The travel and service times are assumed to follow a normal distribution.

2.6 The VRP with stochastic service times

In some types of services, the variability of the travel time is considered small, compared to variability of the service time. Due to that, the travel time might be considered as a deterministic parameter and the stochasticity of the problem is given by the service time. In Lei et al. (2012) the number of vehicles and their capacity is considered unlimited and a stochastic service time is associated with each customer. There is an overtime cost if the route time exceeds a given value. The sum of travel costs, expected service and overtime costs are minimized. The service time is assumed to follow a continuous probability distribution. During the testing, service times in the instances are assumed to be normally distributed.

A VRP with hard time windows and stochastic service times (VRPTW-ST) was studied in Errico et al. (2016). The problem is modeled as SPR and the objective is to minimize the total expected cost (travel costs + cost of recourse actions). Customers that cannot be served within their time windows are skipped at a penalty cost. The recourse cost is a combination of a penalty cost and the variation in the travel cost. The probability of a route being feasible must be greater than a given threshold (CCP). It is assumed that a route requires just one recourse action. An evaluation time is introduced; after arriving at each customer i a constant time is used to evaluate the service time. Once this evaluation time has passed, the service time becomes known. Two versions of the recourse policy are considered, skip current and skip next. In the former, once it is found that the route becomes infeasible due to a time window violation in the next customer, the current customer is not serviced (evaluation time is counted). In the latter, given the same situation, the service is provided at the current customer, but the next in the route is skipped. In both cases a penalty is paid. It is assumed that the service times probability distributions are discrete with finite support (discrete triangular distribution in the tests).

2.7 The CARP with stochastic service times

The routing problem in daily road maintenance operations is formulated as a variation of the arc routing problem, where the travel and service times are considered stochastic in Chen et al. (2014). Each day some segments of the road network need to be monitored, which is an operation performed using a fleet of vehicles. Each monitoring service is associated with an estimated service time and each segment of the road is associated with a stochastic travel time. The objective is to determine a set of monitoring routes of minimum cost and the total service duration of each vehicle must not exceed a given threshold L. The problem is modeled using both CCP and SPR. In the CCP formulation, the objective is to minimize the total service cost, while the probability of the total service duration being greater than L must be kept below a given value for each route. The total service cost includes the total fixed cost of using the vehicles and the total deadheading cost (traveling over a segment of road without servicing it). Travel and service times are considered to follow a normal distribution.

In the SPR approach, the objective is to minimize the total service cost and the expected recourse cost. Weights can be assigned to prioritize any of the costs. Two recourse alternatives are considered: when a failure is expected to occur in a particular arc $a_{ij}$, different than the last one, once the service previous to the arc $a_{ij}$ is finished, the vehicle travels back to the depot and the rest of the services are rescheduled for the next day, at a cost. The other alternative is that the vehicle serves all the arcs that belong to the original route and are located in the shortest path between arc $a_{ij}$ and the depot. In this case the recourse cost includes not only the penalty for rescheduling some services for the next day, but also the excess duration of the work.

2.8 The VRPSTW with stochastic service times and probabilistic customers

The courier delivery problem (CDP) is presented in Sungur et al. (2010) as a variant of the VRPSTW. In the CDP the customers appear probabilistically and service times are stochastic. The objective is to create regular routes, which are later adapted to the demand realizations every day. Delivery requests arrive daily from potential customers. Location and time windows are known, but not the service time. There is a limited number of couriers and a hard time window at the depot. The first goal when solving the problem is to construct the master plan. The second goal is to modify the master plan to construct daily schedules, in a way that the number of customers served is maximized, route similarity (with respect to the master plan) is maintained, penalties for earliness and lateness are minimized, as well as the total time (travel, waiting and service time). The objective function is modeled as a weighted sum of all these goals. Similarity is measured as the number of customers in a daily route that are within a certain distance from any customer in the same master plan route. The recourse action is partial rescheduling. In computational tests, the service times are assumed to follow a lognormal probability distribution, and real-world data is used to introduce uncertainty.

2.9 The CVRP with stochastic demands and travel costs

A robust CVRP is defined by Sörensen and Sevaux (2009) as the problem of finding a solution with a high performance, across most possible outcomes. In such a framework, the CVRP with stochastic demands and travel cost is studied. Demands and travel costs are uniformly distributed. There is a maximum travel cost per route. Some penalties are associated with unsatisfied demand and travel times greater than the maximum. In this problem the regular objective function is replaced by an average cost computed on a set of stochastic parameter realizations. Another way to measure the robustness is to assess the highest cost evaluated on the same set.

2.10 Stochastic multi-objective approaches

The SVRP literature includes some work on problems where the decision-maker faces several optimization criteria, with formulations resembling a multi-objective structure.

A multi-objective CVRPSD was initially formulated with three objectives: to minimize travel time, driver remuneration and number of vehicles in Tan et al. (2007). The demands are assumed to follow a normal probability distribution. It was found that two of the objectives, travel time and number of vehicles, are not in conflict, i.e., it is possible to minimize them together. In the motivating case, the travel time is computed as the Euclidean distance. The problem is modeled as an SPR, with recourse action DTD. In addition, there is an extra cost if the route length exceeds a time limit B.

A multi-objective approach to the CVRP with soft time windows and stochastic travel times (SCVRPSTW) was presented in Russell and Urban (2008). Three objectives are optimized, the minimization of the number of vehicles, the total distance traveled and the total expected penalties for earliness and lateness in the service.

A CVRP with stochastic demands was formulated assuming a percentage of the vehicle’s capacity is reserved as a safety stock in the model of Juan et al. (2011). The routing (stage 1) is done assuming a capacity limit lower than the maximum for the vehicles. Slack capacity can be used to cope with excess in cumulative demands. Two criteria are optimized, one of them is the total expected cost and the other is the reliability, measured as the probability of the solution suffering a route failure. A set of solutions representing a tradeoff between these two criteria is given to the decision-maker. The demands are assumed to follow a known parametric or empirical probability distribution (discrete or continuous); however, the testing is performed on instances with demands that have a lognormal probability distribution. The problem is modeled as SPR: the recourse action is DTD, whenever there is a failure.

An extension of the CVRP was made to include location, allocation and routing decisions under the risk of disruption (Ahmadi-Javid and Seddighi 2013). In this approach a set of potential producer-distributors is considered. The capacities vary randomly due to disruptions. Due to this, the actual capacity of the producer-distributor is assumed to follow a discrete probability distribution (discrete uniform in the tests). The decision regarding which potential producer-distributors should be opened has to be made. There is a set of customers with known, non-negative demands, each of which is allocated to one producer-distributor. The customers are served by a set of vehicles which might suffer disruptions, so the number of times per year that a vehicle can visit the customers allocated to it follows a discrete probability distribution (Binomial in the tests). The problem is modeled as an SPR. In case of disruptions in the producer-distributor location, a risk mitigation strategy has to be used to satisfy the customers’ demand. In the case of vehicle disruptions, another vehicle is dispatched. In both cases the recourse action represents an extra cost. The decision-maker is presented with three different solutions, related to three different types of risk policies (moderate, cautious and pessimistic). For each risk policy, there is a different risk measurement, expected cost for moderate, conditional value-at-risk for cautious and worst case for pessimistic.

In some papers the problems may not be formulated as multi-objective, and no mention of it is done in the paper. Still, the approach can have similarities to multi-objective models, as a tradeoff solution set is obtained by changing parameters in the model. Examples of this can be found in Lecluyse et al. (2009) where a VRP with stochastic time-dependent travel times was presented, and in Zhang et al. (2013) about the stochastic VRP with soft time windows under travel and service time uncertainties.

3 Summary

3.1 Tables

Table 1 shows a list of all abbreviations and acronyms used in this section.

Table 1 Notation

In Table 2 there is a summary of surveyed papers dealing with the CVRPSD, where the demand is assumed to follow a continuous probability distribution.

Table 2 Summary of papers dealing with the CVRPSD with continuous demand distribution

In Table 3 there is a summary of surveyed papers dealing with the CVRPSD where the demand is assumed to follow a discrete probability distribution.

Table 3 Summary of papers dealing with the CVRPSD with discrete demand distribution

In Table 4 there is a summary of surveyed papers dealing with the CARPSD

Table 4 Summary of papers dealing with the CARPSD

In Table 5 there is a summary of surveyed papers dealing with the CVRP with stochastic customers and demands.

Table 5 Papers dealing with the CVRP with stochastic customers and demands

In Table 6 there is a summary of surveyed papers dealing with the CVRP with stochastic travel time (and service time).

Table 6 Summary of papers dealing with the CVRP with stochastic travel time (and service time)

In Table 7 there is a summary of surveyed papers dealing with the VRP with a multi-objective approach.

Table 7 Summary of papers dealing with a multi-objective approach

3.2 Most common types of problems

The most studied SVRP continues to be the CVRPSD. Table 8 shows the attention that different models have received in the literature. It is measured as the percentage of papers where the corresponding problem/model appears (values are rounded to the closest integer). Values do not add up to 100% since one paper may describe more than one problem. Some models that could be relevant for dealing with real-world problems, have received little attention, as the VRP with stochastic travel and service times, or the VRP with stochastic service times.

Table 8 Models found in the literature

3.3 Evaluation of the solutions

The quality of the solutions are evaluated using either a closed form that computes the expected value of an objective function, simulation or by an algebraic approximation of the closed form expected values. In most of the cases (67%) the evaluation is done by expressing such objective functions in closed form. This represents an advantage since for any possible solution, the expected value can be computed. However, the assumptions made on the probability distribution of the stochastic parameters represents a limitation on the model and its application in real-life problems. We noticed that the algebraic approximation has been used just recently, but it can be expected that it will become more popular. Such approximation may be seen as a tradeoff between the accuracy but complexity of the closed form and the simplicity of the simulation.

3.4 Common recourse actions

In the problems modeled as SPR a recourse action is required. The most common in the literature is the detour-to-depot (DTD). Such recourse action is the most common in problems with stochastic demand. Its widespread use may stem from the fact that it is very simple to understand and model. However, the applicability of the models in real-life problems may benefit from using more complex and efficient recourse actions. Table 9 shows the percentage of models where a recourse actions is used, here it is limited to the most common. It may happen that a single model includes more than one recourse action, so the values do not add up to 100%. The values in the table are rounded to the nearest integer.

Table 9 Types of recourse actions

4 Conclusions

In order to survey the past 20 years of research on stochastic VRPs, we found it necessary to limit the scope of the survey to what we consider “core” stochastic VRP papers. Needless to say, there is a vast literature on optimization problems relating to VRPs, which is beyond the scope of this survey. Related problem types include Traveling Salesman Problems (TSP), Inventory Routing Problems (IRP), and Fleet Size and Mix VRP (FSMVRP). In all of these classes there are several papers on stochastic variants of the problems. We refer the reader to general surveys by Coelho et al. (2014) and Andersson et al. (2010) on IRP, Hoff et al. (2010) on FSMVRP, Pillac et al. (2013) on dynamic VRP.

An important feature in the stochastic CVRP is the source of stochasticity. This may be the demand, the travel time, the presence of customers and the service time, among others. The CVRPSD (capacitated vehicle routing problem with stochastic demand) has been by far the most studied version of the problem.

Another important distinguishing feature of stochastic vehicle routing problems is the recourse policy, which describes the actions to take in order to repair the solution after a failure. Three popular actions are as follows:

• The vehicle returns to depot to restock when capacity is attained or exceeded. Service resumes at the customer where route failure occurred.

• A preventive restocking can be done before a route failure occurs.

• Re-optimizing the portion of a route that has not been served after failure or after each customer is served and its demand becomes known.

In other SVRP formulations the recourse policy does not involve routing decisions (as in the DTD case), but a penalty for late/early arrivals or the extra time cost of the driver, can be part of the expected cost when time windows and/or stochastic service time are taken into consideration. Preventative restocking and partial re-optimization seem to be more realistic, but require more sophistication. With improving solver technology and ongoing research, we see the field moving more in this direction.

Looking to the future we expect to see increasing interest in multi-stage SVRP, where there are multiple recourse actions. We also foresee more interest in multiple-objectives as well as so-called robust optimization, which guards against a worst-case or bad-case. Of course, it is difficult to predict the future with certainty, hence the need for stochastic programming.