The applet requires Java 5 or higher. Java must be enabled in your browser settings. Mac users must have Mac OS X 10.4 or higher. Windows and Linux users may obtain the latest Java from Oracle's Java site.

powered by NetLogo

view/download model file: tsp3.nlogo

WHAT IS IT?

This is a demo of using bruteforce to solve the Traveling Salesman Problem.
The Traveling Salesman Problem is about trying to solve problems where every possible solution must be tried to find the best solution to the problem. As there can be a very large number of possibilities it is often computationaly unfeasable to try all possibilities.
This demo gets to a usable solution quickly. Even if it isn’t the best solution.
The basis of this problem is that a salesman must travel to each town once, and only once, while traveling the minimum distance.

HOW IT WORKS

The number of towns you select are randomly placed on the bounded screen. The number of ants you selected are released. each one chooses a path through all the towns, going to each town only once. Each ant measures the distance it traveled and the shortest distances are remembered.

HOW TO USE IT

You select the number of ants and the number of towns using the sliders. The “setup” button randomly places the number of towns you selected. The “go” button releases the ants. You can select whether to show the routes taken by each ant with the “tracks” switch.

THINGS TO NOTICE

A solution that is about 90% good comes quickly, and in a real world situation where other variables may exist, (ie; traffic, weather, tolls…) this is often good enough.

THINGS TO TRY

Notice how using more ants does not decrease the best distance very much.

EXTENDING THE MODEL

Instead of just distance, there could be other factor to determine the “best” route. Maybe time is more important, or maybe costs.

NETLOGO FEATURES

A list is used to record the different routes the ant take.

RELATED MODELS

There are some TSP solvers in the models library, but these use Genetic Algorithms instead of brute force.

CREDITS AND REFERENCES

All the people that have put examples on the web…Thank You.

CODE

;;Using ants to solve TSP

breed [ ants ant ]
breed [ towns town ]
globals [
  totdist
  l
  d
  k
  m
  beento 
  shortestdtot
 shortestroute
  dtot
  ]

to setup
  clear-all
  set shortestdtot 1000000
  create-towns numtowns  [
  setxy random-xcor random-ycor
  set label who
  set color blue
  set shape "house"
  set size 2
  ] 
create-ants numants [
  setxy ([xcor] of ( town 0 )) ([ycor] of town 0 )
  set shape "bug"
  ;;set color red
  set size 2  
  ]
end

to go   
ask ants [
set pen-size 2
  choosepath
   if tracks  [ pendown ]   
  foreach beento [              
    set  d  (distancexy ([xcor] of town ?) ([ycor] of town ?))
    set dtot dtot + d
    facexy ( [xcor] of town ?) ([ycor] of town ?)     
    set l int d
    repeat l [
    fd 1
    ] ;end of repeat
   ];;;end of foreach
  
  if dtot < shortestdtot [
    set shortestdtot dtot 
    set shortestroute beento
     ]
   set k k + 1
   set dtot 0
   plot shortestdtot
 ]   ;end of ask ants
 end

to choosepath
    set beento [ ]
    repeat numtowns - 1 [
    get-listitem
    set beento fput m beento
    ]
   set beento lput 0 beento
end
    
to get-listitem
      set m random numtowns
       if m < 1  [ get-listitem ] 
       foreach beento [
   if m = ?  [ get-listitem ] 
   ]      
end