Back to Project List

Rail CRC Home

Introduction to Rail CRC

Introduction to Problem 

Deadlock

Modelling the Problem

Back to top

Introduction to Rail CRC

Mission:

To understand and address challenges facing the Australian Railway Industry and to deliver innovative, globally competitive solutions.

Objectives:

• Intelligent decision support systems to assist rail managers and operators in making quality decisions;

• On-board control and driver advice systems to support safe train operation and encourage efficient driving practices;

• Automated systems for rail operation and maintenance processes to reduce maintenance cost, increase infrastructure capacity and improve reliability of rail systems and components; 

• Expertise and knowledge to introduce new system design and materials to provide substantial savings for railways by extending vehicle and infrastructure service life;

• National standards for traffic control and environment protection and nation-wide customer information and business e-commerce systems; and

• Technology transfer through integrated and articulated education, training and technology development programs to meet the current and future needs of the rail industry.

Back to top

Introduction to Problem

Most of Australia's long-haul rail network is single-line track, with occasional crossing loops that allow trains to cross or overtake. These crossing loops are usually not much longer than a typical train. For a pair of trains to pass each other, one train will pull off the main line and stop on the loop, the second train will pass on the main line, and then the first train will drive back onto the main line and continue.

Detailed train plans that specify future train movements, including nominal crossing locations and times, are developed by train planners. The methods used are substantially manual, and it can take many weeks to develop a timetable. On the day of operation the train movements and crossing decisions may be revised by a train controller responding to operational disturbances.

Back to top

Deadlock

Train planners and train controllers plan movements that avoid deadlock. Deadlock occurs when it becomes impossible to move every train forwards to its destination.  

Avoiding deadlock is straightforward if there are few trains and many crossing loops. However, avoiding deadlock becomes more difficult as the number of trains increases, or if some of the trains are longer than some of the crossing loops. The following example is deadlocked because neither of the trains will fit on either of the crossing loops.

The Rail CRC is currently funding a project to develop tools that will calculate good crossing plans. These tools use a probabilistic search technique to generate and assess alternative crossing plans. During the search, it is important that crossing plans that will end in deadlock are detected and discarded quickly. It is also important for us to understand the impact of deadlock avoidance schemes on network capacity.

Back to top

Modelling the Problem

Petersen & Taylor (1983) have devised a simple method for ensuring that train movements do not lead to deadlock. However, there are several limitations of their method:

• The method assumes that any train can refuge on any vacant loop. This is not the case if some trains are longer than some loops, and may be other operational reasons why some trains may not use some loops.
• The method is restrictive—it will disallow some movements that would not necessarily lead to deadlock.
• The method assumes that the network is a single-line track with crossing loops. It does not apply to general rail networks with more general train movements.

To model the more general problem, we consider the rail network to be composed of track segments. Each track segment can have at most one train on it at any instant.

A path is a sequence of track segments that a train may follow in order to complete a journey. Each train has associated with it a set of possible paths.

The state of the network is described by the set of (train, segment) pairs that specifies the location of each train. The set of active paths for a train is the set of that train's paths that include the current location. A train is moved by selecting an unoccupied successor segment from one of its active paths. The system is not deadlocked if there is a sequence of train moves that will get each train to the end of one of its paths.

A theoretical understanding of deadlock is essential for operations improvement and for optimisation of network performance. In seeking good train plans it is important that solutions that are leading to deadlock are ruled out quickly. It is also important to avoid unnecessarily conservative practices, such as avoiding long trains because they may lead to deadlock. Additionally, a theoretical understanding of deadlock avoidance will assist in evaluating network capacity and network performance in general.

References

Petersen, E. R. & Taylor, A. J. 1983, Line block prevention in rail line dispatch and simulation models, Information Systems and Operations Research, vol. 21, no. 1, pp. 46-51.

Back to top