Let us build a solution to the sample instance from the ground up.
You do not need to be familiar with the data models yet or the business rules, but we recommend that you keep the following documents handy while working through the example
- The description of the problem instance data model
- The description of the solution data model
- The definition of the twelve business rules that a solution must satisfy
Tip: In order to work with the large JSON files it can be helpful to use an editor that offers a 'grid view', such as the screenshots below, to keep the overview. If anybody knows a good freeware too, please let us know! Otherwise you can also use evaluation versions of Altova or Oxygen.
We study what is contained in the sample instance
There are two service intentions, for trains 111 and 113.
- service intention 111 has three section_requirements, for section_markers 'A', 'B' and 'C'.
- service intention 113 has only two section_requirements, for section_markers 'A' and 'C'.
We notice train 111 must circulate sometime between 8:20, its earliest possible start time at its first section_requirement, and 8:50, its latest desired exit time at its last section_requirement. Train 111 also has a section_requirement at some intermediate section 'B', where it wants to stop for a minimum of 3 minutes and exit that section no earlier than 8:30. Think of this as a commercial stop of the train: if the timetable in 'B' says "Departure at 8:30", then the passengers wanting to catch the train in 'B' would be unhappy if it left at 8:25, or anytime before 8:30. Therefore, it makes sense to require a departure "no earlier than" 8:30. This is what the exit_earliest for section_requirement B ensures.
Likewise, train 113 must circulate sometime between 7:50 and 8:16 (so actually earlier than train 111). It has no other requirements.
Also, note that neither train specifies any connections that would have to be observed. All we have to worry about are the earliest and latest time requirements. That can't be too hard?
We recall from the short introduction that producing a solution amounts to
- picking exactly one of the possible routes for each train, i.e. selecting a path from a source to a sink node in the route graph
- then assign times to all events (nodes) on this path (such that all twelve business rules are satisfied)
We also recall that the route graphs are always directed and acyclic graphs.
So, what are the possible routes for the two services? We will see in the discussion of the problem instance data model how to derive the graph structure from the JSON. For the purpose of this example, let us just pretend we already knew that the two route graphs for service intentions 111 and 113 are actually identical and look as follows:
Hint: you may use the route graph utility script to produce the route graphs as a networkx directed graph and that should produce the same graphs as in these pictures.
Note that the fact that they have identical route graphs means the trains actually have the same travel path. In the "real world" this would mean they travel along the same pyhsical tracks.
We now start to build the solution. The following steps are just an example; it is neither the only nor a very intelligent way to go about this problem. But it works for simple examples such as this one. We will follow these steps:
- select a route for each service intention
- Take a first shot at assigning times to all events along the chosen routes
- check if we satisfy all business rules
- If yes, we are done
- If not, adjust the event times and check again
We must choose a path from a source node to a sink node in the route graph.
We notice that no route_section has a positive penalty. If there were any such route_sections, we might try to avoid them when choosing our first route. But in this case, it really does not matter - all routes are equally 'desirable'. Our choice is as follows (we list the sequence_numbers of the route_sections):
- train 111 shall travel over route_sections # 3 -> 4 -> 5 -> 6 -> 10 -> 13 -> 14
- train 113 shall travel over route_sections # 1 -> 4 -> 5 -> 6 -> 10 -> 13 -> 14
With the route choice above, we have the following paths for the two trains. Each entry and exit event (i.e. each node) needs to be assigned a time. In the language of the solution data model, the arcs in the following graph are called train_run_sections.
Our first inclination for assigning the event times is to schedule every event as early as possible. Specifically,
- let the trains start as early as possible
- let them spend only the required minimum_running_time on each section
To do that, it helps to add some more information to the train_run_sections (i.e. the arcs) in the graph:
- the section_marker of the associated route_sections, if there is one
- the minimum_running_time of the associated route_section
Now the earliest possible starting times for the trains are given by the entry_earliest time of the first section_requirement (by the way: it is a general convention of all problem instances, that the first setion_requirement always has an entry_earliest, and the last section_requirement always has an exit_latest)
In our case, this is 07:50:00 for train 113 and 08:20:00 for train 111:
Now, we just set the event times that result from propagating the minimum_running_time along the path. We get:
This is our initial solution. Let's bring it into the shape of the solution data model. For this, we put the train_run_sections (the arcs in the picture above) in a list and fill in their information. Also, we must add the reference to the problem instance so the grader will know to what problem this is supposed to be a solution. You can download the resulting solution file here. It looks like this:
We check if we have produced a feasible solution, i.e. whether it satisfies all business rules.
We check the Consistency Rules first
- #1 problem_instance_hash present: Yes, the hash -1254734547 of the sample instance is correctly entered as the problem_instance_hash ✔️
- #2 each train is scheduled: We schedule both trains 111 and 113. ✔️
- #3 ordered train_run_sections: Yes, we simply numbered their sequence_numbers incrementally from 1 to 7. ✔️
- #4 reference valid route: Yes, we have added all the necessary information. ✔️
Recall (see here) that the route_section_id is constructed from the pattern route.id#route_section.sequence_number.
Also note that train 111 uses one route_section from the route_path with id 3, while train 113 only uses route_sections from route_path 1. - #5 train_run_sections form a path in the route graph: Yes, they do, we chose them exactly like that above. ✔️
- #6 pass through all section_requirements: Yes, train 111 passes A, B and C, train 113 passes A and C, as required. ✔️
Important remark: In fact, we guarantee that if you pick any path from a source to a sink node in the route graph of a service_intention you will pass all required section_markers and do so in the correct order. All you need to do, therefore, is make sure you add that information to the train_run_sections in their section_requirement field. - #7 consistent entry_time and exit_time times: Yes, by construction we just repeat the exit_time of a train_run_section as the entry_time of the next one ('next' according to their sequence_number). ✔️
Let's check the Planning Rules next
-
#101 Time windows for latest-requirements: We have two latest requirements (see the file or screenshot above:
- exit_latest of 08:16:00 for service_intenation 113 in C. The train_run_section associated to section_requirement C has an exit_time of 07:54:05, which is certainly before 8:16 :heavy_check_mark:
- exit_latest of 08:50:00 for service_intention 111 in C. Here, the relevant train_run_section has exit_time 08:24:05 :heavy_check_mark:
-
#102 Time windows for earliest-requirements: We have three _earliest_requirements:
- service_intention 113:
- entry_earliest 07:50:00 for section A. We scheduled this event for exactly this time, which is ok. :heavy_check_mark:
- service_intention 111:
- entry_earliest 08:20:00 for section A. We scheduled this event for exactly this time. :heavy_check_mark:
- exit_earliest 08:30:00 for section B. We scheduled this event for 08:21:57. :x:
- service_intention 113:
We have found a rule violation. Let's fix that.
In order to satisfy the "exit_earliest at 8:30" requirement for 111 in B and stay true to our idea of scheduling each event as early as possible, we just postpone that event from 08:21:57 to 08:30:00 and propagate the times for the events following it. We get get following picture (adjusted event times in red):
Check Business Rules again
It is immediately obvious that the changes we made do not influence the Consistency Rules #1 - #7. We don't check them in detail anymore.
-
#101 Time windows for latest-requirements: We didn't change anything for train 113, just check 111 again.
- exit_latest of 08:50:00 for service_intention 111 in C. We have postponed this event from 08:24:05 to 08:32:08, but that is still well before the deadline. :heavy_check_mark:
-
#102 Time windows for earliest-requirements: Again, train 113 remains unchanged and was ok before. Just check 111 again.
We have two _earlieste_requirements for train 111:- entry_earliest 08:20:00 for section A. Event is still scheduled at 08:20:00. :heavy_check_mark:
- exit_earliest 08:30:00 for section B. Event is now scheduled at exactly 08:30:00. ✔️
-
#103 Minimum section time: Exactly by construction, we always spend at least the minimum_running_time on each section. In order to satisfy this rule, we just have to check if, for some train_run_section, we also need to account for a min_stopping_time associated with that section.
In our service_intentions (see screenshot above), we have only one section_requirement that requires a stopping time, namely section_requirement #2 for train 111, which refers to the section 'B' and requires 3 minutes of stopping time.
The train_run_section for 'B' has an entry_time of 08:21:25 and an exit_time of 08:30:00. We have exit_time - entry_time = 8 minutes and 35 seconds.
The rule says that 8 minutes and 35 seconds must be greater-or-equal to the minimum_running_time plus the min_stopping_time. But the latter two only sum to 3 minutes and 32 seconds. So the condition of the rule is satisfied ✔️
-
#104 Resource Occupations: We must check that the two trains do not try to occupy two resources "at the same time" (in fact, there must be a positive separation between resource occupations given by the release time of the resource, typically ~30s).
This rule is what makes the problem NP-complete. In our case, we are lucky, because there are only two trains. They actually do use common resources (which resource occupations are occupied on which sections is illustrated in the route graph above). However, we note that- train 113 ends at 07:54:05
- train 111 starts at 08:20:00
- all resources in the instance have a release_time of 30s
In other words, after 07:54:35 train 113 will certainly not occupy any resources anymore at all, train 111 will therefore never come into conflict. The rule is satisfied. ✔️
- #105 Connections: There are no connections defined in our two service_intentions, there is nothing to check. ✔️
We have produced a feasible solution. Here it is again all its glory (you can download the solution file here).
Remark: This solution is actually even an optimal solution, meaning it receives an objective value of 0. Refer to the explanation of the objective function for more details.