Human air traffic controllers dispatch planes in the air so that at any time planes keep enough distance from each other. I.e. an air traffic controller tells pilots where and in which time slot they shall fly so that safety is guaranteed for all planes. A very similar task is done by train dispatchers to organize the daily train traffic in a certain area of a train network.
Over the last few years we gained a lot of experience in the design and implementation of algorithms that support air traffic controllers and train dispatchers by calculating conflict-free solutions to dispatch problems with a wide range of various constraints. If you are interested in this topic and also in a collaboration with us then please contact us. Next we will present these algorithms and their solutions to various dispatch problems with short solution videos.
This video shows the general dispatch problem of automated dispatching. The input for the algorithms consists of:
The conditions modeled here are:
The objective is to route each train with timetable so as to fulfill above conditions and so as to minimize the total time needed for the trains to arrive at their respective destinations.
Note: The initial picture of the video visualizes a great amount of the input information to the algorithm. The movie part with the moving trains then visualizes the result calculated by the algorithm.
Just by looking at this simple artificial dispatch example video it is clear that a human would not be able to come up with such a nice solution. For a human the problem is simply too complex. In particular envisioning how trains move over time is extremely difficult for humans. The software algorithm can do it and even quite quickly.
The algorithm is able to model many more conditions that are relevant in railway dispatching. For instance, overlap conditions, speed differential conditions, capacity on group of rail tracks, blockage conditions caused by trains with oversize freight, ….
The algorithm models the dispatch problem as a 0-1 linear integer problem and then solves it using heuristics and an integer linear programming solver.
This video shows the result of the automated dispatching algorithm for the tunnel between France and England for a 4 hour period. Usually there is one-way traffic in the tunnel. To make it more interesting two sections of the tunnel are blocked. All trains in both directions must be scheduled so as to fit through the bottleneck in the tunnel. Shuttle, freight and intercity trains are visualized with different colors. Note that the visualization is distorted: In reality the tunnel part is much longer (40 km) than the station parts on the French and English sides (1 to 2 km). The conditions in this problem are similar to those of the introductory example but in addition there are safety distance conditions and speed differential conditions.
This video shows the result of the automated dispatching algorithm applied to a shunting area. The red trains want to go to the red flag, the blue trains to the blue flag. Their initial position is intertwined. The trains are locomotives that can change their direction anytime. At any time at most one locomotive may be on a track.
Note that the algorithm comes up with a solution where only two locomotives are routed along the long upper path. A human (unless a genius) would not come up with such a nice solution.
This is an artificial chessboard-like railway network. 80 trains need to be dispatched. Each train has a fixed start and destination point which is input to the dispatching algorithm. The conditions modeled here are:
The aim of the algorithm is to minimize the sum of the delay times over all trains.
Note that this is an artificially made difficult problem because many trains have to move on a small network. The denser the traffic the more difficult is the dispatching problem. This is a hard combinatorial problem. It is solved by splitting the area in subareas. But this is not easy to do because also along the borders of the subareas it must be made sure that the conditions above are fulfilled. However, this approach allows the parallelization of the computation.
However, the algorithm is able to solve much larger problems! Here is a same structured problem but with 1000 trains!
This video shows an air traffic control dispatching problem. Each plane has a fixed entry point and entry time into the network and also a fixed destination exit point. There are three flight levels: a red, a green and a blue flight level. Whenever a plane changes the flight level it changes its color. I.e. the network is a stacked chessboard-like network with 3 levels. The modeled conditions are:
These conditions imply that when two planes in the video cross each other they must be displayed with different colors, i.e. be flying on different flight levels.