Solving the travelling salesman problem with ant colony optimization
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
analysis
project
sample
src/main/scala
.gitignore
LICENSE
README.md
build.sbt

README.md

TravellingAnts

TravellingAnts is an implementation of the Ant Colony metaheuristic optimization algorithm (specifically, Ant System) for solving the travelling salesmen problem.

The repository includes a library for solving arbitrary graphs and also includes a specific example.

The code is intended to be clear and modular. Ants are launched concurrently to improve execution speed. The solver provides call-backs for listening to the running computation rather than hard-coding loggers.

Sample run

A comparison of the mean cost of each ant's solution per iteration to the overal cumulative best solution as the algorithm progress:

Sample iterations

The best solution from the run above:

Sample solution

Use

TravellingAnts is written in Scala. It requires that sbt is installed.

To execute the solver on the example solution and save the solution in the DOT format, execute:

$ sbt --warn run > output.dot

Intermediate progress is printed to the standard error device (stderr) and also to a log file (travelling-ants.log) in comma-separated value (CSV) format suitable for analysis.

To produce a visual image of the resulting solution, you can use neato from the grapviz suite of programs:

$ neato -Tpng output.dot > output.png