2
$\begingroup$

I have a vehicle routing problem solved by linear programming, but I'm confused about the constraints (see the model in figure 1). In the model, $u$ and $x$ are decision variables, and we set node $0$ as the depot, nodes $1$ to $n$ as customers. Constraints 1 & 2 indicate that there can only be one edge for both going into and out of the CUSTOMER nodes. However, when I use Gurobi optimizer to solve it, I find the solution always includes the depot (node $0$. See a solution in figure 2). Even I set the depot to an extremely far location (figure 3), the depot is still in the solution. Theoretically, to minimize the objective function, if there are no constraints about the edges into and out of the depot, then $x_{0i}$ and $x_{i0}$ should always be 0. The constraints about the depot can be like $\sum x_{i0} \ge 1$, but there are no such constraints in the model.

This is the code used for adding constraints:

mdl.addConstrs(   # mdl is the name of the model
    quicksum(x[i, j] for j in V if j != i) == 1 for i in N)  # only one edge into customer node i
mdl.addConstrs(
    quicksum(x[i, j] for i in V if i != j) == 1 for j in N)  # only one edge out of customer node i
mdl.addConstrs((x[i, j] == 1) >> (u[i] + q[i] == u[j]) for i, j in A if i != 0 and j != 0)
mdl.addConstrs(u[i] >= q[i] for i in N)
mdl.addConstrs(u[i] <= Q for i in N)

Now I'm confident that my code is not problematic (if anyone want to check it I've put it on my Github: https://github.com/KaiyuWei/VRP-problem-by-Gurobi--Python), then could anyone explain the reason why the depot is always included? Thanks!

enter image description here enter image description here enter image description here

$\endgroup$
11
  • $\begingroup$ Your first two constraints are over the set $V$, which is all of your nodes including the depot. $\endgroup$
    – EhsanK
    Jul 15 at 13:18
  • $\begingroup$ @EhsanK are you sure ? "mdl.addConstrs(quicksum(x[i, j] for j in V if j != i) == 1 for i in N)" $\endgroup$
    – Kuifje
    Jul 15 at 13:21
  • $\begingroup$ @kaiyu wei could you try running the code without the capacity constraints ? Maybe it needs to initialize the $u_i$ variable at the depot to $0$. $\endgroup$
    – Kuifje
    Jul 15 at 13:23
  • $\begingroup$ @EhsanK "for i in N ", not include the depot $\endgroup$
    – kaiyu wei
    Jul 15 at 13:26
  • 1
    $\begingroup$ @kaiyuwei you have those flow balance constraints and you also have the subtour elimination one. Try it on a piece of paper with only 3 nodes of 0, 1, 2. Assuming all q !=0, Is it possible for you to have, e.g., u1 + q1 = u2 AND u2+q2=u1 (that is to say x[1,2] and x[2,1] both are 1) ? If not, then even though you excluded node 0 in the subtour, you still have them in the flow balance and since a constraint of the form above that I wrote is not possible, then the model chooses to assign a 1 to a variable that enters/leaves the depot. $\endgroup$
    – EhsanK
    Jul 15 at 14:06
5
$\begingroup$

Constraints 1 and 2 ensure that there is an edge going in and out of every node. Constraint 3 works as a subtour elimination and along with the above constraints ensures that there is no subtour and as a result, you must enter and leave the depot.

A simple illustration is to assume there are only 3 nodes. So: $ V = \{0, 1, 2\}$ and $ N = \{1,2\}$. Let's spell out the constraints as coded:

\begin{align} x_{10}+x_{12}&= 1 \tag1\\ x_{20}+x_{21}&= 1 \tag2\\ x_{01}+x_{21}&= 1 \tag3\\ x_{02}+x_{12}&= 1 \tag4\\ \mbox{if } x_{12} = 1 \rightarrow u_1+q_1 &= u_2 \tag5\\ \mbox{if } x_{21} = 1 \rightarrow u_2+q_2 &= u_1 \tag6\\ q_1 \le u_1 &\le Q \tag7\\ q_2 \le u_2 &\le Q \tag8\\ \end{align}

Note that only the first two sets of constraints (equations 1 to 4 above) have anything to do with the depot. If you're wondering why the edges of node $0$ are selected in the solution, let's consider the case that they are not and see if that's possible with the constraints above.

In case you don't want to see an edge from/to depot, that means you want $x_{10}, x_{20}, x_{01}, x_{02}$ to be zero. If you substitute this in the constraints above, you'll have $x_{12}=x_{21}=1$.

However, you cannot have $x_{12} = x_{21} = 1$, because constraints 5 and 6 above cannot both be true at the same time, unless $q_1 = q_2 = 0$.

Now, from here work backwards for yourself. For example, let $x_{12} = 1$:

$x_{12} = 1 \rightarrow \mbox{(equations 1 and 4) } x_{10}=x_{02}=0$

$\mbox{if } x_{12} = 1 \rightarrow \mbox{(equations 5 and 6) } x_{21}=0 \rightarrow \mbox{(equations 2 and 3) } x_{20}=x_{01}=1$

$\endgroup$
1
  • $\begingroup$ Thank you, that makes sense to me. $\endgroup$
    – kaiyu wei
    Jul 16 at 8:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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