Stochastic Network Design for Planning Scheduled Transportation Services: The Value of Deterministic Solutions

Abstract

We study the value of deterministic solutions, in particular their quality and upgradability, in addressing stochastic network design problems, by analyzing their time-dependent formulations known as scheduled service network design problems in freight transportation planning. We study several problem variants and models and investigate, for each case, the immediate quality of the deterministic solutions stemming from the 50th and the 75th percentile of the demand distributions. We then show that for all models, but in different ways, we are able to make effective use of parts of the deterministic solution, confirming the value of the deterministic solution in the stochastic environment, even when the deterministic solution itself performs badly. We also investigate what makes the optimal stochastic solution better in the stochastic environment than other feasible solutions, particularly those obtained by addressing deterministic versions of the problem. We do this by quantitatively analyzing the structures of different solutions. A measurement scheme is proposed to evaluate the level of potentially beneficial structural properties (multipath usage and path sharing) in different solutions. We show that these structural properties are important and correlated with the performance of a solution in the stochastic environment.