The Physical Travelling Salesperson Problem

for GECCO 2005

Simon M. Lucas


The competition is now closed

Results Here

The Physical Travelling Salesperson Problem (PTSP) is a new optimisation problem that's being run as a competition for GECCO 2005.

The competition map is a 30 city problem called: Map-30-g5

This was published on June 7 2005

The competition closes at
13:00 British Summer Time, June 22

The league will stay open for submissions after then,
but submissions after the deadline will not qualify for the competition

Leading entrants will have the opportunity to present their
results at a special GECCO 2005 Competition Session

The problem is described in full detail on the PTSP page, where you'll also find:

The on-line leagues enable you to see immediately how well you're doing compared to the other competitors.

The winning criteria for the this competition are:

I designed the PTSP as an interesting and demanding challenge for designers of evolutionary algorithms.  The PTSP has applications in controlling physical systems and agents. 

The problem is highly non-linear.  For example, consider these two solutions to the Map-10-1 problem:

The valid solution is a string of length 515, but a single edit (removing the first 1, to make the file edit514.txt) makes the solution invalid, and means it only visits two out of 10 cities!

To find good solutions, you'll need to think carefully about the representation, the variation operators, and the fitness function you use.  Have fun!

Entry Instructions

In addition to your on-line entry, you should also submit (by email to sml at a short (3 pages or fewer) PDF document outlining your approach).


Simon M. Lucas
Competitions Chair
GECCO 2005