1
$\begingroup$

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.

mdl = Model('CVRP2')
arc_k = {(i, j) for i in nodes for j in nodes if i != j}
var = {(i) for i in customers}
xt = mdl.addVars(arc_k, vtype=GRB.BINARY, name='xt')
y =  mdl.addVars(var, vtype=GRB.CONTINUOUS, name='y')
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:
            mdl.addConstr(y[j]<=y[i]-df.demand[j] + (truck_capacity) * 
           (1- xt[i, j]))
#Constraint 5: Capacity Bounding Constraint
for i in customers:
    mdl.addConstr(y[i] >=0)
    mdl.addConstr(y[i] <= truck_capacity - df.demand[i])
Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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$? $\endgroup$
    – prubin ♦
    Commented Dec 29, 2023 at 16:28
  • $\begingroup$ 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 $\endgroup$
    – MAYA
    Commented Dec 29, 2023 at 17:06
  • $\begingroup$ 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? $\endgroup$
    – Sutanu Majumdar
    Commented Dec 29, 2023 at 17:21
  • $\begingroup$ If $x_ij=1$ then $y_j <=y_i$ $\endgroup$
    – MAYA
    Commented Dec 29, 2023 at 18:05
  • $\begingroup$ @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$ $\endgroup$
    – Sutanu Majumdar
    Commented Dec 29, 2023 at 20:17

2 Answers 2

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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 $\endgroup$
    – MAYA
    Commented Dec 29, 2023 at 20:02
  • $\begingroup$ Your edited formula is still wrong. It has $d_i$ where it should have $d_j.$ $\endgroup$
    – prubin ♦
    Commented Dec 29, 2023 at 22:39
  • $\begingroup$ Absolutely right, I edited my post. May be I can share the model in python to find out what’s wrong $\endgroup$
    – MAYA
    Commented Dec 30, 2023 at 8:56
  • $\begingroup$ 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 $\endgroup$
    – MAYA
    Commented Dec 30, 2023 at 12:47
  • 1
    $\begingroup$ 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? $\endgroup$
    – prubin ♦
    Commented Dec 30, 2023 at 17:20
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for clarifying me. Now I understand why I got this solution $\endgroup$
    – MAYA
    Commented Jan 2 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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