Skip to main content
5 of 6
added 6 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_j*x_{ij}+ 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