On the Performance of Heuristics on Finite and Infinite Fractal Instances of the Euclidean Traveling Salesman Problem

References

• Amini M. , Racer M. J. A Rigorous Computational Comparison of Alternative Solution Methodologies for the Generalized Assignment Problem. Management Science (1994) 40 868 890 Link, Google Scholar
• Barr R. S. , Golden B. L. , Kelly J. P. , Resende M. G. C. , Stewart W. Designing and Reporting on Computational Experiments with Heuristic Methods. Journal of Heuristics (1995) 1 9 32 Crossref, Google Scholar
• Beardwood J. , Halton J. H. , Hammersley J. M. The Shortest Path through Many Points. Proceeding of the Cambridge Philosophical Society (1959) 55 299 327 Crossref, Google Scholar
• Bentley J. L. Experiments on Traveling Salesman Heuristics. First Annual ACM-SIAM Symposium on Discrete Algorithms (1990) (ACM Press, San Francisco, CA) 91 90 Google Scholar
• Bentley J. L. Fast Algorithms for Geometric Traveling Salesman Problem. ORSA Journal on Computing (1992) 4 387 411 Link, Google Scholar
• Bertsimas D. , Grigni M. Worst-Case Examples for the Spacefilling Curve Heuristic for the Euclidean Travelling Salesman Problem. Operations Research Letters (1989) 8 241 244 Crossref, Google Scholar
• Bonomi E. , Lutton J. L. The N-city Travelling Salesman Problem and the Metropolis Algorithm. SIAM Review (1984) 26 551 568 Crossref, Google Scholar
• Christofides N. Worst-Case Analysis of a New Heuristic for the Traveling Salesman Problem. (1976) (Carnegie Mellon University, Pittsburg, PA) . Report 388 Google Scholar
• Finch S. Traveling Salesman Constants' page. (1997) . At http://www.mathsoft.com/asolve/constant/sales/sales.html Google Scholar
• Fredman M. L. , Johnson D. S. , McGeoch L. A. , Ostheimer G. Data Structures for Traveling Salesmen. Journal of Algorithms (1995) 18 432 479 Crossref, Google Scholar
• Toulouse G. How ‘Frustration' Set In. Physics Today (1989) 42 97 Crossref, Google Scholar
• Hilbert D. Über die stetige Abbildung einer Linie Auf ein Flächenstück. Mathematische Annalen (1891) 38 459 460 Crossref, Google Scholar
• Hooker J. N. Needed: An Empirical Science of Algorithms. Operations Research (1994) 42 201 212 Link, Google Scholar
• Hooker J. N. Testing Heuristics: We have it all Wrong. Journal of Heuristics (1996) 1 33 42 Crossref, Google Scholar
• Hunt H. B. , Marathe M. V. , Radhakrishnan V. , Ravi S. S. , Rosenkrantz D. J. , Stearns R. E. Approximation Schemes Using L-reductions. Proceeding of the 14th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (1994) (Springer Verlag, Heidelberg) 342 353 . Lecture Notes in Computer Science Crossref, Google Scholar
• Bartholdi J. J. , Platzman L. K. On O(n log(n)) Planar Traveling Salesman Problem Heuristic Based on Spacefilling Curves. Operations Research Letters (1982) 1 121 125 Crossref, Google Scholar
• Bartholdi J. J. , Platzman L. K. A Fast Heuristic Based on Spacefilling curves for Minimum-Weight Matching in the Plane. Information Processing Letters (1983) 17 177 180 Crossref, Google Scholar
• Bartholdi J. J. , Platzman L. K. Heuristics Based on Spacefilling Curves for Combinatorial Problems in Euclidean Space. Management Science (1988) 34 291 305 Link, Google Scholar
• Iwama K. , Miyazaki S. SAT-variable Complexity of Hard Combinatorial Problems. Proceedings of the 13th IFIP World Computer Congress (1994) (Elsevier, Amsterdam) 253 258 Google Scholar
• Johnson D. S. Local Optimization and the Traveling Salesman Problem. Proceedings of the 17th Colloquium on Automata, Languages and Programming (1990) (Springer-Verlag, Berlin) 446 461 . Lecture Notes in Computer Science Crossref, Google Scholar
• Johnson D. S. , McGeoch L. A. , Aarts E. H. L. , Lenstra J. K. The Traveling Salesman Problem: A Case Study in Local Optimization. Local Search in Combinatorial Optimization (1997) (John-Wiley and Sons, Ltd.) 215 310 Google Scholar
• Johnson D. S. , McGeoch L. A. , Rothberg E. E. Asymptotic Experimental Analysis for the Held-Karp Traveling Salesman Bound. Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms (1996) (ACM Press, San Francisco) 341 350 Google Scholar
• Kanada Y. Methods of Parallel Processing of Constraint Satisfaction Using CCM—A Model for Emergent Computation. Proceedings of the 9th Meeting of Special Interest Group on Parallel Processing for Artificial Intelligence, Japan Society for Artificial Intelligence (1996) . Available from http://www.rwcp.or.jp/people/yk/Papers/CCM-papers.html Google Scholar
• Lawler E. L. , Lenstra J. K. , Rinnooy Kan A. H. G. , Shmoys D. B. The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization (1985) (Wiley-Interscience, Chichester, U.K) Google Scholar
• Lin S. Computer Solutions of the Traveling Salesman Problem. Bell System Technology Journal (1965) 44 2245 2269 Crossref, Google Scholar
• Lin S. , Kernighan B. W. An Effective Heuristic Algorithm for the Traveling Salesman Problem. Operations Research (1973) 21 498 516 Link, Google Scholar
• Lindenmayer A. Mathematical Models for Cellular Interaction in Development, Parts I and II. Journal of Theoretical Biology (1968) 18 280 315 Crossref, Google Scholar
• Mariano A. , Moscato P. , Norman M. G. Arbitrarily Large Planar ETSP Instances with Known Optimal Tours. Pesquisa Operacional (1995) 15 89 96 Google Scholar
• McGeoch C. C. Analyzing Algorithms by Simulation: Variance Reduction Techniques and Simulation Speedup. ACM Computing Surveys (1992) 24 195 212 Crossref, Google Scholar
• McGeoch C. C. Challenges in Algorithm Simulation. INFORMS Journal on Computing (1996) 8 27 28 Link, Google Scholar
• McGeoch C. C. Towards an Experimental Method for Algorithm Simulation. INFORMS Journal on Computing (1996) 8 1 15 Link, Google Scholar
• Moscato P. An Introduction to Population Approaches for Optimization and Hierarchical Objective Functions: The Role of Tabu Search. Annals of Operations Research (1993) 41 85 121 Crossref, Google Scholar
• Norman M. G. , Moscato P. The Euclidian Traveling Salesman Problem and a Space-Filling Curve. Chaos, Solitons and Fractals (1995) 6 389 397 Crossref, Google Scholar
• Peano G. Sur une Courbe, qui Remplit Toute une Aire Plane. Mathematische Annalen (1890) 36 157 160 Crossref, Google Scholar
• Peitgen H. O. , Jürgens H. , Saupe D. Chaos and Fractals New Frontiers of Science (1992) (Springer-Verlag, New York) Crossref, Google Scholar
• Platzman L. K. , Bartholdi J. J. Spacefilling Curves and the Planar Travelling Salesman Problem. Journal of the ACM (1989) 36 719 737 Crossref, Google Scholar
• Rardin R. , Tovey C. , Pilcher M. , Pardalos P. Analysis of a Random Cut Test Instance Generator for the TSP. Complexity in Numerical Optimization (1993) (World Scientific, Singapore) 387 405 Crossref, Google Scholar
• Reinelt G. TSPLIB—A Traveling Salesman Problem Library. ORSA Journal on Computing (1991) 3 376 384 Link, Google Scholar
• Sahni S. , Gonzalez T. P-Complete Approximation Problems. Journal of the ACM (1976) 23 555 565 Crossref, Google Scholar
• Sanchis L. On the Complexity of Test Case Generation for NP-hard Problems. Information Processing Letters (1990) 36 135 140 Crossref, Google Scholar
• Sierpinski W. Sur une Courbe Cantorienne dont tout Point est un Point de ramification. C. R. Académie, Paris (1915) 160 302 Google Scholar
• Stein D. Scheduling Dial-a-Ride Transportation Systems: An Asymptotic Approach (1977) . PhD thesis, Harvard University, Cambridge, MA Google Scholar
• Toulouse G. Theory of the Frustration Effect in Spin Glasses I. Communications on Physics (1977) 2 115 Google Scholar
• von Koch H. Sur Une Courbe Continue Sans Tangente, Obtenue par une Construction Géometrique Élémentaire. Arkiv för Matematik (1904) 1 681 704 Google Scholar
• Williamson D. P. , Goemans M. X. Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances. INFORMS Journal on Computing (1996) 8 29 40 Link, Google Scholar