Travelling Salesman Problem in JavaScript Canvas

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:


Parameters





Simulation status



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

Tagged : , , , ,

12 Responses to “Travelling Salesman Problem in JavaScript Canvas”

  1. 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

  2. […] 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 […]

  3. 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

  4. Kingsley Oji Says:
    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!

  5. Abhijeet Bhattacharya Says:
    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

    • 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.

      • Baptiste Says:
        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

        • 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!

  6. 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!!!

    • 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.

  7. 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

Leave a Reply




Time limit is exhausted. Please reload CAPTCHA.