VRP Variants

Stochastic VRP (SVRP)

A Stochastic VRP (SVRP) is a VRP in which one or several components of the problem are random. Three classical kinds of SVRP are:

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: the service times $δ_i$ and travel times $t_ij$ are random variables.

In the SVRP, solutions are built in two stages. A first-stage solution is determined before the realizations of the random variables are known. In a second stage, a recourse or corrective action can be taken once the values of the random variables are observed.

Formal description

Objective: minimize the vehicle fleet and the sum of the travel time needed to supply all customers, where the customers to be served, their demands and/or the service and travel times take random values on each realization.
Feasibility: when some data are random, it is no longer possible to require that all constraints be satisfied for every realization of the random variables. The decision maker may instead require that some constraints hold with a given probability (chance constraints), or incorporate into the model 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$ can be equal to 2 when a vehicle makes a return trip between the depot and $v_j$ .
- is the expected second-stage recourse function. It is problem-dependent and also related to the particular choice of 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, then resume collections as planned;
  - return to the depot when the vehicle is full, as above, but re-optimize the remaining part of the planned route;
  - plan a preventive return to the depot even if the vehicle is not full — a decision that can depend on the amount already collected and on the distance separating the vehicle from the depot.
  A vehicle that is not yet full may therefore return to the depot when it is known that going to the next customer would exceed its capacity.

See also: VRP formulation · Capacitated VRP · VRP with Time Windows