×

zbMATH — the first resource for mathematics

Formulations and valid inequalities for the heterogeneous vehicle routing problem. (English) Zbl 1134.90527
Summary: We consider the vehicle routing problem where one can choose among vehicles with different costs and capacities to serve the trips. We develop six different formulations: the first four based on Miller-Tucker-Zemlin constraints and the last two based on flows. We compare the linear programming bounds of these formulations. We derive valid inequalities and lift some of the constraints to improve the lower bounds. We generalize and strengthen subtour elimination and generalized large multistar inequalities.

MSC:
90C35 Programming involving graphs or networks
90B10 Deterministic network models in operations research
90B06 Transportation, logistics and supply chain management
Software:
PORTA; VRP; CVRPSP
PDF BibTeX Cite
Full Text: DOI
References:
[1] Achuthan, N.R., Caccetta, L., Hill, S.P.: An improved branch and cut algorithm for the capacitated vehicle routing problem. Transportation Science 37, 153–169 (2003)
[2] Araque, J.R., Hall, L.A., Magnanti, T.L.: Capacitated trees capacitated routing and associated polyhedra. Discussion paper, Center for Operations Research and Econometrics, Catholic University of Louvain, Belgium, 1990
[3] Balas, E.: Facets of the knapsack polytope. Mathematical Programming 8, 146–164 (1975) · Zbl 0316.90046
[4] Baldacci, R., Hadjiconstantinou, E., Mingozzi, A.: An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Operations Research 52, 723–738 (2004) · Zbl 1165.90353
[5] Christof, T.: PORTA - a POlyhedron Representation Transformation Algorithm. Version 1.3.2 available at http://www.iwr.uni-heidelberg.de/groups/comopt/software/PORTA/ 1999
[6] Desrochers, M., Verhoog, T.W.: A new heuristic for the fleet size and mix vehicle routing problem. Computers & Operations Research 18, 263–274 (1991) · Zbl 0723.90018
[7] Desrochers, M., Laporte, G.: Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints. Operations Research Letters 10, 27–36 (1991) · Zbl 0723.90081
[8] Fisher, M.: Vehicle routing. In: M.O. Ball, T.L. Magnanti, C.L. Monma and G.L. Nemhauser (eds) Handbooks in OR MS, Vol. 8, Elsevier Science, 1995 · Zbl 0870.90058
[9] Gavish, B., Graves, S.C.: The traveling salesman problem and related problems. Working Paper 7905, Graduate School of Management, University of Rochester, Rochester, 1979
[10] Gendreau, M., Laporte, G., Musaraganyi, C., Taillard, E.D.: A tabu search heuristic for the heterogeneous fleet vehicle routing problem. Computers & Operations Research 26, 1153–1173 (1999) · Zbl 0967.90019
[11] Gheysens, F., Golden, B., Assad, A.: A new heuristic for determining fleet size and composition. Mathematical Programming Study 26, 233–236 (1986) · Zbl 0585.90064
[12] Golden, B., Assad, A., Levy, L., Gheysens, F.: The fleet size and mix vehicle routing problem. Computers & Operations Research 11, 49–66 (1984) · Zbl 0607.90043
[13] Gouveia, L.: A result on projection for the vehicle routing problem. European Journal of Operational Research 85, 610–624 (1995) · Zbl 0912.90118
[14] Gouveia, L., Pires, J.M.: The asymmetric traveling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints. European Journal of Operational Research 112, 134–146 (1999) · Zbl 0971.90099
[15] Hammer, P.L., Johnson, E.L., Peled, U.N.: Facets of regular 0–1 polytopes. Mathematical Programming 8, 179–206 (1975) · Zbl 0314.90064
[16] Kara, I., Laporte, G., Bektas, T.: A note on the lifted Miller-Tucker-Zemlin subtour elimination constraints for the capacitated vehicle routing problem. European Journal of Operational Research 158, 793–795 (2004) · Zbl 1061.90020
[17] Langevin, A., Soumis, F., Desrosiers, J.: Classification of traveling salesman problem formulations. Operations Research Letters 9, 127–132 (1990) · Zbl 0697.90057
[18] Laporte, G.: The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research 59, 345–358 (1992) · Zbl 0761.90034
[19] Laporte, G., Osman, I.H.: Routing problems: A bibliography. Annals of Operations Research 61, 227–262 (1995) · Zbl 0839.90032
[20] Letchford, A.N., Salazar-Gonzalez, J.J.: Projection results for vehicle routing. To appear in Mathematical Programming · Zbl 1085.90032
[21] Letchford, A.N., Eglese, R.W., Lysgaard, J.: Multistars partial multistars and the capacitated vehicle routing problem. Mathematical Programming 94, 21–40 (2002) · Zbl 1023.90073
[22] Lysgaard, J., Letchford, A.N., Eglese, R.W.: A new branch and cut algorithm for the capacitated vehicle routing problem. Mathematical Programming 100, 423–445 (2004) · Zbl 1073.90068
[23] Mazur, D.R.: Integer programming approaches to a multi-facility location problem. Ph.D. Thesis, John Hopkins University, 1999
[24] Miller, C., Tucker, A., Zemlin, R.: Integer programming formulations and traveling salesman problems. Journal of ACM 7, 326–329 (1960) · Zbl 0100.15101
[25] Padberg, M., Sung, T.Y.: An analytical comparison of different formulations of the traveling salesman problem. Mathematical Programming 52, 315–357 (1991) · Zbl 0770.90075
[26] Pochet, Y., Wolsey, L.A.: Integer knapsack and flow covers with divisible coefficients: Polyhedra optimization and separation. Discrete Applied Mathematics 59, 57–74 (1995) · Zbl 0835.90052
[27] Renaud, J., Boctor, F.F.: A sweep-based algorithm for the fleet size and mix vehicle routing problem. European Journal of Operational Research 140, 618–628 (2002) · Zbl 0998.90016
[28] Salhi, v., Sari, M., Saidi, D., Touati, N.A.C.: Adaptation of some vehicle fleet mix heuristics. OMEGA 20, 653–660 (1992)
[29] Salhi, S., Rand, G.K.: Incorporating vehicle routing into the vehicle fleet composition problem. European Journal of Operational Research 66, 313–330 (1993) · Zbl 0775.90155
[30] Taillard, E.D.: A heuristic column generation method for the heterogeneous fleet VRP. RAIRO 33, 1–14 (1999) · Zbl 0992.90008
[31] Toth, P., Vigo, D.: Models relaxations and exact approaches for the capacitated vehicle routing problem. Discrete Applied Mathematics 123, 487–512 (2002) · Zbl 1060.90065
[32] Toth, P., Vigo, D.: The vehicle routing problem. SIAM monographs on discrete mathematics and applications. Philadelphia, 2002 · Zbl 1060.90065
[33] Wassan, N.A., Osman, I.H.: Tabu search variants for the mix fleet vehicle routing problem. Journal of the Operational Research Society 53, 768–782 (2002) · Zbl 1130.90311
[34] Wolsey L.: Faces for a linear inequality in 0–1 variables. Mathematical Programming 8, 165–178 (1975) · Zbl 0314.90063
[35] Yaman, H.: The integer knapsack cover polyhedron. Working Paper · Zbl 1177.90298
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.