Fractal Instances of the Traveling Salesman Problem

There are currently four available papers on this subject.

Papers

• The Euclidean Traveling Salesman Problem and a Space-Filling Curve , M. G. Norman and P. Moscato, Chaos, Solitons and Fractals, Vol. 6, pages 389-397, 1995.
• Using L-Systems to generate arbitrarily large instances of the Euclidean Traveling Salesman Problem with known optimal tours , A. Mariano, P. Moscato and M.G Norman, ``Anales del XXVII Simposio Brasileiro de Pesquisa Operacional'', Vitoria, Brazil, 6-8 Nov. 1995.
• An Analysis of the Performance of Traveling Salesman Heuristics on Infinite-Size Fractal Instances in the Euclidean Plane. P. Moscato and M.G. Norman, first version Oct. 1994, to appear in ORSA Journal on Computing.
• Arbitrarily large planar ETSP instances with known optimal tours, by A. Mariano, P. Moscato, and M.G. Norman, expanded version of the paper presented at Vitoria, ES, Brazil, 1995. Paper accepted in the journal ``Pesquisa Operacional''.

Using L-Systems to generate TSP Instances

• Arbitrarily large planar ETSP instances with known optimal tours, by A. Mariano, P. Moscato, and M.G. Norman, expanded version of the paper presented at Vitoria, ES, Brazil, 1995. Paper accepted in the journal ``Pesquisa Operacional''.

More information about the Sierpinski constructions can be obtained from the page called Sierpinski Gasket , by Paul Bourke.

Tutorials on L-Systems

• L-systems , by David J. Wright.
• L-Systems tutorial, by David G. Green.
• Introduction to Fractals and Their Applications , by Alex Sourov.
• Two-dimensional L-Systems , by Robert M. Dickau.
• Three-dimensional L-Systems , by Robert M. Dickau.
• Using L-Systems as Graph Grammars: G2L-Systems , by E.J.W. Boers. He says that One of the advantages of this adaptation is the possibility to make use of the context dependency available in L-systems. This context is calculated by using the graph interpretation of the strings at each successive step of the rewriting mechanism. In addition: A simple proof will be given that every possible directed graph can be generated using this representation.

Software for L-Systems