An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. (English) Zbl 1279.90139
Summary: This paper presents a new exact algorithm for the Capacitated Vehicle Routing Problem (CVRP) based on the set partitioning formulation with additional cuts that correspond to capacity and clique inequalities. The exact algorithm uses a bounding procedure that finds a near optimal dual solution of the LP-relaxation of the resulting mathematical formulation by combining three dual ascent heuristics. The first dual heuristic is based on the \(q\)-route relaxation of the set partitioning formulation of the CVRP. The second one combines Lagrangean relaxation, pricing and cut generation. The third attempts to close the duality gap left by the first two procedures using a classical pricing and cut generation technique. The final dual solution is used to generate a reduced problem containing only the routes whose reduced costs are smaller than the gap between an upper bound and the lower bound achieved. The resulting problem is solved by an integer programming solver. Computational results over the main instances from the literature show the effectiveness of the proposed algorithm.
MSC:
| 90C27 | Combinatorial optimization |
| 49M29 | Numerical methods involving duality |
| 90C39 | Dynamic programming |
References:
| [1] | Augerat, P.: Approche polyédrale du problème de tournées de véhicules. Ph.D. thesis, Institut National Polytechnique de Grenoble (1995) |
| [2] | 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. Tech. Rep. 1 RR949-M, ARTEMIS-IMAG, Grenoble France (1995) |
| [3] | Balas E. and Padberg M.W. (1976). Set partitioning: a survey. SIAM Rev. 18: 710–760 · Zbl 0347.90064 · doi:10.1137/1018115 |
| [4] | Baldacci R., Bodin L.D. and Mingozzi A. (2006). The multiple disposal facilities and multiple inventory locations rollon-rolloff vehicle routing problem. Comput. Oper. Res. 33: 2667–2702 · Zbl 1086.90002 · doi:10.1016/j.cor.2005.02.023 |
| [5] | Baldacci R., Hadjiconstantinou E.A., Maniezzo V. and Mingozzi A. (2002). A new method for solving capacitated location problems based on a set partitioning approach. Comput. Oper. Res. 29: 365–386 · Zbl 0994.90087 · doi:10.1016/S0305-0548(00)00072-1 |
| [6] | Baldacci R., Hadjiconstantinou E.A. and Mingozzi A. (2004). An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Oper. Res. 52: 723–738 · Zbl 1165.90353 · doi:10.1287/opre.1040.0111 |
| [7] | Balinski M. and Quandt R. (1964). On an integer program for a delivery problem. Oper. Res. 12: 300–304 · doi:10.1287/opre.12.2.300 |
| [8] | (1995). Network Routing, Handbooks in Operations Research and Management, vol. 8. Elsevier, Amsterdam · Zbl 0829.00010 |
| [9] | (2007). Transportation, Handbooks in Operations Research and Management Science, vol. 14. North-Holland, Amsterdam · Zbl 1190.90026 |
| [10] | Bianco L., Mingozzi A. and Ricciardelli S. (1994). A set partitioning approach to the multiple depot vehicle scheduling problem. Optim. Methods Softw. 3: 163–194 · doi:10.1080/10556789408805563 |
| [11] | Bodin L.D., Mingozzi A. and Maniezzo V. (2003). Street routing and scheduling problems. In: Hall, R. (eds) Handbook of Transportation Science, vol. 2, pp 413–438. Kluwer, Boston |
| [12] | Bramel, J., Simchi-Levi, D.: Set-covering-based algorithms for the capacitated VRP. In: Toth, P., Vigo D. (eds.) The Vehicle Routing Problem, vol. 9, pp. 85–108 SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, (2002) · Zbl 1076.90541 |
| [13] | Christofides N. and Eilon S. (1969). An algorithm for the vehicle dispatching problem. Oper. Res. Q. 20: 309–318 · doi:10.1057/jors.1969.75 |
| [14] | Christofides N., Mingozzi A. and Toth P. (1979). The vehicle routing problem. In: Christofides, N., Mingozzi, A., Toth, P., and Sandi, C. (eds) Combinatorial Optimization., pp 315–338. Wiley, Chichester · Zbl 0413.90075 |
| [15] | Christofides N., Mingozzi A. and Toth P. (1981). Exact algorithms for the vehicle routing problem based on spanning tree and shortest path relaxation. Math. Program. 10: 255–280 · Zbl 0461.90067 · doi:10.1007/BF01589353 |
| [16] | Cordeau J.-F., Laporte G., Savelsbergh M.W.P. and Vigo D. (2007). Vehicle routing. In: Barnhart, C. and Laporte, G. (eds) Transportation, Handbooks in Operations Research and Management Science, vol. 14, pp 367–428. North-Holland, Amsterdam |
| [17] | Cornuéjols G. and Harche F. (1993). Polyhedral study of the capacitated vehicle routing. Math. Program. 60: 21–52 · Zbl 0790.90029 · doi:10.1007/BF01580599 |
| [18] | CPLEX: ILOG CPLEX 9.0 callable library. ILOG (2004) |
| [19] | Fischetti M. and Toth P. (1989). An additive bounding procedure for combinatorial optimization problems. Oper. Res. 37: 319–328 · Zbl 0676.90049 · doi:10.1287/opre.37.2.319 |
| [20] | Fisher, M.L.: Vehicle routing. In: Ball, M.O., Magnanti T.L., Monma, C.L., Nemhauser, G.L. Network Routing, Handbooks in Operations Research and Management Science, vol. 8, pp. 1–133. North-Holland, Amsterdam (1995) |
| [21] | Fukasawa R., Longo H., Lysgaard J., Poggi de Aragão M., Reis M., Uchoa E. and Werneck R.F. (2006). Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Program. Ser. A 106: 491–511 · Zbl 1094.90050 · doi:10.1007/s10107-005-0644-x |
| [22] | Garey M.R. and Johnson D.S. (1990). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York · Zbl 0411.68039 |
| [23] | Gendreau, M., Laporte, G., Potvin, J.-Y.: Metaheuristics for the capacitated VRP. In: Toth, P., Vigo D. (eds.) The Vehicle Routing Problem, vol. 9, pp. 129–154 SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, (2002) · Zbl 1076.90545 |
| [24] | Hoffman K. and Padberg M.W. (1993). Solving airline crew scheduling problems by branch and cut. Manage. Sci. 39: 657–682 · Zbl 0783.90051 · doi:10.1287/mnsc.39.6.657 |
| [25] | Kim S., Chang K.N. and Lee J.Y. (1995). A descent method with linear programming subproblems for nondifferentiable convex optimization. Math. Program. 71: 17–28 · Zbl 0855.90101 · doi:10.1007/BF01592242 |
| [26] | Laporte G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. Eur. J. Oper. Res. 59: 345–358 · Zbl 0761.90034 · doi:10.1016/0377-2217(92)90192-C |
| [27] | Laporte G., Nobert Y. and Desrochers M. (1985). Optimal routing under capacity and distance restrictions. Oper. Res. 33: 1058–1073 · Zbl 0575.90039 · doi:10.1287/opre.33.5.1050 |
| [28] | Laporte, G., Semet F.: Classical heuristics for the capacitated VRP. In: Toth, P., Vigo, D. (eds.) The Vehicle Routing Problem, vol. 9, pp. 109–128. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia (2002) · Zbl 1076.90549 |
| [29] | Letchford A.N., Eglese R.W. and Lysgaard J. (2002). Multistars, partial multistars and the capacitated vehicle routing problem. Math. Program. Ser. A 94: 21–40 · Zbl 1023.90073 · doi:10.1007/s10107-002-0336-8 |
| [30] | Lübbecke M.E. and Desrosiers J. (2005). Selected topics in column generation. Oper. Res. 53: 1007–1023 · Zbl 1165.90578 · doi:10.1287/opre.1050.0234 |
| [31] | Lysgaard, J.: CVRPSEP: A package of separation routines for the capacitated vehicle routing problem. Technical report, Department of Management Science and Logistics, Aarhus School of Business (2003) |
| [32] | Lysgaard J., Letchford A.N. and Eglese R.W. (2004). A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Program. Ser. A 100: 423–445 · Zbl 1073.90068 · doi:10.1007/s10107-003-0481-8 |
| [33] | Marsten R.E., Hogan W.W. and Blankenship J.W. (1975). The boxstep method for large-scale optimization. Oper. Res. 23: 389–405 · Zbl 0372.90078 · doi:10.1287/opre.23.3.389 |
| [34] | du Merle O., Villeneuve D., Desrosiers J. and Hansen P. (1999). Stabilized column generation. Discrete Math. 194: 229–237 · Zbl 0949.90063 · doi:10.1016/S0012-365X(98)00213-1 |
| [35] | Mingozzi A., Boschetti M.A., Ricciardelli S. and Bianco L. (1999). A set partitioning approach to the crew scheduling problem. Oper. Res. 47: 873–888 · Zbl 1024.90042 · doi:10.1287/opre.47.6.873 |
| [36] | Mingozzi, A., Christofides, N., Hadjiconstantinou, E.A.: An exact algorithm for the vehicle routing problem based on the set partitioning formulation. Tech. rep., University of Bologna (1994) · Zbl 0839.90031 |
| [37] | Mingozzi A., Giorgi S. and Baldacci R. (1999). An exact method for the vehicle routing problem with backhauls. Transp. Sci. 33: 315–329 · Zbl 1004.90016 · doi:10.1287/trsc.33.3.315 |
| [38] | Naddef, D., Rinaldi, G.: Branch-and-cut algorithms for the capacitated VRP. In: Toth, P., Vigo D. (eds.) The Vehicle Routing Problem, vol. 9. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, pp. 53–81 (2002) · Zbl 1076.90550 |
| [39] | Niskanen, S., Östergård, P.R.J.: Cliquer user’s guide. Tech. Rep. 48, Helsinki University of Technology Communications Laboratory (2003) |
| [40] | Östergård P.R.J. (2002). A fast algorithm for the maximum clique problem. Discrete Appl. Math. 120: 197–207 · Zbl 1019.05054 · doi:10.1016/S0166-218X(01)00290-6 |
| [41] | Rousseau, L.-M., Gendreau, M., Feillet, D.: Interior point stabilization for column generation. Oper. Res. Lett. (2006). doi:10.1016/j.orl.2006.11.004 · Zbl 1149.90099 |
| [42] | Toth, P., Vigo, D.: Branch-and-bound algorithms for the capacitated VRP. In: Toth, P., Vigo D. (eds.) The Vehicle Routing Problem, vol. 9. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, pp. 29–51 (2002) · Zbl 1076.90554 |
| [43] | Toth, P., Vigo, D.: The Vehicle Routing Problem, vol. 9. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia (2002) · Zbl 0979.00026 |
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.
