This document describes the rules that have to be observed in order that a solution to a problem instance is considered valid.
Your solver will need to make sure that the solutions it produces observe these rules.
We categorize the rules roughly in two groups:
- Consistency rules, which mostly check technical conformity to the data model
- Planning rules, which represent the actual business rules involved in generating a timetable
| # | Rule Name | Rule Definition | Remarks |
|---|---|---|---|
| 1 | problem_instance_hash present | the field problem_instance_hash is present in the solution and has the correct value (namely that of the problem instance that this solution refers to) | |
| 2 | each train is scheduled | For every service_intention in the problem_instance, there is exactly one train_run in the solution | |
| 3 | ordered train_run_sections | For every train_run, the field sequence_number of the train_run_sections can be ordered as a strictly increasing sequence of positive integers | in other words, the sequence_numbers are unique among all train_run_sections for a train_run. Typically, it is natural to also list the train_run_sections in increasing order in the JSON file, such as is the case for the sample solution. However, strictly speaking de-/serialization from/to JSON need not preserve orders. Having an explicit sequence_number is therefore advisable. Example: The sample solution:  |
| 4 | Reference a valid route, route_path and route_section | each train_run_section references a valid (i.e. one that exists) route for this service_intention, route_path and route_section | for example, in the sample_solution:  |
| 5 | train_run_sections form a path in the route graph | If two train_run_sections A and B are adjacent according to their sequence_number, say B directly follows A, then the associated route_sections A' and B' must also be adjacent in the route graph, i.e. B' directly follows A'. | In other words, the train_run_sections form a path (linear subgraph) in the route graph. Check the illustrations in the Output Data Model description. |
| 6 | pass through all section_requirements | a train_run_section references a section_requirement if and only if this section_requirement is listed in the service_intention. | for example, in the sample solution, the train_run_sections for service_intention 111 have references to the section_requirements A, B and C. But the train_run_sections for service_intention 113 only reference section_requirements A and C:  This is because in the sample instance the service_intention for 113 does not have a section_requirement for the section_marker 'B', but only for 'A' and 'C'  |
| 7 | consistent entry_time and exit_time times | for each pair of immediately subsequent train_run_sections, say S1 followed by S2, we have S1.exit_time = S2.entry_time | recall the ordering of the train_run_sections is given by their sequence_number attribute. Again, look at the sample solution as an example:  |
| # | Rule Name | Rule Definition | Remarks |
|---|---|---|---|
| 101 | Time windows for latest-requirements | If a section_requirement specifies a entry_latest and/or exit_latest time then the event times for the entry_event and/or exit_event on the corresponding train_run_section SHOULD be <= the specified time. If the scheduled time is later than required, the solution will still be accepted, but it will be penalized by the objective function, see below. Important Remark: Among the 12 business rules, this is the only 'soft' constraint, i.e. a rule that may be violated and the solution still accepted. In some cases, for example for problem instance 05, it is impossible to schedule all trains satisfying all 12 business rules. In order to obtain feasible solutions, you have no other choice than to delay some of the trains (i.e. violating some entry_latest/exit_latest requirements). In such cases, you should of course try to minimize the resulting delay penalty. |
for example, in the sample instance for service_intention 111 there is a requirement for section_marker 'C' with a exit_latest of 08:50:00. In the sample solution the corresponding exit_event is scheduled at 08:32:08, so well before the required time. Any time not later than 08:50:00 would be just as fine. Any time >= 08:50:01 would incur a lateness penalty as defined in the objective function below. section_requirement:  solution:  |
| 102 | Time windows for earliest-requirements | If a section_requirement specifies an entry_earliest and/or exit_earliest time, then the event times for the entry_event and/or exit_event on the corresponding train_run_section MUST be >= the specified time | for example, in the sample instance for service_intention 111 there is a requirement for section_marker 'A' with an entry_earliest of 08:20:00. Correspondingly, in the sample solution the corresponding entry_event is scheduled at precisely 08:20:00. This is allowed. But 08:19:59 or earlier would not be allowed; such a solution would be rejected. section_requirement:  solution:  |
| 103 | Minimum section time | For each train_run_section the following holds: texit - tentry >= minimum_running_time + min_stopping_time, where tentry, texit are the entry and exit times into this train_run_section, minimum_running_time is given by the route_section corresponding to this train_run_section and min_stopping_time is given by the section_requirement corresponding to this train_run_section or equal to 0 (zero) if no section_requirement with a min_stopping_time is associated to this train_run_section. |
For example, take train_run_section #3 for train 111 in our sample solution. It refers to route_section 111#5. This route_section has a minimum_running_time of 32 seconds, accoring to the sample scenario. Furthermore, on this train_run_section we claim to satisfy section_requirement for section_marker 'B'. That section_requirement requires a min_stopping_time of 3 minutes. In total, we need to spend at least 3min and 32s on this train_run_section to satisfy this rule. Luckily, we actually spend 8min and 35s (from 08:21:25 until 08:30:00), so we are fine. section_requirement:  route_section:  solution:  |
| 104 | Resource Occupations | Let S1 and S2 be two train_run_sections belonging to distinct service_intentions T1, T2 and such that the associated route_sections occupy at least one common resource. Without loss of generality, assume that T1 enters section S1 before T2 enters S2, i.e. tS1, entry < tS2, entry. Then for each commonly occupied resource R, the following must hold: tS2, entry >= tS1, exit + dR, release where dR, release is the release_time (freigabezeit) of resource R |
In prose, this means that if a train T1 starts occupying a resource R before train T2, then T2 has to wait until T1 releases it (plus the release time of the resource) before it can start to occupy it. This rule explicitly need not hold between train_run_sections of the same train. The problem instances are infeasible if you require this separation of occupations also among train_run_sections of the same train. Example: We will see some examples of what this means in the worked example |
| 105 | Connections | Let C be a connection defined in service_intention SI1 onto service_intention SI2 with section_marker M and let dC be the connection's min_connection_time. Let S1 be the train_run_section for SI1 where the connection will take place (i.e. the section which has 'M' in the section_requirement attribute) and S2 the same for SI2. Then the following must hold: tS2, exit - tS1, entry >= dC, where, again, tS1, entry denotes the time for the entry_event into train_run_section S1 and tS2, exit the time for the exit_event from train_run_section S2. |
Example: The first problem instance with connections is instance 02. Specifically, let's look at the following connection in 'WAE_Halt' from 18013 to 18224, with a minimum connection time of 2minutes and 30s:  We take the sample solution for this instance. The entry_time of 18013 into the relevant train_run_section is 06:42:12: solution for 18013:  The exit_time of 18224 from its relevant train_run_section is 06:48:04: solution for 18224:  Therefore, we have a time difference of almost 6 minutes between the two events, well above the minimum time span of 2.5 minutes. |
The objective function is used by the grader to determine how "good" a solution is. We give a more exact formula below, but basically it is calculated as the weighted sum of all delays plus the sum of routing penalties.
A delay in this context means a violation of a section_requirement with an exit_latest or entry_latest time. Each such violation is multiplied by its entry_delay_weight/exit_delay_weight and then summed up to get the total delay penalties.
Remark: A missing solution in a submission will incur a penalty of 10'000 points. A solution that violates any of the eleven mandatory business rules (all except #101) will be treated like a missing solution.
The best possible objective value a solution can obtain is 0 (zero). A value > 0 means some latest_entry/latest_exit section_requirement is not satisfied in the solution, or a route involving routing_sections with penalty > 0 was chosen.
The "formula" for the objective function is as follows:
where:
- The first sum is taken over all service_intentions SI and all section_requirements SR therein,
- The second sum is taken over all train_run_sections TRS,
- entry_delay_weightSR stands for the entry_delay_weight specified for this particular section_requirement. If the section_requirement does not specify an entry_delay_weight, then it is assumed to be = 0.
- tentry denotes the scheduled time in the solution for the entry_event into the train_run_section associated to this section_requirement,
- entry_latestSR denotes the desired latest entry time specified in the field entry_latest of the section_requirement
Note: If the section_requirement does not specify an entry_latest, then it is assumed to be ∞, i.e. the max will be zero and the term can be ignored. - exit_delay_weightSR is analogous to entry_delay_weightSR, except for the exit_delay_weight of this particular section_requirement,
- texit denotes the scheduled time of the exit_event from the train_run_section associated to this section_requirement,
- exit_latestSR is analogous to entry_latestSR, except for the exit time (as specified in exit_latest of the section_requirement),
- penaltyroute_sectionTRS denotes the value of the field penalty of the route_section associated to this train_run_section.
Remark: All time differences are measured in seconds. The normalization constant 1/60 for the delay penalty term means that 60s of delay will incur 1 penalty point (provided all delay_weight are equal to 1). In other words, we count the delay 'minutes'.
We give a couple of simple examples illustrating the calculation of the delay and routing penalties.
Suppose the service_intention has the following three section_requirements:
- for section_marker A: entry_earliest = 08:50:00
- for section_marker B:
- entry_latest = 09:00:00 with entry_delay_weight = 2
- exit_latest = 09:10:00 with exit_delay_weight = 3
- for section_marker C: exit_latest = 09:220:00 with exit_delay_weight = 1
Suppose also that the routes are rather simple, namely
- there is only one route (no alterntives),
- all its route_sections have zero penalty and
- on the first train_run_section we have section_marker A, then a section without marker, then B, then a section without marker and finally C.
The complete picture with the train_run_sections and the respective section_requirements would therefore look like this:
We now give several example solutions and the value of the objective function for them. Blue dots denote the actual event_times of the solution, i.e. entry and exit times from train_run_sections. The blue lines joining them are purely a visualisation aid, they are not part of the solution.
In this solution, all section_requirements are satisfied. The entry and exit times into the sections are before the desired entry_latest/exit_latest. Therefore, the delay is zero. Since there is no routing penalty, this is also its objective value:
objective_value = 0
In this solution, the train runs earlier than in Example 1. But this is not "better"; it does not get any "bonus points". This solution's objective value is identical to the one of Example 1, i.e.
objective_value = 0
In this solution, the exit from the train_run_section with section_marker 'B' happens only at 09:13:00. This is 3 minutes later than the desired exit_latest of the section_requirement for 'B'. Since the exit_delay_weight is 3, for this solution we have
objective_value = 3 * 3 = 9
In this solution, in addition to the delayed departure at B as in Example 3, we also have a delayed exit_event from section C, namely this event occurs 5.5 minutes after the desired exit_latest of 09:20:00. The exit_delay_weight for this section_requirement is 1, therefore:
objective_value = 3 * 3 + 1 * 5.5 = 14.5
Let's take the same routing graph as in the discussion of the output data model, this time augmented with some routing penalties. The route graph looks like this:
- the numbers in black denote the route_section.id
- the numbers in red denote the route_section.penalty. No number means no penalty is specified for this route_section
In the solution, the route highlighted in yellow was chosen. This route passes through the route_sections 2 -> 4 -> 5 -> 6 -> 11 -> 12 -> 14. None of the sections on this route specify a penalty. Since a missing penalty is equivalent to a penalty of zero, the routing penalty for the whole route is also zero.
Also the following solution does not involve any route_sections with positive penalty and therefore does not incur any routing penalty either. It is an equally good route as the one in Example 1.
This solution chooses a route with one route_section with positve penalty, namely route_section 8 with penalty 0.7.
The routing penalty for this route is therefore 0.7
This solution chooses a route with two route_section with positve penalty, namely
- route_section 1 with penalty 6
- route_section 13 with penalty 1.3
The routing penalty for this route is therefore 6 + 1.3 = 7.3
