Abstract
This note introduces a piecewise-deterministic queueing (PDQ) model to study the stability of traffic queues in parallel-link transportation systems facing stochastic capacity fluctuations. The saturation rate (capacity) of the PDQ model switches between a finite set of modes according to a Markov chain, and link inflows are controlled by a state-feedback policy. A PDQ system is stable only if a lower bound on the time-average link inflows does not exceed the corresponding time-average saturation rate. Furthermore, a PDQ system is stable if the following two conditions hold: the nominal mode's saturation rate is high enough that all queues vanish in this mode, and a bilinear matrix inequality (BMI) involving an underestimate of the discharge rates of the PDQ in individual modes is feasible. The stability conditions can be strengthened for two-mode PDQs. These results can be used for design of routing policies that guarantee stability of traffic queues under stochastic capacity fluctuations.
Introduction
In real-world transportation and communication networks, the capacity of a link is rarely static. External factors such as weather events, accidents, or maintenance cause capacities to fluctuate randomly. Traditional traffic control models often assume static or deterministic time-varying capacities, which fail to account for the "bursty" nature of these disruptions. This paper addresses the challenge of designing routing policies—deciding how to distribute demand across multiple paths—to ensure system stability. In this context, stability implies that queues remain bounded and the system eventually reaches a predictable statistical steady state.
Modeling Framework: The PDQ Model
The authors propose a Piecewise-Deterministic Queueing (PDQ) model, framed as a Piecewise-Deterministic Markov Process (PDMP). The system consists of parallel links where a constant total demand $A$ must be distributed across $n$ queues.
- Deterministic Evolution: Between capacity changes, queue lengths $Q_i(t)$ evolve according to fluid-dynamic differential equations.
- Stochastic Switching: The capacity of the links (the "mode") switches between a finite set of states according to a continuous-time Markov chain.
- State-Feedback Control: Routing decisions $F_i(t)$ are determined by a policy $\phi_i$ that considers both the current capacity mode $I(t)$ and the current queue lengths $Q(t)$.
Stability Analysis and Conditions
To guarantee stability, the authors employ Foster-Lyapunov criteria, seeking a Lyapunov function that demonstrates a negative "drift" toward zero queue lengths.
Key Theoretical Insights
- The Nominal Mode Requirement: A necessary condition for stability is the existence of a "nominal" mode (e.g., clear weather, no accidents) where link capacities are sufficient to clear all queues. If the system is overwhelmed even in its best state, it cannot be stabilized.
- Average Capacity Floor: While the time-average inflow must be less than the time-average capacity, this is merely a necessary condition. Stability actually depends on the feedback policy's ability to react to queue growth.
- Bilinear Matrix Inequality (BMI): For general multi-mode systems, the sufficiency condition for exponential stability is formulated as a BMI feasibility test. This provides a computational bridge for verifying specific routing rules using standard optimization toolboxes.
- Two-Mode Simplification: For systems alternating between only two states (e.g., "Normal" and "Incident"), the complex BMI reduces to a simpler, intuitive inequality relating average demand to average capacity.
Policy Evaluation and Results
The framework was used to evaluate three common routing behaviors:
- Mode-responsive: Simple redirection based solely on the current capacity mode.
- Piecewise-affine: A queue-responsive policy where flow adjustments are linear relative to congestion.
- Logit: A model of human choice where travelers prefer shorter queues but exhibit bounded rationality.
Numerical simulations of three-mode systems revealed a "gap" or "unknown" region between proven stable and unstable zones. This indicates that while the BMI-based conditions are powerful, there is potential for further mathematical refinement to sharpen these bounds.
Limitations and Future Work
While the PDQ model provides a rigorous foundation for stability analysis under stochastic fluctuations, several avenues for future research remain:
- Network Topology: The current study is restricted to parallel-link systems. Extending these results to complex mesh networks is a primary goal.
- Computational Complexity: Solving BMIs is NP-hard, which may limit scalability for massive, city-scale networks.
- Information Delays: The model assumes instantaneous knowledge of queue lengths and capacity modes. Future work should account for sensing and communication latencies that could destabilize the system.
- Stochastic Demand: Expanding the model to include stochastic arrival rates ($A$) would further enhance its realism.
Summary updated