Open access peer-reviewed chapter - ONLINE FIRST

Rare Event Simulation in a Dynamical Model Describing the Spread of Traffic Congestions in Urban Network Systems

By Getachew K. Befekadu

Submitted: July 21st 2020Reviewed: January 4th 2021Published: January 30th 2021

DOI: 10.5772/intechopen.95789

Downloaded: 24

Abstract

In this chapter, we present a mathematical framework that provides a new insight for understanding the spread of traffic congestions in an urban network system. In particular, we consider a dynamical model, based on the well-known susceptible-infected-recovered (SIR) model from mathematical epidemiology, with small random perturbations, that describes the process of traffic congestion propagation and dissipation in an urban network system. Here, we provide the asymptotic probability estimate based on the Freidlin-Wentzell theory of large deviations for certain rare events that are difficult to observe in the simulation of urban traffic network dynamics. Moreover, the framework provides a computational algorithm for constructing efficient importance sampling estimators for rare event simulations of certain events associated with the spread of traffic congestions in the dynamics of the traffic network.

Keywords

  • diffusion processes
  • exit probability
  • HJB equations
  • importance sampling
  • large deviations
  • rare-event simulation
  • SIR model
  • traffic network dynamics

1. Introduction

In recent years, there have been a number of interesting studies related to modeling the spread of traffic congestion propagation and traffic dissipation in urban network systems (e.g., see [1, 2, 3, 4, 5] in the context of macroscopic traffic model involving traffic flux and traffic density; see [6, 7] in the context of percolation theory; see [8] for results based on machine-learning methods; and see [9, 10] for studies based on queuing theory). In this paper, without attempting to give a literature review, we consider a dynamical model, based on the well-known susceptible-infected-recovered (SIR) model from mathematical epidemiology, with small random perturbation, that describes the spread of traffic congestion propagation and dissipation in an urban network system, i.e.,

dcεt=μ+βk1rεtcεtcεtdt+εμ+βk1+rεt+cεtcεtdW1tE1
drεt=μrεt+εμrεtdW2tE2
dfεt=βk1rεtcεtcεtdt+εβk1+rεt+cεtcεtdW3tE3

where

  • cεtrepresents the fraction of congested links in the network

  • rεtrepresents the fraction of recovered links in the network

  • fεtrepresents the fraction of free flow links in the network

  • the parameters βand μrepresent respectively the propagation and recovery rates considering that a certain fraction of congested links will eventually recover as the demand for travel diminishes

  • the quantity /μrepresents the average number of newly congested links that, in a fully freely flowing traffic network, each already congested link can potentially create,

  • W1t, W2tand W3tare three independent standard (one-dimensional) Wiener processes, and

  • εis a small positive number that represents the level of random perturbation in the network.

Notice that Eq. (1) describes the rate at which the fraction of congested links, i.e., cεt, changes over time given the propagation rate βand recovery rate μconsidering that a fraction of congested links will eventually recover as the demand for the travel volume diminishes. Moreover, Eq. (2) describes the rate at which congested links normally recover given the recovery rate μ. Finally, Eq. (3) represents how the fraction of free flow links fεtin the network changes over time given cεtand rεt. Note that, for a normalized SIR based traffic network dynamic model, the following mathematical condition cεt+rεt+fεt=1holds true for all t>0, where fεtrepresents links that have remained in a free flow state starting from t=0(e.g., see Saberi et al. [11] for detailed discussions related to deterministic models).

In this chapter, we provide the asymptotic probability estimate based on the Freidlin-Wentzell theory of large deviations for certain rare events that are difficult to observe in the simulation of urban traffic network dynamics. The framework considered in this study basically relies on the connection between the probability theory of large deviations and that of the values functions for a family of stochastic control problems, where such a connection also provides a desirable computational algorithm for constructing an efficient importance sampling estimator for rare event simulations of certain events associated with the spread of traffic congestions in the dynamics of the traffic network. Here, it is worth mentioning that a number of interesting studies based on various approximations techniques from the theory of large deviations have provided a framework for constructing efficient importance sampling estimators for rare event simulation problems involving the behavior of diffusion processes (e.g., [12, 13, 14, 15, 16] for additional discussions). The approach followed in these studies is to construct exponentially-tilted biasing distributions, which was originally introduced for proving Cramér’s theorem and its extension, and later on it was found to be an efficient importance sampling distribution for certain problems with various approximations involving rare-events (e.g., see [17, 18, 19] or [13] for detailed discussions). The rationale behind our framework follows in some sense the settings of these papers. However, to our knowledge, the problem of rare event simulations involving the spread of traffic congestions in an urban network system has not been addressed in the context of large deviations and stochastic control arguments in the small noise limit; and it is important because it provides a new insight for understanding the spread of traffic congestions in an urban network system.

This chapter is organized as follows. In Section 2, we provide an asymptotic estimate on the exit probability using the Freidlin-Wentzell theory of large deviations [20] (see also [21], Chapter 4) and the stochastic control arguments from Fleming [22] (see also [23]), where such an asymptotic estimate relies on the interpretation of the exit probability function as a value function for a family of stochastic control problems that can be associated with the underlying SIR based traffic network dynamic model with small random perturbations. In Section 3, we discuss importance sampling and the necessary background upon which our main results rely. In Section 4, we provide our main results for an efficient importance sampling estimator for rare event simulations of certain events associated with the spread of traffic congestions in the dynamics of the traffic network. Finally, Section 5 provides some concluding remarks.

2. The Freidlin-Wentzell theory

In this section, we briefly review the classical Freidlin-Wentzell theory of large deviations for the stochastic differential equations (SDEs) with small noise terms. In what follows, let us denote the solution of the SDEs in Eqs. (1)(3) by a bold face letter xtεt0=xtε,1xtε,2xtε,3t0cεtrεtfεtt0as an R3-valued diffusion process and rewrite the above equations as follows

dxtε=fxtεdt+εσxtεdWt,E4

where fxtε=f1xtεf2xtεf3xtεTwith

f1xtε,1xtε,2xtε,3=μ+βk1xtε,2xtε,1xtε,1f2xtε,1xtε,2xtε,3=μxtε,2f3xtε,1xtε,2xtε,3=βk1xtε,2xtε,1xtε,1E5

and σxtε=σ1xtεσ2xtεσ3xtεTwith

σ1xtε,1xtε,2xtε,3=μ+βk1+xtε,2+xtε,1xtε,1σ2xtε,1xtε,2xtε,3=μxtε,2σ3xtε,1xtε,2xtε,3=βk1+xtε,2+xtε,1xtε,1.E6

Moreover, Wtis a standard three-dimensional Wiener process. Note that the corresponding backward operator for the diffusion process xtε, when applied to a certain function υεtx, is given by

tυε+Lευυεtxt+ε2i,j=13ai,jx2υεtxxixj+fxxυεtx,E7

where ax=σxσTx.

Let ΩR3be bounded open domains with smooth boundary (i.e., ∂Ωis a manifold of class C2) and let ΩTbe an open set defined by

ΩT=0T×Ω.E8

Furthermore, let us denote by CΩTthe spaces of infinitely differentiable functions on ΩTand by C0ΩTthe space of the functions ϕCΩTwith compact support in ΩT. A locally square integrable function υεtxon ΩTis said to be a distribution solution to the following equation

tυε+Lευε=0,E9

if, for any test function ϕC0ΩT, the following holds true

ΩTtϕ+LεϕυεdΩT=0,E10

where dΩTdenotes the Lebesgue measure on R3×R+and Lεis an adjoint operator corresponding to the infinitesimal generator Lεof the process xtε.

Moreover, we also assume that the following statements hold for the SDE in (4).

Assumption 1

  1. The function fis a bounded C0×Ω-function, with bounded first derivatives. Moreover, σand σ1are bounded C0×R3-functions, with bounded first derivatives.

  2. Let nxbe the outer normal vector to ∂Ωand, further, let Γ+and Γ0denote the sets of points tx, with x∂Ω, such that

ftxnxE11

is positive and zero, respectively.

Remark 1Note that

Ps,xsεετεxτεεΓ+Γ0τε<=1,sxsεΩ0.E12

where τε=inft>sxtε∂Ω. Moreover, if

Ps,xsεεtxtεΓ0for sometsT=0,sxsεΩ0,E13

and τεT, then we have τεxτεεΓ+, almost surely (see [24], Section 7).

In what follows, let xtε, for 0tT, be the diffusion process associated with (4) (or Eqs. (1)(3)) and consider the following boundary value problem

sυε+Lευε=0inΩTυεsx=1onΓT+υεsx=0onT×ΩE14

where Lεis the backward operator in (7) and

ΓT+=sxΓ+0<sT.E15

Further, let Ω0Tbe the set consisting of ΩTT×Ω, together with the boundary points sxΓ+, with 0<s<T. Then, the following proposition, whose proof is given in [25], provides a solution to the exit probability Ps,xsεετεTwith which the diffusion process xtεexits from the domain Ω.

Proposition 1 Suppose that the statements in Assumption 1 hold true. Then, the exit probability qεsxε=Ps,xsεετεTis a smooth solution to the boundary value problem in (14) and, moreover, it is a continuous function on Ω0T.

Note that, from Proposition 1, the exit probability qεsxεis a smooth solution to the boundary value problem in (14). Further, if we introduce the following logarithmic transformation (e.g., see [22, 26] or [23])

Iεsxε=εlogqεsxε.E16

Then, using ideas from stochastic control theory (see [22] for similar arguments), we present results useful for proving the following asymptotic property

IεsxεI0sxεasε0.E17

The starting point for such an analysis is to introduce a family of related stochastic control problems whose dynamic programming equation, for ε>0, is given below by (21). Then, this also allows us to reinterpret the exit probability function as a value function for a family of stochastic control problems associated with the underlying urban traffic network dynamics with small random perturbation. Moreover, as discussed later in Section 5, such a connection provides a computational paradigm – based on an exponentially-tilted biasing distribution – for constructing an efficient importance sampling estimators for rare-event simulations that further improves the efficiency of Monte Carlo simulations.

Then, we consider the following boundary value problem

sgε+ε2Lε=0inΩTgε=Es,xεexp1εΦεonΩTE18

where Φεsxεis a bounded, nonnegative Lipschitz function such that

Φεsxε=0,sxεΓT+.E19

Observe that the function gεsxεis a smooth solution in ΩTto the backward operator in (9); and it is also continuous on ΩT. Moreover, if we introduce the following logarithm transformation

Jεsxε=εloggεsxε.E20

Then, Jεsxεsatisfies the following dynamic programming equation (i.e., the Hamilton-Jacobi-Bellman equation)

sJε+ε2i,j=13ai,j2Jεxixj+Hε=0,inΩT,E21

where Hε=HεsxεxJεis given by

HεsxεxJε=fxεxJεsxε12xJεsxεTaxεxJεsxε.E22

Note that the duality relation between Hεsxεand Lεsxε, i.e.,

HεsxεxJε=infûLεsxεû+xJεû,E23

with

Lεsxεû=12fxεûaxε12,E24

where axε12denotes the Riemannian norm of a tangent vector.

Then, it is easy to see that Jεsxεis a solution in ΩT, with Jε=Φεon ΩT, to the dynamic programming in (21), where the latter is associated with the following stochastic control problem

Jεsxε=infûÛsxsεEs,xsεsθLεsxεûdt+Φε(θxε)E25

that corresponds to the following system of SDEs

dxtε=ûtdt+εσxtεdWt,E26

with an initial condition xsε=xεand Ûsxεis a class of continuous functions for which θTand θxθεΓT+.

Next, we provide bounds, i.e., the asymptotic lower and upper bounds, on the exit probability qεsxε.

Define

IΩεsxε∂Ω=limε0εlogPs,xsεεxθε∂Ω,limε0εlogqεsxε,E27

where θ(or θ=τεT) is the first exit-time of xtεfrom the domain Ω. Furthermore, let us introduce the following supplementary minimization problem

I˜Ωεsφθ=infφCsTsTR3,θssθLεtφtφ̇tdt,E28

where the infimum is taken among all φCsTsTR3(i.e., from the space of Rd-valued locally absolutely continuous functions, with sTφ̇t2dt<for each T>s) and θs>0such that φsΩT, for all tsθ, and θφθΓT+. Then, it is easy to see that

I˜Ωεsφθ=IΩεsxε∂Ω.E29

Next, we state the following lemma that will be useful for proving Proposition 2 (cf. [22], Lemma 3.1).

Lemma 1 If φCsTsTR3, for s>0, and φs=xsε, tφtΩT, for all tsT, then limTsTLεtφtφ̇tdt=+.

Consider again the stochastic control problem in (25) together with (26). Suppose that ΦMε(with ΦMε0) is class C2such that ΦMε+as Muniformly on any compact subset of ΩT\Γ¯T+and ΦMεon ΓT+. Further, if we let Jε=JΦMε, when Φε=ΦMε, then we have the following lemma.

Lemma 2 Suppose that Lemma 1 holds, then we have

liminfMtxtεsxsεJΦMεsxεIεsxε.E30

Then, we have the following result.

Proposition 2 [25, Proposition 2.8] Suppose that Lemma 1 holds, then we have

IεsxεI0sxεasε0,E31

uniformly for all sxsεin any compact subset Ω¯T.

Proof: It is suffices to show the following conditions

limsupε0εlogPs,xsεεxθε∂ΩIΩεsxε∂ΩE32

and

liminfε0εlogPs,xsεεxθε∂ΩIΩεsxε∂Ω,E33

uniformly for all sxsεin any compact subset Ω¯T. Note that IΩεsxε∂Ω=Iεsxε(cf. Eq. (29)), then the upper bound in (32) can be verified using the Freidlin-Wentzell asymptotic estimates (e.g., see [27], pp. 332–334, [20] or [28]).

On the other hand, to prove the lower bound in (33), we introduce a penalty function ΦMε(with ΦMεty=0for tyΓT+); and write gε=gMε(Es,xsεεexp1εΦMε) and Jε=JΦMε, with Φε=ΦMε. From the boundary condition in (18), then, for each M, we have

gεsxεgMεsxε.E34

Using Lemma 2 and noting further the following

JΦMεsxεIΩεsxε∂Ω.E35

Then, the lower bound in (33) holds uniformly for all sxsεin any compact subset Ω¯T. This completes the proof of Proposition 2.

3. Importance sampling

In this paper, we are mainly concerned with estimating the following quantity

Es,xsεεexp1εΦεxε,E36

where Φεis an appropriate functional on C0TR3and xεis a solution of the SDE in (4) and our analysis is in the situation where the level of the random perturbation is small, i.e., ε1, and the functional Es,xsεεexp1εΦεxεis rapidly varying in xε. Note that the challenge presented by such an analysis of rare event probabilities is well documented (see [12, 18, 29] for additional discussions). In the following (and see also Section 4), we specifically consider the case when the functional Φεis bounded and nonnegative Lipschitz, with Φε=0, if xtεΩTC0T:R3and Φε=otherwise; and we further consider analysis on the asymptotic estimates for exit probabilities from a given bounded open domain in the small noise limit case.

Consider the following simple estimator for the quantity of interest in (36)

ρε=1Nj=1Nexp1εΦεxεj,E37

where xεjj=1Nare N-copies of independent samples of xε. Here we remark that such an estimator is unbiased in the sense that

Es,xsεερε=Es,xsεεexp1εΦεxε,E38

Moreover, its variance is given by

Varρε=1NEs,xsεεexp2εΦεxεEs,xsεεexp1εΦεxε2.E39

Then, we have the following for the relative estimation error

Rerrρε=VarρεEs,xsεερεE40

which can be further rewritten as follows

Rerrρε=1/NΔρε1,E41

where

Δρε=Es,xsεεexp2εΦεxεEs,xsεεexp1εΦεxε2.E42

Note that, as we might expect, the relative estimation error may decrease with increasing the number of the sample size N. However, from Varahhan’s lemma (e.g., see [30]; see also [20, 28]), under suitable assumptions, we also have the following conditions

limsupε0εlogEs,xsεεexp1εΦεxε=infφCsTsTRndφs=xsIφ+ΦεφE43

and

limsupε0εlogEs,xsεεexp2εΦεxε=infφCsTsTRndφs=xsIφ+2ΦεφE44

where CsTsTR3is the set of absolutely continuous functions from sTinto R3, with 0stT, and Iφis the rate functional for the diffusion process xtε. From Jensen’s inequality, the above equations in (43) and (44) also imply the following condition Δρε1.

4. Main results

In this section, we present our main result that asserts the relative error decreases to zero as the small random perturbation tends to zero, which in turn implies the uniform log-efficiency for the estimation problem in (36).

In what follows, let x̂tεbe the solution to the following SDE

dx̂tε=ftx̂tεdt+bσtx̂tεvεtx̂tεdt+εbσtx̂tεdWt,with an initial conditionx̂sε=xsε,E45

where vεis an appropriate control function (which also depends on ε) to be chosen so as to reduce the variance of the importance sampling estimator.

Let

zε=exp1εsTvεtx̂tεdWt12εsTvε(tx̂tε)2dt.E46

Then, the corresponding importance sampling estimator is given by

ρ̂ε=1Nj=1Nexp1εΦεx̂εjzεj,E47

where x̂εjzεjj=1Nare N-copies of independent samples of x̂εzε. Note that, for an appropriately chosen control function vε, the above importance sampling estimator in (47) is an unbiased estimator for (37), i.e.,

Es,xsεερ̂ε=Es,xsεεexp1εΦεxεEs,xsεερε.E48

Moreover, the relative estimation error is given by

Rerrρ̂ε=Varρ̂εEs,xsεερ̂εE49

which can be rewritten as follows

Rerrρ̂ε=1/NΔρ̂ε1,E50

where

Δρ̂ε=Es,xsεεexp2εΦεx̂εzε2Es,xsεεexp1εΦεxε2.E51

Hence, in order to reduce the relative estimation error Rerrρ̂ε, we need to control the term Δρ̂εin (50). Note that, from Jensen’s inequality, we have the following condition

limsupε0εlogEs,xsεεexp2εΦεx̂ε2limε0εlogEs,xsεεexp1εΦεx̂εE52

which also implies Δρ̂ε1with limε0Δρ̂ε=1. Moreover, the statement in (49) further implies the following

Rerrρ̂ε=1Nexpo1/εasε0,E53

which is generally referred as asymptotic efficiency or optimality. In this paper, our main objective is to choose appropriately the control function vεin (45), so that the resulting importance sampling estimator achieves a minimum rate of error growth. For this reason, we introduce the following standard definition from simulation theory (e.g., see [29] or [12]) which is useful for interpreting our main result.

Definition 1 An importance sampling estimator of the form (47) is log-efficient (i.e., asymptotic efficiency or optimal) if

limε0εlogΔρ̂ε=0.E54

Then, we state the following result as follows.

Proposition 3 Suppose that the importance sampling estimator ρ̂εin (47), with vεtx=σTxxJεtx, is uniformly log-efficient (i.e., asymptotic efficient), where Jεtxsatisfies the corresponding dynamic programming equation in ΩTwith respect to the system in (45), with Jε=Φεon ΩT. Then, there exits a set AR3such that the Hausedorf dimension of Acis zero and

limε0Rerrρ̂ε=0,E55

for all xA.

Proof: The above proposition basically asserts that the relative error Rerrρ̂εdecreases to zero as the small random perturbation level εtends to zero. Note that, if Jεsxεsatisfies the dynamic programming equation in (21), then, with vεtx=σTxxJεtx, the importance sampling for the estimation problem in (36), i.e., Es,xsεεexp1εΦεxε, is uniformly log-efficient if the point sxsεis contained in a region of sufficient regularity that encompasses almost all R3. As a result of this, it only suffices to show that

limε0Es,xsεεexp2εΦεx̂εzε2Es,xsεεexp1εΦεxε2=1E56

holds uniformly for all sxsεin any compact subset Ω¯T.

Let us define following two functions

ψ1εsxsε=εlogEs,xsεεexp2εΦεx̂εE57

and

ψ2εsxsε=εlogEs,xsεεexp2εΦεx̂εzε2=εlogEs,xsεεexp2εΦεx̂ε2εsTvε(tx̂tε)dWt1εsTvεtx̂tε2dt.E58

Note that, from the large deviations results for the diffusion process x̂tε(e.g., see [21], Chapter 4, [30] or [27], pp.332–334; and see also the asymptotic estimates in Proposition 2 of Section 3), then there exists a constant C, γ>0and ε0, with ε0ε0, such that

E0,x0εεexp1ε(ψ2ετ̂εx̂τ̂εε2ψ1ε(τ̂εx̂τ̂εε))0τ̂εi,j=13ai,jxsε2ψ1εsx̂sεxixjdsCexpγ/2ε,E59

where τ̂ε=inft>sx̂tε∂ΩT. Note that the above relation further implies that

limε0exp1ε(ψ2ε0x02ψ10(0x0))=exp0Ti,j=13ai,jxsε2ψ1εsx̂sεxixjds.E60

Moreover, in the same way, we can also show the following relation

limε0exp1ε(ψ1ε0x0ψ10(0x0))=exp0Ti,j=13ai,jxsε2ψ1εsx̂sεxixjds.E61

Finally, if we combine the above two equations, then we have the condition following

limε0exp1ε(ψ2ε0x0ψ1ε(0x0))=1,E62

which implies the uniform log-efficiency for the estimation problem in (36). This completes the proof of Proposition 3.

Remark 2 The above proposition basically ensures a minimum relative estimation error in the small noise limit case for the estimation problem in (28). Note that, if Jεtxεsatisfies the dynamic programming equation in (21) (i.e., if it is the solution for the family of stochastic control problems that are associated with the underlying distributed system with small random perturbation). Then, with vεtx=σTxxJεtx, one can provide a numerical computational framework for constructing efficient importance sampling estimators, with an exponential variance decay rate − based on an exponentially-tilted biasing distribution – for rare-event simulations involving the behavior of the diffusion process xε.

Remark 3 Here, our primary intent is to provide a theoretical framework, rather than considering some specific numerical simulation results with respect to system parameters (such as the propagation rate βand recovery rate μof the network), which is an ongoing research area.

5. Concluding remarks

In this chapter, we presented a mathematical framework that provides a new insight for understanding the spread of traffic congestions in an urban network system. In particular, we considered a dynamical model, based on the well-known susceptible-infected-recovered (SIR) model from mathematical epidemiology, with small random perturbations, that describes the process of traffic congestion propagation and dissipation in an urban network system. Moreover, we also provided the asymptotic probability estimate based on the Freidlin-Wentzell theory of large deviations for certain rare events that are difficult to observe in the simulation of an urban traffic network dynamic, where such a framework provides a computational algorithm for constructing efficient importance sampling estimators for rare event simulations of certain events associated with the spread of traffic congestions in the traffic network.

Download for free

chapter PDF

© 2021 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Getachew K. Befekadu (January 30th 2021). Rare Event Simulation in a Dynamical Model Describing the Spread of Traffic Congestions in Urban Network Systems [Online First], IntechOpen, DOI: 10.5772/intechopen.95789. Available from:

chapter statistics

24total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us