Bertrand Simon: Thursday 04/27/2017 at 17h.
Bertrand Simon is a second year PhD student within the ROMA project team. He will present a work that he has performed during his master degree studies entitled "Deadlock Avoidance and Detection In Railway Simulation Systems".
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 talk, we revisit the deadlock avoidance and detection problem, and propose a new deadlock avoidance algorithm, called deadaalg, based on a resource reservation mechanism. The Deadaalg algorithm is proved to be f inite, 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.