AbstractIn this paper, we consider a particular class of network flow problems that seeks a shortest path, if it exists, between a source node s and a destination node d in a connected digraph, such that we arrive at node d at a specified time τ while leaving node s no earlier than a lower-bounding time LB, and where the availability of each network link is time-dependent in the sense that it can be traversed only during specified intervals of time. We refer to this problem as the reverse time-restricted shortest path problem (RTSP), and it arises, for example, in the context of generating flight plans within air traffic management approaches under severe convective weather conditions. We show that this problem is NP-hard in general, but is polynomially solvable under a special regularity condition. A pseudo-polynomial time dynamic programming algorithm is developed to solve Problem RTSP, along with an effective heap implementation strategy. Computational results using real flight generation test cases as well as random simulated problems are presented.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Reverse time-restricted shortest paths: Application to air traffic management


    Beteiligte:


    Erscheinungsdatum :

    2009-04-20


    Format / Umfang :

    11 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch






    Shortest paths in traffic-light networks

    Chen, Yen-Liang | Online Contents | 2000


    Constrained K-Shortest Paths Algorithms within a Dynamic Restricted Searching Area

    Yang, Z. / Gao, P. / Yu, D. et al. | British Library Conference Proceedings | 2009


    Fuzzy Dissimilar Shortest Paths in Urban Traffic Networks

    He, R. / Li, Y. / Beijing jiao tong da xue; Guo jia zi ran ke xue ji jin wei yuan hui (China); Wang Kuancheng jiao yu ji jin hui | British Library Conference Proceedings | 2006