How to remove or replace sub tour elimination constraints in the VRP variant models?

Question

In many of vehicle routing problems variant (VRP), which can be formulated using MIPs, to avoid creating sub tour, we need to use sub tour elimination constraints (SEC). One of the known SEC is (I also know there are other types):

\begin{equation} u_{k}-u_{l}+|H| z_{k l} \leq|H|-1, \quad \forall k, l \in H, l \neq 1, l \neq k \end{equation}

What is interesting is that, in some of MIP models, these constraints are removed and replaced by other constraints.

I would like to know, is there any principle to replace such constraints with other inequalities and also any guarantee to do better performance using them?

Answer 1

The inequalities you have included in your post are the so-called MTZ SEC's which are known to be very weak. That is, they do not provide a very tight approximation of the convex hull of integer feasible solutions. There are tons of papers providing polynomial-sized sets of SEC's (see for instance Bektaş and Gouveia (2014)¹ for stronger versions of the MTZ or Letchford and Salazar-González (2019)² for (multi-)commodity flow-based formulations of the SEC's).

However, in practice, for problems consisting of more than say 20-30 customers, it usually works better to separate stronger SEC's from families of inequalities of exponential sizes. For example, for the CVRP, there is the set of "rounded capacity inequalities" given by \[ \sum_{i\in S}\sum_{j\not\in S}z_{ij} \geq \left\lceil \frac{\sum_{i\in S}q_i}{Q}\right\rceil,\qquad \forall S\subseteq \{1,\dots,n\} \] where $q_i$ is the demand of customer $i$ and $Q$ is the capacity of the vehicles (for information on the strength of different types of SEC's you can take a look at the very nice paper by Letchford and Salazar-González (2006))³. I believe that the state-of-the-art solvers for vehicle routing problems combine the agility of strong cutting planes with the strength of the LP bound obtained from the relaxation of a set-partitioning based formulation of the VRP in question.

---

_References

_{[1] Bektaş, T., Gouveia, L. (2014). Requiem for the Miller-Tucker-Zemlin subtour elimination constraints? European Journal of Operational Research. 236(3):820-832.}

_{[2] Letchford, A. N., Salazar-González, J-J. (2019). The Capacitated Vehicle Routing Problem: Stronger bounds in pseudo-polynomial time. European Journal of Operational Research. 272(1):24-31.}

_{[3] Letchford, A. N., Salazar-González, J-J. (2006). Projection results for vehicle routing. Mathematical Programming. 105(2-3):251-274.}