Probabilistic models and optimization algorithms for large-scale transportation problems

Abstract

This thesis tackles two major challenges of urban transportation optimization problems: (i) high-dimensionality and (ii) uncertainty in both demand and supply. These challenges are addressed from both modeling and algorithm design perspectives. The first part of this thesis focuses on the formulation of analytical transient stochastic link transmission models (LTM) that are computationally tractable and suitable for largescale network analysis and optimization. We first formulate a stochastic LTM based on the model of Osorio and Flötteröd (2015). We propose a formulation with enhanced scalability. In particular, the dimension of the state space is linear, rather than cubic, in the link's space capacity. We then propose a second formulation that has a state space of dimension two; it scales independently of the link's space capacity. Both link models are validated versus benchmark models, both analytical and simulation-based. The proposed models are used to address a probabilistic formulation of a city-wide signal control problem and are benchmarked versus other existing network models. Compared to the benchmarks, both models derive signal plans that perform systematically better considering various performance metrics. The second model, compared to the first model, reduces the computational runtime by at least two orders of magnitude. The second part of this thesis proposes a technique to enhance the computational efficiency of simulation-based optimization (SO) algorithms for high-dimensional discrete SO problems. The technique is based on an adaptive partitioning strategy. It is embedded within the Empirical Stochastic Branch-and-Bound (ESB&B) algorithm of Xu and Nelson (2013). This combination leads to a discrete SO algorithm that is both globally convergent and has good small sample performance. The proposed algorithm is validated and used to address a high-dimensional car-sharing optimization problem.