Kevin R. Hutson

Douglas R. Shier

Abstract: In the context of stochastic networks, we study the problem of finding a path P that combines in a reasonable way the mean m(P) and variance v(P) of its length. Specifically we study a separable objective function that combines these two path measures: namely, z(P) = f (m(P)) + g(v(P)), where f is an increasing convex function and g is an increasing concave function. A new type of dominance (e-dominance), stronger than the standard form of dominance, is then introduced, and it is shown to satisfy a certain form of Bellman’s optimality principle. This means that it is possible to modify existing label-setting and label-correcting methods by using e-dominance, and without sacrificing optimality. Computational experience with these enhanced labeling algorithms has been promising. Test results for a variety of sample problems show that the e-dominance criterion can often significantly reduce the number of nondominated path vectors, compared to the standard dominance criterion. We observe a consequent reduction in both computation time and storage requirements.

Key Words: bicriterion shortest paths, dominance, efficiency, labeling algorithms, Pareto optimality, stochastic shortest paths