Mitigating network congestion : analytical models, optimization methods and their applications

Congestion is a phenomenon that arises in a variety of contexts. The most familiar representation is urban traffic congestion. Nonetheless, phenomenons such as prison cell congestion, hospital bed blocking or, at a cellular scale, ribosome congestion, also arise and affect the performance of the underlying networks. The study of network congestion is therefore of interest in numerous application fields. Analytical mathematical models enable the identification and the quantification of network congestion. Furthermore, these methods can be used to identify strategies that mitigate network congestion, by integrating them within optimization frameworks. Deriving such models is an intricate task. Congested networks involve complex traffic interactions. Providing an analytical description of these intricate interactions is challenging. Furthermore, to identify traffic management strategies that indeed mitigate congestion, these models need to be realistic representations of the underlying process, while remaining computationally tractable such that efficient and operational optimization methods can be derived. This thesis presents an analytical network model based on finite capacity queueing theory. Through a novel state space formulation and the use of structural parameters, the model provides a detailed decomposition of congestion. It describes congestion in terms of its sources, its propagation and dissipation rates as well as its frequency. The model is validated versus existing methods, exact results and simulation results. Particularly tractable formulations are derived for single server bufferless queues in a tandem topology and for single server queues with finite buffers in an arbitrary topology network. Unlike existing models, the proposed model maintains the network topology and the queue capacities exogenous. An urban vehicle traffic model is formulated based on this network model. A detailed formulation, based on national transportation standards, is provided. This model is then used to perform optimization for congested road networks. A traffic signal control problem is formulated and solved for the Lausanne city road network. The signal plans derived are evaluated at the microscopic scale with a calibrated simulation model, and compared to both an existing signal plan for the city of Lausanne and to signal plans derived by other methods. The proposed plans delay the propagation of congestion, and lead to improved performance measures. The contributions in the urban transportation field are two-fold. Firstly, the proposed model considers a set of intersections and analytically captures the interactions between queues, contrarily to existing analytic queueing models for urban networks which are formulated for a single intersection, and thus do not take such interactions into account. Secondly, although there is a great variety of signal control methodologies in the literature, there is still a need for solutions that are appropriate and ef