Automated rail and air traffic flow routing

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.

1) Introductory example

This video shows the general dispatch problem of automated dispatching. The input for the algorithms consists of:

  1. The network. I.e. the graph of railway connections and nodes.
  2. The position of each train. I.e. the start node of each train.
  3. The destination node for each train. Here each train wants to travel to the node with the same colored flag as the train has.
  4. max possible speed for each train on each rail track.

The conditions modeled here are:

  1. At any time there may be at most one train on each track.
  2. At any time no two trains are allowed to travel towards the same node.

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.

2) A tunnel example

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.

3) Automated dispatching for a shunting problem

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.

4) A chessboard-like network example

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:

  1. On each track there can be at most one train at any time.
  2. On diagonals in the same square there must be at most one train at any time.
  3. At any time there must not be two trains moving towards the same node.
  4. A train is only allowed to take a turn strictly less than 90 degrees.

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!

5) An air traffic control example

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:

  1. Inside one air cube there must be at most one plane at any time. However, on opposite sides of an air cube there can be two planes, one plane on each side.
  2. No two planes can fly towards the same node at any time.
  3. Planes are not allowed to fly sharp turns. I.e. in planar and vertical direction only a simple (45 degrees like in the video) turn is allowed.

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.