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:
[1]

A. Adas, Traffic models in broadband networks, Communications Magazine, IEEE, 35 (1997), 82-89.  doi: 10.1109/35.601746.  Google Scholar

[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.   Google Scholar

[3]

X.J. BanJ.-S. PangH.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.  Google Scholar

[4]

X.J. BanJ.-S. PangH.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.  Google Scholar

[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.  Google Scholar

[6]

C.-S. Chang, Performance Guarantees in Communication Networks, Springer, 2000 doi: 10.1007/978-1-4471-0459-9.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[9]

C.F. DaganzoW.-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.  Google Scholar

[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.  Google Scholar

[11]

T.L. FrieszK. HanP.A. NetoA. 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.  Google Scholar

[12]

V.S. Frost and B. Melamed, Traffic modeling for telecommunications networks, Communications Magazine, IEEE, 32 (1994), 70-81.  doi: 10.1109/35.267444.  Google Scholar

[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. Google Scholar

[14]

K. HanT.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.  Google Scholar

[15]

K. HanT.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.  Google Scholar

[16]

K. HanT.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.  Google Scholar

[17]

M. HertyA. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[20]

Y. Hollander and R. Liu, The principles of calibrating traffic microsimulation models, Transportation, 35 (2008), 347-362.   Google Scholar

[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.  Google Scholar

[22]

S. JainK. Fall and R. Patra, Routing in a delay tolerant network, , ().  doi: 10.1145/1015467.1015484.  Google Scholar

[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.  Google Scholar

[24]

J. Lafontaine, An Introduction to Differential Manifolds, 2015. doi: 10.1007/978-3-319-20735-3.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[28]

H.K. LoE. 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.  Google Scholar

[29]

R. MaX.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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[32]

I.M. MitchellA.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.  Google Scholar

[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.  Google Scholar

[34]

A. NagurneyJ. 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.  Google Scholar

[35]

G. Newell, A simplified theory of kinematic waves in highway traffic, part Ⅰ: General theory, Transportation Research Part B: Methodological, 27 (1993a), 281-287.   Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[41]

C. OsorioG. 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.   Google Scholar

[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.   Google Scholar

[43]

J. ReillyS. SamaranayakeM.L.D. MonacheW. KricheneP. 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.  Google Scholar

[44]

P.I. Richards, Shock waves on the highway, Operations research, 4 (1956), 42-51.  doi: 10.1287/opre.4.1.42.  Google Scholar

[45]

W. Rudin, Principles of Mathematical Analysis -Volume 3, McGraw-Hill New York, 1964.  Google Scholar

[46]

S. SamaranayakeA. ParmentierY. 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.   Google Scholar

[47]

S. SamaranayakeJ. ReillyW. MonacheM. L. D. KirchenbeP. 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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[50]

M.H. Stone, The generalized weierstrass approximation theorem, Mathematics Magazine, 21 (1948), 237-254.  doi: 10.2307/3029750.  Google Scholar

[51]

C.M. TampereR. CorthoutD. 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.  Google Scholar

[52]

W.S. Vickrey, Congestion theory and transport investment, The American Economic Review, 59 (1969), 251-260.   Google Scholar

[53]

D. WorkS. BlandinO.-P. TossavainenB. Piccoli and A.M. Bayen, A traffic model for velocity data assimilation, AMRX Applied Mathematics Research eXpress, 1 (2010), 1-35.   Google Scholar

[54]

I. Yperman, The Link Transmission Model for Dynamic Network Loading, Ph. D. Thesis, Katholieke Universiteit Leuven, Belgium, 2007. Google Scholar

show all references

References:
[1]

A. Adas, Traffic models in broadband networks, Communications Magazine, IEEE, 35 (1997), 82-89.  doi: 10.1109/35.601746.  Google Scholar

[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.   Google Scholar

[3]

X.J. BanJ.-S. PangH.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.  Google Scholar

[4]

X.J. BanJ.-S. PangH.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.  Google Scholar

[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.  Google Scholar

[6]

C.-S. Chang, Performance Guarantees in Communication Networks, Springer, 2000 doi: 10.1007/978-1-4471-0459-9.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[9]

C.F. DaganzoW.-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.  Google Scholar

[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.  Google Scholar

[11]

T.L. FrieszK. HanP.A. NetoA. 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.  Google Scholar

[12]

V.S. Frost and B. Melamed, Traffic modeling for telecommunications networks, Communications Magazine, IEEE, 32 (1994), 70-81.  doi: 10.1109/35.267444.  Google Scholar

[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. Google Scholar

[14]

K. HanT.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.  Google Scholar

[15]

K. HanT.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.  Google Scholar

[16]

K. HanT.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.  Google Scholar

[17]

M. HertyA. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[20]

Y. Hollander and R. Liu, The principles of calibrating traffic microsimulation models, Transportation, 35 (2008), 347-362.   Google Scholar

[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.  Google Scholar

[22]

S. JainK. Fall and R. Patra, Routing in a delay tolerant network, , ().  doi: 10.1145/1015467.1015484.  Google Scholar

[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.  Google Scholar

[24]

J. Lafontaine, An Introduction to Differential Manifolds, 2015. doi: 10.1007/978-3-319-20735-3.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[28]

H.K. LoE. 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.  Google Scholar

[29]

R. MaX.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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[32]

I.M. MitchellA.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.  Google Scholar

[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.  Google Scholar

[34]

A. NagurneyJ. 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.  Google Scholar

[35]

G. Newell, A simplified theory of kinematic waves in highway traffic, part Ⅰ: General theory, Transportation Research Part B: Methodological, 27 (1993a), 281-287.   Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[41]

C. OsorioG. 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.   Google Scholar

[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.   Google Scholar

[43]

J. ReillyS. SamaranayakeM.L.D. MonacheW. KricheneP. 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.  Google Scholar

[44]

P.I. Richards, Shock waves on the highway, Operations research, 4 (1956), 42-51.  doi: 10.1287/opre.4.1.42.  Google Scholar

[45]

W. Rudin, Principles of Mathematical Analysis -Volume 3, McGraw-Hill New York, 1964.  Google Scholar

[46]

S. SamaranayakeA. ParmentierY. 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.   Google Scholar

[47]

S. SamaranayakeJ. ReillyW. MonacheM. L. D. KirchenbeP. 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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[50]

M.H. Stone, The generalized weierstrass approximation theorem, Mathematics Magazine, 21 (1948), 237-254.  doi: 10.2307/3029750.  Google Scholar

[51]

C.M. TampereR. CorthoutD. 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.  Google Scholar

[52]

W.S. Vickrey, Congestion theory and transport investment, The American Economic Review, 59 (1969), 251-260.   Google Scholar

[53]

D. WorkS. BlandinO.-P. TossavainenB. Piccoli and A.M. Bayen, A traffic model for velocity data assimilation, AMRX Applied Mathematics Research eXpress, 1 (2010), 1-35.   Google Scholar

[54]

I. Yperman, The Link Transmission Model for Dynamic Network Loading, Ph. D. Thesis, Katholieke Universiteit Leuven, Belgium, 2007. Google Scholar

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

Metrics

  • PDF downloads (13)
  • HTML views (9)
  • Cited by (0)

[Back to Top]