Linear Time Dynamic-Programming Algorithms for New Classes of Restricted TSPs: A Computational Study

References

• Applegate D., Bixby R. E., Chvatal V., Cook W. J.A new paradigm for finding cutting planes in the TSP (1997) (International Symposium on Mathematical Programming, Lausanne, Switzerland) Google Scholar
• Ascheuer N., Fischetti M., Grötschel M.Solving ATSP with time windows by branch-and-cut (1997) (ZIB Berlin). Technical reportGoogle Scholar
• Baker E. An exact algorithm for the time-constrained traveling salesman problem. Operations Research (1983) 31:938–945Link, Google Scholar
• Balas E. New classes of efficiently solvable generalized traveling salesman problems. Annals of Operations Research (1999) 86:529–558Crossref, Google Scholar
• Balas E. The prize collecting traveling salesman problem. Networks (1989) 19:621–636Crossref, Google Scholar
• Burkard R. E., Deineko V. G., van Dal R., van der Veen J. A. A., Woeginger G. J.Well solvable special cases of the TSP: a survey (1997) (Technical University, Graz, Austria) . SFB Report 52Google Scholar
• Dumas Y., Desrosiers J., Gelinas E., Solomon M. An optimal algorithm for the traveling salesman problem with time windows. Operations Research (1995) 43:367–371Link, Google Scholar
• Gendreau M., Hertz A., Laporte G., Stan M.A generalized insertion heuristic for the traveling salesman problem with time windows (1995) (Centre de Recherche sur les Transports, Université de Montréal, Montréal, PQ, Canada) . CRT-95-07Google Scholar
• Gilmore P. C., Lawler E. L., Shmoys D., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. Well-solved special cases. The Traveling Salesman Problem: A Guided Tour to Combinatorial Optimization (1985) (Wiley, New York) 87–145Google Scholar
• Johnson D. S., McGeoch L. A., Aarts E. H. L., Lenstra J. K. L. The traveling salesman problem: a case study in local optimization. Local Search in Combinatorial Optimization (1997) (Wiley, New York) 215–311Google Scholar
• Jünger M., Reinelt G., Rinaldi G., Ball M., Magnanti T., Monma C., Nemhauser G. The traveling salesman problem. Network Models (1995) (Elsevier)225–330Crossref, Google Scholar
• Kanellakis P., Papadimitriou C. Local search for the traveling salesman problem. Operations Research (1980) 28:1086–1099Link, Google Scholar
• Lin S., Kernighan B. W. An effective heuristic algorithm for the traveling salesman problem. Operations Research (1973) 21:495–516Link, Google Scholar
• Martin O., Otto S. W., Felten E. W. Large step markov chains for the TSP incorporating local search heuristics. Operations Research Letters (1992) 11:219–225Crossref, Google Scholar
• Or I.Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking (1992) (Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL) . Ph.D. ThesisGoogle Scholar
• Potvin J. Y., Bengio S.A genetic approach to the vehicle routing problem with time windows (1993) (Centre de Recherche sur les Transports, Université de Montréal, Montreal, PQ, Canada) . CRT-93-5Google Scholar
• Reinelt G. (1997) . Personal communicationGoogle Scholar
• Repetto B. (1996) . Personal communicationGoogle Scholar
• Repetto B.Upper and Lower Bounding Procedures for the Asymmetric Traveling Salesman Problem (1994) (GSIA, Carnegie Mellon University, Pittsburgh, PA) . Ph.D. ThesisGoogle Scholar
• Solomon M. Algorithms for vehicle routing and scheduling with time window constraints. Operations Research (1987) 35:254–265Link, Google Scholar
• Stan M. (1997) . Personal communicationGoogle Scholar
• Tama J.Polyhedral Aspects of Scheduling Problems with an Application to the Time-Constrained Traveling Salesman Problem (1990) (GSIA. Carnegie Mellon University, Pittsburgh, PA) . Ph.D. thesisGoogle Scholar
• Van der Veen A. A.Solvable Cases of the Traveling Salesman Problem with Various Objective Functions (1992) (University of Groningen, Gronigen, The Netherlands) . Ph.D. DissertationGoogle Scholar