Nitty-gritty

Here are the details of the problem. For convenience, we will describe the problem in terms of bus travel.

• 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.
• 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 five types of data files files: problem files, solution files, schedule files, city files, and tour files. Example source files are given below.
• A problem is a map (given as a file name), a schedule (given as a file name), a start city (an integer), and a start time (an integer).
• A schedule entry consists of source city (an integer), a destination city (an integer), a departure time (an integer), a travel time (an integer), and a route name (a string). A schedule is a list of schedule entries as well as the number of cities (an integer) and the period of the schedule (an integer). The order of the schedule entries is important, since schedule entries will be refered to by index (starting from 0). 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 of indices of schedule entries.
• The map files give lists of cities along with their x-y coordinates. The coordinates are designed for an 800x800 window with the origin in the upper left hand corner. The map files actually do not enter into the tour finding at all - they are just available to allow for graphical output.
• A solution file consists of an author, a time, a problem, an algorithm name and a tour. The tour is given as a list of indices of schedule entries. The time and problem are strings, and the author and algorithm name are text.

Sample files

Problem file (.ttp) uk-25.ttp

<problem>
  <map>uk-25</map>
  <schedule>uk-25</schedule>
  <startcity>10</startcity>
  <starttime>480</starttime>
</problem>

Schedule file (.tts) uk-25.tts

<schedule>
<cities> 25 </cities>
<period> 1440 </period>
<entries>
<se> 0 23 894 61 <name>BUS 0</name> </se>
<se> 0 23 460 56 <name>BUS 1</name> </se>
<se> 0 23 458 37 <name>BUS 2</name> </se>
<se> 0 23 760 60 <name>BUS 3</name> </se>
<se> 0 2 60 166 <name>BUS 4</name> </se>
<se> 0 2 538 143 <name>BUS 5</name> </se>
...
<se> 24 19 1342 82 <name>BUS 342</name> </se>
<se> 24 22 219 108 <name>BUS 343</name> </se>
</entries></schedule>

Map file (.ttm) uk-25.ttm

<citylist>
  <city> 
    <name> Jersey</name>
    <location> 391.291  785.553</location>
  </city>
  <city> 
    <name> Baltasound</name>
    <location> 437.461  16.675</location>
  </city>
...
  <city> 
    <name> Guernsey</name>
    <location> 373.987  771.114</location>
  </city>
  <city> 
    <name> Sunderland</name>
    <location> 423.639  406.671</location>
  </city>
</citylist>

Tour file (.ttt) uk-25.ttt

<tour>  238  314  0  333  20  . . . 333  28  97  343  311  </tour>

Solution file (.ttr) uk-25.ttr

<solution>
  <author> Richard Anderson </author>
  <time> 45:10:52 </time>
  <problem> uk-25 </problem>
  <algorithm> Visit All </algorithm>
  <tour>  238  314  0  333  20  . . . 333  28  97  343  311  </tour>
</solution>