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$$

But something is wrong that I can not identify.

mdl = Model('CVRP2')
arc_k = {(i, j) for i in nodes for j in nodes if i != j}
var = {(i) for i in customers}
mdl.modelSense = GRB.MINIMIZE
mdl.setObjective(grb.quicksum(time_truck[i][j] * xt[i, j] if i!=j else 0
for i in nodes for j in nodes))
#Constraint 1- Exactly the total number of vehicles leaves and return to
the depot
mdl.addConstr(grb.quicksum(xt[0, j] for j in customers) <= nT)
mdl.addConstr(grb.quicksum(xt[i, 0] for i in customers) <= nT)
# Constraint 2- Customer is only served once by only one vehicle
for j in customers:
mdl.addConstr(grb.quicksum(xt[i, j] for i in nodes if i != j) == 1)
# Constraint 3- Only one vehicle enters and leaves each customer
for j in customers:
mdl.addConstr(grb.quicksum(xt[i, j] if i != j else 0 for i in nodes) - grb.quicksum(xt[j, i] if i != j else 0 for i in nodes) == 0)
# Constraint 4: Subtour Elimination
for i in customers:
for j in customers:
if i != j:
(1- xt[i, j]))
#Constraint 5: Capacity Bounding Constraint
for i in customers:

• The question needs some clarification. You say you use MTZ to eliminate subtours, but your solution visits 0 (the depot?) repeatedly. So are subtours beginning and ending at 0 allowed? Second, is the vehicle picking up or dropping off at customers? One constraint suggests dropping off, but another suggests picking up. Finally, just to be clear, $y_i$ is the payload of the vehicle immediately after leaving $i$ (on its way to its next stop), as opposed to the payload on arrival at $i$?
– prubin
Commented Dec 29, 2023 at 16:28
• Basically, I'm trying to do the same model in this article for the case of delivery. The authors propose a model for collecting goods: hrcak.srce.hr/file/285563
– MAYA
Commented Dec 29, 2023 at 17:06
• if $x_{i,j}=1$ implies flow from node $i$ to $j$ then $y_i \lt y_j$ as per MTZ, so do your constraints enforce this? Commented Dec 29, 2023 at 17:21
• If $x_ij=1$ then $y_j <=y_i$
– MAYA
Commented Dec 29, 2023 at 18:05
• @MAYA you may need to modify with $y_j \le y_i -d_jx_{i,j} + Q(1-x_{i,j})$. That's what is given in the paper also. Otherwise either way $x=1/0$; $y_j \le y_i$ since $Q \gt d_j$ Commented Dec 29, 2023 at 20:17

Assuming that $$y_i$$ is the load in the vehicle when exiting customer $$i$$ (after dropping of $$d_i$$ units of goods there), then your first constraint has an incorrect middle term. It should be $$y_j \le y_i - d_j + Q(1 - x_{ij}).$$ This enforces the constraint $$x_{ij} = 1 \implies y_j <= y_i - d_j,$$ i.e., if the vehicle visits $$j$$ immediately after $$i$$ then the load when leaving $$j$$ is the load when leaving $$i$$ minus what is dropped off at $$j.$$

• Thank you for this explanation. I edited my post because it was not the correct formula. Using your formulas, which is the correct one, I got the solution presented in my post. The problem that why $y_4 = 11$. I except to have $y_4 = 12 (35 - 23)$ and then $y_5 = 12 - 11 = 1$ since the vehicle visits the customer 4 and then 5. Thank you
– MAYA
Commented Dec 29, 2023 at 20:02
• Your edited formula is still wrong. It has $d_i$ where it should have $d_j.$
– prubin
Commented Dec 29, 2023 at 22:39
• Absolutely right, I edited my post. May be I can share the model in python to find out what’s wrong
– MAYA
Commented Dec 30, 2023 at 8:56
• I have just added the model in Python using Gurobi. The plot of the solution is the output of this model. But I can not figure out what I miss in the formulas. The value of $y_4$ is incorrect. Thank you
– MAYA
Commented Dec 30, 2023 at 12:47
• You appear to be assuming that the vehicle always leaves the depot with load $Q$ (35 in your example), but the model does not require that. Consider the final route $(0 \rightarrow 4 \rightarrow 5 \rightarrow 0).$ Combined demand at 4 and 5 is 23 + 11 = 34, so the vehicle can leave the depot with 34 units, drop 23 units at customer 4 $(y_4 = 34-23 = 11),$, drop the remaining units at customer 5 $(y_5 = 11 - 11 = 0)$ and return empty. What is the problem with that?
– prubin
Commented Dec 30, 2023 at 17:20

Assuming your customers are $$N =\{1,2,...5 \}$$ while nodes $$N+\{0\}$$, subtour elimination constraint involves

$$(3,1)$$ and $$(4,5)$$
$$y_1 + 16 \le y_3 \le 19 = (35-16)$$ and
$$y_5 + 11 \le y_4 \le 12$$

$$y_4 \le y_5 + 12$$ since in your code you are still missing $$x_{i,j}d_{j}$$. you are using only $$d_j$$ which is still ok.

also all $$y_s$$ are bounded by $$\{1:14, 2:5,3:19,4:12,5:24 \}$$

Since the model sense is 'min' & thogh it applies to the objective value that doesn't include $$y$$ but since $$y_5 =[0,1]$$ solver chooses $$y_5 = 0$$ and that bounds $$11 \le y_4 \le 12$$, allowed min values for decision variables.

• Thank you for clarifying me. Now I understand why I got this solution
– MAYA
Commented Jan 2 at 10:23