SELECTION AND SCHEDULING OF INTERRELATED NETWORK IMPROVEMENT PROJECTS UNDER UNCERTAINTIES

Abstract

The analysis of improvements in transportation networks is complicated by the interdependence of those improvements. Changes in links or nodes tend to shift traffic flows. Hence, the benefits of changes in any network component depend on what changes are made at what time in other components. There may also be synergies in the costs of implementing network changes. Methods are needed for selecting and scheduling interrelated network changes under uncertainties regarding demand, costs, implementation times and other factors. The proposed research focuses on optimizing the selection and schedule of interrelated network projects for enhancing a network’s performance under various uncertainties. Two multi-level models are formulated for analyzing problems on two types of transportation networks: rail freight networks in Problem 1 and road networks in Problem 2. For rail freight networks, the proposed tri-level model jointly optimizes short-term post-disruption restoration schedules and long-term network development schedules. Its lower level assigns capacitated freight flows to minimize total hourly cost, and its middle level optimizes the restoration sequence for the minimized cumulative cost increment (excess) during the restoration process under a given disruption scenario. At the upper level, given probabilistic disruption scenarios, network improvement projects are selected from a given set and sequenced to minimize the sum of construction cost and cumulative expected excess over the planning horizon. For road networks, the lower level of the proposed bi-level model performs user-equilibrium (UE) traffic assignment using the Frank-Wolfe (F-W) algorithm. The upper-level model first generates multiple scenarios with samples from the multivariate distribution of multiple correlated uncertain parameters. For a given long-term network improvement plan, an expected present value (PV) of cumulative system travel time cost over the planning horizon plus construction costs of implemented projects is obtained after computing this discounted sum separately under each generated scenario. To minimize this expected PV, the upper level optimizes the improvement plan with a specified selection and sequence of projects. In both problems, any sequence of restoration or improvement actions is mapped to a unique schedule under the rules based on binding constraints of resources, budget, and required work time. The planning horizon is segmented into short sub-periods based on the improvement schedule to approximate the effects of demand growth and cost discounting. A genetic algorithm (GA) with its operators is customized for optimizing restorations and improvement plans. For road networks, with the internal budget supply based on a fraction of the travel time cost, a set of methods is proposed for determining budget-ready times of projects. The model also allows the use of buses as a mode competing with cars in road networks, and the iteration of mode shares is integrated with the lower-level F-W traffic assignment. In Problem 1, the proposed model is demonstrated with short-term and long-term numerical cases in a small demand-loaded network. In the short-term problem, the optimized restoration sequences with different numbers of available work teams are obtained by the GA, whose solutions to relatively small problems are shown to be globally optimal through exhaustive enumeration. The restoration itineraries and schedules of work teams along with corresponding changes in hourly cost are shown in figures. For a small long-term problem, the selection, sequence, and schedule of projects are optimized by exhaustive enumeration. Sensitivity analyses show that the availability of more work teams greatly reduces cumulative expected excess and thus justifies implementing fewer improvement projects. With a longer planning horizon, lower construction costs, and a higher interest rate, more improvements are favored. Evaluations of cumulative expected excess with probabilistic growth rates of demand are provided. The model is also tested on a larger network where the long-term improvement plan is optimized by the GA. The quality of its solution is statistically verified. In Problem 2, 50 scenarios are generated by a quasi-Monte-Carlo sampling method. Demand growth rate, external budget supply, and the multiplier of required construction time are three correlated uncertainties whose effects are analyzed. The selection and sequencing of improvement projects are optimized by the GA. When introducing buses in the network, two operation modes are considered: using dedicated bus lanes and sharing roads with cars. The iteration of bus shares shows that the bus operation is more desirable with dedicated lanes, and that the potential demand from bus passengers greatly affects that desirability. In sensitivity analyses the factors favoring the implementation of projects include a higher demand level, a higher value of travel time, lower construction costs, and a higher demand growth rate. Across the scenarios, the demand growth rate and the external budget supply directly affect the PVC and last completion time (LCT), respectively. Modifying correlation coefficients of uncertain parameters has slight impact on the minimized PVC, but greatly affects the correlation between PVC and LCT for a given improvement sequence.