A heuristic approach for selecting highway investment alternatives

A heuristic approach is developed for systemwide highway project selection. It can assess changes in total project benefits using different project implementation options under budget uncertainty and identify the best option to achieve maximized total benefits. The proposed approach consists of a stochastic model formulated as the zero/one integer doubly constrained multidimensional knapsack problem and an efficient heuristic solution algorithm developed using the Lagrange relaxation technique. A method is also introduced to improve the upper bound for the objective function by simultaneously changing multiple Lagrange multipliers. The approach is applied in a computational study to obtain a comprehensive highway investment plan for a State-maintained highway system in the United States.