×

Projection results for vehicle routing. (English) Zbl 1085.90032

Summary: A variety of integer programming formulations have been proposed for Vehicle Routing Problems (VRPs), including the so-called two- and three-index formulations, the set partitioning formulation, and various formulations based on extra variables representing the flow of one or more commodities. Until now, there has not been a systematic study of how these formulations relate to each other. An exception is a paper of Luis Gouveia, which shows that a one-commodity flow formulation of Gavish and Graves yields, by projection, certain ‘multistar’ inequalities in the two-index space.
We give a survey of formulations for the capacitated VRP, and then present various results of a similar flavour to those of Gouveia. In particular, we show that:
– the three-index formulation, augmented by certain families of valid inequalities, gives the same lower bound as the two-index formulation, augmented by certain simpler families of valid inequalities,
– the two-commodity flow formulation of Baldacci et al. gives the same lower bound and the same multistar inequalities as the one-commodity Gavish and Graves formulation,
– a certain non-standard multi-commodity flow formulation, with one commodity per customer, implies by projection certain ‘hypotour-like’ inequalities in the two-index space,
– the set partitioning formulation implies by projection both multistar and hypotour-like inequalities in the two-index space.
We also briefly look at some other variants of the VRP, such as the VRP with time windows, and derive multistar-like inequalities for them. We also present polynomial-time separation algorithms for some of the new inequalities.

MSC:

90C10 Integer programming
90B20 Traffic problems in operations research

Software:

VRP; CVRPSP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, algorithms and applications. Prentice-Hall, 1993 · Zbl 1201.90001
[2] Ascheuer, N., Fischetti, M., Grötschel, M.: A polyhedral study of the asymmetric traveling salesman problem with time windows. Networks 36, 69–79 (2000) · Zbl 0972.90085 · doi:10.1002/1097-0037(200009)36:2<69::AID-NET1>3.0.CO;2-Q
[3] Augerat, P.: Approche Polyèdrale du Problème de Tournées de Véhicles. PhD thesis, Institut National Polytechnique de Grenoble, France, 1995
[4] Augerat, P., Belenguer, J.M., Benavent, E., Corberán, A., Naddef, D., Rinaldi, G.: Computational results with a branch-and-cut code for the capacitated vehicle routing problem. Research report RR949-M, ARTEMIS-IMAG, France (1995)
[5] 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 · doi:10.1287/opre.1040.0111
[6] Bauer, P., Linderoth, J.T., Savelsbergh, M.W.P.: A branch and cut approach to the cardinality constrained circuit problem. Math. Program. 91, 307–348 (2002) · Zbl 1049.90135 · doi:10.1007/s101070100209
[7] Bixby, A.E., Coullard, C., Simchi-Levi, D.: The capacitated prize-collecting traveling salesman problem. Working paper, Department of Industrial Engineering and Engineering Management, Northwestern University, 1997
[8] Blasum, U., Hochstättler, W.: Application of the branch and cut method to the vehicle routing problem. Working Paper, Zentrum fur Angewandte Informatik, Koln, 2000
[9] Cordeau, J.F., Desaulniers, G., Desrosiers, J., Solomon, M.M. VRP with time windows. In: Toth, P., Vigo, D. (eds.), The Vehicle Routing Problem. SIAM, 2001 · Zbl 1076.90543
[10] Desaulniers, G., Desrosiers, J., Erdmann, A., Solomon, M.M., Soumis, F.: VRP with pickup and delivery. In: Toth, P., Vigo D. (eds.), The Vehicle Routing Problem. SIAM, 2001 · Zbl 1076.90544
[11] Desrosiers, J., Dumas, Y., Solomon, M.M., Soumis, F.: Time-constrained routing and scheduling. In: Ball M.O. et al. (eds.), Network Routing. Handbooks in OR/MS 8, North-Holland, Amsterdam, 1995 · Zbl 0861.90052
[12] Eglese, R.W., Letchford, A.N.: Polyhedral theory for arc routing problems. In: Dror, M. (ed.), Arc Routing: Theory, Solutions and Applications. Kluwer Academic Publishers, 2000 · Zbl 0970.90071
[13] Ferreira, C.E., Martin, A., Weismantel, R.: Solving multiple knapsack problems by cutting planes. SIAM J. Opt. 6, 858–877 (1996) · Zbl 0856.90082 · doi:10.1137/S1052623493254455
[14] Fischetti, M., Salazar-González, J.J., Toth, P.: Experiments with a multi-commodity formulation for the symmetric capacitated vehicle routing problem. In Proceedings of the 3rd Meeting of the EURO Working Group on Transportation, Barcelona, 1995, pp. 169–173
[15] Fisher, M.L., Jaikumar, R.: A generalized assignment heuristic for the vehicle routing problem. Networks 11, 109–124 (1981) · doi:10.1002/net.3230110205
[16] Fukasawa, R., Lysgaard, J., de Aragão, M.P., Reis, M., Uchoa, E., Werneck, R.F.: Robust branch-and-cut-and-price for the capacitated vehicle routing problem. In: Nemhauser, G., Bienstock, D. (eds.), Integer Programming and Combinatorial Optimization 10. Lecture Notes in Computer Science 3064, Springer, Berlin Heidelberg, 2004, pp. 1–15 · Zbl 1092.90540
[17] Gavish, B., Graves, S.: The traveling salesman problem and related problems. Working Paper, Graduate School of Management, University of Rochester, New York, 1979
[18] Gavish, B., Graves, S.: Scheduling and routing in transportation and distribution systems: formulations and new relaxations. Working Paper, Graduate School of Management, University of Rochester, New York, 1982
[19] Goemans, M.X., Myung, Y.S.: A catalog of steiner tree formulations. Networks 23, 19–28 (1993) · Zbl 0794.90074 · doi:10.1002/net.3230230104
[20] Gouveia, L. A result on projection for the vehicle routing problem. European J. Oper. Res. 85, 610–624 (1995) · Zbl 0912.90118
[21] Grötschel, M., Lovász, L., Schrijver, A.J.: Geometric Algorithms in Combinatorial Optimisation. Springer, 1988 · Zbl 0634.05001
[22] Hernández-Pérez, H., Salazar-González, J.J.: The one-commodity pickup-and-delivery traveling salesman problem. In: Jünger, M., Reinelt, G., Rinaldi, G. (eds.), Eureka! You Shrink, Lecture Notes in Computer Science 2570, Springer, Berlin Heidelberg, 2003, pp. 89–104 · Zbl 1024.90057
[23] Irnich, S., Villeneuve, D.: The shortest path problem with resource constraints and k-cycle elimination with k 3. Working Paper, RWTH Aachen, 2003 · Zbl 1241.90161
[24] Kohl, N., Desrosiers, J., Madsen, O.B.G., Solomon, M.M., Soumis, F.: 2-path cuts for the vehicle routing problem with time windows. Transportation Science 33, 101–116 (1999) · Zbl 1004.90015 · doi:10.1287/trsc.33.1.101
[25] Langevin, A., Soumis, F., Desrochers, J. Classification of traveling salesman formulations. Oper. Res. Lett. 9, 127–132 (1990) · Zbl 0697.90057
[26] Langevin, A., Desrochers, M., Desrosiers, J., Gélinas, S., Soumis, F.: A two commodity flow formulation for the travelling salesman and makespan problems with time windows. Networks 23, 631–640 (1993) · Zbl 0792.90084 · doi:10.1002/net.3230230706
[27] Laporte, G., Nobert, Y.: A branch and bound algorithm for the capacitated vehicle routing problem. OR Spektrum 5, 77–85 (1983) · Zbl 0523.90088 · doi:10.1007/BF01720015
[28] Laporte, G., Nobert, Y.: Exact algorithms for the vehicle routing problem. Ann. Discr. Math. 31, 147–184 (1987) · Zbl 0611.90055
[29] Laporte, G., Nobert, Y., Desrochers, M.: Optimal routing under capacity and distance restrictions. Operations Research 33, 1050–1073 (1985) · Zbl 0575.90039 · doi:10.1287/opre.33.5.1050
[30] Letchford, A.N., Eglese, R.W.: New cutting-planes for vehicle routing problems. Presented at CO96, Imperial College, London, 1996
[31] Letchford, A.N., Eglese, R.W., Lysgaard, J.: Multistars, partial multistars and the capacitated vehicle routing problem. Math. Program. 94, 21–40 (2002) · Zbl 1023.90073 · doi:10.1007/s10107-002-0336-8
[32] Lysgaard, J., Letchford, A.N., Eglese, R.W.: A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Program. 100, 423–445 (2004) · Zbl 1073.90068 · doi:10.1007/s10107-003-0481-8
[33] Maffioli, F., Sciomachen, A.: A mixed-integer model for solving ordering problems with side constraints. Ann. Operations Res. 69, 277–297 (1997) · Zbl 0880.90078 · doi:10.1023/A:1018989130169
[34] Naddef, D., Rinaldi, G.: Branch-and-cut algorithms for the capacitated VRP. In: Toth, P., Vigo, D. (eds.), The Vehicle Routing Problem. SIAM, 2001 · Zbl 1076.90550
[35] Padberg, M., Sung, T.Y.: An analytical comparison of different formulations of the travelling salesman problem. Math. Program. 52, 315–357 (1991) · Zbl 0770.90075 · doi:10.1007/BF01582894
[36] Papadimitriou, C.H., Yannakakis, M.: The complexity of facets (and some facets of complexity). J. Comp. System Sci. 28, 244–259 (1984) · Zbl 0571.68028 · doi:10.1016/0022-0000(84)90068-0
[37] Picard, J.C., Ratliff, H.D.: Minimum cuts and related problems. Networks 5, 357–370 (1975) · Zbl 0325.90047 · doi:10.1002/net.3230050405
[38] Toth, P., Vigo, D.: An overview of vehicle routing problems. In: Toth, P., Vigo, D. (eds.), The Vehicle Routing Problem. SIAM, 2001 · Zbl 1076.90553
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.