A mathematical framework for delay analysis in single source networks

Samitha Samaranayake; Axel Parmentier; Ethan Xuan; Alexandre Bayen

doi:10.3934/nhm.2017005

Article Contents

2017, Volume 12, Issue 1: 113-145. Doi: 10.3934/nhm.2017005

This issue Previous Article A discrete Hughes model for pedestrian flow on graphs Next Article An improved homogenization result for immiscible compressible two-phase flow in porous media

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
* Corresponding author

Received: May 31, 2016

Revised: November 30, 2016

Published: May 2017

Abstract Full Text(HTML) Figure(6) / Table(1) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 34B45.

Citation:

FullText(HTML)

Figure 1. Diverge model

Download: Full-size image PowerPoint slide

Figure 2. Time mapping nodes

Download: Full-size image PowerPoint slide

Figure 3. Multiple bottlenecks on a road.

Download: Full-size image PowerPoint slide

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.

Download: Full-size image PowerPoint slide

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.

Download: Full-size image PowerPoint slide

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$

Download: Full-size image PowerPoint slide

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}}$

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	A. Adas, Traffic models in broadband networks, Communications Magazine, IEEE, 35 (1997), 82-89. doi: 10.1109/35.601746.
[2]	V. Astarita, A continuous time link model for dynamic network loading based on travel time function, 13th International Symposium on Transportation and Traffic Theory, (1996), 79-102, Lyon, France.
[3]	X.J. Ban, J.-S. Pang, H.X. Liu and R. Ma, Continuous-time point-queue models in dynamic network loading, Transportation Research Part B: Methodological, 46 (2012), 360-380. doi: 10.1016/j.trb.2011.11.004.
[4]	X.J. Ban, J.-S. Pang, H.X. Liu and R. Ma, Modeling and solving continuous-time instantaneous dynamic user equilibria: A differential complementarity systems approach, Transportation Research Part B: Methodological, 46 (2012), 389-408. doi: 10.1016/j.trb.2011.11.002.
[5]	A. Bressan and K. Han, Existence of optima and equlibria for traffic flow on networks, Networks} & Heterogeneous Media, 8 (2013), 627-648. doi: 10.3934/nhm.2013.8.627.
[6]	C.-S. Chang, Performance Guarantees in Communication Networks, Springer, 2000 doi: 10.1007/978-1-4471-0459-9.
[7]	C.F. Daganzo, The cell transmission model, Part Ⅱ network traffic, Transportation Research Part B: Methodological, 29 (1995), 79-93. doi: 10.1016/0191-2615(94)00022-R.
[8]	C.F. Daganzo, A continuum theory of traffic dynamics for freeways with special lanes, Transportation Research Part B: Methodological, 31 (1997), 83-102. doi: 10.1016/S0191-2615(96)00017-3.
[9]	C.F. Daganzo, W.-H. Lin and J.M. Del Castillo, A simple physical principle for the simulation of freeways with special lanes and priority vehicles, Transportation Research Part B: Methodological, 31 (1997), 103-125. doi: 10.1016/S0191-2615(96)00032-X.
[10]	H. M. Edwards, Advanced Calculus: A Differential Forms Approach, Springer Science & Business Media, New York, 2014. doi: 10.1007/978-0-8176-8412-9.
[11]	T.L. Friesz, K. Han, P.A. Neto, A. Meimand and T. Yao, Dynamic user equilibrium based on a hydrodynamic model, Transportation Research Part B: Methodological, 47 (2013), 102-126. doi: 10.1016/j.trb.2012.10.001.
[12]	V.S. Frost and B. Melamed, Traffic modeling for telecommunications networks, Communications Magazine, IEEE, 32 (1994), 70-81. doi: 10.1109/35.267444.
[13]	K. Han, B. Piccoli, T. L. Friesz and T. Yao, A continuous-time link-based kinematic wave model for dynamic traffic networks, arXiv preprint, arXiv: 1208.5141, 2012.
[14]	K. Han, T.L. Friesz and T. Yao, Existence of simultaneous route and departure choice dynamic user equilibrium, Transportation Research Part B: Methodological, 53 (2013a), 17-30. doi: 10.1016/j.trb.2013.01.009.
[15]	K. Han, T.L. Friesz and T. Yao, A partial differential equation formulation of {V}ickrey's bottleneck model, part i: Methodology and theoretical analysis, Transportation Research Part B: Methodological, 49 (2013b), 55-74. doi: 10.1016/j.trb.2012.10.003.
[16]	K. Han, T.L. Friesz and T. Yao, A partial differential equation formulation of Vickrey's bottleneck model, part ii: Numerical analysis and computation, Transportation Research Part B: Methodological, 49 (2013c), 75-93. doi: 10.1016/j.trb.2012.10.004.
[17]	M. Herty, A. Klar and B. Piccoli, Existence of solutions for supply chain models based on partial differential equations, SIAM Journal on Mathematical Analysis, 39 (2007), 160-173. doi: 10.1137/060659478.
[18]	P. Hidas, Modelling vehicle interactions in microscopic simulation of merging and weaving, Transportation Research Part C: Emerging Technologies, 13 (2005), 37-62. doi: 10.1016/j.trc.2004.12.003.
[19]	H. Holden and N.H. Risebro, A mathematical model of traffic flow on a network of unidirectional roads, SIAM J. Math. Anal., 26 (1995), 999-1017. doi: 10.1137/S0036141093243289.
[20]	Y. Hollander and R. Liu, The principles of calibrating traffic microsimulation models, Transportation, 35 (2008), 347-362.
[21]	D.-W. Huang, Effects of ramps in the nagel-schreckenberg traffic model, International Journal of Modern Physics C, 13 (2002), 739-749. doi: 10.1142/S0129183102003541.
[22]	S. Jain, K. Fall and R. Patra, Routing in a delay tolerant network, , (). doi: 10.1145/1015467.1015484.
[23]	B. Jia, R. Jiang and Q. -S. Wu, Traffic behavior near an off ramp in the cellular automaton traffic model, Phys. Rev. E, 69 (2004), 056105. doi: 10.1103/PhysRevE.69.056105.
[24]	J. Lafontaine, An Introduction to Differential Manifolds, 2015. doi: 10.1007/978-3-319-20735-3.
[25]	J. Lebacque, The godunov scheme and what it means for first order traffic flow models, Proceedings of the 13th International Symposium on Transportation and Traffic Theory, (1996a), 647-678.
[26]	M.J. Lighthill and G.B. Whitham, On kinematic waves Ⅰ. flood movement in long rivers, Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 229 (1955), 281-316. doi: 10.1098/rspa.1955.0088.
[27]	M.J. Lighthill and G.B. Whitham, On kinematic waves Ⅱ. a theory of traffic flow on long crowded roads, Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 229 (1955), 317-345. doi: 10.1098/rspa.1955.0089.
[28]	H.K. Lo, E. Chang and Y.C. Chan, Dynamic network traffic control, Transportation Research Part A: Policy and Practice, 35 (2001), 721-744. doi: 10.1016/S0965-8564(00)00014-8.
[29]	R. Ma, X.J. Ban and J.-S. Pang, Continuous-time dynamic system optimum for single-destination traffic networks with queue spillbacks, Transportation Research Part B: Methodological, 68 (2014), 98-122. doi: 10.1016/j.trb.2014.06.003.
[30]	D.K. Merchant and G.L. Nemhauserm, A model and an algorithm for the dynamic traffic assignment problems, Transportation science, 12 (1978), 183-199. doi: 10.1287/trsc.12.3.183.
[31]	D.K. Merchant and G.L. Nemhauser, Optimality conditions for a dynamic traffic assignment model, Transportation Science, 12 (1978), 200-207. doi: 10.1287/trsc.12.3.200.
[32]	I.M. Mitchell, A.M. Bayen and C.J. Tomlin, A time-dependent hamilton-jacobi formulation of reachable sets for continuous dynamic games, IEEE Transactions on Automatic Control, 50 (2005), 947-957. doi: 10.1109/TAC.2005.851439.
[33]	K. Nagel and M. Schreckenberg, A cellular automaton model for freeway traffic, J. Phys. I France, 2 (1992), 2221-2229. doi: 10.1051/jp1:1992277.
[34]	A. Nagurney, J. Dong and D. Zhang, A supply chain network equilibrium model, Transportation Research Part E: Logistics and Transportation Review, 38 (2002), 281-303. doi: 10.1016/S1366-5545(01)00020-5.
[35]	G. Newell, A simplified theory of kinematic waves in highway traffic, part Ⅰ: General theory, Transportation Research Part B: Methodological, 27 (1993a), 281-287.
[36]	G. Newell, A simplified theory of kinematic waves in highway traffic, part Ⅱ: Queueing at freeway bottlenecks, Transportation Research Part B: Methodological, 27 (1993b), 289-303.
[37]	G. Newell, A simplified theory of kinematic waves in highway traffic, part Ⅲ: Multi-destination flows, Transportation Research Part B: Methodological, 27 (1993c), 305-313.
[38]	G.F. Newell, Delays caused by a queue at a freeway exit ramp, Transportation Research Part B: Methodological, 33 (1999), 337-350. doi: 10.1016/S0191-2615(98)00039-3.
[39]	N. Nezamuddin and S.D. Boyles, A continuous due algorithm using the link transmission model, Networks and Spatial Economics, 15 (2015), 465-483. doi: 10.1007/s11067-014-9234-x.
[40]	C. Osorio and G. Flötteröd, Capturing dependency among link boundaries in a stochastic dynamic network loading model, Transportation Science, 49 (2014), 420-431. doi: 10.1287/trsc.2013.0504.
[41]	C. Osorio, G. Flötteröd and M. Bierlaire, Dynamic network loading: A stochastic differentiable model that derives link state distributions, Transportation Research Part B: Methodological, 45 (2011), 1410-1423.
[42]	S. Peeta and A.K. Ziliaskopoulos, Foundations of dynamic traffic assignment: The past, the present and the future, Networks and Spatial Economics, (2001), 233-265.
[43]	J. Reilly, S. Samaranayake, M.L.D. Monache, W. Krichene, P. Gaotin and A.M. Bayen, An efficient method for coordinated ramp metering using the discrete adjoint method, Journal of Optimization Theory and Applications, 167 (2015), 733-760. doi: 10.1007/s10957-015-0749-1.
[44]	P.I. Richards, Shock waves on the highway, Operations research, 4 (1956), 42-51. doi: 10.1287/opre.4.1.42.
[45]	W. Rudin, Principles of Mathematical Analysis -Volume 3, McGraw-Hill New York, 1964.
[46]	S. Samaranayake, A. Parmentier, Y. Xuan and A.M. Bayen, Congestion reduction at an off-ramp via incentives for demand shift, Proceedings of the IEEE European Control Conference, (2015), 3465-3471.
[47]	S. Samaranayake, J. Reilly, W. Monache, M. L. D. Kirchenbe, P. Gaotin and A.M. Bayen, System optimal dynamic traffic assignment with partial compliance (SO-DTA-PC), Proceedings of the IEEE American Control Conference, (2015), 663-670.
[48]	I. Simaiakis and H. Balakrishnan, Queuing models of airport departure processes for emissions reduction In Proceedings of the AIAA Guidance, Navigation and Control Conference and Exhibit, (2009). doi: 10.2514/6.2009-5650.
[49]	H.S. Stone, Multiprocessor scheduling with the aid of network flow algorithms, IEEE Transactions on Software Engineering, SE-3 (1997), 85-93. doi: 10.1109/TSE.1977.233840.
[50]	M.H. Stone, The generalized weierstrass approximation theorem, Mathematics Magazine, 21 (1948), 237-254. doi: 10.2307/3029750.
[51]	C.M. Tampere, R. Corthout, D. Cattrysse and L.H. Immers, A generic class of first order node models for dynamic macroscopic simulation of traffic flows, Transportation Research Part B: Methodological, 45 (2011), 289-309. doi: 10.1016/j.trb.2010.06.004.
[52]	W.S. Vickrey, Congestion theory and transport investment, The American Economic Review, 59 (1969), 251-260.
[53]	D. Work, S. Blandin, O.-P. Tossavainen, B. Piccoli and A.M. Bayen, A traffic model for velocity data assimilation, AMRX Applied Mathematics Research eXpress, 1 (2010), 1-35.
[54]	I. Yperman, The Link Transmission Model for Dynamic Network Loading, Ph. D. Thesis, Katholieke Universiteit Leuven, Belgium, 2007.