Article Contents
Article Contents

# A mathematical framework for delay analysis in single source networks

• * Corresponding author
• This article presents a mathematical framework for modeling heterogeneous flow networks with a single source and multiple sinks with no merging. The traffic is differentiated by the destination (i.e. Lagrangian flow) and different flow groups are assumed to satisfy the first-in-first-out (FIFO) condition at each junction. The queuing in the network is assumed to be contained at each junction node and spill-back to the previous junction is ignored. We show that this model leads to a well-posed problem for computing the dynamics of the system and prove that the solution is unique through a mathematical derivation of the model properties. The framework is then used to analytically prescribe the delays at each junction of the network and across any sub-path, which is the main contribution of the article. This is a critical requirement when solving control and optimization problems over the network, such as system optimal network routing and solving for equilibrium behavior. In fact, the framework provides analytical expressions for the delay at any node or sub-path as a function of the inflow at any upstream node. Furthermore, the model can be solved numerically using a very simple and efficient feed forward algorithm. We demonstrate the versatility of the framework by applying it to two example networks, a single path of multiple bottlenecks and a diverge junction with complex junction dynamics.

Mathematics Subject Classification: Primary: 34B45.

 Citation:

• Figure 1.  Diverge model

Figure 2.  Time mapping nodes

Figure 3.  Multiple bottlenecks on a road.

Figure 4.  Off-Ramp model with its four states -(a) state $\phi$ ; (b) state $Q_e$ (c) state $(Q_e; Q_h)$ (d) state $Q_h$ . See figure 5 for a illustration of the state transitions.

Figure 5.  State transitions in the off-ramp model. The four states $\phi, Q_e, (Q_e, Q_h)$ and $Q_h$ correspond respectively to the cases (a), (b), (c) and (d) from figure 4.

Figure 6.  Simulation of states and delays $(\delta_E; \delta_H)$ as functions of time $t$ , given the incoming flows at the off ramp, and road parameters: $\mu_E = 5; \mu_H = 30\ and \\mu = 45$

 Algorithm 1 Calculate approximate solution of problem (2) $\mathit{\boldsymbol{solveDelays}}(sourceFlow: \lambda^0; initialDelays: \delta^0[0]; capacities: \mu)$ $\ \mathit{\boldsymbol{for}}\ l \in L^{out}_0\ \mathit{\boldsymbol{do}}$ $\ \ \ \mathit{\boldsymbol{for}}\ t = 1\ to\ T\ \mathit{\boldsymbol{do}}$ $\ \ \ \ \ \mathit{\boldsymbol{update}}(v_l^{out}; t; 1; 0)$ $\ \ \ \mathit{\boldsymbol{end\ for}}$ $\ \mathit{\boldsymbol{end\ for}}$ $\ \mathit{\boldsymbol{update}}(node: v, timeStep: t, lastActiveConstraint: \hat{\omega})$ $\ \mathit{\boldsymbol{if}}\ v \notin S\ then$ $\ \ \ \Delta^0_{0,v}[t] = \Delta^0_{0,\pi_v}[t] + \delta_v^0[t − 1]$ $\ \ \ \mathit{\boldsymbol{for}}\ l \in L_v\ \mathit{\boldsymbol{do}}$ $\ \ \ \ \ \mu_0^l [t] = \mu_l(t + \Delta_0^{0,v}[t])$ $\ \ \ \ \ c^0_l [t] =\frac{\sum_{p \in P_l}\lambda^0_p[t]}{\mu^0_l[t]}$ $\ \ \ \mathit{\boldsymbol{end\ for}}$ $\ \ \ \gamma_v[t] = \arg \max_l \in L^{out}_v c_{v,l}(t)$ $\ \ \ \Gamma_v[t]=P_{\gamma_v(t)}$ $\ \ \ \omega_v[t]=\frac{\sum_{p \in \Gamma_v[t]}\lambda^0_p[t]}{\mu^0_l[t]}$ $\ \ \ \delta^0_v[t]=max(0,(\omega_v-\hat{\omega}\cdot \Delta t)$ $\ \ \ \mathit{\boldsymbol{for}}\ l \in L^{out}_v\ \mathit{\boldsymbol{do}}$ $\ \ \ \ \ \mathit{\boldsymbol{if}}\ \delta^0_v[t]>0\ \mathit{\boldsymbol{then}}$ $\ \ \ \ \ \ \ update(v_l^{out}; t; \omega_v)$ $\ \ \ \ \ \mathit{\boldsymbol{else}}$ $\ \ \ \ \ \ \ update(v_l^{out}; t; \hat{\omega})$ $\ \ \ \ \ \mathit{\boldsymbol{end\ if}}$ $\ \ \ \mathit{\boldsymbol{end\ for}}$ $\ \mathit{\boldsymbol{end\ if}}$

Figures(6)

Tables(1)