The Traveling Tourist Problem (TTP) is to visit a set of cities in the minimum total time where travel is constrained by a schedule. This is the Traveling Salesman Problem for public transportation. The input is a schedule giving the times that you can travel between pairs of cities, and the goal is to find a tour which visits all cities and returns you to your starting point with the minimum duration.
The CSE 521 course project is to develop and implement algorithms for the Traveling Tourist Problem and test them on various data sets. We will maintain a list of speedy tourists to keep track of the best tours found on each problem instance in the data set as well as the best known lowerbound for each instance.
An instance of the TTP is given by providing a schedule, as well as a starting time and starting city. The schedule is a list of city pairs with departure and arrival times. The schedule is assumed to be periodic (i.e., the same each day), so we only give a single days schedule. The goal is to find a minimum duration tour which visits every city, and gets back to the original city. A tour is allowed to visit the same city multiple times. The Traveling Tourist Problem can be shown to be NP-complete by a reduction from the Hamiltonian Cycle Problem.
Since the problem is NP-complete, it is unlikely that you can find an algorithm that efficiently solves large instances. So it is natural to look for approximation algorithms, which find good (but not optimal tours). Another approach is to see how large instances can be solved in a reasonable time using algorithms which in the worst case are exponential. There is a lot of literature on the Traveling Salesman Problem which will suggest a number of approaches. However, there are significant differences between the Traveling Salesmen and Traveling Tourists, so it will be necessary to invent new algorithms.
This project is modeled after various DIMACS Challenges, where researchers are invited to implement algorithms to solve specific problems. An important aspect of the DIMACS Challenges are publically available problem instances which make it possible to compare results of competing algorithms. For this problem there are two challenge directions: find exact solutions for instances as large as possible, and for large instances, find approximations that are as good as possible. I have not been able to find literature on this problem, inspite of its practical applications, so there is a chance to prove some interesting theorems.
This code was developed in 1996 for different file formats. I doubt if it is still of use.
Some source code is available to "use at your own risk". This code handles I/0 and provides some very primitive graphics capabilities. There is also an algorithm which finds very bad tours. You can use the showmap, showsch, and showtour programs to examine the data files. If you submit a tour, make sure that it conforms to the format of a tour file.