A genetic algorithm that finds solutions for the Traveling Salesman Problem
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.
.gitignore
GeneticAlgorithm.py
README
TravelingSalesman.py

README

* The Traveling Salesman Problem

This project uses a Genetic Algorithm to solve the Traveling Salesman
Problem. The positions of the cities are given as coordinates on a 2D
plane. The script returns the cities in the order of one of the
shortest routes and can also write the route to an SVG image.

#+BEGIN_QUOTE
The travelling salesman problem (TSP) is an NP-hard problem in
combinatorial optimization studied in operations research and
theoretical computer science. Given a list of cities and their
pairwise distances, the task is to find the shortest possible route
that visits each city exactly once and returns to the origin city. It
is a special case of the travelling purchaser problem.

@<div class="source">[[http://en.wikipedia.org/wiki/Traveling_salesman_problem][Wikipedia]]@</div>
#+END_QUOTE

A set of 10 cities has 10!(factorial) = 3,628,800 possible routes. A
genetic algorithm can find an acceptable path in a small amount of
time by creating a pool of random routes and selecting the shortest
to create a new generation. Each generation random mutations are
introduced and pairs of routes are combined to create a new route.


* Usage

This runs the algorithm with an octagon:

#+BEGIN_EXAMPLE
python TravelingSalesman.py 26,2 62,2 87,26 87,62 62,87 26,87 2,62 2,26
#+END_EXAMPLE

You can also let it use random input:

#+BEGIN_EXAMPLE
python TravelingSalesman.py -r
#+END_EXAMPLE

Output a map to an image:

#+BEGIN_EXAMPLE
python TravelingSalesman.py -r -i map.svg
#+END_EXAMPLE