Robustness approach to the integrated network design problem, signal optimization and dynamic traffic assignment problem

This dissertation focuses on formulating robust optimization models and developing exact algorithms and various metaheuristics for the integrated network design (NDP), signal setting design (SSD) and dynamic traffic assignment (DTA) problem (NDP-SSD) when accounting for the bi-level nature and the long-term origin-destination demand uncertainty. The NDP determines the optimal budget allocation to improve link capacity, given the available budget. The SSD determines the optimal signal setting (cycle lengths, phase sequencing, green splits and time offsets). NDP-SSD provides a mutually consistent solution where the traffic flows are at dynamic user equilibrium, signal settings are optimal, and link capacity improvement decisions are most favorable. Three bi-level NDP, SSD and NDP-SSD models are proposed: deterministic, stochastic and robust. Also, three single-level SSD and NDP-SSD models are developed: useroptimal, stochastic system-optimal and stochastic user-optimal. The stochastic models minimize the expected cost, whereas the robust models minimize the tradeoff between the expected cost and risk. A solution of robust optimization remains close to optimal for all demand scenarios, while a solution of stochastic optimization may yield large changes in the objective value among different scenarios. v The proposed exact solution methods for bi-level NDP models are the Kth-best algorithm and the Karush-Kuhn-Tucker based mixed-integer programming reformulation. For the exact solution methods of bi-level SSD and NDP-SSD models, we show two mathematical proofs for reducing a mixed-zero-one continuous linear bi-level program and a mixed-zero-one continuous quadratic-linear bi-level program to a parametric linear bi-level program and a parametric quadratic-linear bi-level program, respectively. Although the analytical approach is limited to solving a small single-destination network, it is mathematically tractable and provides insight into the problems. For metaheuristic methods, many assumptions of analytical approach can be relaxed, and multi-destination problems can be solved with the use of existing simulation-based DTA software. Four metaheuristics are developed: random search, simulated annealing, genetic algorithm and reactive tabu search. Extensive numerical experiments are conducted to assess the performance of the metaheuristic algorithms, demonstrate the worthiness of the proposed robust formulations and show the benefit of the integrated approach over the sequential approach. The proposed models and metaheuristic algorithms are tested on limited transportation networks.