A self organizing feature map for Travelling Salesman Problems implemented in Microsoft Excel
In the recent post we discussed the question whether Microsoft Excel is a viable platform for developing and testing models and algorithms for complex combinatorial optimization problems.
The Travelling Salesman Problem (TSP) is probably one of the most popular challenges in combinatorial optimization and Operations Research. Why? I suppose because it is so easy to describe, but hard to solve.
There are hundreds or even thousands of different algorithms (exact solutions or heuristics) for the basic TSP or its variants. One approach is a so called self organizing feature map also known as a Kohonen Map: an artificial neural network using unsupervised learning to solve combinatorial optimization problems.
I selected this approach not only because I have done some studies on this topic back in the 1990s, but rather because both, the problem itself and the self organizing algorithm are very well fitting for an interesting visualization model that is fun to watch working.
Today’s post describes such a self organizing feature map for Travelling Salesman Problems. I will not discuss the math in detail, but rather try to explain the approach itself, the algorithm’s mode of operation and the implementation with Microsoft Excel. As always, the result (i.e. the Microsoft Excel workbook) is provided for free download.