A Stochastic Optimization Model for Highway Project Selection and Programming under Budget Uncertainty

Federal, state, and local transportation agencies are faced by issues of steady increase in travel demand, deterioration of physical asset conditions, public demand for government accountability, and pressure of constrained budget. Responding to these challenges, transportation agencies have started to advance asset management concepts that cover all physical assets and usage of a highway transportation system, identify needs of the entire system, and determine investments to maintain and improve highway performance most cost-effectively. The existing models for project selection in investment decision process treat the optimization problem as a deterministic problem. The random nature of budget faced by the decision-maker is not considered, which limits achieving robust results. This paper introduces a stochastic optimization model for project selection that considers budget uncertainty. The model was formulated as the stochastic multi-choice multidimensional Knapsack problem with Ω-stage budget recourses. Multi-choice corresponds to multiple budget levels for different asset management programs, while multi-dimension refers to multiple years of analysis. The objective was to select a subset of candidate projects to achieve maximized system benefits under budget and other constraints. An efficient solution algorithm was developed using Lagrangian relaxation techniques. Data on candidate projects for Indiana state highway programming in 1998–2001 were used to apply the proposed stochastic model and solution algorithm. To assess the impact of budget uncertainty on project selection, the stochastic model was also applied to the same data set without considering budget recourses, namely, the model was treated as a single-stage deterministic model by only executing the first stage optimization using expected budget. The two sets of results generated were compared and it was revealed that the stochastic model and solution algorithm could assist transportation agencies for enhanced highway investment decisions for optimal system performance.