Extended dominance and a stochastic shortest path problem

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)m(P) and variance v(P)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))z(P)=f(m(P))+g(v(P)), where ff 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.