Deadlock Avoidance and Detection in Railway Simulation Systems

Bertrand Simon, Brigitte Jaumard, Thai Hoa Le

Abstract

Avoiding or preventing deadlocks in simulation tools for train scheduling remains a critical issue, especially when combined with the objective of minimization (e.g., the travel times of the trains). The deadlock avoidance and detection problem is revisited, and a new deadlock avoidance algorithm, called DEADAALG, is proposed based on a resource reservation mechanism. The DEADAALG algorithm is proved to be exact; that is, it either detects an unavoidable deadlock resulting from the input data or provides train scheduling free of deadlocks with the scheduling algorithm SIMTRAS. Moreover, it is shown that SIMTRAS is a polynomial time algorithm with an O(|S|·|T|2 log |T|) time complexity, where T is the set of trains and S is the set of sections in the railway topology. Numerical experiments are conducted on Canada's Vancouver-Calgary single-track corridor of Canadian Pacific Railway Limited. Then it is shown that SIMTRAS is efficient and provides schedules of a quality that is comparable with that of an exa...
BibTeX
@inproceedings{simon2014deadlock,
  author = {Bertrand Simon and Brigitte Jaumard and Thai Hoa Le},
  title = {{Deadlock Avoidance and Detection in Railway Simulation Systems}},
  booktitle = {Transportation},
  year = {2014},
  doi = {10.3141/2448-06},
}

Loading related content...

Figure