DSpace Repository

Geometric Algorithms for Capacity Estimation and Routing in Air Traffic Management

Show simple item record

dc.contributor.advisor Joseph S. B -- Mitchell. en_US
dc.contributor.author Zou, Jingyu en_US
dc.contributor.other Department of Applied Mathematics and Statistics en_US
dc.date.accessioned 2012-05-15T18:08:09Z
dc.date.accessioned 2015-04-24T14:53:26Z
dc.date.available 2012-05-15T18:08:09Z
dc.date.available 2015-04-24T14:53:26Z
dc.date.issued 2010-08-01 en_US
dc.identifier Zou_grad.sunysb_0771E_10255.pdf en_US
dc.identifier.uri http://hdl.handle.net/1951/55705 en_US
dc.identifier.uri http://hdl.handle.net/11401/72738 en_US
dc.description.abstract We study various problems that arise from two inter-related fundamental computational problems in Air Traffic Management (ATM): that of estimating the capacity of an airspace that is cluttered with hazardous weather constraints, and that of routing aircraft on trajectories in space-time to avoid hazardous weather constraints and to achieve maximum efficiency while maintaining safe separation distances between all pairs of aircraft at all times.We model the problem of capacity estimation as a geometric problem of finding the maximum number of pairwise disjoint"thick" paths in a polygonal domain with holes. For the case where all thick paths are of the same width, we give a 1/2-approximation algorithm using geometric spanners. We also show experimentally that using a spanner (e.g., Delaunay graph) yields approximation ratios very close to one. For the case where thick paths are of two or more different widths, we show that the problem becomes strongly NP-hard; we also give polynomial-time algorithm for the special case where the order of the widths of the paths as they appear on the polygonal boundary is given.We also study the capacity estimation problem for any airspace under different dominant demand (flow) directions and see how the directional capacity changes as a function of the demand direction. We lay out grids on the whole National Airspace System (NAS), put square or circular kernels of appropriate sizes on each grid point, and apply the directional capacity analysis for each kernel; this way we get an idea on the directional capacity for the whole NAS. Further, we describe how the grid-based analysis can be used in ATM applications.We investigate methods of computing flexible trees of arrival and departure routes for the transition airspace. We model the problem of routing flows of arrival aircraft on a merge tree with constraints imposed by hazardous weather, special use airspace, and operational constraints on merge points. We have proved that this problem is in general NP-hard; an polynomial-time algorithm is presented to compute an optimal merge tree if the number of"layers" in the search graph is constant. The algorithm applies both to the case of fixed (constant) Required Navigation Performance (RNP) and the case of a mixture of different RNP values. We show experimental results demonstrating the application of the algorithm to problem instances that are based on actual weather data. en_US
dc.description.sponsorship This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree. en_US
dc.format Monograph en_US
dc.format.medium Electronic Resource en_US
dc.language.iso en_US en_US
dc.publisher The Graduate School, Stony Brook University: Stony Brook, NY. en_US
dc.subject.lcsh Applied Mathematics -- Operations Research -- Computer Science en_US
dc.subject.other Air Traffic Management, Capacity Estimation, Geometric Algorithm, NP-hardness, Routing, Thick Paths en_US
dc.title Geometric Algorithms for Capacity Estimation and Routing in Air Traffic Management en_US
dc.type Dissertation en_US
dc.mimetype Application/PDF en_US
dc.contributor.committeemember Esther M. Arkin en_US
dc.contributor.committeemember Xiangmin Jiao en_US
dc.contributor.committeemember Jie Gao. en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search DSpace

Advanced Search


My Account