Arc Reduction and Path Preference in Stochastic Acyclic Networks
针对随机无环网络中最短路径问题，提出一种基于随机占优的弧缩减启发式算法，用蒙特卡洛模拟评估，在70个随机测试中显示计算效率随网络规模提升，且解质量优于原问题。
The paper presents a heuristic for determining the path that maximizes the expected utility of a stochastic acyclic network. The focus is on shortest route problems where a general, nonlinear utility function is used to measure outcomes. For such problems, enumerating all feasible paths is the only way to guarantee that the global optimum has been found. Alternatively, we develop a reduction algorithm based on stochastic dominance to speed up the computations. Monte Carlo simulation is used to evaluate the approach. In all, 70 test problems comprising 20 to 60 nodes are randomly generated and analyzed. The results indicate that the heuristic produces significant computational saving as the size of the network grows, and that the quality of the reduced network solutions are better than those obtained from the original formulation.