FLEXMAP-a neural network for the traveling salesman problem with linear time and space complexity

The authors present a self-organizing 'neural' network for the traveling salesman problem. It is partly based on the model of Kohonen. The proposed approach differs from former work in this direction as no ring structure with a fixed number of elements is used. Instead a small initial structure is enlarged during a distribution process. This makes it possible to replace the central search step, which normally needs time O(n), by a local procedure that needs time O(1). Since the total number of search steps that must be performed is O(n) the runtime of the model scales linearly with problem size. This is better than every known neural or conventional algorithm. The path lengths of the solutions generated are less than 10% longer than the optimum solutions of solved problems from the literature.<
>