0
$\begingroup$

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

$\endgroup$
7
  • 3
    $\begingroup$ Wouldn't $\omega$ have indices $i,j$? $\endgroup$ Commented Jan 7 at 4:54
  • $\begingroup$ $w$ depends on $x1$ and $x2$. I can’t figure out why should it have indices i,j? $\endgroup$
    – MAYA
    Commented Jan 7 at 9:41
  • 1
    $\begingroup$ 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$ $\endgroup$ Commented Jan 7 at 12:41
  • $\begingroup$ 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). $\endgroup$
    – MAYA
    Commented Jan 7 at 19:02
  • 1
    $\begingroup$ 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 \}$ $\endgroup$ Commented Jan 7 at 19:32

1 Answer 1

1
$\begingroup$

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$

$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$
    – MAYA
    Commented Jan 8 at 9:45
  • $\begingroup$ @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. $\endgroup$ Commented Jan 8 at 16:52
  • $\begingroup$ 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. $\endgroup$
    – MAYA
    Commented Jan 8 at 20:16
  • 1
    $\begingroup$ You can try the constraint in the answer edited above. $\endgroup$ Commented Jan 8 at 22:32
  • 1
    $\begingroup$ @MAYA, that $k$ is your $1,2$ representing 2 types of fleet. You can use $x1, x2$ as well. $\endgroup$ Commented Jan 9 at 19:07

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.