An instance of the traveling tourist problem consists of a schedule, along with a starting city, and a starting time. The goal is to find a tour of minimum duration which visits all of the cities.
A schedule is a set of routes, where a route specifies a starting city, a destination city, a departure time, and a travel time. A bus travels on each route once a day, leaving at the same time each day.
A tour is a sequence of routes, with the source of route i+1 the same as the destination of route i. To solve the tourist problem, the tour is required to visit all of the cities, and start and end at a specified city. A tour is allowed to visit the same city multiple times.
The duration of a tour is the sum of the travel times and the waiting times. Since busses travel once a day, one may have to wait up to twenty four hours for the bus along a particular route.
There is no minimum time between busses, if a bus A arrives at time T, and bus B departs at time T, it is possible to arrive in the city on bus A, and depart on B on the same day. (So the tourist need not spend much time in each city!)
Busses always run on time.
Travel times are all positive. A twenty four hour clock is used, with times specified in minutes since midnight.
An instance of the problem specifies the start city and the start time.
The current data sets are all based upon schedules with a daily period and a time unit of minutes. It is possible that other data sets will be made available with different periods and time units. To handle this, a schedule specifies a period - the default is 1440 (the number of minutes in a day). Design your algorithms so that they can easily accomodate a different period. (For example, the period for many airline schedules is one week.)
There are three types of data files: schedule files, city files, and tour files. Look at the source code to figure out the exact file formats. A route consists of a source city, destination city, departure time, travel time and route name. A schedule is a list of routes. It is safe to assume that the schedule is strongly connected so that every city is reachable from every other city. A tour consists of a list our route numbers. The city files give lists of cities along with their x-y coordinates. The coordinates are designed for an 800x800 window with the origin in the lower left hand corner. The city files actually do not enter into the tour finding at all - they are just available to allow for graphical output.