bjornson’s blog

this blog is very young, come again to watch it grow

Visualisation of heuristics to solve the Travelling Salesman Problem (TSP) in Flash

with 14 comments

This little Flash application implements four heuristics to solve the Travelling Salesman Problem:

This movie requires Flash Player 9

How to use this application:

Type in the number of nodes and press build to set them up randomly (now max. 300 nodes).

Then you can test the different heuristics by clicking on the buttons in the top area. To hide a solution you can click the button again.

To set the nodes up differently, press build again.

NEW functionalities: Now you can edit the nodes and add new ones. Snap to grid and let the application show each step of the process.

Please comment if you are interested in some additional functionalities.

Download the AS3 Class now here. It is licensed under the Creative Commons Attribution 3.0 License. This allows you to use this class in personal and commercial products but you need to leave my name and link in the class, which is actually not seen by anyone after you publish the file. It would be nice to receive an html link, but it is not required.

To use this class do the following:

Unzip the class into the your class root folder (usually you can use the folder your .FLA file resides in). In your FLA import the class, create an object of the TSP class with an adjacency matrix. Call one of the four heuristics to receive a route array. Add the withHistory flag as true to receive the unfinished routes as well.

  1. import bjornson.Algos.TSP;
  2. var myTSP:TSP = new TSP(matrix);
  3. var nextNeighbour:Array = myTSP.returnNextNeighbour();
  4. var nearestInsertion:Array = myTSP.returnNearestInsertion();
  5. var farthestInsertion:Array = myTSP.returnFarthestInsertion();
  6. var cheapestInsertion:Array = myTSP.returnCheapestInsertion();

Now you can use the found path in any way you like. For example simply trace one:

trace(“Route found by cheapest insertion heuristic: “+cheapestInsertion.toString());

An adjacency matrix is simply a two-dimensional array containing the distances from each node to every other node. For example a small matrix containing only three nodes can look like this:

var matrix:Array = new Array( new Array( 0 , 1 , 2 ), new Array( 1,  0 , 3 ), new Array( 2 , 3 , 0 ));

At the moment only symmetric matrices can be used.

Written by bjornson

September 12th, 2008 at 8:41 am

14 Responses to 'Visualisation of heuristics to solve the Travelling Salesman Problem (TSP) in Flash'

Subscribe to comments with RSS or TrackBack to 'Visualisation of heuristics to solve the Travelling Salesman Problem (TSP) in Flash'.

  1. Great example. I am anxious to see the AS3 Class. It would be nice to add the ability to display a background map, build some real world examples, and compare the results against some of the published real world solutions.

    Bart

    23 Sep 08 at 4:58 pm

  2. I’m glad you like it. I’m very busy until next Tuesday, but then I have enough time to clean up the code and post it here.

    Adding a background map? That would certainly help visualise the examples. I was also thinking about an option to upload your own coordinates to test them so you do not have to place each point with the mouse. Maybe in the form of CSV (for example “20:12|12:234|342:400|…”). But I cannot promise a certain date when this will be included.

    If anyone is interested in other heuristics or solutions to be included please post a link here to a description of it and I will attempt to implement it.

    bjornson

    24 Sep 08 at 9:29 am

  3. Yes this is very cool stuff, TSP is quite and interesting thing indeed. I look forward to checking out your AS3 code, thanks so much for sharing!

    Sean

    28 Sep 08 at 8:46 am

  4. Thanks very much for sharing this example :) . Great work ! I would just suggest adding a slider to adjust speed for show all steps option . Thanks again .

    Zeljko

    24 Dec 08 at 6:47 pm

  5. Great information. Thank you for share

    Aöf Matematik

    28 Feb 09 at 2:02 pm

  6. The style of writing is quite familiar . Did you write guest posts for other blogs?

    Ted Burrett

    24 Apr 09 at 12:57 pm

  7. @Ted:
    No I have not. This is my first blog and I so far I have not posted in other blogs.

    bjornson

    28 Apr 09 at 9:58 am

  8. is there a way to make a way betwen 2 points imposible?
    in mathematic you would do it making the distance between these points infinite. but how do you do it in your library?¿

    Klaus

    8 May 09 at 7:43 am

  9. sorry i downloaded the file and saw the Infinity constant.

    thanks for the code.

    Klaus

    8 May 09 at 8:18 am

  10. I’ve been scouting for a good TSP applet for a while: this one is the best I’ve seen, especially the add/edit with snap to grid feature. What you’ve done is pretty remarkable, and it’s well implemented.

    One interesting caveat of all four equations is that they cannot find the optimum path for a 6×6 square of points, where the points are laid out in a square so that the minimum distance between each point and it’s nearest neighbors is 1. When you try to find a route via your intuition, it’s shorter than any of the 4 listed:

    My Path (‘x’ is a point, ‘-‘ or ‘|’ are connections)

    x – x – x – x – x – x
    | |
    x x – x x – x x
    | | | | | |
    x x x x x x
    | | | | | |
    x x x x x x
    | | | | | |
    x x x x x x
    | | | | | |
    x – x x – x x – x

    (Value from my math)
    Intuitive Distance*: 1900

    (Value From Applet)
    Next neighbor: 2058
    nearest Insert: 1926
    Farthest Insert: 2222
    Cheapest Insert: 1968

    I’m not really a phenomenal mathematics guy, so I probably violated one of the rules of the problem; but I think it’s still an interesting result.

    Thanks for publishing the applet! It’s really cool!

    – Anonymous Student

    Anonymous Student

    3 Nov 10 at 11:22 pm

  11. **Oops!

    I see after my previous comment was posted, that it was formatted such that my path diagram didn’t show up right. The path should form the outline of a block letter ‘m’.

    Anonymous Student

    3 Nov 10 at 11:25 pm

  12. Can anyone solve this question? or suggest a reference for help please? Re-formulate it in pure binary integer linear problem

    Maximize Z = 2(X1) – (X1)^2 +3(X2) – 3(X2)^2
    subject to:
    x1 + x2 ≤ 0.75
    and each variable is restricted to take the following values: 1/2, 1/3, 1/4, 1/5
    This is a discrete nonlinear problem.

    Optimizer

    13 Nov 12 at 12:44 am

  13. Really cool :)

    I’ve implmented several TSP heuristics in Python too.

    Here the source code is:
    https://github.com/ntrifunovic/TSP

    Screenshots of program are availabale at: http://ntrifunovic.github.io/projekti/tsp/

    ntrifunovic

    13 Apr 13 at 4:15 pm

  14. Thank you for sharing your work it was really interesting.

    josh

    4 Nov 13 at 9:56 am

Leave a Reply