# American Institute of Mathematical Sciences

March  2017, 12(1): 113-145. doi: 10.3934/nhm.2017005

## A mathematical framework for delay analysis in single source networks

 1 School of Civil and Environmental Engineering, Cornell University, Ithaca, NY 14853, USA 2 CERMICS, École des Ponts Paristech, Université Paris Est, 6 et 8 Avenue Blaise Pascal, 77420 Champs sur Marne, France 3 Facebook Inc., New York, NY 10003, USA 4 Department of Electrical Engineering & Computer Science and Department of Civil and Environmental Engineering, University of California Berkeley, Berkeley, CA 94702, USA

* Corresponding author

Received  June 2016 Revised  December 2016 Published  February 2017

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.

Citation: Samitha Samaranayake, Axel Parmentier, Ethan Xuan, Alexandre Bayen. A mathematical framework for delay analysis in single source networks. Networks and Heterogeneous Media, 2017, 12 (1) : 113-145. doi: 10.3934/nhm.2017005
##### References:

show all references

##### References:
Diverge model
Time mapping nodes
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.
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.
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}}$
 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}}$
 [1] Mary Luz Mouronte, Rosa María Benito. Structural analysis and traffic flow in the transport networks of Madrid. Networks and Heterogeneous Media, 2015, 10 (1) : 127-148. doi: 10.3934/nhm.2015.10.127 [2] Gabriella Bretti, Roberto Natalini, Benedetto Piccoli. Numerical approximations of a traffic flow model on networks. Networks and Heterogeneous Media, 2006, 1 (1) : 57-84. doi: 10.3934/nhm.2006.1.57 [3] Gabriella Bretti, Roberto Natalini, Benedetto Piccoli. Fast algorithms for the approximation of a traffic flow model on networks. Discrete and Continuous Dynamical Systems - B, 2006, 6 (3) : 427-448. doi: 10.3934/dcdsb.2006.6.427 [4] Paola Goatin. Traffic flow models with phase transitions on road networks. Networks and Heterogeneous Media, 2009, 4 (2) : 287-301. doi: 10.3934/nhm.2009.4.287 [5] Alberto Bressan, Ke Han. Existence of optima and equilibria for traffic flow on networks. Networks and Heterogeneous Media, 2013, 8 (3) : 627-648. doi: 10.3934/nhm.2013.8.627 [6] Tong Li. Qualitative analysis of some PDE models of traffic flow. Networks and Heterogeneous Media, 2013, 8 (3) : 773-781. doi: 10.3934/nhm.2013.8.773 [7] Emiliano Cristiani, Fabio S. Priuli. A destination-preserving model for simulating Wardrop equilibria in traffic flow on networks. Networks and Heterogeneous Media, 2015, 10 (4) : 857-876. doi: 10.3934/nhm.2015.10.857 [8] Gabriella Bretti, Maya Briani, Emiliano Cristiani. An easy-to-use algorithm for simulating traffic flow on networks: Numerical experiments. Discrete and Continuous Dynamical Systems - S, 2014, 7 (3) : 379-394. doi: 10.3934/dcdss.2014.7.379 [9] Maya Briani, Emiliano Cristiani. An easy-to-use algorithm for simulating traffic flow on networks: Theoretical study. Networks and Heterogeneous Media, 2014, 9 (3) : 519-552. doi: 10.3934/nhm.2014.9.519 [10] Lino J. Alvarez-Vázquez, Néstor García-Chan, Aurea Martínez, Miguel E. Vázquez-Méndez. Optimal control of urban air pollution related to traffic flow in road networks. Mathematical Control and Related Fields, 2018, 8 (1) : 177-193. doi: 10.3934/mcrf.2018008 [11] Alberto Bressan, Khai T. Nguyen. Optima and equilibria for traffic flow on networks with backward propagating queues. Networks and Heterogeneous Media, 2015, 10 (4) : 717-748. doi: 10.3934/nhm.2015.10.717 [12] Matteo Piu, Gabriella Puppo. Stability analysis of microscopic models for traffic flow with lane changing. Networks and Heterogeneous Media, 2022  doi: 10.3934/nhm.2022006 [13] Martin Gugat, Alexander Keimer, Günter Leugering, Zhiqiang Wang. Analysis of a system of nonlocal conservation laws for multi-commodity flow on networks. Networks and Heterogeneous Media, 2015, 10 (4) : 749-785. doi: 10.3934/nhm.2015.10.749 [14] Yacine Chitour, Benedetto Piccoli. Traffic circles and timing of traffic lights for cars flow. Discrete and Continuous Dynamical Systems - B, 2005, 5 (3) : 599-630. doi: 10.3934/dcdsb.2005.5.599 [15] Emiliano Cristiani, Smita Sahu. On the micro-to-macro limit for first-order traffic flow models on networks. Networks and Heterogeneous Media, 2016, 11 (3) : 395-413. doi: 10.3934/nhm.2016002 [16] Radu C. Cascaval, Ciro D'Apice, Maria Pia D'Arienzo, Rosanna Manzo. Flow optimization in vascular networks. Mathematical Biosciences & Engineering, 2017, 14 (3) : 607-624. doi: 10.3934/mbe.2017035 [17] Mapundi K. Banda, Michael Herty, Axel Klar. Gas flow in pipeline networks. Networks and Heterogeneous Media, 2006, 1 (1) : 41-56. doi: 10.3934/nhm.2006.1.41 [18] Alberto Bressan, Khai T. Nguyen. Conservation law models for traffic flow on a network of roads. Networks and Heterogeneous Media, 2015, 10 (2) : 255-293. doi: 10.3934/nhm.2015.10.255 [19] Johanna Ridder, Wen Shen. Traveling waves for nonlocal models of traffic flow. Discrete and Continuous Dynamical Systems, 2019, 39 (7) : 4001-4040. doi: 10.3934/dcds.2019161 [20] Rinaldo M. Colombo, Andrea Corli. Dynamic parameters identification in traffic flow modeling. Conference Publications, 2005, 2005 (Special) : 190-199. doi: 10.3934/proc.2005.2005.190

2021 Impact Factor: 1.41