Algorithms for optimizing multiple routes through constrained geometric domains

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.