The application of single-source shortest path algorithms to an OJSC contingency planning model and a vehicle routing model
Brown, Jerome W. Jr.
MetadataShow full item record
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.
Showing items related by title, author, creator and subject.
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 ...
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 ...
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 ...