A Branch-and-Cut Procedure for the Vehicle Routing Problem with Time Windows

References

• Araque J. R., Kudva G., Morin T., Pekny J. F. A branch-and-cut algorithm for vehicle routing problems. Ann. Oper. Res. (1994) 50:37–59Crossref, Google Scholar
• Ascheuer N., Fischetti M., Grötschel M. Solving the asymmetric travelling salesman problem with time windows by branch and cut. Konard-Zuse-Zentrum für Informationstechnik (1999) (Berlin, Germany) . Preprint SC 99-31Google Scholar
• Augerat P. Approache polyédrale du problème de tournées de véhicules. (1995) . Ph.D. thesis, Institut National Polytechnique de Grenoble, Grenoble, FranceGoogle Scholar
• Bodin L. B., Golden B. L., Assad A. A., Ball M. O. Routing and scheduling of vehicles and crews—The state of the art. Comput. Oper. Res. (1983) 10:63–211Crossref, Google Scholar
• Cook W., Rich J. L. A parallel cutting plan algorithm for the vehicle routing problem with time windows. (1999) . Technical report, Computational and Applied Mathematics, Rice University, Houston, TXGoogle Scholar
• Cornuéjols G., Harche F. Polyhedral study of the capacitated vehicle routing. Math. Programming (1993) 60:21–52Crossref, Google Scholar
• Desrochers M., Desrosiers J., Solomon M. M. A new optimization algorithm for the vehicle routing problem with time windows. Oper. Res. (1992) 40:342–354Link, Google Scholar
• Desrochers M., Lenstra J. K., Savelsbergh M. W. P., Soumis F., Golden B. L., Assad A. A. Vehicle routing with time windows: Optimization and approximation. Vehicle Routing: Methods and Studies (1988) (North-Holland, Amsterdam, The Netherlands) 65–84Google Scholar
• Desrosiers J., Dumas Y., Solomon M. M., Soumis F., Ball M. O., Magnati T. L., Monma C. L., Nemhauser G. L. Time constrained routing and scheduling. Handbooks in Operations Research and Management Science: Network Routing (1995) 8(North-Holland, Amsterdam, The Netherlands)35–139Google Scholar
• Fischetti M., Toth P. A polyhedral approach to the asymmetric travelling salesman problem. Management Sci. (1997) 43Link, Google Scholar
• Fischetti M., Salazar González J. J., Toth P. Solving the orienteering problem through branch-and-cut. INFORMS J. Comput. (1998) 10:133–148Link, Google Scholar
• Floyd R. Algorithm 97, shortest path. Comm. ACM (1962) 5–345Crossref, Google Scholar
• Frank A. On the edge-connectivity algorithm of Nagamochi and Ibaraki. (1994) . Working paper, ARTEMIS-IMAG, Université de Grenoble, Grenoble, FranceGoogle Scholar
• Gomory R. E., Hu T. C. Multiterminal network flows. SIAM J. Appl. Math. (1961) 9:551–570Crossref, Google Scholar
• Grötschel M., Padberg M. W. Polyhedral theory. The Traveling Salesman Problem (1985) (Wiley, Chichester, U.K.) 251–306Google Scholar
• Hoffman K. L., Padberg M. W. Solving airline crew scheduling problems by branch-and-cut. Management Sci. (1993) 39:657–683Link, Google Scholar
• Kohl N. Exact methods for time constrained routing and related scheduling problems. (1995) . Ph.D. thesis, Technical University of Denmark, Lyngby, DenmarkGoogle Scholar
• Kohl N., Madsen O. B. G. An optimization algorithm for the vehicle routing problem with time windows based on Lagrangian relaxation. Oper. Res. (1997) 45:395–406Link, Google Scholar
• Kohl N., Desrosiers J., Madsen O. B. G., Solomon M. M., Soumis F. Two-path cuts for the vehicle routing problem with time windows. Transportation Sci. (1999) 33:101–116Link, Google Scholar
• Kontoravdis G. The vehicle routing problem with time windows. (1997) . Ph.D. thesis, Graduate Program in Operations Research, The University of Texas, Austin, TXGoogle Scholar
• Kontoravdis G., Bard J. F. A GRASP for the vehicle routing problem with time windows. ORSA J. Comput. (1995) 7:10–23Link, Google Scholar
• Laporte G., Nobert Y. Comb inequalities for the vehicle routing problem. Methods Oper. Res. (1984) 51:271–276Google Scholar
• Nagamochi H., Ibaraki T. Computing edge-connectivity in multigraphs and capacitated graphs. SIAM J. Discrete Math. (1992) 5:54–66Crossref, Google Scholar
• Nemhauser G. L., Wolsey L. A.Integer and Combinatorial Optim. (1988) (Wiley, New York) Google Scholar
• Padberg M. W., Rinaldi G. An efficient algorithm for the minimum capacity cut problem. Math. Programming (1990a) 47:19–36Crossref, Google Scholar
• Padberg M. W., Rinaldi G. Facet identification for the symmetric traveling salesman polytope. Math. Programming (1990b) 47:219–257Crossref, Google Scholar
• Padberg M. W., Rinaldi G. A branch-and-cut algorithm for the resolution of large scale symmetric traveling salesman problems. SIAM Rev. (1991) 33:60–100Crossref, Google Scholar
• Rich J. L. A computational study of vehicle routing problem applications. (1999) . Ph.D. thesis, Computational and Applied Mathematics, Rice University, Houston, TXGoogle Scholar
• Sol M., Savelsbergh M. W. P. A branch-and-price algorithm for the pickup and delivery problem with time windows. (1994) . Memorandum COSOR 94-22, Department of Mathematics and Computing Science, Eindoven University of Technology, Eindoven, The NetherlandsGoogle Scholar
• Solomon M. M. Algorithms for the vehicle routing and scheduling problem with time window constraints. Oper. Res. (1987) 35:254–265Link, Google Scholar
• Solomon M. M., Desrosiers J. Time window constrained routing and scheduling problems. Transportation Sci. (1988) 22:1–13Link, Google Scholar