# Vehicle Routing Problem with Two fleets

Based on the suggestion in the comment below. I edited my model by removing $$w$$. Here is the context: I'm dealing with the CVRP with two heterogeneous fleets with the following capacities $$q_1$$ and $$q_2$$. I'm using the model based on flow. I tried to sepearate constraints for each type of fleet but the result is a disconnected route. Thus, the following model consists in combining the constaints. When $$x_1(i,j)=0$$ then $$x_2(i,j)=1$$ and when $$x_1(i,j)=1$$ then $$x_2(i,j)=0$$. For the last constraint on capacity, I define $$CL$$ the set of customers where demand doesn't exceed $$q_2$$.

$$\min \sum_{i \in N, j \in N} {c_1(i,j)*x_1(i,j) + c_2(i,j)*x_2(i,j)}$$

$$\sum_{j \in C} x_1(0,j) <= n$$

$$\sum_{j \in C} x_2(0,j) <= m$$

$$\sum_{i \in C} x_1(i,0) <= n$$

$$\sum_{i \in C} x_2(i,0) <= m$$

$$\sum_{i \in N} x_1(i,j) + x_2(i,j) = 1 \quad \forall j \in C$$

$$\sum_{i \in N} x_1(i,j) - x_1(j,i) = 0 \quad \forall j \in C$$

$$\sum_{i \in N} x_2(i,j) - x_2(j,i) = 0 \quad \forall j \in C$$

$$y(j) + z(j) <= y(i) + z(i) -d_j*(x_1(i,j) + x_2(i,j)) + M*(1-(x_1(i,j) + x_2(i,j)) \quad \forall i \in C, j \in C$$

$$0 <= y(i) <= q_1 - d_i \quad \forall i \in C$$

$$0 <= z(i) <= q_2 - d_i \quad \forall i \in CL$$

I run the code on the following data ($$q_1=35$$ and $$q_2=15$$):

    lat  long  demand
0  30.0  40.0       0
1  37.0  52.0      19
2  49.0  49.0      30
3  52.0  64.0      16
4  31.0  62.0      23
5  52.0  33.0      11


The solution is wrong since the demand of the customer 4 is 23 >= q_2 = 15: $$x_1 = [(0, 2), (2, 5), (1, 3), (3, 0), (5, 0), (0, 1)] x_2 = [(4, 0), (0, 4)]$$

y[1] = 16.0
y[2] = 0.0
y[3] = 0.0
y[4] = 0.0
y[5] = 0.0
z[1] = 7.615501519756847
z[2] = 11.0
z[3] = 7.615501519756847
z[4] = 0.7720364741641355
z[5] = 0.0


I have doubt in the constraint 8 that assure the flow. When I seperate this type of constraint, I got disconnected routes. Someone can help me in this model? I'm not sure what is wrong in my model. Does anyone have any idea? Thank you

• Wouldn't $\omega$ have indices $i,j$? Commented Jan 7 at 4:54
• $w$ depends on $x1$ and $x2$. I can’t figure out why should it have indices i,j?
– MAYA
Commented Jan 7 at 9:41
• Otherwise $w$ will keep changing with $i,j$ pair. Also if you are restricting $x1+x2=1$ for pairs of edges you may not need $w$ as it seems to be $w=x1+x2$ Commented Jan 7 at 12:41
• Thank you for the explanation. In fact, I remove $w$ from the model described above (I edited my post). I run it the model but the solution that I get is wrong. I still miss something in my model. What should I do to respect the constraint of customers demand (I put the numerical details in my post above).
– MAYA
Commented Jan 7 at 19:02
• one more thing no need for separate counters like $y,z$. Only one type will do say $0 \le y_i \le \max \{ q1-d_i,q2-d_i \}$ Commented Jan 7 at 19:32

Also since depot $$0$$ is not part of $$C$$ so for arcs$$(0,4),(4,0)$$ constraint 8 isn't applicable.
Together with bounds on counters $$y$$ or $$z$$ the solver finds $$x_1$$ more feasible so long it meets constraints
If you want second type of vehicles to cover more routes try increasing the capacity $$q_2$$ or reducing demand at the customer nodes.

In case you'd want vehicle to serve a customer node only if $$q_2 \le d_i$$ then you can add a constraint
$$q^k (\sum_jx_{j,i}^k - 1) \le d_i - q^k \quad \forall k=1,2 \ \ \forall i \in C$$

Or for depot specific constraint since constraint (8) is taking care
$$q^k (x_{0,i}^k+x_{i,0}^k - 1) \le d_i -q^k \quad \forall k=1,2 \ \ \forall i \in C$$

• It makes sense to only keep one variable representing the flow after leaving the customer $i$. Let's assume $y$. Then, the constraint (8) become: $y_j<=y_i-d_j(x_1(i,j)+x_2(i,j)) - M*(1- (x_1(i,j)+x_2(i,j)))$ where $M = max{q1,q2}$ and $0<=y_i<=max{q1-d_i,q2-d_i}$. The solution that I get is: $x_1= [(4, 0), (3, 1), (5, 4), (0, 5), (1, 0), (0, 3)]$ and $x_2=[(0, 2), (2, 0)]$ I suppose that the customer $2$ must not served by the fleet 2 since $d_2=30 > q_2=15$. The problem that my model did not state this assumption.
– MAYA
Commented Jan 8 at 9:45
• @MAYA, look constraint 8 excludes $0$ as your set $C$ doesn't include $0$. right? As for the rest where there's a selected edge from other customers $(3,1)$ the solver finds $q_1$ more feasible. Commented Jan 8 at 16:52
• Yes, the constraint 8 includes customers since $y_i$ Is the load after visiting customer $i$. But for (0,2) is not correct to belong to the solution x_2. The latter concerns trucks with $q_2=15$ and demand for the customer 2 is 30.
– MAYA
Commented Jan 8 at 20:16
• You can try the constraint in the answer edited above. Commented Jan 8 at 22:32
• @MAYA, that $k$ is your $1,2$ representing 2 types of fleet. You can use $x1, x2$ as well. Commented Jan 9 at 19:07