Routing multi-class traffic flows in the plane
Venue
Computational Geometry, vol. 45 (2012), pp. 99-114
Publication Year
2012
Authors
Joondong Kim, Joseph S. B. Mitchell, Valentin Polishchuk, Shang Yang, Jingyu Zou
BibTeX
Abstract
We study a class of multi-commodity flow problems in geometric domains: For a given
planar domain P populated with obstacles (holes) of K⩾2types, compute a set of
thick paths from a “source” edge of P to a “sink” edge of P for vehicles of K
distinct classes. Each class k of vehicle has a given set, Ok, of obstacles it must
avoid and a certain width, wk, of path it requires. The problem is to determine if
it is possible to route Nk width-wk paths for class k vehicles from source to sink,
with each path avoiding the requisite set Ok of obstacles, and no two paths
overlapping. This form of multi-commodity flow in two-dimensional domains arises in
computing throughput capacity for multiple classes of aircraft in an airspace
impacted by different types of constraints, such as those arising from weather
hazards. We give both algorithmic theory results and experimental results. We show
hardness of many versions of the problem by proving that two simple variants are
NP-hard even in the case K=2. If w1=w2=1, then the problem is NP-hard even when
O1=∅. If w1=2, w2=3, then the problem is NP-hard even when O1=O2. In contrast, the
problem for a single width and a single type of obstacles is polynomially solvable.
We present approximation algorithms for the multi-criteria optimization problems
that arise when trying to maximize the number of routable paths. We also give a
polynomial-time algorithm for the case in which the number of holes in the input
domain is bounded. Finally, we give experimental results based on an implementation
of our methods and experiment with enhanced heuristics for efficient solutions in
practice. Our algorithms are being utilized in simulations with NASAʼs Future Air
traffic management Concepts Evaluation Tool (FACET). We report on experimental
results based on applying our algorithms to weather-impacted airspaces, comparing
heuristic strategies for searching for feasible path orderings and for computing
short multi-class routes. Our results show that multi-class routes can feasibly be
computed on real weather data instances on the scale required in air traffic
management applications.
