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

In this paper, we consider a particular class of network flow problems that seeks a shortest path, if it exists, between a source node and a destination node in a connected digraph, such that we arrive at node at a specified time while leaving the source node no earlier than a lower-bounding time, 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.

Language

  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01141726
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Oct 2 2009 2:43PM