Travelling Salesman Problem

back

?

Parameters

Start
Starts the simulation.
Stop
Stops the simulation.
Reset
Resets the current simulation to its start point.
Default
Sets the default TSP graph, which is shown after each program start. It bases on the distance matrix of 40 cities in Germany.
Random
Allows to create random TSP graphs. Specify the number of desired cities in the text field below. A bigger graph needs more ants and maybe an increase of 'q0'. To gain more performance change the value of the candidate lists size properly, so that it is much smaller than graph size minus 1.
ants
The desired number of ants in the colony. Too many ants will decrease performance, so please do not orientate on real ant colonies.
'q0'
Chooses the exploration rate for each ant. A value of 5 means that during their tour through the whole graph each ant will choose in 5 cases not the edge with the strongest pheromone level, but one with a weaker content, to increase variability.
alpha
Higher values decrease the weight of pheromone on the edge in comparison to the egde length. The default value works quite well.
beta
Higher values decrease the weight of the edqe length in comparison to its pheromone level. The default value works quite well.
gamma
Higher values stand for a higher pheromone decay. It prevents a too strong accumulation of pheromone on edges, leading to suboptimal results. Make sure that this value is out of the interval ]0;1[.
candidate list
Increases the performance in huger TSP-graphs, as for each city only the here specified number n, representing the n nearest cities, is used in the computations. So make sure that n is at least 1 and smaller than the number of cities (vertices) in the graph.
update list
Updates the candidate list from time to time in such a way, that not only the pure edge lengths, but also the changing pheromone levels are taken to account. So the list of the n 'nearest' cities for each city is allowed to change during the simulation.

Results

The area in the middle represents the current situation. Each small square stands for one city. If it is complete black, at least one ant is in that city. There are always two tours shown: the red one shows the shortest tour ever reached and the blue tour is the best tour out of the n last ones (n is the number of ants). At the bottom the total number of completed tours is shown. To have a realistic value for comparison the tour length received by the nearest neighbor heuristic is displayed. Again the lengths of the two drawn tours are presented. The percentage stands for the improval compared to the value of nearest neighbor heuristic.

back