zbMATH — the first resource for mathematics

Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints. (English) Zbl 0723.90081
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 C. E. Miller, A. W. Tucker and 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.

90C35 Programming involving graphs or networks
90-08 Computational methods for problems pertaining to operations research and mathematical programming
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
90C09 Boolean programming
PDF BibTeX Cite
Full Text: DOI
[1] Dantzig, G.B.; Fulkerson, D.R.; Johnson, S.M., Solution of a large scale traveling salesman problem, Oper. res., 2, 393-410, (1954) · Zbl 1414.90372
[2] Desrochers, M.; Lenstra, J.K.; Savelsbergh, M.W.P.; Soumis, F., Vehicle routing with time windows: optimization and approximation, (), 65-84 · Zbl 0642.90055
[3] ()
[4] Grötschel, M.; Padberg, M.W., Partial linear characterizations of the asymmetric traveling salesman polytope, Math. programming, 8, 378-381, (1975) · Zbl 0348.90146
[5] Kulkarni, R.V.; Bhave, P.R., Integer programming formulations of vehicle routing problems, Eur. J. oper. res., 20, 58-67, (1985)
[6] Langevin, A.; Soumis, F.; Desrosiers, J., Classification of traveling salesman problem formulations, Oper. res. lett., 9, 127-132, (1990) · Zbl 0697.90057
[7] Laporte, G.; Nobert, Y.; Desrochers, M., Optimal routing under capacity and distances restrictions, Oper. res., 33, 1050-1073, (1985) · Zbl 0575.90039
[8] Laporte, G.; Nobert, Y., Exact algorithms for the vehicle routing problem, (), 147-184
[9] ()
[10] Miller, C.E.; Tucker, A.W.; Zemlin, R.A., Integer programming formulations and traveling salesman problems, J. ACM, 7, 326-329, (1960) · Zbl 0100.15101
[11] Padberg, M.W., On the facial structure of set packing polyhedra, Math. programming, 5, 199-216, (1973) · Zbl 0272.90041
[12] Padberg, M.W.; Sung, T.Y., An analytical comparison of different formulations of the traveling salesmas problem, (1988), New York University, Working paper
[13] Wolsey, L.A., Faces for a linear inequality in 0-1 variables, Math. programming, 8, 165-178, (1975) · Zbl 0314.90063
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.