Multiple Objectives and the Path Determination Problem.

Abstract : The shortests path problem exists as a major component of many network problems. For problems with a single objective, algorithms developed over the past twenty-five years have made the solution of this problem a relatively simple exercise. For multiobjective problems, adaptation of shortest path methodologies to generate noninferior solutions is a complex and difficult task. This thesis introduces an algorithm, based on label-correcting algorithmic techniques, which identifies all noninferior paths from one node in a network to all other nodes in the network in a single computer run. The algorithm, titled the Noninferior Path Labeling Algorithm (NPLA), is shown to be at least four to ten times faster than shortest path labeling algorithms applied multiobjectively for a problem with two objectives. NPLA is judged to be unique in its capability to identify all solutions which lie in duality gaps of the noninferior solution set. NPLA has been found to be easily programmed, efficient, and capable of being used with all network designs. It is readily adaptable to problems of more than two objectives. (Author)