EAPSI: Optimal Design of Time-Variant Networks with Uncertainty

Richmond Nathaniel O, Coralville IA

Investigators

Abstract

This award supports research related to networks that change over time. Examples of such networks include road systems, railways, power grids, and telecommunication networks. Because networks form the backbone of many integral components of society, designing efficient network layouts is crucial. Historically, network design studies have predominantly emphasized the final design while ignoring uncertainties that are inherent in the future, such as construction delays or variable user demand. This research aims to devise network design strategies that take both time and future uncertainties into account. To that end, this work will be conducted with Dr. Dmytro Matsypura, one of the pioneering experts in time-varying network design, at the University of Sydney. The result will be a mathematical model and solution framework that produces efficient design strategies for expanding networks. This framework will intentionally be made as general as possible, to allow for direct application to various types of networks. This work bridges the areas of network design and stochastic optimization by incorporating uncertainty into the design model. The initial focus will be on the traditional Shortest Path Problem, solved to optimality on the user-defined network at every time within a predetermined period. In order to account for future uncertainties (i.e. arc build times, arc build costs, user demand), this project will use a stochastic multi-stage programming framework with the objective of minimizing total cost. This modeling strategy, though very powerful, is expected to be computationally expensive. To overcome this hurdle, this research will analyze solution properties and emphasize algorithm development and heuristic methods. Solutions to this newly proposed ?Stochastic Incremental Network Design Problem? will be compared to those from existing methods. This project will give insights into balancing modern computational ability with modeling and optimization frameworks for network design. This NSF EAPSI award is funded in collaboration with the Australian Academy of Science.