The application of single-source shortest path algorithms to an OJSC contingency planning model and a vehicle routing model
Download
Author
Brown, Jerome W. Jr.
Date
1987-03Advisor
Rosenthal, R.E.
Second Reader
Brown, G.G.
Metadata
Show full item recordAbstract
This thesis investigates the use of" single-source shortest path algorithms in two
unrelated contexts. In the first application, the label setting and label correcting
algorithms are examined for applicability to and implementation within a J-S.
Organization of the Joint Chiefs of Staff contingency planning model. This model has
encountered problems of slow execution directly related to shortest path computations,
which can be resolved by the methods proposed. Additionally, these two shortest path
algorithms are examined for use within the model for identification and presentation of
alternate optima when they exist.
The second application involves the development of a new algorithm, called
reference node aggregation, which is designed to efficiently produce a subset of the allpairs
shortest path solution for large scale networks. The anticipated use of this
algorithm is in connection with vehicle routing models. The motivation for producing
a subset of the full solution is that only a very small subset of all possible pairs of
nodes will ever be considered for consecutive visitation by a vehicle; hence, most of the
information in an all-pairs solution is irrelevant. For those pairs whose exact shortest
paths are not computed, a single-step approximation is devised which does not require
access to peripheral storage. The new algorithm has three user-specified engineering
parameters which effectively control the tradeoff between the accuracy of the subset
solution and the effort required to compute it.
Collections
Related items
Showing items related by title, author, creator and subject.
-
Solving dynamic battlespace movement problems using dynamic distributed computer networks
Bradford, Robert D., III (Monterey, California. Naval Postgraduate School, 2000-06-01);This thesis develops an architecture for dynamic distributed military operations research. This architecture assumes that a network of heterogeneous computing devices connects forces throughout the battlespace. Both the ... -
APPLICATION OF TIME-REVERSAL MIRROR TO PASSIVE REMOTE SENSING OF THE OCEAN
Tan, Dexter Y. (Monterey, CA; Naval Postgraduate School, 2021-06);Characterizing the underwater environment can be approached directly by taking measurements, or by inversion where geoacoustic properties of the environment are derived from the way sound interacts with it. Single-element ... -
Adaptive Branch and Bound for Efficient Solution of Mixed-Integer Programs Formulated with Big-M
Gan, Eng Kiat Russell (Monterey, California. Naval Postgraduate School, 2012-09);This thesis describes three specialized branch-and-bound (B and B) algorithms for solving a mixed-integer program (MIP) that incorporates standard big-M constructs. The goal is to identify valid values for M that also lead ...