# 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Heterogeneous Media, 2015, 10 (4) : 717-748. doi: 10.3934/nhm.2015.10.717 [12] Martin Gugat, Alexander Keimer, Günter Leugering, Zhiqiang Wang. Analysis of a system of nonlocal conservation laws for multi-commodity flow on networks. Networks & Heterogeneous Media, 2015, 10 (4) : 749-785. doi: 10.3934/nhm.2015.10.749 [13] Yacine Chitour, Benedetto Piccoli. Traffic circles and timing of traffic lights for cars flow. Discrete & Continuous Dynamical Systems - B, 2005, 5 (3) : 599-630. doi: 10.3934/dcdsb.2005.5.599 [14] Mapundi K. Banda, Michael Herty, Axel Klar. Gas flow in pipeline networks. Networks & Heterogeneous Media, 2006, 1 (1) : 41-56. doi: 10.3934/nhm.2006.1.41 [15] 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 [16] Emiliano Cristiani, Smita Sahu. On the micro-to-macro limit for first-order traffic flow models on networks. Networks & Heterogeneous Media, 2016, 11 (3) : 395-413. doi: 10.3934/nhm.2016002 [17] Alberto Bressan, Khai T. Nguyen. Conservation law models for traffic flow on a network of roads. Networks & Heterogeneous Media, 2015, 10 (2) : 255-293. doi: 10.3934/nhm.2015.10.255 [18] 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 [19] Alberto Bressan, Fang Yu. Continuous Riemann solvers for traffic flow at a junction. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4149-4171. doi: 10.3934/dcds.2015.35.4149 [20] Wen Shen, Karim Shikh-Khalil. Traveling waves for a microscopic model of traffic flow. Discrete & Continuous Dynamical Systems - A, 2018, 38 (5) : 2571-2589. doi: 10.3934/dcds.2018108

2018 Impact Factor: 0.871