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 f 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.
dominance stochastic shortest paths labeling algorithms bicriterion shortest paths efficiency pareto optimality