Application of Single-Source Shortest Path Algorithms to an OJCS (Organization of the Joint Chiefs of Staff) Contingency Planning Model and a Vehicle Routing Model

摘要

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 with a J-8, 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 new algorithm, called reference node aggregation, which is designed to efficiently produce a subset of the all-pairs 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. (Theses)