Algorithms for optimizing multiple routes through constrained geometric domains
by Kim, Joondong, Ph.D., STATE UNIVERSITY OF NEW YORK AT STONY BROOK, 2010, 95 pages; 3423697
 Abstract: We study optimization problems associated with routing multiple moving objects through a two- or three-dimensional geometric domain. We focus primarily on trajectories for moving disks, which can be used to model motion of objects (e.g., aircraft) that are required to remain separated by certain distances. Our primary motivation comes from air traffic management. We examine three main types of problems; for each type, we consider variations, given hardness results, and present algorithms for approximation or special cases. The first type of problem is that of finding multiple routes for moving objects through a given geometric domain. The moving objects must avoid obstacles (holes) within the domain. The objective is to maximize the number of possible routes through the domain, for moving objects that enter through a source (portion of the boundary) and exit through a sink (portion of the boundary). We study two variations of the problem: that in which trajectories of moving objects are required to be straight and that in which trajectories form a bounded degree tree, such as arises in arriving aircraft that must merge as they approach an airport. A second type of problem is to estimate the “capacity” of a domain, defined to be the maximum number of possible routes through the domain from source to sink. We are not required to compute the actual routes, but only to determine the maximum number possible. The exact solution can be found using a geometric version of the theory of maximum flows and minimum cuts in a network. We demonstrate that one can compute an approximate solution using the notion of geometric spanner graphs, such as the Delaunay diagram. Further, we perform a sensitivity analysis of capacity estimation, under probabilistic models of uncertainty in the description of the domain. This problem arises in applications to air traffic management in the face of uncertainty in weather forecasts. The third type of problem involves scheduling the dispatch of the moving objects, each of which is required to follow a pre-established route. In this situation, we consider the domain to be decomposed into a number of subregions (e.g., sectors, in the air traffic control scenario), and the goal is to determine dispatch times for each object such that we minimize the maximum number of objects ever simultaneously in a single sub-region. Typically, the dispatch times are constrained to be within some time interval. The problem is motivated by flight scheduling in order to optimize capacity in the air traffic control system. We examine the algorithmic complexity, propose algorithms, and conduct performance experiments for instances using actual and synthetic air traffic and weather data.

 Adviser Joseph S. B. Mitchell School STATE UNIVERSITY OF NEW YORK AT STONY BROOK Source DAI/B 71-11, p. , Nov 2010 Source Type Dissertation Subjects Applied mathematics; Operations research; Computer science Publication Number 3423697
Access the complete dissertation:

» Find an electronic copy at your library.
 Use the link below to access a full citation record of this graduate work: http://gateway.proquest.com/openurl%3furl_ver=Z39.88-2004%26res_dat=xri:pqdiss%26rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation%26rft_dat=xri:pqdiss:3423697 If your library subscribes to the ProQuest Dissertations & Theses (PQDT) database, you may be entitled to a free electronic version of this graduate work. If not, you will have the option to purchase one, and access a 24 page preview for free (if available).