Say you are living in Eindhoven and would like to spend a day in Amsterdam: what better way to get there than taking the train? Before your train departs, a whole logistic operation has taken place in the headquarters of the railway company to make this trip possible.
This operation starts some years in advance, where train lines are specified by their routes and subsequent stops, as well as by their hourly frequency: for example the decision that the train you are taking starts in Maastricht and ends in Den Helder. This first stage is called the line planning.
The next decision, taken a year in advance, is the time that the train is leaving: the construction of a timetable (see Figure 1 for an example of a timetable). Then, the length of each train is determined by scheduling rolling stock. Finally, duties are assigned to the personnel in the crew scheduling phase. The timetable and planning of rolling stock and crew is changed around four weeks in advance in case of, for example, maintenance on the infrastructure, and even changes in real-time could be needed when, for example, accidents take place.
Figure 1: Example of a timetable in the Netherlands
In this article I discuss new research we have conducted at Netherlands Railways (Nederlandse Spoorwegen, NS). In this research we developed a new method to automatically construct a train schedule that can meet the growing transportation needs in the Netherlands.
Timetabling at NS
Say you want to go from Eindhoven to Amsterdam, you can then take a train operated by NS. NS is the largest provider of mobility services in the Netherlands: approximately 62% of all people in the Netherlands use their services on a yearly basis. Passenger numbers have fallen because of COVID-19, but in 2019 NS transported approximately 750,000 unique passengers every day.
The timetable of NS is cyclic with a cycle time of an hour, which means that the timetabling process starts with the design of a basic hour pattern. The setting at the end of this pattern must agree with the setting at the start of the pattern: in this way we can repeat the basic hour pattern to create a timetable for a longer period. An advantage of this cyclic timetable is that it is transparent to passengers, as there is no need to remember complex timetables by heart. As a passenger going to your work in Amsterdam from Utrecht for example, you know that there is a train every 10 minutes starting at 07.09. Additionally, a cyclic timetable is relatively easy to handle for employees across the different departments of NS.
Until 1992, timetabling was done by hand. Automatic tools did not exist and frequencies were still low. Due to a growing number of train connections and higher frequencies of train lines, the requirements for the timetable increased and the need for a decision support system also grew. Therefore, NS developed a system called DONS (‘Designer of Network Schedules’). First, DONS was used in combination with the solver CADANS. Based on the infrastructure and the line planning, a model is built in DONS, including the frequency constraints and connections. In this process, the track that each train uses between stations is predetermined beforehand. As you will see in this article this feature of CADANS can be very restrictive in finding a timetable.
Predetermining the tracks that trains will use raises a complication regarding tracks crossing each other. Trains using these tracks should be scheduled in such a way such that they don’t meet at the intersection. An example of such a track can be seen in Figure 2, where station Leiden, with two tracks, is shown. There is a yellow train coming from The Hague and going in the direction of Haarlem, and a blue train coming from Schiphol and going in the direction of The Hague. Here it is predetermined that the yellow train stops at the bottom track in Leiden and the blue train stops at the upper track.
Therefore, we know that these trains might cross at the right side of Leiden. A timetable should of course take this into consideration. The yellow train and the blue train cannot thus leave whenever they want. At the same time, their departure times depends also on the schedule of all the trains in the region around Leiden. This means that their departure times should be chosen according to two restrictions, the first is that these trains won’t meet at the crossing, and the second comes from the schedules of all other trains in the region.
These restrictions might lead to a situation where no solution exists, when these trains have to be at the crossing point at the same time because of restrictions elsewhere. If such a conflict arises we say that a solution for this rail network and track assignment does not exist, or that the timetable problem is not satisfiable.
Figure 2: Predetermined routes of two trains in yellow and blue.
In case a solution for this rail network and track assignment does exist, CADANS can generate a timetable with this track assignment. A timetable generated by DONS and CADANS was used to create the Dutch railway timetable of 2007. In subsequent years, the Dutch railway timetable was based on this timetable.
The process of constructing a timetable became more and more difficult in the past years because frequencies for some connections have increased—sometimes up to 6 trains per hour, for example between Eindhoven and Amsterdam—and better train connections are sought. This results in a problem with a lot of restrictions. According to CADANS, these restrictions are in conflict with each other and therefore no solution exists.
However, our planning specialists observe that solutions do exist when making small adjustments. For example, they can omit some connection constraints, shorten a follow-up time when this is allowed, or they can be more flexible with which tracks are used. But CADANS cannot find these solutions, because in this program the tracks are predetermined and cannot change. The following example, following on the example of Figure 2, illustrates that this implies a lot of restrictions and could easily result in a problem that is not satisfiable.
In this example, illustrated in Figure 3, we consider again the area around station Leiden, with a yellow train coming from The Hague and traveling in the direction of Haarlem, and a blue train coming from Schiphol and traveling in the direction of The Hague. The default route would be to take the right track as long as possible. This results in the routes in Figure 3a. Say, for example because of restrictions elsewhere, the trains both have a fixed starting point as the indicated trains in Figure 3b. Then, continuing their routes, this will lead to a problem at the crossing as in Figure 3c. Here, we have a problem that is not satisfiable.
If different routes are used as in Figure 3d, the routes of the yellow and blue train will cross at the other side of Leiden. Considering the same starting point as before (Figure 3e), no problems are encountered while creating a feasible timetable (Figure 3f).
Figure 3: Illustration of the route choice of trains.
As CADANS could not find solutions anymore, the construction of the timetable became again at some point mainly a human planning process, although it is supported by computer aided design tools. DONS is now used as a support system, mainly for conflict signaling. In what follows I will show how this weakness of CADANS can be resolved, and how we can free our software from having to work with predetermined track assignment. But before that we need to answer an important question, why is it so complex to make a timetable in the Netherlands?
The Dutch Train Network Infrastructure
One of the reasons why constructing a basic hour pattern is so complex is the density of the infrastructure in the Netherlands. The infrastructure of a train network corresponds to a network structure. Figure 4 shows examples of different network structures. For a bus network, as in Figure 4a, it is easy to construct a timetable, as all stations are connected in just one line. For a star network, as in Figure 4b, it is also relatively easy to construct a timetable. All train lines start or end at the central node, but apart from this node they are independent from each other. Therefore, the departure times of the trains have to match at this central node and the rest of the timetable can be derived from these departure times. The train network infrastructure in Denmark is an example of this.
The infrastructure in the Netherlands looks more like a hybrid network, of which an example is shown in Figure 4c. A hybrid network is a combination of two or more other network types; in case of this example a star network and multiple bus networks. The infrastructure in the Netherlands is and will be created to match the demand of the passengers and to have travel times that are as low as possible. This results in a dense network that contains a lot of cycles. These cycles break the independence of the different lines as in a star network, as there are multiple nodes in the network where departure times of the trains should correspond to each other. This makes the construction of a timetable more difficult.
Figure 4: From left to right: (a) Example of a bus network (b) Example of a star network (c) Example of a hybrid network.
New Research on the Dutch Railway Timetabling Problem
Let’s go back to the timetabling problem. The problem that CADANS is trying to solve is called the Periodic Event Scheduling Problem (PESP). As mentioned before in PESP the tracks that trains can use are predetermined. The example above in Figure 3 shows that a timetabling problem that is considered as not satisfiable using fixed routes might be satisfiable when using another combination of detailed routes. This might be easy to see in a small example as above, but in an extensive network such as the Dutch railway network support is needed. Therefore, I have developed an alternative method for constructing timetables that is able to incorporate multiple route options.
The Open-ended Periodic Event Scheduling Problem
The method that can incorporate multiple route options has been introduced as the Open-ended Periodic Event Scheduling Problem (OPESP). In this problem, departure times are assigned to the departures of trains at each station they visit. All departure times together form a new timetable (a schedule).
In the PESP, where the tracks are given, departure times are given a number between 0 and 59, corresponding to the minute at which the train departs. The departure entails the departure from a given track, and in a valid timetable the train is free to use this given track at the specified time.
In the new OPESP, a departure entails the departure from the station, where the track is not yet specified. Therefore, for each departure there are multiple route options that this train can take.
Say that a specific train departing at some station has options. The specialty in this new problem is that the departure time is now determined between 0 and . Then, a departure time in the kth interval of 60 corresponds to choosing the kth route option. An illustration of this idea can be seen in Figure 5: if the departure time is i, then the train will depart around minute 30 and will take the second route option.
Figure 5: Determining a departure time in OPESP
SATisfiability problems
The Dutch railway timetabling problem is equivalent to a SAT(isfiability) problem. By using state-of-the-art SAT solvers, this encoding to a SAT problem leads to a very efficient solving approach for the problem of constructing a timetable.
In a SAT problem we start with a formula, which is a kind of sentence. This formula consists of variables, which can be true or false, and connectives that connect the variables. These connectives can be or, and or not. A solution to the problem consists of an assignment of true or false to each variable, such that the formula is true.
For example, let the formula be and . Then the only solution to the problem would be the assignment true and true. If the formula is or not then the assignment true and false is an example of a solution.
In the encoding of the railway timetabling problem, we have a variable for each train , station and time . If true, then train leaves station before or at time . This encoding works very well in the new OPESP: if we have true, we know that train takes the first route option after leaving station (see also Figure 5).
Results
By introducing the Open-ended Periodic Event Scheduling Problem (OPESP), flexible track use is incorporated in the SAT model of the cyclic railway timetabling problem. This method is also tested on a test instance based on all train lines in the area between Amsterdam Sloterdijk, Enkhuizen and Den Helder. This area is also called the ‘Kop van Noord-Holland’, see Figure 6.
Figure 6: Train lines in the area ‘Kop van Noord-Holland’.
When the previous method is used, with fixed default routes for each train (taking the right track as long as possible), a solution does not exist. Using the new method, a timetable for this substantial part of the Dutch railway network can be found in less than a minute. Further research is currently being done to extend this method and apply the method to a larger part of the Dutch railway network!
On Friday 24th of September Professor Ton Koonen received a royal distinction “Ridder in the Orde van de Nederlandse Leeuw” during the symposium “Optical Networks – communication fabric of our society”, preceding his valedictory lecture “Light work(s)”.
We might not be fully aware of it, but we all use wireless communication everyday in many familiar situations, such as when we connect our laptop to the local Wi-Fi network, when we use navigation apps to orientate ourselves while driving, or when we send a message to a friend using our smartphones. It has become so natural for the world we live in, that we often take it for granted and have no idea of how it works.
options. The specialty in this new problem is that the departure time is now determined between 0 and 
. Then, a departure time in the kth interval of 60 corresponds to choosing the kth route option. An illustration of this idea can be seen in Figure 5: if the departure time is i, then the train will depart around minute 30 and will take the second route option.
, which can be true or false, and connectives that connect the variables. These connectives can be or, and or not. A solution to the problem consists of an assignment of true or false to each variable, such that the formula is true.
and 
. Then the only solution to the problem would be the assignment 
true and 
true. If the formula is 
then the assignment 
for each train 
, station 
and time 
. If 
true, then train 
true, we know that train 
