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.
Reverse time-restricted shortest paths: Application to air traffic management
Tramsportation Research, Part C: Emerging Technologies ; 17 , 6 ; 631-641
2009-04-20
11 pages
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch
Reverse time-restricted shortest paths: Application to air traffic management
Online Contents | 2009
|Reverse time-restricted shortest paths: Application to air traffic management
Online Contents | 2009
|Shortest paths in traffic-light networks
Online Contents | 2000
|Constrained K-Shortest Paths Algorithms within a Dynamic Restricted Searching Area
British Library Conference Proceedings | 2009
|Fuzzy Dissimilar Shortest Paths in Urban Traffic Networks
British Library Conference Proceedings | 2006
|