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.
The Travelling Salesman Problem
As already mentioned in the introduction, the TSP is still very popular in Operations Research.
Here is the definition of a TSP from Wikipedia:
“Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once.”
As I said, the TSP is very easy to describe and to understand.
But it is hard to solve: the TSP belongs to the so called NP-complete problems, i.e. it is easy to verify any given solution for a problem, but it is assumed that there is no efficient algorithm to solve the problem. The number of possible solutions (and thus the time to find a solution) grows over-exponentially with the size of the problem:
|
Number of Cities |
Number of feasible solutions |
|
10 |
181,440 |
|
15 |
4.4E+10 |
|
20 |
6.1E+16 |
|
25 |
3.1E+23 |
|
50 |
3.0E+62 |
|
100 |
4.7E+155 |
The origin and the basic idea in a nutshell
The optimization model at hand is based on the article “an analogue approach to the travelling salesman problem using an elastic net method”, by Richard Durbin and David Willshaw published in Nature already back in 1987. As mentioned in the introduction to this post, I will not discuss the mathematics in detail, but here is the basic idea of this approach:
Many other solution approaches for TSPs start with one feasible solution and try to switch to better solutions from iteration to iteration (i.e. shorter total tour length). The approach of Durbin and Willshaw is different: they don’t start with a feasible solution. They start with an elastic net, i.e. a circle of nodes where the number of nodes is a multiple of the number of cities of the TSP. This circle is gradually deformed until it finally passes through all cities and describes a feasible and short tour for the travelling salesman. The algorithm treats this circle like a rubber band and pulls parts of it towards the cities on the map. If you visualize this behavior of the algorithm, it looks as if this rubber band is deformed and elongated until a feasible solution is found. The tension of the rubber band guarantees that dragging the rubber band complies with the objective function of the TSP, i.e. to minimize the total tour length.
Since the elastic net is more a closed ring than a net, we will call it “adaptive ring” in the following.
One iteration of the algorithm - a step by step demonstration
Step 1 - Select a random city
One of the cities is randomly selected and presented to the adaptive ring. It goes without saying that using a random generator means it is not a deterministic algorithm. Thus, you have to be aware of the fact that different runs of the algorithms might lead to different results.
Step 2 - Find the nearest node (the “winner node”)
In the next step, the algorithm loops through all nodes on the adaptive ring and finds the nearest node, i.e. the node on the ring with the smallest distance to the city randomly selected in step 1.
Step 3 - Adapt the location of the winner node
The location of the winner node is pulled towards the selected city. An algorithm parameter (the learning rate) defines how far the node will be moved. The learning rate decreases over time in order to give maximum flexibility at the beginning and to stabilize the solution in the later stages of the algorithm.
Step 4 - Adapt the location of the winner’s right neighbors
After relocating the winner node, the right neighbors of the winner are pulled towards the selected city as well. The farther they are located from the winner node, the less they are pulled towards the city and vice versa. This rule creates the “rubber band” effect and keeps the “tension” on the adaptive ring.
Step 5 - Adapt the location of the winner’s left neighbors
Analog to step 4, the locations of the winner’s left neighbors are adapted. Another parameter of the algorithm (the radius) defines the number of left and right neighbors that will be moved. Like the learning rate, this radius decreases over time and allows the adaptive ring to converge to a stable solution.
These 5 basic steps represent only one single iteration of the algorithm. After a couple of hundred or thousand iterations (depending on the size of the problem, i.e. the number of cities), the adaptive ring converges to a feasible and comparatively good solution: the cities along the ring represent a short tour visiting all cities once:
The implementation with Microsoft Excel
You guessed it: the algorithm is implemented with Microsoft Excel and VBA and all the visualizations shown above are screenshots from this Excel model.
The workbook contains 3 simple worksheets:
- Dashboard
This is the user interface of the model: select an example TSP, set the parameters of the algorithm and watch the model run, visualized with 5 standard Excel charts
- Calculation
This worksheet does the math, stores the results of the VBA code and contains the data source of the charts shown on the dashboard
- Data
The data of 8 TSP examples of different sizes from 10 to 230 cities
The complexity of the Excel model
Coming back to the question of the recent post: Is Microsoft Excel is a viable platform for the development of a complex combinatorial optimization model?
Here are the statistics of the Excel workbook:
- 1.19 MB workbook (including data of 8 different TSPs)
- 3 worksheets
- 5 Excel standard charts
- 116,802 cells in used range
- 1,633 formula cells
- 32 cell range names
- 205 lines of VBA code (excluding empty lines and comments)
Not a simple Excel workbook anymore, but for sure not the most complex one I ever did.
The best thing about it? It is all in there. If you download the workbook (download link see below), you can watch the algorithm work, easily change parameters on the dashboard and see the impacts, copy data of other TSPs to the data worksheet or even implement an alternative algorithm and compare it to the results of the elastic net. All you need is Microsoft Excel and the workbook.
One of the biggest disadvantages of using Excel and VBA is the poor performance. However, the model at hand solves a TSP with 230 cities in 65 seconds, if you turn off the screen updating. I think this is still acceptable. Though, if you have to solve a TSP with - let’s say - 20,000 cities, an Excel implementation will definitely not be a feasible option anymore. See the recent post for a detailed discussion on the pros, cons and use cases of Microsoft Excel for developing combinatorial optimization algorithms.
The Dashboard
The interactive dashboard of the model provides all input and output parameters of the algorithm and various visualizations of the algorithm on one page at a glance:
The used techniques are simple: an XY scatter chart, line charts, a column chart, a combo box, a spinner and a command button. The usual suspects, no tweaks or hacks necessary.
Download the Excel Model
Here is the free download link of the Microsoft Excel implementation of a self organizing map for Travelling Salesman Problems:
Download Self Organizing Map for TSPs (Microsoft Excel 2003, zipped 284.1K)
Acknowledgement
Many thanks go to Daniel Ferry (Excel Hero) who was kind enough to review my Excel model. Daniel, I greatly appreciate all of your precious time, your valuable inputs and the encouragement!
What’s next?
This and the recent article were the first contributions to the category “optimization” here on Clearly and Simply. I am planning to have some more posts regarding intelligent optimization techniques later this year. The upcoming articles, however, will discuss visualizations, Tableau tips and project management topics again.
Stay tuned.