Implementation issues for the reliable a priori shortest path problem

Solution techniques are studied for the problem of finding a priori paths that are shortest to ensure a specified probability of on-time arrival in a stochastic network. A new discretization scheme called α-discrete is proposed. The scheme is well suited to large-scale applications because it does not depend on problem-specific parameters. A procedure for evaluating convolution integrals based on the new scheme is given, and its complexity is analyzed. Other implementation strategies also are discussed to improve the computational performance of the exact yet nondeterministic polynomial label-correcting algorithm. These include an approximate method based on extreme dominance and two cycle-avoidance strategies. Comprehensive numerical experiments are conducted to test the effects of the proposed implementation strategies using different networks and different distribution types.