3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Are you sure this is a model for delivery to customers and not a model for pickup from customers? $\endgroup$ Commented Jun 3, 2018 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$ Commented Jun 4, 2018 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$ Commented Jun 4, 2018 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$ Commented Jun 5, 2018 at 6:00

1 Answer 1

Reset to default
1
$\begingroup$

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$

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.