A Hybrid Exact Algorithm for the TSPTW

References

• Applegate D., Bixby R. E., Chvátal V., Cook W. On the solution of traveling salesman problems. Documenta Mathematica (1998) 645–656Extra Volume ICM IIIGoogle Scholar
• Ascheuer N.Hamiltonian Path Problems in the On-line Optimization of Flexible Manufacturing Systems (1995) . PhD thesis Technische Universität Berlin, Berlin, GermanyGoogle Scholar
• Ascheuer N., Fischetti M., Grötschel M. A polyhedral study of the asymmetric travelling salesman problem with time Windows. Networks (2000) 36:69–79Crossref, Google Scholar
• Ascheuer N., Fischetti M., Grötschel M. Solving asymmetric travelling salesman problem with time windows by branch-and-cut. Mathematical Programming (2001) 90:475–506Crossref, Google Scholar
• Baker E. K. An exact algorithm for the time-constrained travelling salesman problem. Operations Research (1983) 31:938–945Link, Google Scholar
• Balas E., Fischetti M., Pulleyblank W. The precedence constrained asymmetric travelling salesman problem. Mathematical Programming (1995) 68:241–265Crossref, Google Scholar
• Balas E., Simonetti N. Linear time dynamic programming algorithms for new classes of restricted TSPs: a computational study. INFORMS Journal on Computing (2001) 13:56–75Link, Google Scholar
• Baptiste P., Le Pape C., Nuijten W. Incorporating efficient operations research algorithms in constraint-based scheduling. Proceedings of the 1st International Joint Workshop on Artificial Intelligence and Operations Research (1995) June 6–10TimberlineGoogle Scholar
• Benoist T., Laburthe F., Rottembourg B. Lagrange-relaxation and constraint programming collaborative schemes for the travelling tournament problems. Proceedings of the CP-AI-OR'01 (2001) April 8–10IC-PARC, Ashford, UK http://www.icparc. ic.ac.uk/cpAIOR01/program.htmGoogle Scholar
• Carlier J., Pinson E. An algorithm for solving job shop scheduling. Management Science (1995) 35:164–176Link, Google Scholar
• Carpaneto G., Martello S., Toth P. Algorithms and codes for the assignment problem. Annals of Operations Research (1988) 13:193–223Crossref, Google Scholar
• Caseau Y., Koppstein P. A rule-based approach to a time-constrained traveling sales-man problem. Proceedings of the 2nd International Symposium of Artificial Intelligence and Mathematics (1992) Fort Lauderdale, FLGoogle Scholar
• Caseau Y., Laburthe F., Hentenryck P. Van. Improved CLP scheduling with task intervals. Logic Programming—Proceedings of the 1994 International Conference on Logic Programming (1994) (MIT Press, Cambridge, MA) 369–383Google Scholar
• Caseau Y., Laburthe F. Cumulative scheduling with task intervals. Proceedings of the JICSLP'96 (1996) September 2–6Bonn, Germany:363–377Google Scholar
• Caseau Y., Laburthe F., Naish L. Solving small TSPs with constraints. Logic Programming-Proceedings of the 1994 International Conference on Logic Programming (1997) (MIT Press, Cambridge, MA) 316–330Crossref, Google Scholar
• Christofides N., Mingozzi A., Toth P. State space relaxation procedures for the computation of bounds to routing problems. Networks (1981) 11:145–164Crossref, Google Scholar
• Dell′Amico M., Martello S., Dell′Amico M., Maffioli F., Martello S. Linear assignment. Annotated Bibliographies in Combinatorial Optimization (1997) (Wiley, Chichester, UK) 355–371Google Scholar
• Desrochers M., Desrosiers J., Solomon M. M. A new optimization algorithm for the vehicle routing problem with time windows. Operations Research (1992) 40:342–354Link, Google Scholar
• Desrosiers J. Y. Dumas, Solomon M. M., Soumis F., Ball M. O., Magnanti T. L., Monma C. L., Nemhauser G. L. Time constrained routing and scheduling. Network Routing (1995) (Elsevier, Amsterdam, The Netherlands) 35–139Crossref, Google Scholar
• Dumas Y., Desrosiers J., Gelinas E., Solomon M. M. An optimal algorithm for the travelling salesman problem with time windows. Operations Research (1995) 43:367–371Link, Google Scholar
• Fischetti M., Toth P. A polyhedral approach to the Asymmetric Traveling Salesman Problem. Management Science (1997) 43:1520–1536Link, Google Scholar
• Focacci F., Lodi A., Milano M., Jaffar J. Cost-based domain filtering. Principle and Practice of Constraint Programming—CP'99 LNCS (1999a) (Springer-Verlag, Berlin, Germany) 189–203Crossref, Google Scholar
• Focacci F., Lodi A., Milano M., Schreye D. De. Solving TSP with time windows with constraints. Logic Programming—Proceedings of the 1999 International Conference on Logic Programming (1999b) (MIT Press, Cambridge, MA) 515–529Google Scholar
• Focacci F., Lodi A., Milano M., Dechter R. Cutting planes in constraint programming: a hybrid approach. Principle and Practice of Constraint Programming—CP 2000 (2000) (Springer-Verlag, Berlin, Germany) 187–201LNCS 1894Crossref, Google Scholar
• Focacci F., Lodi A., Milano M. Embedding relaxations in global constraints for solving TSP and TSPTW. Ann. Math. Artificial Intelligence (2002) 34:291–311Crossref, Google Scholar
• Garey M. R., Johnson D. S.Computers and Intractability: a Guide to the Theory of NP-Completeness (1979) (Freeman, San Francisco, CA) Google Scholar
• Grötschel M., Lovász L., Schrijver A. J.Geometric Algorithms and Combinatorial Optimization (1988) (Wiley, New York) Crossref, Google Scholar
• ILOGILOG Scheduler 4.4 (2000a) (Reference Manual, Paris, France) Google Scholar
• ILOGILOG Solver 4.4 (2000b) (Reference Manual, Paris, France) Google Scholar
• Johnson D. S., McGeoch L. A., Aarts E., Lenstra J. K. The traveling salesman problem: a case study. Local Search in Combinatorial Optimization (1997) (Wiley, Chichester, UK) 215–310Google Scholar
• Jünger M., Rinaldi G., Thienel S. Practical performance of efficient minimum cut algorithms. Algorithmica (2000) 26:172–195 http://www.informatik.uni-koeln.de/ls_juenger/projects/mincut.htmlCrossref, Google Scholar
• Langevin A., Desrochers M., Desrosiers J., Soumis F. A two-commodity flow formulation for the traveling salesman and makespan problem with time windows. Networks (1993) 23:631–640Crossref, Google Scholar
• Mingozzi A., Bianco L., Ricciardelli S. Dynamic programming strategies for the travelling salesman problem with time windows and precedence constraints. Operations Research (1997) 45:365–377Link, Google Scholar
• Padberg M., Rinaldi G. An efficient algorithm for the minimum capacity cut problem. Mathematical Programming (1990) 47:19–36Crossref, Google Scholar
• Pesant G., Gendreau M., Potvin J.-Y., Rousseau J. M. An exact constraint logic programming algorithm for the travelling salesman problem with time windows. Transportation Science (1998) 32:12–29Link, Google Scholar
• Pesant G., Gendreau M., Potvin J.-Y., Rousseau J. M. On the flexibility of constraint programming models: from single to multiple Time Windows for the travelling salesman problem. European Journal of Operational Research (1999) 117:253–263Crossref, Google Scholar
• Régin J. C. A filtering algorithm for constraints of difference in CSPs. Proceedings of the 12th National Conference on Artificial Intelligence—AAAI'94 (1994) (MIT Press, Cambridge, MA) 362–367Google Scholar
• Rochat Y., Taillard E. D. Probabilistic diversification and intensification in local search for Vehicle Routing. Journal of Heuristics (1995) 1:147–167Crossref, Google Scholar
• Savelsberg M. W. P. Local search in routing problems with time windows. Annals of Operations Research (1985) 4:285–305Crossref, Google Scholar
• Sellmann M., Fahle T. CP-based lagrangean relaxation for a multimedia application. Proceedings of CP-AI-OR'01 (2001) April 8–10IC-PARC, Ashford, UK http://www.icparc.ic.ac.uk/cpAIOR01/program.htmGoogle Scholar
• Solomon M. M. Algorithms for the vehicle routing and scheduling problem with time window constraints. Operations Research (1987) 35:254–265Link, Google Scholar
• Taillard E. D., Badeau P., Gendreau M., Guertin F., Potvin J.-Y. A new neighborhood structure for the vehicle routing problems with time windows. (1995) . Publication CRT-95-66, Centre de Recherche sur les Transports, Université de Montréal, Montréal, Quebec, CanadaGoogle Scholar