Type
Text
Type
Dissertation
Advisor
Mitchell, Joseph S. B. | Esther M. Arkin | Jiaqiao Hu | Jie Gao.
Date
2010-08-01
Keywords
Applied Mathematics -- Computer Science -- Operations Research | Air Traffic Management, Packing Algorithm, Routing Algorithm, Scheduling Algorithm
Department
Department of Applied Mathematics and Statistics
Language
en_US
Source
This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree.
Identifier
http://hdl.handle.net/11401/71003
Publisher
The Graduate School, Stony Brook University: Stony Brook, NY.
Format
application/pdf
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.
Recommended Citation
Kim, Joon Dong, "Algorithms for Optimizing Multiple Routes Through Constrained Geometric Domain" (2010). Stony Brook Theses and Dissertations Collection, 2006-2020 (closed to submissions). 211.
https://commons.library.stonybrook.edu/stony-brook-theses-and-dissertations-collection/211