Skip to main content
3 of 6
added 85 characters in body
MAYA
  • 129
  • 5

Capacited Vehicle Routing Problem with flow formulations

I'm trying to solve the CVRP based on flow-formulation. In such a model, we have a decision variable with two-index, $x_{ij}$, where I'm using the MTZ formula to eliminate sub-tours. We have then a continuous variable that represents the flow of the vehicle after visiting a customer. Let's say $y_i$. In the case of delivery, the constraints that I formulate is:

$y_j \le y_i - d_i + Q*(1-x_{ij})$
where $ 0\le y_i \le Q - d_i$

For this example with 5 customers : $\{1:19;2:30;3:16;4:23;5:11\}$ and $Q=35$
The solution I got is:

$x : \{(0,3);(3,1);(1,0);(0,2);(2,0);(0,4);(4,5);(5,0)\}$
For the other variables, $x$ is null.
$y: \{1:0;2:0;3:16;4:11;5:0\}$.
I expected 12 for $y_4 = 35 - 23 = 12$ and $y_5 = 12 - 11 = 1$ enter image description here But something is wrong that I can not identify.

MAYA
  • 129
  • 5