Problem Background
I wished to understand an IP model for the Capacitated Vehicle Routeing problem described below.
There are vehicles (of limited capacity) driving around delivering goods to customers (Graph vertices) to satisfy demand.
Assumptions: Vehicles are identical, there is a single central depot (node 0), the maximum capacity of each vehicle is C.
The objective is to minimize cost.
G = (V,A) is a complete Graph (Edge between every pair of distinct vertices)
V = {0, ...., n} is the set of vertices, 0 is the 'home' node. A is the set of edges.
A cost $ c_{ij} \geq 0$ is associated with every edge $ (i, j) \in A, c_{ii} = M \quad \forall i \in V$.
Each customer i (i = 1,...,n) is associated with a demand $ d_i \geq 0 $, $ d_0 = 0 $
The number of identical vehicles is $ K \geq K_{min} $
We assume $ d_i \leq C \quad \forall i \in V $.
$ u_i, i\neq 0$ is a continuous variable = the load of a vehicle after visiting node i.
Variable $ x_{ij} = 1$ if the edge (i, j) $ \in A $, belongs to the optimal solution and = 0 otherwise.
Two of the programming constraints in the so called 'Vehicle Flow Formulation' were
$$u_i - u_j + Cx_{ij} \leq C - d_j \quad \forall i,j \in V \backslash \{0\}, i \neq j,\text{ such that } d_i + d_j \leq C \tag{1} $$
$$d_i \leq u_i \leq C \quad \forall i \in V \backslash \{0\} \tag{2}$$
The text 'The Vehcile Routing Problem' by Toth and Vigo points out that (2) implies (1) when $x_{ij} = 0$ however when $x_{ij} = 1$ the condiditon imposed is
$$ u_j \geq u_i + d_j \tag{3}$$
I am unable to understand the origin of (3), especially since it seems fundamentally wrong that $u_j$ (The load after demand of j was met) should be related to $d_j$ in such a way.
Try to imagine the problem as a pick-up problem... Imagine you have a recycling factory (depot) and clients want to send you their recycling garbage, but you have to go search for it on their addresses...
Then a vehicle leaves the depot with full capacity, passes through the first client $i$, pick-up its demand $d_i$ and goes on to the next client $j$... Thus the load after the second client ($u_j$) must be greater or equal than the load after the first client plus the demand of the second ($u_i + d_j$):
$u_j \geq u_i + d_j$