Visualisation of heuristics to solve the Travelling Salesman Problem (TSP) in Flash
This little Flash application implements four heuristics to solve the Travelling Salesman Problem:
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.
- import bjornson.Algos.TSP;
- var myTSP:TSP = new TSP(matrix);
- var nextNeighbour:Array = myTSP.returnNextNeighbour();
- var nearestInsertion:Array = myTSP.returnNearestInsertion();
- var farthestInsertion:Array = myTSP.returnFarthestInsertion();
- 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.
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
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
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
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
Great information. Thank you for share
Aöf Matematik
28 Feb 09 at 2:02 pm
The style of writing is quite familiar . Did you write guest posts for other blogs?
Ted Burrett
24 Apr 09 at 12:57 pm
@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
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
sorry i downloaded the file and saw the Infinity constant.
thanks for the code.
Klaus
8 May 09 at 8:18 am