VRP Variants

VRP with Pickup and Delivery (VRPPD)

The Vehicle Routing Problem with Pickup and Delivery (VRPPD) is a VRP in which customers may also return some commodities. The goods that customers return to the delivery vehicle must fit into it, which makes the planning problem harder: ignoring this can lead to poor utilization of vehicle capacity, longer travel distances, or the need for more vehicles.

It is common to consider restricted situations in which all delivery demands start from the depot and all picked-up goods are brought back to the depot, so there are no exchanges of goods between customers. Another usual simplification is to require that every vehicle delivers all of its commodities before picking up any goods; that restricted case is the VRP with Backhauls.

Formal description

Objective: minimize the vehicle fleet and the sum of travel time, with the restriction that the vehicle must have enough capacity both for the commodities to be delivered and for those picked up at customers and returned to the depot.
Feasibility: a solution is feasible if the total quantity assigned to each route does not exceed the capacity of the vehicle serving the route, and the vehicle has enough free capacity to pick up the commodities at the customers.
Formulation: the cost of a route is computed as in the VRP, with the additional restriction that a route is feasible if and only if it is delivery-feasible, pickup-feasible and load-feasible. We define as the vector of the customers' pickup demands.
- Delivery-feasible: the total amount of commodities to be served on a route must not exceed the vehicle capacity. Given a route $R_i = (x0, …, x_{m+1})$ and its assigned vehicle with capacity C, this is expressed by $C_d(v_k) ≤ C$ and $C_d(v_{k+1}) > C$ , where $C_d(v_k)$ is the total quantity of goods delivered to all customers on the path of the route that begins at $v_0$ (the depot) and finishes at $v_k$ : $C_d(v_k) = sum of d_i over P(1, v_k)$ . Here $P(1, v_k)$ denotes the customers visited along the path from the depot up to and including $v_k$ .
- Pickup-feasible: the vehicle must have enough capacity to pick up the goods of all customers on the route: $C_p(v_k) ≤ C$ and $C_p(v_{k+1}) > C$ , where $C_p(v_k)$ is the total quantity of goods picked up from all customers along the path of the route up to and including node $v_k$ , that is, $C_p(v_k) = sum of p_i over P(1, v_k)$ .
- Load-feasible: the vehicle capacity may be violated at any node of the route, depending on the sequence of customers. Let $L(v_k)$ be the vehicle's load just after leaving customer $v_k$ , and assume the vehicle leaves the depot with an initial load $L(1) ≤ C$ . Then the vehicle's load at any point of the route is $L(v_k) = C_p(v_k) + L(1) − C_d(v_k)$ . If this load exceeds the capacity, the path is infeasible because the vehicle cannot serve the next customer $v_{k+1}$ . A route is load-feasible if $L(v_k) ≤ C$ and $L(v_{k+1}) > C$ .

See also: VRP with Backhauls · Capacitated VRP · VRPPD instances