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.

  • $\begingroup$ Are you sure this is a model for delivery to customers and not a model for pickup from customers? $\endgroup$
    – prubin
    Jun 3 '18 at 17:54
  • $\begingroup$ @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. $\endgroup$
    – ijuneja
    Jun 4 '18 at 4:30
  • $\begingroup$ 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$? $\endgroup$
    – prubin
    Jun 4 '18 at 23:08
  • $\begingroup$ @prubin I'll get back to you on this. I have been following (somewhat blindly) the notation of the book by Toth and Vigo. $\endgroup$
    – ijuneja
    Jun 5 '18 at 6:00

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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.