PTSP: The Physical Travelling Salesperson Problem

Simon M. Lucas

PTSP Leagues

Contents

Introduction

The travelling salesperson problem is one of the most widely studied optimisation problems, and there are a plethora of clever algorithms and meta-heuristics for finding good solutions.  Close to optimal routes can now be found for problems involving thousands of cities.  For an idea of the current state of the art see the DIMACS 8th TSP Implementation Challenge.

The objective in the standard TSP is to minimise the total distance travelled.  The PTSP adds a simple twist that has far-reaching effects: the salesman has mass, and moves by choosing a force vector (see below) to apply to the mass at each point in time.

The objective now is to minimise the number of time steps taken to visit all the cities.  If two solutions tie on this, the tie-breaker is the solution that uses the least force i.e. that minimises the number of non-zero force vectors.  The screenshot below shows a sample run - this took 723 time steps (it is far from optimal!).

Specification

The problem is specified on a 2d grid.  The input to your algorithm is a set of cities, each specified by it's x-y position.  Each x-y city co-ordinate is an integer, using the 1/2 standard VGA range (320 x 240).  S.I. units are used for all measures; for screen display, 1 pixel corresponds to 1 meter.

Note that if there are any discrepancies between the above description and the Java code, the Java code is the reference. *

The output of your algorithm is the selected x-y force to apply at each time-step.  These forces are illustrated below.  The co-ordinates have the screen interpretation of  x: positive right; y : positive down.

Force Vector Id x,y (Newtons)
0 0, 0
1 0,-1
2 1, 0
3 0, 1
4 -1, 0

Simulation

The algorithm for checking a route is specified as follows:

 Input: Set of cities, list of force vectors for each time step
 Initialise position to INIT_POSITION
 Initialise velocity to ZERO
 for each force_t at each time step {
   update position(force_t)
   update velocity(force_t)
   remove all cities touched by new position
 }
 Output is the set of remaining cities: for a valid solution, should be the empty set.

The reference simulation is implemented in Java using double precision arithmetic.

Source Code

The Java source code is available here in a zip file.

Use the main method of Run to evaluate your solutions.

You can solve a problem (map) by controlling your agent directly using the cursor keys.  You'll need a web connection for this.  Then, type the following to play Map-10-1, giving your name as the second argument (this will appear in the league table).

java games.ptsp.Controller Map-10-1 MyName

The evaluation program has also been ported to C++ - thanks to Mathew Walker of Massey University:

File Formats

Input

The first line of the file is the number of cities, then each line is the x-y position of a city.  For example, a five city problem might look like this:

5
120 3
100 100
340 250
345 470
567 345

A sample set of cities (for the above screen shot) is here.

Solution

A solution is a statement of the number of steps taken, followed by the selected force vector for each step: for example:

368
1
2
2
2
4
0
0
...

A sample solution for the above set of cities is here.

Submission Server

You submit your solution for a particular map to the on-line submission server.

Then view the results in the on-line leagues.

Hints

You might try solving it as a conventional TSP, then working out a set of force vectors that would steer that route.  However, a glance at typical optimal TSP solutions indicate a high degree of curvature, which may be unlikely to form a good basis for PTSP solutions.

Related Ideas

The physics model is simple, and similar to that used for the Cellz challenge for GECCO 2004, and also similar to XQuest, the classic MAC and PC game. 

I had the idea for this problem while attempting the Crystal Collection Challenge for Crash Nitro Kart  (I've still only managed to collect 16 out of the 20 crystals...).

I'd like to thank Edward Tsang and Mark Johnston for their feedback and encouragement on this idea.

*

I'm grateful to Rok Sibanc, Cara McNish and Martin Byröd for pointing out a bug in the Java code, where I'd used v = u+aa instead of v = u+at.  For the remainder of the Gecco conference, the code will be left as it is (with the bug).  The Java code should be taken as the reference.  The effect of this is approximately the same as using the correct equation but with t=sqrt(0.1) instead of t = 0.1.