Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows

References

• Barnhart C., Johnson E. L., Nemhauser G. L., Savelsbergh M. W. P., Vance P. H. Branch-and-price: Column generation for solving huge integer programs. Oper. Res. (1998) 46:316–329Link, Google Scholar
• Beasley J. E., Christofides N. An algorithm for the resource constrained shortest path problem. Networks (1989) 19:379–394Crossref, Google Scholar
• Boland N., Dethridge J., Dumitrescu I. Accelerated label setting algorithms for the elementary resource constrained shortest path problem. Oper. Res. Lett. (2006) 34(1):58–68Crossref, Google Scholar
• Caprara A., Fischetti M., Letchford A. N. On the separation of maximally violated mod-k cuts. Math. Programming (2000) 87(1):37–56Crossref, Google Scholar
• Chabrier A. Vehicle routing problem with elementary shortest path based column generation. Comput. Oper. Res. (2005) 23(10):2972–2990Crossref, Google Scholar
• Chvatal V. Edmonds polytopes and hierarchy of combinatorial problems. Discrete Math. (1973) 4:305–337Crossref, Google Scholar
• COIN COIN—COmputational INfrastructure for Operations Research. (2005) . www.coin-or.orgGoogle Scholar
• Cook W., Rich J. L. A parallel cutting plane algorithm for the vehicle routing problem with time windows. (1999) . Technical Report TR99-04, Computational and Applied Mathematics, Rice University, Houston, TXGoogle Scholar
• Danna E., Le Pape C., Desaulniers G., Desrosiers J., Solomon M. M. Accelerating branch-and-price with local search: A case study on the vehicle routing problem with time windows. Column Generation (2005) (Springer, New York) 90–130Chapter 3Crossref, Google Scholar
• Desaulniers G., Desrosiers J., Ioachim J., Solomon I. M., Soumis F., Villeneuve D., Crainic T. G., Laporte G. A unified framework for deterministic time constrained vehicle routing and crew scheduling problems. Fleet Management and Logistics (1998) (Kluwer, Norwell, MA) 57–93Crossref, Google Scholar
• Desrochers M. La fabrication d'horaires de travail pour les conducteurs d'autobus par une méthode de génération de colonnes. (1986) . Ph.D. thesis, Université de Montréal, Montréal, Quebec, CanadaGoogle Scholar
• Desrochers M., Desrosiers J., Solomon M. A new optimization algorithm for the vehicle routing problem with time windows. Oper. Res. (1992) 40:342–354Link, Google Scholar
• Dror M. Note on the complexity of the shortest path models for column generation in VRPTW. Oper. Res. (1994) 42:977–979Link, Google Scholar
• Dumitrescu I. Constrained path and cycle problems. (2002) . Ph.D. thesis, Department of Mathematics and Statistics, University of Melbourne, Melbourne, AustraliaGoogle Scholar
• Eisenbrand F. Note on the membership problem for the elementary closure of a polyhedron. Combinatorica (1999) 19(2):297–300Crossref, Google Scholar
• Feillet D., Dejax P., Gendreau M., Gueguen C. An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Networks (2004) 44(3):216–229Crossref, Google Scholar
• Fukasawa R., Longo H., Lysgaard J., Poggi de Aragão M., Reis M., Uchoa E., Werneck R. F. Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Programming (2006) 106(3):491–511Crossref, Google Scholar
• Irnich S. Resource extension functions: Properties, inversion, and generalization to segments. (2006) . Technical Report 2006-01, Deutsche Post Endowed Chair of Optimization of Distribution Networks, RWTH Aachen University, Aachen, Germany. www.dpor.rwth-aachen.deGoogle Scholar
• Irnich S., Desaulniers G., Desaulniers G., Desrosiers J., Solomon M. M. Shortest path problems with resource constraints. Column Generation (2005) (Springer, New York) 33–65Chapter 2Crossref, Google Scholar
• Irnich S., Villeneuve D. The shortest path problem with resource constraints and k-cycle elimination for k ≥ 3. INFORMS J. Comput. (2006) 18(3):391–406Link, Google Scholar
• Jepsen M., Petersen B., Spoorendonk S. A branch-and-cut-and-price framework for the VRP applied on CVRP and VRPTW. (2005) . Master's thesis, DIKU, University of Copenhagen, Copenhagen, DenmarkGoogle Scholar
• Kallehauge B., Larsen J., Madsen O. B. G. Lagrangean duality and non-differentiable optimization applied on routing with time windows—Experimental results. (2000) . Technical Report IMM-REP-2001-9, Department of Mathematical Modelling, Technical University of Denmark, Lyngby, DenmarkGoogle Scholar
• 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 Sci. (1999) 33(1):101–116Link, Google Scholar
• Larsen J. Parallelization of the vehicle routing problem with time windows. (1999) . Ph.D. thesis, Department of Mathematical Modelling, Technical University of Denmark, Lyngby, DenmarkGoogle Scholar
• Lubbecke M. E., Desrosiers J. Selected topics in column generation. Oper. Res. (2005) 53(6):1007–1023Link, Google Scholar
• Lysgaard J. CVRPSEP: A package of separation routines for the capacitated vehicle routing problem. (2003) Google Scholar
• Lysgaard J., Letchford A. N., Eglese R. W. A new branch-and-cut algorithm for the capacitated vehicle problem. Math. Programming (2004) 100(2):423–445Crossref, Google Scholar
• Nemhauser G., Park S. A polyhedral approach to edge coloring. Oper. Res. Lett. (1991) 10:315–322Crossref, Google Scholar
• Nemhauser G. L., Wolsey L. A.Integer and Combinatorial Optimization (1988) (John Wiley & Sons, Inc., New York) Crossref, Google Scholar
• Pisinger D., Reinhardt L. B. Multi-objective non-additive shortest path. (2006) . Working paper, DIKU, University of Copenhagen, Copenhagen, DenmarkGoogle Scholar
• Righini G., Salani M. Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints. (2004) . Technical Report 66, Note del Polo—Ricerca, Dipartimento di Tecnologie dell'Informazione, Università degli Studi di Milano, Milano, ItalyGoogle Scholar
• Righini G., Salani M. New dynamic programming algorithms for the resource constrained shortest path problem. (2005) . Technical Report 69, Note del Polo—Ricerca, Dipartimento di Tecnologie dell'Informazione, Università degli Studi di Milano, Milano, ItalyGoogle Scholar
• Salani M. Branch-and-price algorithms for vehicle routing problems. (2005) . Ph.D. thesis, Università degli Studi di Milano, Facoltà di Scienza Matematiche, Fisiche e Naturali, Dipartimento di Technologie dell'Informazione, Milano, ItalyGoogle Scholar
• Solomon M. M. Algorithms for the vehicle routing and scheduling problem with time window constraints. Oper. Res. (1987) 35:234–265Link, Google Scholar
• SPEC Standard Performance Evaluation Corporation. (2005) . www.spec.orgGoogle Scholar
• Toth P., Vigo D.The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications (2002) 9(SIAM, Philadelphia, PA) Crossref, Google Scholar
• Wolsey L. A.Integer Programming (1998) (John Wiley & Sons, Inc., New York) Google Scholar