Abstract
Many analyses of traffic signal queues use Webster and Cobbe's formula, which combines the net effect of the red/green cycle with a term representing stochastic effects, idealised as an M/D/1 queue process having random arrivals and uniform service. Several authors have noted that this component should depend not only on demand intensity but also on throughput capacity in each green period, although an extra empirical term may partially allow for this. Extending the service interval in M/D/1 (M = Markovian, i.e. random, D = deterministic, i.e. uniform, 1 = one server) enables the effect to be reproduced, but no exact expressions for its moments are found. Approximate formulae for the extended mean exist but are accurate only near saturation. The paper derives novel approximations for the equilibrium mean and also variance and utilisation, using functions linking traffic intensity with green period capacity. With three moments, equilibrium probability distributions can be estimated for which a method based on a doubly nested geometric distribution is described.
Introduction and background
Real signalised junctions are complicated by demand-responsive timings, conflicting movements and coordination. Microscopic simulation, which need only specify short-term individual behaviour, is used increasingly. Nevertheless, the formula of Webster and Cobbe (Citation1966) for queue size or delay at an isolated signal is still widely regarded. In addition to red and green phase component, it contains a term representing stochastic effects, including transient overload. This is equivalent to an idealised queuing process where customers arrive randomly and are served at uniform intervals. Several authors, including Olszewski (Citation1990), have pointed out that this overestimates the true stochastic queue component, which simulation shows falls, albeit slowly, with increasing throughput capacity in the green period. Webster's formula has an empirical term that may compensate for this effect and can be related to a more exact formula. However, it is difficult to integrate these with computationally efficient time-dependent approximate methods.
After describing the basic stochastic process, an extension is developed to take account of green period capacity. Simulation results based on it are used to derive approximations to the queue's equilibrium utilisation, mean and variance in forms compatible with time-dependent queuing methods, which are shown to be more consistent than earlier empirical approximations. A novel approach makes use of link functions between traffic intensity and green period capacity, allowing a broad physical interpretation. Comparison with simulation shows that the results are accurate over a range of traffic intensities and green period capacities. A method of estimating a probability distribution from the three moments is described that may have wider application. Finally, the theoretical nature of the analysis is justified, and various conceptual and practical issues are discussed.
The mean queue size at a signal
Allsop and Hutchinson (Citation1972) trace the origins of signal queue analysis back to A J H Clayton in 1940, as well as discuss the impact of different assumptions about arrival patterns. A well-established expression for the mean queue size L at a fixed-time traffic signal is EquationEquation (1), ascribed to Webster (Webster and Cobbe Citation1966):
c signal cycle time;
g green time within each cycle;
r red time within cycle;
Λ green cycle time ratio = g/c (avoiding possible confusion with demand rate λ);
s saturation flow, the maximum flow rate across the stop-line;
µ = gs/c, capacity of the movement taking account of the green/cycle ratio;
x average degree of saturation or utilisation of service at the stop-line.
G = gs = µ c, the number of vehiclesFootnote1 that can pass in a single green period
ρ = λ/µ, demand intensity, relative to capacity
Dependence of the stochastic queue on green period capacity
Olszewski (Citation1990) uses Markov simulation based on transition probabilities, allowing for a general arrival distribution and variable cycle time, to confirm observations by Newell (Citation1965) and Miller (Citation1969) that the mean size of the stochastic queue at a signal decreases systematically with increasing green period capacityFootnote2 G. Although the decline is gradual, it can be substantial for long green times, and this trend appears to continue indefinitely. For example, at 90% saturation (x = 0.9), the mean queue with 40 second green is half that with a short (1–2 second) green. The US Highway Capacity Manual (HCM) (Rouphail, Tarko, and Li Citation1996) and Australian time-dependent formulae (Akçelik Citation1998) also contain empirical terms depending on green period capacity. Olszewski's Footnote3 shows that his EVOL simulation results compare well with Newell's formula, though less well with Akçelik's.
Some fundamental properties of queues and time-dependent approximation
All queues obey the time-dependent deterministic EquationEquation (3) representing conservation of units (customers, vehicles etc.), where L0 is the initial queue and x is the average utilisation or degree of saturation over the period of development [0,t]. If the demand intensity ρ < 1, the mean queue tends to an equilibrium value given by the Pollaczek–Khinchin (P–K) mean queue formula (4) (e.g. Kleinrock Citation1975):
The coefficient I in EquationEquation (4) reflects unavoidable service time, which conventionally applies only to priority junctions, while C depends on the coefficient of variation of service time.Footnote4 For a signal I = 0, while theoretically C = 0.5, giving LV as in EquationEquation (1). Empirically, C is found to be in the range of 0.5–0.6 (Burrow Citation1987). When EquationEquations (3) and Equation(4) are equated and solved for x or L, the result is the quasi-static ‘sheared’ approximation to time-dependent queuing, including stochastic effects, being defined for all ρ, since x never exceeds 1 (e.g. Kimber and Hollis Citation1979). This has some accuracy issues but is convenient for use in dynamic network assignment programs such as CONTRAM (Taylor Citation2003). Shearing the entire signal queue formula is problematic, as found by Han (Citation1996). However, the methods described so far do not provide all the moments needed to determine queue size probability distributions, enabling the risk of long tailbacks, or spillback across upstream facilities, to be estimated. The rest of the paper, therefore, aims to obtain variance along with mean.
The M/D/1 process as an idealisation of the stochastic queue at a signal
The M/D/1 queue (M = Markovian, i.e. random, D = deterministic, i.e. uniform, 1 = one server) represents an idealised system where customers are served singly, but more than one random arrival can take place in each fixed average service time interval 1/µ. The effect of overflow from the red/green signal cycle is averaged out. In the M/M/1 process, by contrast, arrivals and service both occur randomly at given mean rates, which is more typical of a priority junction. Each process can be described by recurrence relations between queue state probabilities, which can be animated as Markov processes (Kendall Citation1951). Both yield closed-form equilibrium moments, including means in the P–K form EquationEquation (4), making them convenient for use in time-dependent traffic modelling.
Arrivals at exponentially distributed random intervals result in the number of arrivals in each service period being Poisson distributed. For M/D/1, the probability of i customers being in the queue after µt + 1 service periods (i.e. that amount of throughput capacity) is the sum of the probabilities of i + 1 being in the queue at service point µt and no arrivals in the interval [µt, µt +1), i at µt and one arrival, i − 1 at µt with two arrivals, and so on. Hence, the probabilities of queue states {pi} where i={0,1,2,…} evolve according to:
Extending the M/D/1 queue process to general green period capacities
In this paper, we use a common subscript notation for queue moments, where e indicates equilibrium, [G] is added to indicate the dependence on green period capacity and if omitted G = 1 is assumed, and a final letter, e.g. M, distinguishes a particular origin, for example, the initial of an author, while an overscore indicates an average value and notional negative queue state indices are placed in brackets.
The basic M/D/1 process describes a situation where only one customer can be served in each green period (like a ramp-metre with a fixed cycle time). A more realistic model should allow up to G customers to be serviced in each green period in which case the conditions for final queues of specified sizes are as given in .
Table 1. Conditions for specified final queue in green period with capacity G.
suggests that while the development of the queue size probability distribution {pi} for i > > 0 will be broadly similar to EquationEquation (6), the expression for p0 will be more complicated, involving several components. Cronjé (Citation1983b) introduces negative net contributions in each cycle, from −G to 0, representing actual arrivals minus green period capacity and sums these terms to give the value of p0 at the end of the cycle. This amounts effectively to employing notional negative queue states down to −G. By a similar analysis to that for M/D/1, recurrence relations corresponding to EquationEquations (6–Equation9) are obtained:
visualises the raw recurrence relations for G = 5, where notional states appear in the final state (leftmost) column as bracketed indices, and the real initial states on which they depend are shaded. The figures in interior cells are numbers of arrivals, which translate into Poisson coefficients of the initial probabilities (columns) as in EquationEquation (13).
Table 2. Representation of recurrence relations for G = 5 lower queue states.
The sum of terms in the column for an initial state k in is given by:
Earlier empirical approximations to the mean stochastic queue
Given the computational cost of simulation, Miller (Citation1969) proposed the following empirical approximation to the stochastic mean queue (with notation modified to be consistent with that used throughout this paper):
Link-function approach
The adjustment to Cronjé's method in EquationEquation (24) is unsatisfying because apart from its one change of gradient, it conveys the message that no practical smooth function can represent the errors in a way that gives insight into an underlying structure. Experimentation reveals that the trends of p0e[G], Le[G] and Ve[G] for various values of ρ and G can be made to overlap by transforming them using ‘link functions’ of the form of EquationEquations (25–Equation26).
plots link-transformed p0e[G] against z(2) for a range of values of ρ and G, showing how closely the points lie on a common parametric curve. For G = 1, p0e and ρ are already related by EquationEquation (10). Because those points are dispersed along the graph, extension to G > 1 is immediate by defining an ‘effective ρ′, η0:
Estimating equilibrium queue size probability distributions
Based on his simulation results, Olszewski (Citation1990) proposes Gamma or Negative Binomial distributions to represent the time-averaged queue size probability distribution over a peak. The Gamma distribution has been proposed elsewhere for describing queue size distributions during oversaturated peaks (Halcrow Fox and Associates, under contract to TRL, unpublished report). It has several advantages including having two parameters for fitting and the exponential distribution (continuous equivalent of geometric) as a special case. The extended equilibrium probability distributions of M/D/1[G], including the notional terms, have a Gamma-like appearance, and manual fitting demonstrates that a close fit can be obtained for higher values of G, as shown by . Poisson or LogNormal functions are unsatisfactory because they retain too much skewness, and their asymptotic behaviour is not exponential.
A simpler approach can be used for the real probabilities only by noting that, sufficiently far from the zero state, any equilibrium distribution is geometric, with a constant ratio between successive discrete state probabilities. This can be ascribed to a need for local invariance of the form of the distribution with change of viewpoint.
Certain equilibrium distributions in the literature have a nested form, involving two parameters instead of just ρ, where the geometric sequence applies only to queue sizes >0. However, three moments, p0, L and V are needed to estimate queue size probability distributions (Taylor Citation2005), and three parameters are required to fit three known moments. With three parameters as in EquationEquation (32), the distribution becomes doubly nested geometric, whose first and second moments are given by EquationEquation (33):
In principle, a fourth nesting level would allow p1 to be fitted precisely. However, unlike p0, which is related to the utilisation of service, p1 cannot be calculated by analytical approximations such as shearing. Apart from this, a fourth moment, as required for a fully specified problem, is unlikely to be available from analytical approximations. So there would seem to be little benefit from making the method more complicated.
The doubly nested geometric distribution is limited to unimodal cases with mode ≤1. However, being based on general principles, it can be applied to any equilibrium distribution where all three ‘effective ρs’ are less than 1, such as those arising from Erlang-k bunched or staged arrivals or service. It cannot be assumed without justification, as is sometimes done, that equilibrium results can be applied to transient behaviour (Sharma Citation1990). One of us (Taylor) has also been investigating ways of fitting functions representing instantaneous probability distributions to dynamic queue moments.
Discussion
No new work has been found relevant to the topic of the effect of green period capacity on signal queues since the derivation by Heidemann (Citation1994), possibly because the problem has been considered solved or of limited practical importance compared to the effects of optimisation, adaptive timing, platooning, coordination, etc. State-of-the-art reviews by Rouphail, Tarko, and Li (Citation1996) and Akçelik (Citation1998) quote Newell's approximation, and the empirically corrected HCM and Australian formulae developed in the 1980s, but do not propose any new methods, possibly because existing ones are considered sufficient.
While acknowledging this, the motivation for this paper lies in widening the range of queue types that can be handled by computationally efficient time-dependent methods like shearing, and in predicting variance and probability distributions along with means. That the green period effect emerges naturally from Heidemann's derivation indicates that it is more than just a convenient idealisation. Given that M/D/1 is taken to be a model of a stochastic signal queue, it would seem remiss to ignore the effect of something so essential.
Aside from computational efficiency, the need for simplifying approximations in queue calculation arises from the difficulty of describing even the simplest queue processes. Morse (Citation1958) gives an exact formula for the time development of probabilities of the simplest M/M/1 random queue as a potentially infinite series of exponential or Bessel functions. Even this only describes development from a precise initial size. In realistic calculations, convolution with an initial probability distribution is required. Kleinrock (Citation1975) calls this situation ‘disheartening. While common methods exist for analysing queuing, such as the P–K transform approach (e.g. Kleinrock Citation1975), recent research tends to be microscopic and complex (e.g. Mirchandani and Zou Citation2007).
A feature of queuing, as of nature generally, is that simple relationships may emerge from a complex process through general principles of conservation and symmetry. Equilibrium results like that in EquationEquation (4) are ‘emergent’ in the sense that exact formulae need not exist for the equilibrium mean of a general queuing process, since it is the limiting outcome of an infinite sequence of random events repeated infinitely many times. Yet all queue processes must obey deterministic conservation EquationEquation (3), which, therefore, cannot say anything about any result that depends on the details of the process.
An equilibrium queue is defined only for traffic intensities 0 ≤ ρ < 1 and is unbounded as ρ → 1. Thus it should be possible to normalise equilibrium moments by factoring by finite expressions in ρ and G since this maps an infinite range into an infinite range. A physical interpretation is that random arrivals in green periods of different duration should on average have a similar impact on the stochastic queue at the end of a period, provided that the relationship between green time and the characteristic stochastic time scale is the same. The link-function approach exploits this symmetry. But constant factors are not necessarily appropriate for time-dependent queues. Expressing results in terms of generic formulae (3) and (4) with modified parameters – in the present case ‘effective ρs’ – allows the use of existing computationally efficient time-dependent methods.
On what basis can it be claimed that ‘effective ρs’ can be substituted directly into the time-dependent methods? Physically, the longer the green period, the more traffic can ‘disappear without trace’ before the queue is assessed at the end of the green period. This translates into a reduction in the effective demand intensity and degree of saturation, which are the critical variables in time-dependent queuing. The quasi-static principle relies on the rate at which information propagates through a queue being much greater than the rate of change of the queue itself so that the static relationship between queue size and degree of saturation can be assumed to apply approximately to dynamic cases. As long as these assumptions hold, it should be possible to apply methods like shearing with some confidence. Some observational validation of shearing was done by Kimber and Daly (Citation1986). Validation of the extensions proposed here is part of a larger question concerning time-dependent methods, which involves considering dynamic probability distributions or at least their moments, currently being addressed by one of us (e.g. Taylor Citation2005).
The primary impact of the work described here is, therefore, greater consistency. The extent to which approximate time-dependent methods can accommodate realistic factors such as platooning, coordination and finite capacity queues has yet to be determined, though pursuance of research may depend on whether macroscopic modelling is considered likely to have a role as against microscopic simulation, an issue which is still disputed (Wood Citation2012). An ad hoc method of accounting for green waves was used in CONTRAM (Taylor Citation2003), but manipulation of parameters in an extended P–K mean formula representing arrival and service statistics would be preferable. On the other hand, a purely statistical model like the P–K formula may be inappropriate to cases where variability of demand is no longer simply random (Chow Citation2013). Whether efficient time-dependent methods can continue to absorb real-life complexities through the implementation of general principles may be a question for further research.
Conclusion
This paper responds to a perceived need to: (1) broaden the range of queue processes that can be modelled using computationally efficient time-dependent methods based on closed formulae; (2) incorporate variance and in particular (3) take account of the observation that the size of a stochastic signal queue depends on the green period capacity and not just the ratio of green to cycle time through the demand intensity.
An idealised stochastic signal queue process that takes account of green period capacity has been formulated by extending the basic M/D/1 model embodied in some existing signal queue formulae. Simulation using Markov methods has been used to generate test cases to compare with existing empirical approximations and to verify novel formulae for equilibrium values of the probability of zero queue, mean queue and variance in a form compatible with computationally efficient macroscopic time-dependent methods.
It is thought on structural grounds that the realism of transient behaviour using time-dependent methods should be similar to that for the basic process. Three moments enable probability distributions to be estimated and a simple doubly nested geometric approximation has been defined and demonstrated.
Acknowledgements
The work described in this paper forms part of the first author's research towards Ph.D. under the supervision of the second author. An early version of the paper was presented at the Universities Transport Studies Group (UTSG) Conference at Oxford, January 2013. Helpful comments by the editors and two anonymous reviewers and the general support of Dr Alan Stevens Transportation Chief Scientist at TRL are gratefully acknowledged.
Notes
1. Strictly, capacity in vehicles should vary with traffic composition.
2. G as used here corresponds to Olszewski's B.
3. We were unable to obtain permission to reproduce this, but some points taken from it are shown in later.
4. Some authors make C include the dispersion of arrivals also, but this does not emerge from the derivation.
5. The Markov simulation program used, which evaluates recurrence relations using small time steps, was developed by the first author with algorithm design and programming assistance by Neil H Spencer, then a sandwich student at TRL.
References
- Akçelik, R. 1998. Traffic Signals: Capacity and Timing Analysis. Report ARR 123. Vermont South: Australian Road Research Board. [Most recent edition of review first published 1981].
- Allsop, R. E., and T. P. Hutchinson. 1972. “Delay at Fixed-Time Traffic Signals [Parts I and II Respectively].” Transportation Science 6 (3): 260–305. doi:10.1287/trsc.6.3.260.
- Burrow, I. J. 1987. OSCADY: A Computer Program to Model Capacities, Queue and Delays at Isolated Traffic Signal Junctions. TRL Report RR 105. Crowthorne House: Transport Research Laboratory.
- Chow, J. Y. J. 2013. “On Observable Chaotic Maps for Queueing Analysis.” In Proceedings of 92nd TRB Annual Meeting, January 2013, January 13–17. Washington, DC: Transportation Research Board.
- Cronjé, W. B. 1983a. “Analysis of Existing Formulas for Delay, Overflow and Stops.” Transportation Research Record 905: 89–93. Washington, DC: Transportation Research Board.
- Cronjé, W. B. 1983b. “Optimization Model for Isolated Signalized Traffic Intersections.” Transportation Research Record 905, 80–82. Washington, DC: Transportation Research Board.
- Han, B. 1996. “A New Comprehensive Sheared Delay Formula for Traffic Signal Optimisation.” Transportation Research A 30 (2): 155–171.
- Heidemann, D. 1994. “Queue Length and Delay Distributions at Traffic Signals.” Transportation Research 24B (5): 377–389.
- Kendall, D. G. 1951. “Some Problems in the Theory of Queues.” Journal of Royal Statistical Society B (Methodological) 13(2): 151–183.
- Kimber, R. M., and P. Daly. 1986. “Time-Dependent Queuing at Road Junctions: Observation and Prediction.” Transportation Research 20B (3): 187–203.
- Kimber, R. M., and E. M. Hollis. 1979. Traffic Queues and Delays at Road Junctions. TRL Report LR 909. Crowthorne House: Transport Research Laboratory.
- Kleinrock, L. 1975. Queueing Systems: Vol. 1 Theory. New York: Wiley Interscience.
- Meissl, P. 1963. “Zufallsmodell einer Lichtsignalanlage mit mehrspurigem Stauraum [A Random Model of a Traffic Signal with Multilane Storage].” Mathematik-Technik-Wirtschaft 63 (1): 1 4 and 63 (2): 63–68.
- Miller, A. J. 1969. Some Operating Characteristics of Fixed-Time Signals with Random Arrivals. Sydney: Institution of Highways and Traffic Research, University of New South Wales.
- Mirchandani, P. B., and N. Zou. 2007. “Queuing Models for Analysis of Adaptive Signal Control.” IEEE Transactions on Intelligent Transportation Systems 8 (1): 50–59. doi:10.1109/TITS.2006.888619.
- Morse, P. M. 1958. Queues Inventories and Maintenance. New York: John Wiley.
- Newell, G. F. 1960. “Queues for a Fixed-Cycle Traffic Light.” Annals of Mathematical Statistics 31: 589–597. doi:10.1214/aoms/1177705787.
- Newell, G. F. 1965. “Approximation Methods for Queues with Application to the Fixed-Cycle Traffic Light.” SIAM Review 7: 223–240. doi:10.1137/1007038.
- Olszewski, P. S. 1990. “Modelling of Queue Probability Distribution at Traffic Signals.” In Proceedings of the International Symposium of Traffic and Transportation Theory, edited by M. Koshi, 569–588. New York: Elsevier.
- Rouphail, N., A. Tarko, and J. Li. 1996. “Traffic Flow at Signalized Intersections.” In Chapter 9 of Traffic Flow Monograph. Washington, DC: Transportation Research Board, pp. 9-1–9-32. http://www.fhwa.dot.gov/publications/research/operations/tft/chap9.pdf
- Sharma, O. P. 1990. Markovian Queues. Chichester: Ellis Horwood.
- Taylor, N. B. 2003. “The CONTRAM Dynamic Traffic Assignment Model.” Networks and Spatial Economics Journal – Special Issue on Dynamic Traffic Assignment 3: 297–322. doi:10.1023/A:1025394201651.
- Taylor, N. B. 2005. “Variance and Accuracy of the Sheared Queue Model.” In Proceedings of IMA Mathematics in Transport Conference, edited by B. G. Heydecker, 259–278. Amsterdam: University College London, September 7–9.
- Webster, F. V, and B. M. Cobbe. 1966. “Traffic Signals.” Road Research Technical Paper 56. London: HMSO.
- Wood, S. 2012. “Traffic Microsimulation – Dispelling the Myths.” Traffic Engineering and Control 53 (9): 339–344.