Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints (Q2276891)

The paper deals with various kinds of vehicle routing problems (VRP): (i) the capacitated VRP (CVRP): every vertex \(v_ i\) has a positive weight \(q_ i\) and the total weight of any route must not exceed Q, the capacity of each vehicle. (ii) The distance constrained VRP (DVRP): the total length of any route may not exceed a given bound L. (iii) The VRP with time windows (TWVRP): every vertex \(v_ i\) must be visited within a time window \([a_ i,b_ i]\), where waiting at \(v_ i\) is allowed. As the classical subtour elimination constraints (due to Dantzig, Fulkerson and Johnson) are hard to adapt to the DVRP and no generalization of DFJ-constraints are known with respect to the TWVRP, the authors propose to improve and to extend the subtour elimination constraints of \textit{C. E. Miller, A. W. Tucker} and \textit{R. A. Zemlin} [J. Assoc. Comput. Mach. 7, 326-329 (1960; Zbl 0100.151)], \[ (MTZ)\quad u_ i-u_ j+(n-1)x_{ij}\leq n-2\quad (i,j=2,...,n;\quad i\neq j),\quad 1\leq u_ i\leq n-1\quad (i=2,...,n). \] By a lifting technique they get valid inequalities for the TSP, CVRP, DVRP and TWVRP. Some analysis of the induced polytopes and facets are given for the asymmetric TSP too. A couple of experiments indicate that the lifted MTZ-constraints are of relative strength even for TSP.