LEDA Assignment 2:
Travelling Tourist Problem Implementation Challenge
(Due: 20 October 2000)
The aim of this assignment is to use LEDA to solve the Travelling Tourist Problem (TTP), a modified version of the (more famous) travelling saleman problem (TSP). This problem was originally given as a project to students in the University of Washington at Seattle in their algorithms course, CS521.
Given a detailed bus schedule of a country, can you visit every city by bus within a fixed number of days? That is the Travelling Tourist Problem.
This is the formal statement of the problem, and here is some theoretical background for the TTP.
There are already some C++ source codes and bus schedules given in the CS521 course of Washington University. You will base your implementation on these codes and data. Note that you won't actually be able to compile those original codes from University of Washington. Here's a modified package with LEDA wrapper routines (in the file leda.cc) so that you can code in the comfort of LEDA. To implement the TTP solver, you should study the file leda.h to get to know the data structure to work in. You are expected to fill in the routine
list<edge>& TTP(int start_time, node start_city GRAPH<int,schedule *> G);
which can be found in leda-ttp.cc (which currently implements a
naive algorithm).
Please start thinking about the problem right away. Although the deadline is still some time away, I expect you to have working code by 10-Oct-2000, so that we can put up a website, publishing the best tours as they are obtained. You are also expected to post your results to your personal score page - if you are user "leonghw", your personal page is at http://www-appn.comp.nus.edu.sg/~cs6204/cgi-bin/ttp-results.cgi?personal=leonghw.