VRP Variants

VRP with Backhauls (VRPB)

The Vehicle Routing Problem with Backhauls (VRPB) is a VRP in which customers can demand or return some commodities. The critical assumption is that on each route all deliveries must be made before any pickups. This arises from the fact that vehicles are rear-loaded, and rearranging the load on the truck at delivery points is not deemed economical or feasible. The quantities to be delivered and picked up are fixed and known in advance.

The VRPB is similar to the VRPPD, with the additional restriction that all deliveries on each route must be completed before any pickups are made.

Formal description

Objective: find a set of routes that minimizes the total distance traveled.
Feasibility: a feasible solution consists of a set of routes where all deliveries on each route are completed before any pickups, and the vehicle capacity is violated by neither the linehaul (delivery) nor the backhaul (pickup) customers assigned to the route.
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 delivered 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 constraint 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 $v_k$ , including $v_k$ itself.
- 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 must never be exceeded at any node of the route; such a violation depends 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 the load given by this equation exceeds the capacity, the path becomes infeasible because the vehicle cannot perform the service at the next customer $v_{k+1}$ on the path. A route is therefore load-feasible if $L(v_k) ≤ C$ and $L(v_{k+1}) > C$ .

The figure below shows a schematic example of a VRP with backhauls, with linehaul (delivery) and backhaul (pickup) customers served on the same routes.

Schematic graph of a VRP with backhauls: routes serving delivery customers followed by pickup customers — Figure 1: Schematic example of a VRP with Backhauls.