An Exact Constraint Logic Programming Algorithm for the Traveling Salesman Problem with Time Windows

References

• Aho A. V. , Hopcroft J. E. , Ullman J. D. Data Structures and Algorithms (1983) (Addison-Wesley, Reading, Mass) Google Scholar
• Baker E. An exact algorithm for the time constrained traveling salesman problem. Opns. Res. (1983) 31 938 945 Link, Google Scholar
• Baptiste P. , Le Pape C. , Nuijten W. Incorporating efficient operations research algorithms in constraint-based scheduling. Proc. 1st Internat. Joint Workshop Artificial Intelligence and Operations Research (1995) Timberline Lodge, Oregon Google Scholar
• Carlier J. , Pinson E. An algorithm for solving the job shop problem. Mgmt. Sci. (1989) 35 164 176 Link, Google Scholar
• Caseau Y. , Koppstein P. A rule-based approach to a time-constrained traveling salesman problem. Symposium on Artificial Intelligence and Mathematics (1993) . 1992. Also, Bellcore Technical Memorandum Google Scholar
• Caseau Y. , Laburthe F. , van Hentenryck P. Improved CLP scheduling with task intervals. Proc. 11th Internat. Conf. Logic Programming (1994) (MIT Press, Cambridge, Mass) Google Scholar
• Christofides N. , Mingozzi A. , Toth P. State space relaxation procedures for the computation of bounds to routing problems. Networks (1981) 11 145 164 Crossref, Google Scholar
• Desrochers M. , Desrosiers J. , Solomon M. M. A new optimisation algorithm for the vehicle routing problem with time windows. Opns. Res. (1992) 40 342 354 Link, Google Scholar
• Desrosiers J. , Dumas Y. , Solomon M. M. , Soumis F. , Ball M. O. , Magnanti T. L. , Monma C. L. , Nemhauser G. L. Time constrained routing and scheduling. Network Routing, Handbooks in Operations Research and Management Science (1995) 8 (North-Holland, Amsterdam) 35 139 Google Scholar
• Diaz D. , Codognet P. A minimal extension of the WAM for clp(FD). Proc. 10th Internat. Conf. Logic Programming (1993) (MIT Press, Cambridge, Mass) 774 790 Google Scholar
• Dincbas M. , van Hentenryck P. , Simonis H. , Aggoun A. , Graf T. , Berthier F. The constraint logic programming language CHIP. Proc. Internat. Conf. 5th Generation Computer Systems (1988) (Ohmsha Publishers, Tokyo) 693 702 Google Scholar
• Dumas Y. , Desrosiers J. , Gélinas É. , Solomon M. M. An optimal algorithm for the traveling salesman problem with time windows. Opns. Res. (1995) 43 367 371 Link, Google Scholar
• European Computer-Industry Research Center ECLiPSe 3.5.1 User Manual. (1995) (Munich, Germany) Google Scholar
• Gendreau M. , Hertz A. , Laporte G. New insertion and postoptimization procedures for the traveling salesman problem. Opns. Res. (1992) 40 1086 1094 Link, Google Scholar
• Gendreau M. , Hertz A. , Laporte G. , Stan M. A generalized insertion heuristic for the traveling salesman problem with time windows. (1995) . Publication CRT-95-07, Centre de recherche sur les transports, Université de Montréal, Montréal Google Scholar
• Haralick R. M. , Elliott G. L. Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence (1980) 14 263 313 Crossref, Google Scholar
• Jaffar J. , Lassez J.-L. constraint logic programming. (1986) . Technical report 86/73Department of Computer Science, Monash University, June. (An abstract appears in the Proceedings of the 14th ACM Symposium on Principles of Programming Languages, Munich (January 1987), 111–119.) Google Scholar
• Jaffar J. , Lassez J.-L. , Wada E. , Furukawa K. , Tanaka H. , Fujisaki T. From unification to constraints. Proc. 6th Japanese Conference Logic Programming (1987) June Tokyo Google Scholar
• Jaffar J. , Maher M. J. Constraint logic programming: A survey. J. Logic Program. (1994) 19/20 503 581 Crossref, Google Scholar
• Kanellakis P. C. , Kuper G. M. , Revesz P. Z. Constraint query languages. J. Comput. System Sci. (1995) 51 26 52 Crossref, Google Scholar
• Langevin A. , Desrochers M. , Desrosiers J. , Soumis F. A two-commodity flow formulation for the traveling salesman and makespan problems with time windows. Networks (1993) 23 631 640 Crossref, Google Scholar
• Mingozzi A. , Bianco L. , Ricciardelli S. Dynamic programming strategies for the traveling salesman problem with time window and precedence constraints. (1993) . Technical report, Department of Mathematics, University of Bologna Google Scholar
• Pesant G. , Gendreau M. A view of local search in constraint programming. Principles and Practice of Constraint Programming—CP96: Proc. 2nd Internat. Conf., Lecture Notes in Computer Science (1996) 1118 (Springer-Verlag, Berlin) 353 366 Crossref, Google Scholar
• Potvin J.-Y. , Kervahut T. , Garcia B. L. , Rousseau J.-M. A tabu search heuristic for the vehicle routing problem with time windows. (1993) . Publication CRT-855, Centre de recherche sur les transports, Université de Montréal, Montréal Google Scholar
• Puget J.-F. Object-oriented constraint programming for transportation problems. Proc. Advanced Software Technology in Air Transport (ASTAIR) (1992) Google Scholar
• Pujet J.-F. A C++ implementation of CLP. (1994) . Technical report 94-01, ILOG S.A., Gentilly, France Google Scholar
• Rochat Y. , Taillard É. Probabilistic diversification and intensification in local search for vehicle routing. J. Heuristics (1995) 1 147 167 Crossref, Google Scholar
• Saraswat V. A. Concurrent constraint programming languages. (1989) . Ph.D. thesis, Carnegie-Mellon University Google Scholar
• Savelsberg H. M. W. P. Local search in routing problems with time windows. Ann. Opns. Res. (1985) 4 285 305 Crossref, Google Scholar
• Savelsbergh M. W. P. The vehicle routing problem with time windows: Minimizing route duration. ORSA J. Comput. (1992) 4 146 154 Link, Google Scholar
• Solomon M. M. Algorithms for the vehicle routing and scheduling problem with time window constraints. Opns. Res. (1987) 35 254 265 Link, Google Scholar
• Taillard É. , Badeau P. , Gendreau M. , Guertin F. , Potvin J.-Y. A new neighborhood structure for the vehicle routing problem with time windows. (1995) . Publication CRT-95-66, Centre de recherche sur les transports, Université de Montréal, Montréal Google Scholar
• Thangiah S. R. , Osman I. H. , Sun T. Hybrid genetic algorithms, simulated annealing and tabu search methods for vehicle routing problems with time windows. (1994) . Technical report UKC/OR94/4, Institute of Mathematics and Statistics, University of Kent, Canterbury, UK Google Scholar
• Tsang E. Foundations of Constraint Satisfaction (1993) (Academic Press, London) Google Scholar
• van Hentenryck P. , Saraswat V. , Deville Y. Design, implementations and evaluation of the constraint language cc(FD). (1993) . Technical report CS-93-02, Brown University Google Scholar
• Waltz D. L. Generating semantic descriptions from drawings of scenes with shadows. (1972) . Technical report AI-TR-271, MIT Google Scholar