Travelling Salesman Problem in JavaScript Canvas
Posted by joe | Filed under Javascript, Software Development
A long a time ago – when I was student at university – I wrote a small, but somewhat impressing program. It is a heuristic (and thus suboptimal) solver for the travelling salesman problem, using an algorithm from the field of neuronal network which is called a self organizing feature map
You can read details on the neuronal network and the algorithm in my university paper self organising maps based on a Kohonen neuronal network (in german) or follow the literature references given.
Now I took the chance of a rainy winter evening to convert the original code to JavaScript and render the output with the HTML5 Canvas 2D API – for me the chance to learn and keep up with the different HTML5 specs which have now step by step have become reality. So first have a look on the application:
If you look at the JavaScript code, the part which takes care of the painting is remarkable simple, consisting of 3 sections.
Creating the drawing context on the canvas element:
elem = document.getElementById('#canvas');
ctx = elem.getContext('2d');
height = elem.height;
width= elem.width;
Drawing the cities as filled circles:
var centerX = city.x * width + 0.5;
var centerY = height - city.y * height + 0.5;
ctx.fillStyle = "#C06060";
ctx.beginPath();
ctx.arc(centerX, centerY, 3, 0, Math.PI*2, true);
ctx.closePath();
ctx.fill();
and drawing the candidates and connecting them to a tour:
ctx.strokeStyle = "#80D080";
ctx.beginPath();
// move to first node
n = neurons.start;
ctx.moveTo(n.x * width + 0.5, height - n.y * height + 0.5);
for each node n
// each node as a small dot
var centerX = n.x * width + 0.5;
var centerY = height - n.y * height + 0.5;
ctx.fillStyle = "#208020";
ctx.fillRect(centerX, centerY, 1, 1);
// draw a line to the next node
ctx.lineTo(n.right.x * width + 0.5, height - n.right.y * height + 0.5);
// draw all lines
ctx.lineWidth = 1;
ctx.stroke();
ctx.closePath();
You can checkout the source code here: https://github.com/kifj/tsp-js
January 11, 2015 at 12:26 am
Johanes, this is a great piece of code.
I’m really impressed. The algorithm is damn effective. All those clove hitches (aka sub optimalities) can be solved via “moving window” of 3 , 4 or 5 isolated vertices. Even with this improvement (coz it is finite) the code would be extremely fast as #nodes grows.
All my regards, Alex
February 3, 2016 at 6:06 pm
[…] of Traveling Salesman Problem or TSP. there are various ways to address it, often involving neural networks or genetic algorithm (I believe the latter is more robust) but there’s another approach […]
April 7, 2016 at 9:34 am
Johanes,
I’m really impress by the effectivness of you algorithm. I have been looking for a javascrip implementation for a long time.
It’s indeed suboptimal, but as metioned by Alex it can be solved quite easily .
Thanks for your contribution.
Best regards,
Pierre
May 25, 2016 at 9:29 pm
Hello. I’m new to all this, but I want to learn. Why exactly is it suboptimal? And what would make it optimal? I didn’t understand the “moving windows” reference, nor am I familiar with neural networks or genetic algorithms although I am about to research them right now.
Any help in understanding would be greatly appreciated.
Thanks!
December 14, 2016 at 5:27 pm
Hi Joe, I came across your blog when I was searching for TSP implementation in javascript.
I am making a project for my college. Can you please mail me the javascript code to the mail specified above.
Thanks for the help
December 15, 2016 at 7:09 pm
basically everything is on the web page, but hard to find in all that WordPress code. I sent you a mail, with the HTML pieces. The JavaScript is linked and you can download the file.
March 12, 2017 at 7:33 pm
Hi Joe,
Great job. Thanks again for sharing.
I am also working on a project linked to Traveling Salesman Problem.
May I ask you to send me the javascript code as well?
Thanks in advance
March 24, 2017 at 1:23 am
Hi Joe,
I got very intrigued by your solution after reading your blog. If you do not mind to send me your solution as well.
Also, just curious, why not to share your solution through GitHub or other code sharing portal so that people in academia could benefit from it?
Thanks!
March 29, 2017 at 6:06 pm
Convinced, never thought there is much interest in that
https://github.com/kifj/tsp-js
December 23, 2016 at 11:56 pm
Thanks so much for sharing this, it’s really impressive. I am very curious about the gain and alpha parameters used by the algorithm. Would you please provide a brief, layman’s explanation of what those parameters do and how they might affect the result? Or if there are any recommended guidelines for choosing them? Thanks!!!
December 26, 2016 at 11:08 am
First of all, I didn’t invent the algorithm and its parameters. If you are really interested in the theory and explanation, I would recommend the original paper describing the details.
[AVT88] Bernhard Angeniol, Gael De La Croix Vaubois & Jean-Yves Le Texier
Self-Organizing Feature Maps and the Travelling Salesman
Problem, Neural Networks, Vol. 1, pp. 289-293, 1988
The short explanation for G and alpha: high values of G causes neighbours to be moved with each node. alpha describes the reduction of G after each round – the learning rate. Both parameters influence the convergence speed of the algorrithm (and by that the qualitiy of the solution). For a given TSP I would expect that you can iterate from faster to slower convergence(starting with high G and alpha and reducing it), until the algorithms is too slow or the solution is not improving enough. The speed and quality is heavily influenced of the TSP you want to solve (cluster vs. true random cities). So these parameters are empirically determined.
January 31, 2017 at 12:30 am
Hi Joe:
Thanks for sharing this. This is one of the fastest js implemtations Ive seen.
would it be posible to send the html pieces and link as Abhijeet Bhattacharya asked for to my included eail address. Your right
thank you so much, this is excellent
September 4, 2018 at 2:57 pm
Hi Joe,
Many thanks for sharing this great code. I have a problem case same as above but need to code in SQL Server. I am not good in the algorithm of Nueron Network. I am very appreciated if you contract me to help me.
Hope to get contact from you
April 16, 2019 at 8:30 pm
Thanks to Fil, he pointed me to https://observablehq.com/@fil/som-tsp for his version of this, and this here https://diego.codes/post/som-tsp/ with a very good explanation in text and a python version.