×

zbMATH — the first resource for mathematics

Robust branch-and-cut-and-price for the capacitated vehicle routing problem. (English) Zbl 1094.90050
The authors present a branch-and-cut-and-price algorithm for the capacitated vehicle routing problem (CVRP). They combine two CVRP formulations, one using bound, degree, and capacity constraints and one using \(q\)-routes to formulate a Dantzig-Wolfe master problem which has exponentially many variables and constraints. The column generation procedure is solved using dynamic programming and generates \(s\)-cycle free \(q\)-routes for small values of \(s\).
Heuristics are used to speed up the dynamic programming procedure. Several known types of cuts are employed. An exact separation procedure for rounded capacity cuts is used to compute lower bounds for the first and combined CVRP formulation to be used in a heuristic separation procedure. Details on the representation of variables and constraints and dynamic selection of column generation are given. The numerical results show that all literature instances up to 135 customers are solved optimally. 18 instances are solved to optimality for the first time.

MSC:
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C27 Combinatorial optimization
90C10 Integer programming
Software:
VRP; CVRPSEP; CVRPSP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achuthan, N., Caccetta, L., Hill, S.: Capacited vehicle routing problem: Some new cutting planes. Asia-Pacific J. Oper. Res. 15, 109–123 (1998) · Zbl 0912.90113
[2] Achuthan, N., Caccetta, L., Hill, S.: An improved branch-and-cut algorithm for the capacitated vehicle routing problem. Transportation Sci. 37, 153–169 (2003)
[3] Agarwal, Y., Mathur, K., Salkin, H.: A set-partitioning based exact algorithm for the vehicle routing problem. Networks 19, 731–739 (1989) · Zbl 0682.90050
[4] Araque, J., Hall, L., Magnanti, T.: Capacitated trees, capacitated routing and polyhedra. Technical Report SOR-90-12. Princeton University, 1990
[5] Araque, J., Kudva, G., Morin, T., Pekny, J.: A branch-and-cut algorithm for the vehicle routing problem. Ann. Oper. Res. 50, 37–59 (1994) · Zbl 0815.90062
[6] Augerat, P.: Approche polyèdrale du problème de tournées de véhicles. PhD thesis, Institut National Polytechnique de Grenoble, 1995
[7] Augerat, P., Belenguer, J., Benavent, E., Corberán, A., Naddef, D., Rinaldi, G.: Computational results with a branch and cut code for the capacitated vehicle routing problem. Technical Report 949-M, Université Joseph Fourier, Grenoble, France, 1995
[8] Balinski, M., Quandt, R.: On an integer program for a delivery problem. Oper. Res. 12, 300–304 (1964)
[9] Barnhart, C., Hane, C., Vance, P.: Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems. Oper. Res. 40, 318–326 (2000)
[10] Blasum, U., Hochstättler, W.: Application of the branch and cut method to the vehicle routing problem. Technical Report ZPR2000-386, Zentrum fur Angewandte Informatik Köln, 2000
[11] Christofides, N., Eilon, S.: An algorithm for the vehicle-dispatching problem. Oper. Res. Q. 20, 309–318 (1969)
[12] Christofides, N., Mingozzi, A., Toth, P.: Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations. Math. Prog. 20, 255–282 (1981) · Zbl 0461.90067
[13] Cornuéjols, G., Harche, F.: Polyhedral study of the capacitated vehicle routing problem. Math. Prog. 60, 21–52 (1993) · Zbl 0790.90029
[14] Dantzig, G., Ramser, R.: The truck dispatching problem. Management Science 6, 80–91 (1959) · Zbl 0995.90560
[15] Desrochers, M., Desrosiers, J., Solomon, M.: A new optimization algorithm for the vehicle routing problem with time windows. Oper. Res. 40, 342–354 (1992) · Zbl 0749.90025
[16] Felici, G., Gentile, C., Rinaldi, G.: Solving large MIP models in supply chain management by branch & cut. Technical report, Istituto di Analisi dei Sistemi ed Informatica del CNR, Italy, 2000
[17] Fisher, M.: Optimal solution of vehicle routing problem using minimum k-trees. Oper. Res. 42, 626–642 (1994) · Zbl 0815.90066
[18] Fukasawa, R., Poggi de Aragão, M., Porto, O., Uchoa, E.: Robust branch-and-cut-and-price for the capacitated minimum spanning tree problem. In: Proc. of the International Network Optimization Conference. Evry, France, 2003, pp. 231–236
[19] Fukasawa, R., Reis, M., Poggi de Aragão, M., Uchoa, E.: Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Technical Report RPEP Vol.3 no.8, Universidade Federal Fluminense, Engenharia de Produção, Niterói, Brazil, 2003 · Zbl 1092.90540
[20] Hadjiconstantinou, E., Christofides, N., Mingozzi, A.: A new exact algorithm from the vehicle routing problem based on q-paths and k-shortest paths relaxations. In: Laporte, G., Michel Gendreau (eds.), Freight Transportation, 61 in Annals of Operations Research. Baltzer Science Publishers, 1995, pp. 21–44 · Zbl 0839.90031
[21] Irnich, S., Villeneuve, D.: The shortest path problem with resource constraints and k-cycle elimination for k 3, 2003. To appear in JNFORMS Journal on computing. Available at http://www.dpor.rwth-aachen.de/de/publikationen/pdf/or_2003-01.pdf . · Zbl 1241.90161
[22] Kim, D., Barnhart, C., Ware, K., Reinhardt, G.: Multimodal express package delivery: A service network design application. Transportation Science 33, 391–407 (1999) · Zbl 0958.90004
[23] Kohl, N., Desrosiers, J., Madsen, O., Solomon, M., Soumis, F.: 2-Path cuts for the vehicle routing problem with time windows. Transportation Science 33, 101–116 (1999) · Zbl 1004.90015
[24] Laporte, G., Norbert, Y.: A branch and bound algorithm for the capacitated vehicle routing problem. Oper. Res. Spektrum 5, 77–85 (1983) · Zbl 0523.90088
[25] Letchford, A., Eglese, R., Lysgaard, J.: Multistars, partial multistars and the capacitated vehicle routing problem. Math. Prog. 94, 21–40 (2002) · Zbl 1023.90073
[26] Letchford, A., Reinelt, G., Theis, D.: A faster exact separation algorithm for blossom inequalities. In: Proceedings of the X IPCO, volume 3064 of Lecture Notes in Computer Science. New York, 2004, pp. 196–205 · Zbl 1092.90542
[27] Letchford, A.N., Salazar, J.J.: Projection results for vehicle routing. Math. Prog. 2004, To appear · Zbl 1085.90032
[28] Longo, H., Poggi de Aragão, M., Uchoa, E.: Solving capacitated arc routing problems using a transformation to the CVRP. Computers & Operations Research, 2004, To appear · Zbl 1087.90054
[29] Lysgaard, J.: CVRPSEP: A package of separation routines for the capacitated vehicle routing problem, 2003. Available at http://www.asb.dk/\(\sim\)lys
[30] Lysgaard, J., Letchford, A., Eglese, R.: A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Prog. 100 (2), 423–445 (2004) · Zbl 1073.90068
[31] Martinhon, C., Lucena, A., Maculan, N.: Stronger k-tree relaxations for the vehicle routing problem. European J. Oper. Res. 158 (1), 56–71 (2004) · Zbl 1061.90023
[32] Miller, D.: A matching based exact algorithm for capacitated vehicle routing problems. ORSA J. Comput. 7, 1–9 (1995) · Zbl 0822.90057
[33] Naddef, D., Rinaldi, G.: Branch-and-cut algorithms for the capacitated VRP. In: Toth, P., Vigo, D. (eds.) The Vehicle Routing Problem, chapter 3. SIAM, 2002, pp. 53–84 · Zbl 1076.90550
[34] Padberg, M., Rao, M.: Odd minimum cut-sets and b-matchings. Math. Oper. Res. 7 (1), 67–80 (1982) · Zbl 0499.90056
[35] Pigatti, A.: Modelos e algoritmos para o problema de alocação generalizada e aplicações. Master’s thesis, Pontifí cia Universidade Católica do Rio de Janeiro, Brazil, July 2003
[36] Poggi de Aragão, M., Uchoa, E.: Integer program reformulation for robust branch-and-cut-and-price. In: Annals of Mathematical Programming in Rio. Búzios, Brazil, 2003, pp. 56–61
[37] Ralphs, T.: Parallel branch and cut for capacitated vehicle routing. Parallel Computing 29, 607–629 (2003)
[38] Ralphs, T., Kopman, L., Pulleyblank, W., Trotter, L. Jr.: On the capacitated vehicle routing problem. Math. Prog. 94, 343–359 (2003) · Zbl 1030.90131
[39] 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
[40] Toth, P., Vigo, D.:The Vehicle Routing Problem. Monographs on Discrete Mathematics and Applications. SIAM, 2002 · Zbl 0979.00026
[41] Van den Akker, J., Hurkens, C., Savelsbergh, M.: Time-indexed formulation for machine scheduling problems: column generation. INFORMS J. on Computing 12, 111–124 (2000) · Zbl 1034.90004
[42] Vanderbeck, F.: Lot-sizing with start-up times. Management Science 44, 1409–1425 (1998) · Zbl 0989.90069
[43] Wenger, K.M.: Generic Cut Generation Methods for Routing Problems. PhD thesis, Institute of Computer Science, University of Heidelberg, 2003 · Zbl 1103.90394
[44] Werneck, R.F., Setubal, J.C.: Finding minimum congestion spanning trees. ACM J. of Experimental Algorithmics, 5, 2000 · Zbl 1066.05050
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.