Traveling Salesman Problem (TSP) in Excel/VBA. The use of graphics in Informatics II class

The most advanced topic that has been addressed in our Informatics II for non-IT students: VBA, class is the Traveling Salesman Problem (in this file). As TSP is NP-complete, as far as its complexity is concerned, problems such as traversing all the 24978 towns of Sweden are solved. Our problem is a very simple one – of passing through 16 cities.

The Waites family project VisualBots has created an Excel Add-In by that name. My thanks go to their project regarding the TSP – from which I borrowed the algorithm that is used. The algorithm used is simulated annealing, which is a heuristic that, with a decreasing probability, chooses a longer total distance – in order to avoid getting stuck in a local minima. The VisualBots is an add-in that gives Excel additional graphical capabilities.

With a bit different accentuation it has also been a goal in our university to rely on Excel’s graphical objects. For years the Informatics II for non-IT students has used those to convey the essentials of programming with VBA. Lately, with the advent of educational programming languages, such as Scratch, our approach has been validated, as courses like Harvard’s CS50 also start with graphical objects now. In the present example graphical objects are complemented with Excel’s charts displaying the dynamics of the solution process.