Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows

References

• Balas E., Fischetti M., Pulleyblank W. R. The precedence-constrained asymmetric traveling salesman polytope. Math. Programming (1995) 68:241–265Crossref, Google Scholar
• Baldacci R., Christofides N., Migozzi A. An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math. Programming, Ser. A (2008) 115:351–385Crossref, Google Scholar
• Barnhart C., Johnson E. L., Nemhauser G. L., Savelsbergh M. W. P., Vance P. H. Branch-and-price: Column generation for solving integer programs. Oper. Res. (1998) 46(3):316–329Link, Google Scholar
• Boland N., Detridge J., Dumitrescu I. Accelerated label setting algorithms for the elementary resource constrained shortest path problem. Oper. Res. Lett. (2006) 34:58–68Crossref, Google Scholar
• Bramel J., Simchi-Levi D., Toth P., Vigo D. Set-covering-based algorithms for the capacitated VRP. The Vehicle Routing Problem, Vol. 9. SIAM Monographs on Discrete Mathematics and Applications (2002) (SIAM, Philadelphia) 85–108Google Scholar
• Cordeau J.-F. A branch-and-cut algorithm for the dial-a-ride problem. Oper. Res. (2006) 54(3):573–586Link, Google Scholar
• Cordeau J.-F., Laporte G., Potvin J.-Y., Savelsbergh M. W. P., Barnhart C., Laporte G. Transportation on demand. Transportation Handbooks in Operations Research and Management Science (2007) (Elsevier, Amsterdam) 429–466Google Scholar
• Dell'Amico M., Rihigni G., Salani M. A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection. Transportation Sci. (2006) 40(2):235–247Link, Google Scholar
• Desaulniers G., Lessard F., Hadjar A. Tabu search, partial elementarity, and generalized k-path inequalities for the vehicle routing problem with time windows. Transportation Sci. (2008) 42(3):387–404Link, Google Scholar
• Desaulniers G., Desrosiers J., Erdmann A., Solomon M. M., Soumis F., Toth P., Vigo D. VRP with pickup and delivery. The Vehicle Routing Problem, Vol. 9. SIAM Monographs on Discrete Mathematics and Applications (2002) (SIAM, Philadelphia) 225–242Google Scholar
• Desaulniers G., Desrosiers J., Ioachim I., Solomon M. 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., Desrosiers J., Solomon M. A new optimization algorithm for the vehicle routing problem with time windows. Oper. Res. (1992) 40(2):342–354Link, Google Scholar
• Desrosiers J., Dumas Y., Soumis F. A dynamic programming solution of the large-scale single-vehicle dial-a-ride problem with time windows. Amer. J. Math. Management Sci. (1986) 6:301–325Crossref, Google Scholar
• Dumas Y., Desrosiers J., Soumis F. The pickup and delivery problem with time windows. Eur. J. Oper. Res. (1991) 54:7–22Crossref, Google Scholar
• Dumitrescu I., Ropke S., Cordeau J.-F., Laporte G. The traveling salesman problem with pickup and delivery: Polyhedral results and a branch-and-cut algorithm. Math. Programming, Ser. A. (2009) . Forthcoming. DOI 10.1007/s10107-008-0234-9Google 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, Ser. A (2006) 106(3):491–511Crossref, 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–65Crossref, 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., Pisinger D. Subset-row inequalities applied to the vehicle-routing problem with time windows. Oper. Res. (2008) 56(2):497–511Link, Google 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
• Letchford A. N., Salazar González J. J. Projection results for vehicle routing. Math. Programming, Ser. B (2006) 105:251–274Crossref, Google Scholar
• Li H., Lim A. A metaheuristic for the pickup and delivery problem with time windows. 13th IEEE Internat. Conf. Tools with Artificial Intelligence, ICTAI-2001 (2001) Dallas(IEEE)160–167Google Scholar
• Lu Q., Dessouky M. An exact algorithm for the multiple vehicle pickup and delivery problem. Transportation Sci. (2004) 38(4):503–514Link, Google Scholar
• Lysgaard J. Reachability cuts for the vehicle routing problem with time windows. Eur. J. Oper. Res. (2006) 175(1):210–223Crossref, Google Scholar
• Naddef D., Rinaldi G., Toth P., Vigo D. Branch-and-cut algorithms for the capacitated VRP. The Vehicle Routing Problem, Vol. 9. SIAM Monographs on Discrete Mathematics and Applications (2002) (SIAM, Philadelphia) 53–84Google 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
• Righini G., Salani M. New dynamic programming algorithms for the resource constrained elementary shortest path problem. Networks (2008) 51(3):155–170Crossref, Google Scholar
• Ropke S. Heuristic and exact algorithms for vehicle routing problems. (2005) . Doctoral dissertation, Department of Computer Science, University of Copenhagen, CopenhagenGoogle Scholar
• Ropke S., Cordeau J.-F. Branch-and-cut-and-price for the pickup and delivery problem with time windows. (2008) . Technical Report CIRRELT-2008–33, HEC Montréal, Montréal, Quebec, CanadaGoogle Scholar
• Ropke S., Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Sci. (2006) 40(4):455–472Link, Google Scholar
• Ropke S., Cordeau J.-F., Laporte G. Models and branch-and-cut algorithms for pickup and delivery problems with time windows. Networks (2007) 49(4):258–272Crossref, Google Scholar
• Ruland K. S., Rodin E. Y. The pickup and delivery problem: Faces and branch-and-cut algorithm. Comput. Math. Appl. (1997) 33(12):1–13Crossref, Google Scholar
• Salani M. Branch-and-price algorithms for vehicle routing problems. (2005) . Ph.D. dissertation, Università of Milan, MilanGoogle Scholar
• Savelsbergh M. W. P., Sol M. The general pickup and delivery problem. Transportation Sci. (1995) 29(1):17–29Link, Google Scholar
• Savelsbergh M. W. P., Sol M. DRIVE: Dynamic routing of independent vehicles. Oper. Res. (1998) 46(4):474–490Link, Google Scholar
• Shaw P. Using constraint programming and local search methods to solve vehicle routing problems. CP-98 Fourth Internat. Conf. Principles and Practice of Constraint Programming (1998) 1520(Springer-Verlag, Berlin) 417–431Lecture Notes in Computer ScienceGoogle Scholar
• Sigurd M., Pisinger D., Sig M. Scheduling transportation of live animals to avoid the spread of diseases. Transportation Sci. (2004) 38(2):197–209Link, Google Scholar
• Sol M. Column generation techniques for pickup and delivery problems. (1994) . Unpublished doctoral dissertation, Technische Universiteit Eindhoven, Eindhoven, The NetherlandsGoogle Scholar
• Solomon M. M. Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. (1987) 35(2):254–265Link, Google Scholar
• Toth P., Vigo D.The Vehicle Routing Problem, Vol. 9, SIAM Monographs on Discrete Mathematics and Applications (2002) (SIAM, Philadelphia) Google Scholar
• Wolsey L. A. Wiley-Interscience series in discrete mathematics. Integer Programming (1998) (Wiley-Interscience, New York) Google Scholar
• Xu H., Chen Z.-L., Rajagopal S., Arunapuram S. Solving a practical pickup and delivery problem. Transportation Sci. (2003) 37(3):347–364Link, Google Scholar