Dynamic Programming-Based Column Generation on Time-Expanded Networks: Application to the Dial-a-Flight Problem

References

• Beasley J. E., Christofides N. An algorithm for the resource constrained shortest path problem. Networks (1989) 19(4):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
• Desrochers M. An algorithm for the shortest path problem with resource constraints. (1988) . Technical Report Les Cahiers du GERAD G-88-27, University of Montréal, MontréalGoogle Scholar
• Desrosiers J., Dumas Y., Solomon M., Soumis F., Ball M. O., Magnanti T. L., Nemhauser G. L. Time constrained routing and scheduling. Handbook in Operations Research and Management Science: Network Routing (1995) 8(Elsevier Science, Amsterdam) 35–139Google Scholar
• Dumitrescu I., Boland N. Algorithms for the weight constrained shortest path problem. Internat. Trans. Oper. Res. (2001) 8(1):15–29Crossref, Google Scholar
• Espinoza D., Garcia R., Goycoolea M., Nemhauser G. L., Savelsbergh M. W. P. Per-seat, on-demand air transportation part I: Problem description and an integer multicommodity flow model. Transportation Sci. (2008) 42(3):263–278Link, Google Scholar
• Feillet D., Gendreau M., Rousseau L. M. New refinements for the solution of vehicle routing problems with branch and price. (2005) . Technical Report C7PQMRPO2005-08-X, Center for Research on Transportation, MontréalGoogle Scholar
• Feillet D., Dejax P., Gendreau M., Gueguen C. An exact algorithm for the elementary problem with resource constraints: Application to some vehicle routing problems. Networks (2004) 44(3):216–229Crossref, Google Scholar
• Garcia R. Resource constrained shortest paths and extensions. (2009) . Ph.D. thesis, Georgia Institute of Technology, AtlantaGoogle Scholar
• Garey M. R., Johnson D. S.Computer and Intractability: A Guide to the Theory of NP-Completeness (1979) (Freeman, San Francisco) Google Scholar
• Handler G. Y., Zang I. A dual algorithm for the constrained shortest path problem. Networks (1980) 10(4):293–309Crossref, Google Scholar
• Hassin R. Approximation schemes for the restricted shortest path problem. Math. Oper. Res. (1992) 17(1):36–42Link, Google 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
• Jepsen M. K., Petersen B., Spoorendonk S. A branch-and-cut algorithm for the elementary shortest path problem with a capacity constraint. (2008a) . Technical report, DIKU, University of Copenhagen, CopenhagenGoogle Scholar
• Jepsen M. K., Petersen B., Spoorendonk S., Pisinger D. Subset-row inequalities applied to the vehicle-routing problem with time windows. Oper. Res. (2008b) 56(2):497–511Link, Google Scholar
• Lorenz D. H., Raz D. R. A simple efficient approximation scheme for the restricted shortest path problem. Oper. Res. Lett. (2001) 28(5):213–219Crossref, Google Scholar
• Lübbecke M. E. Dual variable based fathoming in dynamic programs for column generation. Eur. J. Oper. Res. (2003) 162(1):122–125Crossref, Google Scholar
• Mehlhorn K., Ziegelmann M., Paterson M. Resource constrained shortest paths. Proc. 7th Annual Eur. Sympos. Algorithms (ESA2000) (2000) 1879(Springer, Berlin) 326–337Lecture Notes in Computer ScienceCrossref, Google Scholar
• Righini G., Salani M. New dynamic programming algorithms for the resource-constrained elementary shortest path problem. (2005) . Technical report, Dipartimento di Tecnologie dell'Informazione, Universita degli Studi di Milano, Crema, ItalyGoogle Scholar
• Righini G., Salani M. Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints. Discrete Optim. (2006) 3(3):255–273Crossref, Google Scholar
• Ropke S., Cordeau J.-F. Branch-and-cut-and-price for the pickup and delivery problem with time windows. (2006) . Technical Report C7PQMR PO2006-21-X, Center for Research on Transportation, MontréalGoogle Scholar