Problem with vehicle routing problem in Gurobi Python

Question

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!

Answer 1

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$