Abstract
Congestion is a pervasive phenomenon across diverse domains, from urban traffic and hospital bed management to cellular-level protein synthesis. This paper presents an analytical framework based on finite capacity queueing theory designed to identify and quantify network congestion. By introducing a novel state space formulation, the model provides a detailed decomposition of congestion into its sources, propagation, and dissipation rates. Validated against simulation and exact results, the framework is applied to optimize traffic signal plans in Lausanne, Switzerland, manage patient flow in Geneva, and model ribosome traffic. The results demonstrate significant improvements in performance measures and computational efficiency compared to traditional methods.
1. Introduction
Congestion arises whenever demand for a resource exceeds its capacity. While most visible in urban traffic, it equally affects prison systems, hospital wards, and biological processes. Effective management requires mathematical models that are both realistic—capturing intricate traffic interactions—and computationally tractable for use in optimization frameworks. This work addresses the gap between high-fidelity but expensive microscopic simulations and efficient but overly simplified macroscopic models.
2. Modeling Finite Capacity Networks
The core innovation of this research is a network model based on finite capacity queueing theory (FCQN). Unlike standard queueing models that assume infinite buffer space, this approach explicitly accounts for "blocking-after-service." In this state, a job (e.g., a vehicle or patient) that has completed service cannot move to the next node because that node is full, thereby occupying the current server and preventing it from processing subsequent jobs.
The model utilizes a novel state space formulation and structural parameters to describe congestion. Key features include:
- Exogenous Topology and Capacity: Unlike previous approximations, the network structure and queue capacities are fixed inputs, ensuring stability during optimization.
- Detailed Decomposition: Congestion is analyzed through its frequency, duration, and propagation/dissipation rates.
- Scalability: For large-scale applications, the model can be reduced from $6n$ to $3n$ equations without significant loss of accuracy, making it suitable for entire city networks.
3. Optimization via Hybrid Metamodeling
To bridge the gap between analytical models and realistic simulations, a simulation-based optimization framework was developed. It employs a hybrid metamodel that combines a physical metamodel (structural information derived from the analytical queueing model) with a functional metamodel (general-purpose quadratic polynomials used in traditional derivative-free trust region algorithms).
This combination allows the optimizer to find high-performing solutions with a very limited computational budget. By "seeding" the optimizer with the structural logic of queueing theory, the system can identify good traffic signal plans almost immediately, overcoming the need for a substantial initial sample of simulation runs.
4. Domain Applications
4.1 Urban Traffic Control
The model was applied to the road network of Lausanne, Switzerland, using a calibrated microscopic simulation covering 652 roads and 231 intersections. By treating road segments as finite buffers, the model analytically captures "spillbacks"—where a queue at one intersection blocks the upstream intersection. Optimization of traffic signal plans using this framework delayed congestion propagation and improved travel times compared to existing city plans and standard engineering methods like Webster’s.
4.2 Healthcare Systems
In collaboration with the Geneva University Hospitals (HUG), the model investigated "bed blocking" in operative and post-operative units using data from over 25,000 patient records. The study identified three primary sources of blocking and quantified how even low-probability blocking events (e.g., 3%) can lead to significant resource tie-ups, such as 11% of beds in recovery rooms being occupied by blocked patients. This responds to a critical need for methods that quantify in-patient bed blocking.
4.3 Protein Synthesis
At the cellular scale, the traffic of ribosomes along mRNA strands was modeled as a system of linear and quadratic equations. This formulation proved numerically stable even in highly congested scenarios where previous models often became ill-conditioned. It provides a scalable tool for studying large-scale protein synthesis networks using simple numerical techniques.
5. Conclusion and Future Directions
The research demonstrates that integrating structural queueing logic into optimization frameworks significantly enhances the management of congested networks. Future work aims to extend the model to capture transient (time-varying) behavior during peak periods and to explore higher-order decompositions that capture local correlations between adjacent queues more accurately.
Reference: Osorio Pizano, C. (2010). Mitigating Network Congestion: Analytical Models, Optimization Methods and their Applications. PhD Thesis, École Polytechnique Fédérale de Lausanne.
Summary updated