Avoiding or preventing deadlocks in simulation tools for train scheduling remains a critical issue, especially when combined with the objective of minimizing, e.g., the travel times of the trains. In this paper, we revisit the deadlock avoidance and detection problem, and propose a new deadlock avoidance algorithm, called DEADAALG, based on a resource reservation mechanism. The DEARAALG algorithm is proved to be finite, and either detects an unavoidable deadlock resulting form the input data or provide a train scheduling thanks the SIMTRAS algorithm, which is free of deadlocks in O (|S |.|T |2 log |T |), where T is the set of trains and S is the set of sections in the railway topology. Experiments are conducted on the Vancouver-Calgary single track corridor of Canadian Pacific. We then show that the SIMTRAS algorithm is very efficient and provides schedules of a quality that is comparable to those of an exact optimization algorithm, in tens of seconds for up to 30 trains/day over a planning period of 60 days.
Published June 2013 , 36 pages