A mathematical framework for delay analysis in single source networks

Samitha Samaranayake; Axel Parmentier; Ethan Xuan; Alexandre Bayen; Samitha Samaranayake; Axel Parmentier; Ethan Xuan; Alexandre Bayen

doi:10.3934/nhm.2017005

Networks and Heterogeneous Media

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

Previous Article Next Article

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

Received: 01 June 2016 Revised: 01 December 2016
Primary: 34B45

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.
- Delay analysis,
- traffic flow,
- flow networks
Citation: Samitha Samaranayake, Axel Parmentier, Ethan Xuan, Alexandre Bayen. A mathematical framework for delay analysis in single source networks[J]. Networks and Heterogeneous Media, 2017, 12(1): 113-145. doi: 10.3934/nhm.2017005

Related Papers:

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.

References

[1]	Traffic models in broadband networks. Communications Magazine, IEEE (1997) 35: 82-89.
[2]	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]	Continuous-time point-queue models in dynamic network loading. Transportation Research Part B: Methodological (2012) 46: 360-380.
[4]	Modeling and solving continuous-time instantaneous dynamic user equilibria: A differential complementarity systems approach. Transportation Research Part B: Methodological (2012) 46: 389-408.
[5]	Existence of optima and equlibria for traffic flow on networks. Networks} & Heterogeneous Media (2013) 8: 627-648.
[6]	C.-S. Chang, Performance Guarantees in Communication Networks, Springer, 2000 doi: 10.1007/978-1-4471-0459-9
[7]	The cell transmission model, Part Ⅱ network traffic. Transportation Research Part B: Methodological (1995) 29: 79-93.
[8]	A continuum theory of traffic dynamics for freeways with special lanes. Transportation Research Part B: Methodological (1997) 31: 83-102.
[9]	A simple physical principle for the simulation of freeways with special lanes and priority vehicles. Transportation Research Part B: Methodological (1997) 31: 103-125.
[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]	Dynamic user equilibrium based on a hydrodynamic model. Transportation Research Part B: Methodological (2013) 47: 102-126.
[12]	Traffic modeling for telecommunications networks. Communications Magazine, IEEE (1994) 32: 70-81.
[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]	Existence of simultaneous route and departure choice dynamic user equilibrium. Transportation Research Part B: Methodological (2013a) 53: 17-30.
[15]	A partial differential equation formulation of {V}ickrey's bottleneck model, part i: Methodology and theoretical analysis. Transportation Research Part B: Methodological (2013b) 49: 55-74.
[16]	A partial differential equation formulation of Vickrey's bottleneck model, part ii: Numerical analysis and computation. Transportation Research Part B: Methodological (2013c) 49: 75-93.
[17]	Existence of solutions for supply chain models based on partial differential equations. SIAM Journal on Mathematical Analysis (2007) 39: 160-173.
[18]	Modelling vehicle interactions in microscopic simulation of merging and weaving. Transportation Research Part C: Emerging Technologies (2005) 13: 37-62.
[19]	A mathematical model of traffic flow on a network of unidirectional roads. SIAM J. Math. Anal. (1995) 26: 999-1017.
[20]	The principles of calibrating traffic microsimulation models. Transportation (2008) 35: 347-362.
[21]	Effects of ramps in the nagel-schreckenberg traffic model. International Journal of Modern Physics C (2002) 13: 739-749.
[22]	Routing in a delay tolerant network..
[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]	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]	On kinematic waves Ⅰ. flood movement in long rivers. Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences (1955) 229: 281-316.
[27]	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 (1955) 229: 317-345.
[28]	Dynamic network traffic control. Transportation Research Part A: Policy and Practice (2001) 35: 721-744.
[29]	Continuous-time dynamic system optimum for single-destination traffic networks with queue spillbacks. Transportation Research Part B: Methodological (2014) 68: 98-122.
[30]	A model and an algorithm for the dynamic traffic assignment problems. Transportation science (1978) 12: 183-199.
[31]	Optimality conditions for a dynamic traffic assignment model. Transportation Science (1978) 12: 200-207.
[32]	A time-dependent hamilton-jacobi formulation of reachable sets for continuous dynamic games. IEEE Transactions on Automatic Control (2005) 50: 947-957.
[33]	A cellular automaton model for freeway traffic. J. Phys. I France (1992) 2: 2221-2229.
[34]	A supply chain network equilibrium model. Transportation Research Part E: Logistics and Transportation Review (2002) 38: 281-303.
[35]	A simplified theory of kinematic waves in highway traffic, part Ⅰ: General theory. Transportation Research Part B: Methodological (1993a) 27: 281-287.
[36]	A simplified theory of kinematic waves in highway traffic, part Ⅱ: Queueing at freeway bottlenecks. Transportation Research Part B: Methodological (1993b) 27: 289-303.
[37]	A simplified theory of kinematic waves in highway traffic, part Ⅲ: Multi-destination flows. Transportation Research Part B: Methodological (1993c) 27: 305-313.
[38]	Delays caused by a queue at a freeway exit ramp. Transportation Research Part B: Methodological (1999) 33: 337-350.
[39]	A continuous due algorithm using the link transmission model. Networks and Spatial Economics (2015) 15: 465-483.
[40]	Capturing dependency among link boundaries in a stochastic dynamic network loading model. Transportation Science (2014) 49: 420-431.
[41]	Dynamic network loading: A stochastic differentiable model that derives link state distributions. Transportation Research Part B: Methodological (2011) 45: 1410-1423.
[42]	Foundations of dynamic traffic assignment: The past, the present and the future. Networks and Spatial Economics (2001) 233-265.
[43]	An efficient method for coordinated ramp metering using the discrete adjoint method. Journal of Optimization Theory and Applications (2015) 167: 733-760.
[44]	Shock waves on the highway. Operations research (1956) 4: 42-51.
[45]	W. Rudin, Principles of Mathematical Analysis -Volume 3, McGraw-Hill New York, 1964.
[46]	Congestion reduction at an off-ramp via incentives for demand shift. Proceedings of the IEEE European Control Conference (2015) 3465-3471.
[47]	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]	Multiprocessor scheduling with the aid of network flow algorithms. IEEE Transactions on Software Engineering (1997) SE-3: 85-93.
[50]	The generalized weierstrass approximation theorem. Mathematics Magazine (1948) 21: 237-254.
[51]	A generic class of first order node models for dynamic macroscopic simulation of traffic flows. Transportation Research Part B: Methodological (2011) 45: 289-309.
[52]	Congestion theory and transport investment. The American Economic Review (1969) 59: 251-260.
[53]	A traffic model for velocity data assimilation. AMRX Applied Mathematics Research eXpress (2010) 1: 1-35.
[54]	I. Yperman, The Link Transmission Model for Dynamic Network Loading, Ph. D. Thesis, Katholieke Universiteit Leuven, Belgium, 2007.

Reader Comments

Your name:*

Email:*
© 2017 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)