A Neural Network to solve Travelling Salesman Problems in Excel

Artificial Intelligence in Microsoft Excel: watch a Neural Network solving a Travelling Salesman Problem

869 words, ~4 minutes read

Neural Network solving TSPs in Excel - IntroTerms like Artificial Intelligence, Machine Learning, Deep Learning and (Artificial) Neural Networks are all over the place nowadays.

If you are reading Tech News, Data Science blogs or your LinkedIn feed, it will be little short of a miracle, if you don’t see one of those expressions at least once.

This is just the revival of those techniques, though. Neural Networks, for one, have been around for many years. In the mid 1990s (!), I did some research and wrote my thesis about Artificial Neural Networks. We even had a blog post here on this topic 10 years ago: Where the rubber meets the road. For whatever reason, that article didn’t make many friends. I was always wondering why. Probably too academic and not visually appealing enough.

Now, with the recent revival of Artificial Intelligence and Neural Networks, I decided to give it another shot. Today’s post provides an updated, improved version of a Neural Network solving Travelling Salesman Problems in Microsoft Excel.

You always wanted to watch a Neural Network solving an optimization problem? If so, this article is for you. Either watch one of three videos provided in the post or download the Excel workbook and play around with it at your own speed. No add-in or third party software necessary. All you have to do is to enable macros.

The Algorithm

The Neural Network provided today is exactly the same as in the original post (Where the rubber meets the road). It 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 back in 1987.

Without going into the details of the mathematics, here is the basic idea of this approach:

Many other algorithms for solving TSPs start with one feasible solution and try to switch to better ones 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 (or adaptive ring), 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.

You can think of this ring as if it would be a rubber band. In each iteration, the Neural Network randomly selects a city, finds the nearest node on the ring and pulls the node and its neighbours towards this city. If you visualize this behaviour 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.

The Updated Version

As already stated above, the used algorithm is exactly the same as in the original post. However, I made quite a few changes in the workbook to make the handling of the model easier and the views more interesting:

Neural Network solving TSPs in ExcelThe most obvious change is the map. Instead of showing generic points in the Euclidean space, today’s workbook solves Travelling Salesman Problems through cities of the United States and provides the geospatial context with a US map in the background.

Furthermore, I simplified the dashboard:

Neural Network in Excel - User Defined ParametersOnly the most important user-selections are still available on the dashboard and only a selection of results is shown.

With that said, I did not only simplify, I also added a few helpful features:

  • With the play buttons, you can start, pause, resume and stop the algorithm at any time
  • With the two checkboxes, you can decide whether or not all cities of the US shall be shown on the map (i.e. not only the ones of the TSP) and whether or not the names of the TSP cities shall be displayed

At the bottom right of the dashboard, four charts visualize some key metrics of the algorithm during execution:

Neural Network in Excel - Additional Charts

  • a column chart shows the distribution of the cities, i.e. how often the cities are randomly selected and processed during the algorithm
  • the three line charts visualize the development of the length of the adaptive ring, the decreasing learn rate and the size of the radius, i.e. the decreasing number of nodes being moved on the ring

Now, let’s see this in action:

Watch examples right here in a video…

Here is a 10 cities TSP. The algorithm is slowed down intentionally by waiting 200 milliseconds after each step to better understand how the Neural Network works:

The next video shows how a 20 cities TSP is solved. No waiting time, but still updating the screen after each iteration:

Finally, a 100 cities TSP. The views on the dashboard are updated every 50th iteration:

… or download the workbook and have a look for yourself

Not only interested in watching the videos, but also in playing around with the model or even dissecting the code? Here you go:

Download Neural Network Solving TSP (zipped Excel workbook, 663K)

Stay tuned.

Comments

10 responses to “A Neural Network to solve Travelling Salesman Problems in Excel”

  1. Microsoft Excel Recalc Or Die Avatar

    Robert, voilà !!!!!!
    This is amazing mate! kudos all the way!
    This is a hall of fame blogpost. No less.

  2. sam Avatar
    sam

    ” For whatever reason, that article didn’t make many friends…”
    That’s because back then we excel mortals were speechless and nothing had changed is the last 10 years… we continue to remain dumbstruck
    Thanks Robert for sharing this with the world
    Sam

  3. Aleen Avatar
    Aleen

    As always, Robert rocks.
    And the reason as why your articles don’t make many friends is – You are beyond complexity and people are still at intermediate level.

  4. Ron Whale Avatar
    Ron Whale

    What a great program! I have written a number of distance calculating programs and I got thinking. It might be fun to convert the program to a warehouse distribution scenario with multiple warehouse locations and a certain number of trucks making runs. What is the shortest truck route based on the number of trucks? Where would the best location for additional warehouses be?
    I have worked with the problems presented by straight line distances. In the Western United States, there are not near as many roads as in the East. Eastern roads tend to be in a box grid formation while the West has a lot of mountains, lakes, and deserts that travelers are forced to go around. I have developed some traffic congestion and geographic detour ratios for my programs which are specific to each state. Something like that could help make the Traveling Salesman map a little more “true-to-life” as far as distance and travel time measurements are concerned.
    Thanks for the inspiration.

  5. Robert Avatar

    Ron,
    it was great to see your comment. My apologies for this late reply, I have been pretty busy the last few days.
    I fully agree with you. Solving a TSP in the Euclidean Space (i.e. as the crow flies), isn’t of great practical use. This wasn’t my intention, though. I simply wanted to visualize how a Neural Network is working and the TSP is a perfect example for this. Even if it is not “true-to-life” as you wrote with good reason.
    Your remarks about your work on traffic congestion and geographic detour ratios sound intriguing. I would love to hear more about that.

  6. global truck bloger Avatar

    A neural network to solve truck driver problem on ther traffic jams 🙂 sounds like better title

  7. AVL Avatar
    AVL

    Mm i do not have the skills or knowledge to create such wonderful macros, but i came accross your website while doing some work on implementing a “routing optimization” project.
    I am just surprised to not see any starting point. The salesman always start from its home and return to his home ? It looks like this optimization will change the start point to any city
    I will try to understand how this work and maybe use your solution to calculate some routes optimisation.
    Thanks from France

  8. Robert Avatar

    AVL,
    the classic Travelling Salesman Problem is defined as follows: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?” (source: Wikipedia).
    Since the route must return to the origin, the algorithm does not have to take into consideration which one of the cities is the starting point. After a viable solution is found, you can define any of the cities as the starting point. The route will be the same, no matter in which city you start the tour.

  9. Steve Avatar
    Steve

    This is one of a kind. Thanks! I just found your website and i’m loving the posts. The download link is down. Would you be able to repair the link?

  10. Robert Avatar

    Steve,
    I just checked and the download link works fine for me. If it does not work for you, you may try to right click on the link and select Save Target As to download.

Leave a Reply

Your email address will not be published. Required fields are marked *