CS4234/CS5234 - Combinatorial and Graph Algorithms
School of Computing, National University of Singapore
(Fall Semester 2001)

Challenge Problem -- Travelling Tourist Problem (TTP)
(Due: 2nd November 2001)

Aims of this LEDA Assignment

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 (or see local copy here) to students in the University of Washington at Seattle in their algorithms course, CS521. Last year, we adopted the TTP as the challenge problem for our "Combinatorial and Graph Algorithms" course.

The Travelling Tourist Problem

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.

You should look for details on the problem instances, including start cities and start times in the README file in the package.

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).

Some Milestones

Please start thinking about the problem right away even though the deadline is still some time away. The idea is to first and quickly get a basic working code done and publish initial results. Then, you can work on improving the algorithm to get better results. This may take quite a bit of trial and error.

There are three milestones,

  • M1: Basic Working Code -- by 19-Oct-2001;
  • M2: Improved Code -- by 26-Oct-2001;
  • M3: Final Code and Report -- by 02-Nov-2001.


    • Publishing Your Results on the TTP Challenge Website

    We have a TTP Challenge Website (to be announced soon) that publishes the best tours obtained by the students. For now, you can see the best tours obtained by last year's class.

    After milestone M1, you can start submitting your solutions to the TTP Challenge website. 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/~cs4234/cgi-bin/2001/ttp-results.cgi?personal=leonghw.

    Note: If you have problem accessing this link, please verify first that you have set your proxy preference to "bypass proxy for domain www-appn.comp.nus.edu.sg" before you send an enquiry to Kal.

    Your TTP Project Report

    By the due date of the project, you should have

    Where to get help...

    First, check out this page on getting help. If that does give the answer to your problem, you can send email to my RS assistant, Mr Kal Ng for help. If you do so, please also cc the mail to me.
    TTP Challenge Project