Stochastic VRP

CVRP

MDVRP

PVRP

SDVRP

SVRP

VRPB

VRPPD

VRPTW

Stochastic VRP (SVRP)

Stochastic VRP (SVRP) are VRPs where one or several components of the problem are random. Three different kinds of SVRP are the next examples:

Stochastic customers: Each customer $v_i$ is present with probability $p_i$ and absent with probability $1-p_i$ .

Stochastic demands: The demand $d_i$ of each customer is a random variable.

Stochastic times: Service times $\delta _i$ and travel times $t_{ij}$ are random variables.

In SVRP, two stages are made for getting a solution. A first solution is determined before knowing the realizations of the random variables. In a second stage, a recourse or corrective action can be taken when the values of the random variables are known.

Objective: The objective is to minimize the vehicle fleet and the sum of travel time needed to supply all customers with random values on each execution for the customers to be served, their demands and/or the service and travel times.

Feasibility: When some data are random, it is no longer possible to require that all constraints be satisfied for all realizations of the random variables. So the decision maker may either require the satisfaction of some constraints with a given probability, or the incorporation into the model of corrective actions to be taken when a constraint is violated.

Formulation: Minimize , where
- $x_{ij}$ is an integer variable equal to the number of times edge $(v_i, v_j)$ appears in the first stage solution. If $i, j > 1$ , then $x_{ij}$ can only take the values 0 or 1, if $i=1$ , $x_ij$ be equal to 2 if a vehicle makes a return trip between the depot and $v_j$ .
- $Q(x)$ is the expected second stage recourse function. It is problem dependent and is also related to the particular choice of possible recourse actions. For example, in the capacity constrained SVRP with collections, possible recourse actions are:
  - Return to the depot when the vehicle is full in order to unload, and then resume collections as planned.
  - Return to the depot when the vehicle is full as in the previous case and reoptimize the remaining part of the planned route.
  - Planning a preventive return to the depot even if the vehicle is not full. In such case, this decision could depend on the amount already collected and on the distance separating the vehicle from the depot.
  A vehicle not yet full may return to the depot if it is known that going to the next customer would cause its capacity to be exceeded.