You probably know that the travelling salesman problem is one of the classics of computer science theory. Now we have a new challenge - the Physical Travelling Salesman Problem and anyone can join in.

The Physical Travelling Salesman Problem (PTSP) is really a lot of fun. The idea is similar to the original Travelling Salesman Problem - you simply have to visit each city or point in turn and travel the smallest distance. The "physical" in the problem's title is due to the extra difficulty of actually driving a vehicle around the course.

In this case the vehicle is simulated and obeys a simple set of dynamical rules - it has both friction and inertia to deal with. As a result you can't just move in a straight line from one point to the next. You have to steer your way round the course allowing time to decelerate and swing around corners.

There are two competitions you can enter - a human solution or a bot-based solution. For the human competition you simply sign in to the site and start steering the ship.

For the bot version you have to design a program that does the same job. The coding is done in Java and all you have to do is provide a list of actions selected from six possible actions to steer the "ship" around the course. The ship can collide with obstacles and the objective is to complete the journey in the minimum number of steps.

To quote the website:

The PTSP was first introduced as a competition at the Genetic and Evolutionary Computation Conference (GECCO) in 2005. Compared to the TSP, the PTSP adds some interesting challenges over the standard TSP. For a given number of waypoints, PTSP solutions are much longer. For example, a 10 waypoint map may require a sequence of several hundred actions (force vectors) to solve it. Furthermore, the length of the optimal sequence is unknown in advance.

If you watch the video, you can see a human solution to the problem and stand a good chance of getting hooked on the challenge - so you have been warned!

Both the human and bot competitions have leader boards and it will be interesting to see if bots do better than humans - of course they will. You have to solve 20 maps and the software is all easy to download and use. As the number of maps seem to have a small number of points to visit, most of the difficulties in the algorithm will be about plotting the course and this suggests some sort of dynamic programming, optimization, genetic algorithm etc, is most likely to be successful.

The human competition runs to May 7th and the bot competition starts its final trials on the May 27th 2012.

More Information

The PTSP Competition

Related Articles

The Genetic Algorithm

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

To be informed about new articles on I Programmer, subscribe to the RSS feed, follow us on Google+, Twitter, Linkedin or Facebook or sign up for our weekly newsletter.