Input and output specification

The datafiles used in TTP-Lib are based on XML. The necessary specifications of the input and output files (i.e. XML schemas) and a description of the used entities and attributes can be found on this page.

XML Schemas

Description	Schema	Example
Macroscopic infrastructure	TbMacroInfra.xsd	TbMacroInfraExample.xml
Request set	TbRequestSet.xsd	TbRequestSetExample.xml
Macroscopic timetable	TbMacroTimetable.xsd	TbMacroTimetableExample.xml

I. Macroscopic infrastructure

The most important information needed to compute a train schedule is saved in the macroscopic infrastructure data file. Stations, tracks, traintypes and corresponding macroscopic operational constraints are defined; all times are discretize to some defined unit in seconds, given by the attribute "timeunit_in_seconds". The data is strucutured in two parts:

1. Traintype definitions

In this part of the infrastructure definition we declare the traintypes and define in which way they dominate each other. In order to aggregate common properties and restrictions - traintypes typically given as a hierarchically build tree. For each train type all properties of the higher level train type are valid; analogously restrictions of the higher level train type has to be fulfilled, as well as the train type specific ones.

Example

<traintypetree treeID="hierarchy">
	<traintype traintypeID="TRAINTYPE_1"
		 treelevel="0"
		 treeposition="0">
		<successor traintypeID="TRAINTYPE_2"/>
		<successor traintypeID="TRAINTYPE_3"/>
	</traintype>
	<traintype traintypeID="TRAINTYPE_2"
		 treelevel="1"
		 treeposition="0">
		<predecessor traintypeID="TRAINTYPE_1"/>
	</traintype>
	<traintype traintypeID="TRAINTYPE_3"
		 treelevel="1"
		 treeposition="1">
		<predecessor traintypeID="TRAINTYPE_1"/>
	</traintype>
</traintypetree>

In this case we have an abstract traintype "TRAINTYPE_1" and two "really existing" traintypes "TRAINTYPE_2" and "TRAINTYPE_3" which are both children of "TRAINTYPE_1" in the hierarchy tree. All defined restrictions and properties of train type "TRAINTYPE_1" are thatswhy valid for "TRAINTYPE_2" and "TRAINTYPE_3".

2. The infrastructure definition part

This part contains the needed infrastructure informations and is splitted into two subsections:

2.1 Knots

The knot section contains the needed informations for every station and the inner-station tracks. Besides holding attributes for an unique id ("knotID"), a name ("knot_name") and the geographic coordinates (i.e. degree of latitude "knot_Coordinate_X" and degree of longitude "knot_Coordinate_Y" ). Furthermore a knot contains entities which specify the station capacity ("knotTracks") and the time a train needed to change the moving direction ("knot_turnaround_time"). Another important attribute is the "knot_type" attribute. This one specifies whether the knot is a standard pass-through-station with two sides or directions ("standard"), a deadend station ("deadend") or a artificial point or station of any other type ("pseudo"). All times are given in specified discrete time units (e.g. minutes) for every traintype that can turnaround in the current knot. The station capacities can be specified by the "knotTracks" entity which can be interpreted as knot-inner tracks. This tracks are classified in (for now) three types: running, platform and all. So it is possible to create restrictions for the maximum number of possible trains driving through a station ("running"), the number of trains waiting or turnaround inside a station ("platform") or a number of maximal operating trains ("all").

Example

<knot knotID="KNOT_001"
	 knot_name="Station_Knot_001"
	 knot_type="standard"
	 knot_Coordinate_X="50"
	 knot_Coordinate_Y="10">
	<knotTracks knot_track_type="all"
		 traintypeID="TRAINTYPE_1"
		 knot_trackNo="8"/>
	<turnaround_times traintypeID="TRAINTYPE_2"
		 knot_turnaround_time="8"/>
	<turnaround_times traintypeID="TRAINTYPE_3"
		 knot_turnaround_time="10"/>
</knot>
<knot knotID="KNOT_002"
	 knot_name="Station_Knot_002"
	 knot_type="standard"
	 knot_Coordinate_X="51"
	 knot_Coordinate_Y="10">
	<knotTracks knot_track_type="all"
		 traintypeID="TRAINTYPE_1"
		 knot_trackNo="5"/>
	<knotTracks knot_track_type="platform"
		 traintypeID="TRAINTYPE_1"
		 knot_trackNo="3"/>
	<knotTracks knot_track_type="running"
		 traintypeID="TRAINTYPE_3"
		 knot_trackNo="1"/>
	<turnaround_times traintypeID="TRAINTYPE_2"
		 knot_turnaround_time="8"/>
	<turnaround_times traintypeID="TRAINTYPE_3"
		 knot_turnaround_time="10"/>
</knot>
<knot knotID="KNOT_003"
	 knot_name="Station_Knot_003"
	 knot_type="deadend"
	 knot_Coordinate_X="50"
	 knot_Coordinate_Y="11">
	<turnaround_times traintypeID="TRAINTYPE_2"
		 knot_turnaround_time="5"/>
	<turnaround_times traintypeID="TRAINTYPE_3"
		 knot_turnaround_time="5"/>
</knot>

2.2 Tracks

This section contains the important technical tracks-data. A track entity holds at least the attributes "start_knotID", "end_knotID", "start_knot_side" and "end_knot_side" to determine from wherefrom (including departure side or direction) to wherto (including arrival side or direction) the track goes. We expect at least some child-entities "drivetime" for all train types operating on this track, otherwise the definition of this track would be redundant. The attribute "drive_mode" specifies the type of runnning, see routing trains. "headways" for every pair of operated train types ensure a valid usage of this track. We explicitly mention that in our specification headway times are only w.r.t. train types and independent from their drive mode. The drive times and headways are - like the above mentioned turnaround times - given in discrete time units.

Example

<track trackID="TRACK_1_2"
	 start_knotID="KNOT_001"
	 start_knot_side="1"
	 end_knotID="KNOT_002"
	 end_knot_side="2"
	 number_tracks="2"
	 number_conflicting_tracks="1">
	<drivetime traintypeID="TRAINTYPE_2"
		 value="55"
		 drivemode="1"/>
	<drivetime traintypeID="TRAINTYPE_3"
		 value="75"
		 drivemode="1"/>
	<headway traintypeID_preceded="TRAINTYPE_2"
		 trackID_preceded="TRACK_1_2"
		 traintypeID_succeded="TRAINTYPE_2"
		 trackID_succeded="TRACK_1_2"
		 value="2"/>
	<headway traintypeID_preceded="TRAINTYPE_2"
		 trackID_preceded="TRACK_1_2"
		 traintypeID_succeded="TRAINTYPE_3"
		 trackID_succeded="TRACK_1_2"
		 value="2"/>
	<headway traintypeID_preceded="TRAINTYPE_3"
		 trackID_preceded="TRACK_1_2"
		 traintypeID_succeded="TRAINTYPE_2"
		 trackID_succeded="TRACK_1_2"
		 value="22"/>
	<headway traintypeID_preceded="TRAINTYPE_3"
		 trackID_preceded="TRACK_1_2"
		 traintypeID_succeded="TRAINTYPE_3"
		 trackID_succeded="TRACK_1_2"
		 value="10"/>
</track>
<track trackID="TRACK_2_1"
	 start_knotID="KNOT_002"
	 start_knot_side="2"
	 end_knotID="KNOT_001"
	 end_knot_side="1"
	 number_tracks="2"
	 number_conflicting_tracks="1">
	<drivetime traintypeID="TRAINTYPE_2"
		 value="50"
		 drivemode="1"/>
	<drivetime traintypeID="TRAINTYPE_3"
		 value="72"
		 drivemode="1"/>
	<headway traintypeID_preceded="TRAINTYPE_2"
		 trackID_preceded="TRACK_2_1"
		 traintypeID_succeded="TRAINTYPE_2"
		 trackID_succeded="TRACK_2_1"
		 value="3"/>
	<headway traintypeID_preceded="TRAINTYPE_2"
		 trackID_preceded="TRACK_2_1"
		 traintypeID_succeded="TRAINTYPE_3"
		 trackID_succeded="TRACK_2_1"
		 value="3"/>
	<headway traintypeID_preceded="TRAINTYPE_3"
		 trackID_preceded="TRACK_2_1"
		 traintypeID_succeded="TRAINTYPE_2"
		 trackID_succeded="TRACK_2_1"
		 value="25"/>
	<headway traintypeID_preceded="TRAINTYPE_3"
		 trackID_preceded="TRACK_2_1"
		 traintypeID_succeded="TRAINTYPE_3"
		 trackID_succeded="TRACK_2_1"
		 value="10"/>
</track>
<track trackID="TRACK_2_3"
	 start_knotID="KNOT_002"
	 start_knot_side="1"
	 end_knotID="KNOT_003"
	 end_knot_side="1"
	 number_tracks="2"
	 number_conflicting_tracks="1">
	<drivetime traintypeID="TRAINTYPE_2"
		 value="40"
		 drivemode="1"/>
	<drivetime traintypeID="TRAINTYPE_3"
		 value="60"
		 drivemode="1"/>
	<headway traintypeID_preceded="TRAINTYPE_2"
		 trackID_preceded="TRACK_2_3"
		 traintypeID_succeded="TRAINTYPE_2"
		 trackID_succeded="TRACK_2_3"
		 value="2"/>
	<headway traintypeID_preceded="TRAINTYPE_2"
		 trackID_preceded="TRACK_2_3"
		 traintypeID_succeded="TRAINTYPE_3"
		 trackID_succeded="TRACK_2_3"
		 value="2"/>
	<headway traintypeID_preceded="TRAINTYPE_3"
		 trackID_preceded="TRACK_2_3"
		 traintypeID_succeded="TRAINTYPE_2"
		 trackID_succeded="TRACK_2_3"
		 value="22"/>
	<headway traintypeID_preceded="TRAINTYPE_3"
		 trackID_preceded="TRACK_2_3"
		 traintypeID_succeded="TRAINTYPE_3"
		 trackID_succeded="TRACK_2_3"
		 value="11"/>
</track>

II. Requests

Further demand-data are needed for a TTP instance; stored in a request-file. A request file is strucutred as a set of train requests. A slot request describes the desired route of a train through the network. A train is identified by "TrainName" and "TrainNumbers". A train type - taken from the leaves of the train type tree from the infrastructure file - should be specified as well. Finally, a "BasicValue" is attached to the train; interpreted as a profit value to maximize. Specification of start and final stations are mandatory. Optionally, in-between stops may be specified. To reflect the fact that there is usually some flexibility in the planning of a train with respect to arrival and departure times, a request specifies time windows around the optimal time, within which arrival and departure at specified stops may be scheduled. Diversion from theses "OptimalValues" within the bounds of the time window may be penalized by linear functions given by "LeftSlope" and "RightSlope". Details to this can be found in the paper. The value of a scheduled train as given in a solution (see below) is defined to be the basic value, minus the sum of all penalties that the train collects during its course. We allow forcing a train into a solution by assigning to it a special flag "fixed". If this flag is set, this train has to be scheduled for a computed solution to be feasible. Optionally, for intermediate stops, minimal and maximal "DwellingTime", that is, the time that a train should or is allowed to wait at the platform, can be specified. This is useful for passenger trains that possibly need a longer stop at some stations where many passengers enter or leave the train.

Example

<SlotRequest TrainNumber="00115873"
	 TrainType="TRAINTYPE_2"
	 TrainName="TRAIN_REQ_001"
	 BasicValue="120"
	 UnspecifiedStopMinimumDwellingTime="0">
	<StopList>
		<StartSlotRequestStop KnotId="KNOT_001">
			<EarliestDeparture OptimalValue="120"
				 MinimalValue="100"
				 MaximalValue="130"
				 LeftSlope="2"
				 RightSlope="0"/>
		</StartSlotRequestStop>
		<FinalSlotRequestStop KnotId="KNOT_002">
			<LatestArrival OptimalValue="175"
				 MinimalValue="100"
				 MaximalValue="160"
				 LeftSlope="0"
				 RightSlope="5"/>
		</FinalSlotRequestStop>
	</StopList>
</SlotRequest>
<SlotRequest TrainNumber="00214587"
	 TrainType="TRAINTYPE_3"
	 TrainName="TRAIN_REQ_002"
	 BasicValue="180"
	 UnspecifiedStopMinimumDwellingTime="0">
	<StopList>
		<StartSlotRequestStop KnotId="KNOT_001">
			<EarliestDeparture OptimalValue="120"
				 MinimalValue="100"
				 MaximalValue="200"
				 LeftSlope="2"
				 RightSlope="0"/>
		</StartSlotRequestStop>
		<FinalSlotRequestStop KnotId="KNOT_003">
			<LatestArrival OptimalValue="215"
				 MinimalValue="200"
				 MaximalValue="350"
				 LeftSlope="0"
				 RightSlope="5"/>
		</FinalSlotRequestStop>
	</StopList>
</SlotRequest>
<SlotRequest TrainNumber="00314587"
	 TrainType="TRAINTYPE_2"
	 TrainName="TRAIN_REQ_003"
	 BasicValue="480"
	 UnspecifiedStopMinimumDwellingTime="0">
	<StopList>
		<StartSlotRequestStop KnotId="KNOT_002">
			<EarliestDeparture OptimalValue="120"
				 MinimalValue="100"
				 MaximalValue="200"
				 LeftSlope="10"
				 RightSlope="0"/>
		</StartSlotRequestStop>
		<FinalSlotRequestStop KnotId="KNOT_001">
			<LatestArrival OptimalValue="145"
				 MinimalValue="100"
				 MaximalValue="350"
				 LeftSlope="0"
				 RightSlope="15"/>
		</FinalSlotRequestStop>
	</StopList>
</SlotRequest>
<SlotRequest TrainNumber="00414587"
	 TrainType="TRAINTYPE_2"
	 TrainName="TRAIN_REQ_004"
	 BasicValue="280"
	 UnspecifiedStopMinimumDwellingTime="0">
	<StopList>
		<StartSlotRequestStop KnotId="KNOT_002">
			<EarliestDeparture OptimalValue="120"
				 MinimalValue="100"
				 MaximalValue="200"
				 LeftSlope="1"
				 RightSlope="0"/>
		</StartSlotRequestStop>
		<FinalSlotRequestStop KnotId="KNOT_001">
			<LatestArrival OptimalValue="145"
				 MinimalValue="100"
				 MaximalValue="350"
				 LeftSlope="0"
				 RightSlope="1"/>
		</FinalSlotRequestStop>
	</StopList>
</SlotRequest>

III. Solution

A solution of an instance of the train timetabling problem together with the network can be visualized by TraVis. Therefore we need some additional setting information; a mapping of a color to each leaf or used train type; the maximal "time_horizon", that means the maximum arrival minus the minimal departure time of that solution; the number of scheduled trains or equivalent number of paths to visualize denoted by "nr_paths". Optionally, "sol_profit" specifies the objective value of the given solution and "proven_upper_bound" denotes a valid upper bound of the train timetabling instance. The solution itself is then given as a list of paths. Beside some labels,"trainnumber", "traintype" and the length of the path must be specified. Then we expect a sorted list of knots, their arrival and departure times, and a list of used tracks. This format is leaned on the timetable format of RailML with respect to macroscopic and abstract train types.

Example

<solution scenario="noname"
	 network="TbMacroInfraExample.xml"
	 requests="TbRequestSetExample.xml"
	 time_horizon="250"
	 sol_profit="574.000000"
	 proven_upper_bound="574.000000"
	 nr_paths="4">
	<settings>
		<TrainColor traintype="TRAINTYPE_2"
			 color="C0C0C0"/>
		<TrainColor traintype="TRAINTYPE_3"
			 color="FF0000"/>
	</settings>
	<path bundle_id="1"
		 bundle_name="TRAIN_REQ_001"
		 trainnumber="00115873"
		 traintype="TRAINTYPE_2"
		 path_profit="80.00"
		 path_length="2">
		<knot path_knot_index="1"
			 knotID="KNOT_001"
			 station_id="1"
			 arrival_time="100"
			 departure_time="100"
			 turnover_flag="0"
			 stop_flag="1"
			 station_label=""/>
		<knot path_knot_index="2"
			 knotID="KNOT_002"
			 station_id="2"
			 arrival_time="155"
			 departure_time="155"
			 turnover_flag="0"
			 stop_flag="1"
			 station_label=""/>
		<track path_track_index="1"
			 trackID="TRACK_1_2"
			 track_id="1"
			 track_label="TRAINTYPE_2_1_1.67"/>
	</path>
	<path bundle_id="2"
		 bundle_name="TRAIN_REQ_002"
		 trainnumber="00214587"
		 traintype="TRAINTYPE_3"
		 path_profit="34.00"
		 path_length="3">
		<knot path_knot_index="1"
			 knotID="KNOT_001"
			 station_id="1"
			 arrival_time="100"
			 departure_time="102"
			 turnover_flag="0"
			 stop_flag="1"
			 station_label=""/>
		<knot path_knot_index="2"
			 knotID="KNOT_002"
			 station_id="2"
			 arrival_time="177"
			 departure_time="177"
			 turnover_flag="0"
			 stop_flag="1"
			 station_label=""/>
		<knot path_knot_index="3"
			 knotID="KNOT_003"
			 station_id="3"
			 arrival_time="237"
			 departure_time="237"
			 turnover_flag="0"
			 stop_flag="1"
			 station_label=""/>
		<track path_track_index="1"
			 trackID="TRACK_1_2"
			 track_id="1"
			 track_label="TRAINTYPE_3_1_3.00"/>
		<track path_track_index="2"
			 trackID="TRACK_2_3"
			 track_id="3"
			 track_label="TRAINTYPE_3_3_-2.29"/>
	</path>
	<path bundle_id="3"
		 bundle_name="TRAIN_REQ_003"
		 trainnumber="00314587"
		 traintype="TRAINTYPE_2"
		 path_profit="205.00"
		 path_length="2">
		<knot path_knot_index="1"
			 knotID="KNOT_002"
			 station_id="2"
			 arrival_time="100"
			 departure_time="100"
			 turnover_flag="0"
			 stop_flag="1"
			 station_label=""/>
		<knot path_knot_index="2"
			 knotID="KNOT_001"
			 station_id="1"
			 arrival_time="150"
			 departure_time="150"
			 turnover_flag="0"
			 stop_flag="1"
			 station_label=""/>
		<track path_track_index="1"
			 trackID="TRACK_2_1"
			 track_id="2"
			 track_label="TRAINTYPE_2_2_4.27"/>
	</path>
	<path bundle_id="4"
		 bundle_name="TRAIN_REQ_004"
		 trainnumber="00414587"
		 traintype="TRAINTYPE_2"
		 path_profit="255.00"
		 path_length="2">
		<knot path_knot_index="1"
			 knotID="KNOT_002"
			 station_id="2"
			 arrival_time="100"
			 departure_time="103"
			 turnover_flag="0"
			 stop_flag="1"
			 station_label=""/>
		<knot path_knot_index="2"
			 knotID="KNOT_001"
			 station_id="1"
			 arrival_time="153"
			 departure_time="153"
			 turnover_flag="0"
			 stop_flag="1"
			 station_label=""/>
		<track path_track_index="1"
			 trackID="TRACK_2_1"
			 track_id="2"
			 track_label="TRAINTYPE_2_2_5.31"/>
	</path>
</solution>