Kerner’s breakdown minimization principle

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Kerner’s breakdown minimization principle (BM principle) is a principle for the optimization of vehicular traffic networks introduced by Boris Kerner in 2011.[1]

Definition of Kerner’s BM principle[edit]

The BM principle states that the optimum of a traffic network with N network bottlenecks is reached, when dynamic traffic optimization and/or control are performed in the network in such a way that the probability for spontaneous occurrence of traffic breakdown in at least one of the network bottlenecks during a given observation time reaches the minimum possible value. The BM principle is equivalent to the maximization of the probability that traffic breakdown occurs at none of the network bottlenecks.

Empirical ground of the BM principle[edit]

The empirical ground for Kerner’s BM principle is the set of fundamental empirical features of traffic breakdown at a highway bottleneck found in measured traffic data:

  1. Traffic breakdown at a highway bottleneck is a local phase transition from free flow (F) to congested traffic whose downstream front is usually fixed at the bottleneck location. Within this front, vehicles accelerate from congested traffic to free flow downstream of the bottleneck.
  2. At the same bottleneck, traffic breakdown can be either spontaneous (Figure 1(a)) or induced (Figure 1 (b)).
  3. The probability of traffic breakdown is an increasing flow rate function.
  4. There is a well-known hysteresis phenomenon associated with traffic breakdown: When the breakdown has occurred at some flow rates with resulting congested pattern formation upstream of the bottleneck, then a return transition to free flow at the bottleneck is usually observed at considerably smaller flow rates (Figure 2).

A spontaneous traffic breakdown occurs, where there are free flows both upstream and downstream of the bottleneck before the breakdown has occurred (Fig. 1(a)). In contrast, an induced traffic breakdown is caused by a propagation of a congested pattern that has earlier emerged for example at another downstream bottleneck (Figure 1 (b)).

Figure 1: Fundamental empirical features of traffic breakdown (FS transition) at a highway bottleneck: (a, b) Averaged measured speed in space and time in the cases of spontaneous (a) and induced (b) traffic breakdowns.
Figure 2: Fundamental empirical features of traffic breakdown at a highway bottleneck: Hysteresis phenomenon cause by traffic breakdown (FS transition) and return transition from congested to free flow (SF transition).

The set 1–4 of the fundamental empirical features of traffic breakdown at a highway bottleneck has first been explained in Kerner’s three-phase theory (Figure 3). In Kerner’s theory there are three phases: Free flow (F), synchronized flow (S), wide moving jam (J). Synchronized flow and wide moving jam are associated with congested traffic. The synchronized flow phase is defined as congested traffic whose downstream front is fixed at the bottleneck. Therefore, in accordance with empirical feature 1 traffic breakdown is a phase transition from free flow to synchronized flow (called FS transition). The main feature of an FS transition is as follows (Figure 3 (c, d)): There is a broad range of flow rates on a link of the traffic network between the minimum and maximum capacities of free flow. Within this range of flow rates traffic breakdown occurs with some probability, which depends on the flow rate (Figure 3 (c)).

Figure 3: Explanations of the fundamental empirical features of traffic breakdown at a highway bottleneck with Kerner’s three-phase theory: (a, b) Simulations of spontaneous (a) and induced (b) traffic breakdowns at a highway bottleneck. (c) Simulated flow-rate dependence of probability of traffic breakdown at a highway bottleneck. (d) Qualitative Z-characteristic for highway traffic in the speed—flow-rate plane (arrow is related to an FS transition); bottleneck states labeled by circles F and S are related to free flow and synchronized flow.

Mathematical formulation of the BM principle[edit]

Assuming that at different bottlenecks traffic breakdown occurs independently, the probability for spontaneous occurrence of traffic breakdown in at least one of the network bottlenecks during a given observation time can be written as:

P_\mathrm{net}=1-\prod^N_{k=1}(1-P^{(B,k)})

In accordance with the BM principle, the network optimum is reached at

\min_{q_1,q_2,\ldots,q_M}\{P_\mathrm{net}( q_1,q_2,\ldots,q_M)\}>

Here, M is the number of network links for which flow rates can be adjusted; q_{m} is the link inflow rate for a link with index m; m=1,2,\ldots,M, where M>1; k is the bottleneck index, k=1,2,\ldots,N, N>1;  P^{(B,k)} is the probability that during the observation time interval traffic breakdown occurs at bottleneck with index k.

Simulations of the BM principle[edit]

Results of simulations of the BM principle for a simple network consisting of only two routes are shown in Figure 4(a). Although the probability of traffic breakdown is an increasing flow rate function for each of the bottlenecks (Figure 3(c)), the probability of traffic breakdown in the network P_{net} has a minimum as a function of the link inflow rates q_1 and q_2 (Figure 4(b, c)).

Figure 4: Simulations of the BM principle for simple network model shown in (a). (b, c) probability of traffic breakdown in the network P_{net} found with the BM principle. In (a), alternative routes 1 and 2 have lengths L_1 and L_2, where L_2>L_1; routes 1 and 2 are roads with on-ramp bottlenecks whose on-ramp inflow rates q_{on1} and q_{on2} are given constants. Network optimization is performed through the assignment of a network inflow with the rate q_O between network links m=1 and m=2.

Alternative routes in a network[edit]

Before the BM principle is applied to a large traffic network, for each of the origin-destination (O–D) pairs of the network a set of alternative routes (paths) should be found. The alternative routes can be calculated based on the following assumptions: (i) there is free flow in the whole network and (ii) the maximum difference between travel times for alternative routes does not exceed a given value that can be chosen differently for different O–D pairs.

How to apply the BM principle if traffic breakdown has already occurred at a network bottleneck[edit]

Network optimization with measured features of traffic breakdown can consist of the stages: (i) A spatial limitation of congestion growth with the subsequent congestion dissolution at the bottleneck, if the dissolution of congestion due to traffic management in a neighborhood of the bottleneck is possible. (ii) The minimization of traffic breakdown probability with the BM principle in the remaining network, i.e., the network part that is not influenced by congestion.

The BM principle and classical Wardrop’s UE and SO principles[edit]

The BM principle is an alternative to well-known principles for vehicular network optimization and control based on the minimization of travel costs (travel time, fuel consumption, etc.) or the maximization of traffic throughput (like the maximization of band width of green wave in a city).[2][3][4][5][6][7][8][9][10][11][12][13][14] In particular, the most prominent classical principles for the minimization of travel costs in a traffic network are Wardrop’s user equilibrium (UE) and system optimum (SO) principles[2] that are widely used in a theory of dynamic traffic assignment in the network.[4][6][13] Wardrop's SO and UE principles have been explained in Secs. 7.1 and 7.2 of Wikipedia article traffic flow.

However, when the flow rate on a link of a network is between the maximum and minimum capacities, there may be at least two different states of a bottleneck on the link denoted by circles F and S shown in Figure 3 (d). The state F is related to free flow and state S to synchronized flow. Therefore, hypothetically assuming that each of the link flow rates for each of the N network bottlenecks is between the associated minimum and maximum bottleneck capacities, we find that there may be 2^N different bottleneck states in the network at the same distribution of the flow rates in the network. If we apply an optimization algorithm associated with the minimization of travel cost in the network random transitions between these bottleneck states F and S may occur at different network bottlenecks during network optimization and/or control.

Rather than some travel costs, in the BM principle the objective function that should be minimized is the probability of traffic breakdown in the network P_{net}. Thus the objective function in the BM principle that should be minimized depends neither on travel time nor other travel cost. The BM principle demands the minimization of the probability of traffic breakdown, i.e., the probability of the occurrence of congestion in the network. Under great traffic demand, the application of the BM principle should result in relatively small travel cost associated with free flow in a network.

Notes[edit]

  1. ^ Boris S. Kerner (2011), "Optimum principle for a vehicular traffic network: minimum probability of congestion", J. Phys. A: Math. Theor. 44 092001. doi:10.1088/1751-8113/44/9/092001
  2. ^ a b Wardrop J.G. (1952). Some theoretical aspects of road traffic research. In Proc. of Inst. of Civil Eng. II. Vol. 1, pp. 325–378.
  3. ^ Daganzo C. F. and Sheffi Y. (1977). On Stochastic Models of Traffic Assignment. Transportation Science, 11, 253–274.
  4. ^ a b M.G.H. Bell, Y. Iida (1997), Transportation network analysis, (John Wiley & Sons, Incorporated, Hoboken, NJ 07030-6000 USA)
  5. ^ C.F. Daganzo (1998), Transportation Science 32, 3–11
  6. ^ a b S. Peeta, A.K. Ziliaskopoulos (2001), Networks and Spatial Economics 1, 233–265
  7. ^ H. Ceylan, M.G.H. Bell (2005), Transp. Res. B 39, 169–185
  8. ^ Zhang, C., Chen, X., Sumalee, A. (2011). Robust Wardrop's user equilibrium assignment under stochastic demand and supply: Expected residual minimization approach. Transp. Res. B, Vol. 45, pp. 534–552.
  9. ^ Hoogendoorn, S.P., Knoop, V.L., Van Zuylen, H.J. (2008). Robust control of traffic networks under uncertain conditions. J. of Adv. Transp. Vol. 42, pp. 357–377.
  10. ^ Wahle J., Bazzan A.L.C., Klugl F., Schreckenberg M. (2000), Decision dynamics in a traffic scenario. Physica A, Vol. 287, pp. 669–681.
  11. ^ Davis L.C. (2009). Realizing Wardrop equilibria with real-time traffic information. Physica A, Vol. 388, pp. 4459–4474;
  12. ^ Davis L.C. (2010). Predicting travel time to limit congestion at a highway bottleneck. Physica A, Vol. 389, pp. 3588–3599.
  13. ^ a b Rakha H., Tawfik A. (2009). Traffic Networks, Dynamic Traffic Routing, Assignment, and Assessment. In Encyclopedia of Complexity and System Science, ed. by R.A. Meyers. Springer, Berlin, pp. 9429–9470.
  14. ^ Gartner N.H., Stamatiadis Ch. (2009). Traffic Networks, Optimization and Control of Urban. In Encyclopedia of Complexity and System Science, ed. by R.A. Meyers. Springer, Berlin, pp. 9470—9500.

See also[edit]