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|&Middot;|T|2 log |T|) time complexity, where T is the set of trains and S is the set of sections in the railway topo logy. 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 exact optimization algorithm in tens of seconds for up to 30 trains/day over a planning period of 60 days.


    Access

    Download

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Deadlock Avoidance and Detection in Railway Simulation Systems


    Additional title:

    Transportation Research Record: Journal of the Transportation Research Board


    Contributors:


    Publication date :

    2014-01-01




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    JRC2014-3864 Deadlock Avoidance and Detection in Railway Simulation Systems

    Simon, B. / Jaumard, B. / Le, T.H. et al. | British Library Conference Proceedings | 2014


    Autonomous navigation with deadlock detection and avoidance

    Sanchez, Guido Marcelo / Giovanini, Leonardo Luis | BASE

    Free access

    Kronecker Algebra-based Deadlock Analysis for Railway Systems

    Robert Mittermayr / Johann Blieberger / Andreas Schöbel | DOAJ | 2012

    Free access

    TRAFFIC CONTROL SYSTEM HAVING DEADLOCK AVOIDANCE FUNCTIONALITY

    POVEY DEAN G / SIEMER MICHAEL | European Patent Office | 2017

    Free access

    Traffic control system having deadlock avoidance functionality

    POVEY DEAN G / SIEMER MICHAEL | European Patent Office | 2018

    Free access