# Constraints in Vehicle Routing Problem Programming Formulation

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.

• Are you sure this is a model for delivery to customers and not a model for pickup from customers? – prubin Jun 3 '18 at 17:54
• @prubin Yes, I am positive. It is supposed to be a formulation for the simplest case of a vehicle routing problem. I have made some notes from the text linked in the ans, they may help fill up inconsistencies in notation if any. Notes. – ijuneja Jun 4 '18 at 4:30
• If this is a delivery model, with $d_i$ the demand at customer $i$ and $u_i$ the load after $i$, then why does (2) say that $u_i \ge d_i$? – prubin Jun 4 '18 at 23:08
• @prubin I'll get back to you on this. I have been following (somewhat blindly) the notation of the book by Toth and Vigo. – ijuneja Jun 5 '18 at 6:00

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$