Traffic signal control and route choice: distributed control strategies which are sometimes inconsistent with users route choices

Abstract

FOR hEART2014

Traffic signal control and route choice: distributed control strategies which are sometimes inconsistent with users route choices

Mike Smith (152mikesmith@gmail.com) and Eddie Wilson University of York, UK, University of Bristol, UK.

Abstract: The paper considers the interaction between traffic control policies and route choice.

The main purpose of this paper and previous work

This paper is designed to illuminate the interaction between various signal control policies and travellers’ route choice decisions. A long term objective of the paper is to help identify and / or design distributed urban traffic control systems which make the best of limited urban network capacity while taking reasonable account of route choices and being reasonably “fair”.

The paper considers models of traffic signal control and route choice which explicitly involve queues, flows and signal green-times when there are responsive signal timing systems in place and travelers may change route.

Our main objective is to display some characteristics of certain distributed control systems when these interact with routeing decisions under a variety of assumptions. The distributed control systems include the distributed backpressure control systems designed by Varaiya (2013) and Le et al (2013), and the non-backpressure control system designed by Smith (1979, 1987).

The following particular results will be proved: 1. While the Varaiya control is queue-stabilising (see Varaiya (2013)) the routes determined by the Varaiya backpressure algorithm are typically not user-equilibrated; and, further, the control is not queue-stabilising when route choices are allowed for. 2. While the Le et al control is queue-stabilising (see Le et al (2013)) the routes determined by the Le et al backpressure control are not typically user equilibria; and, further, the control is not queue-stabilising when route choices are allowed for. 3. P0 control is queue stabilizing when the routes are in user equilibrium; and, further, the control is queue-stabilising when route choices are allowed for.

The above results will be shown to hold within a quasi-dynamic vertical queueing environment. (This is a dynamic environment in which the inflows

are stationary deterministic or stationary stochastic processes and queue evolution is realistic (see Thompson and Payne (1975), Bliemer et al (2012) and Nesterov and de Palma (2003)); but vehicles are very short.) The paper will extend both the negative and positive results 1-3 above to embrace (a) a peak period where the inputs are not stationary; (b) different signal control models and strategies; and (c) spatial queueing and blocking back as opposed to vertical queueing. These extensions in certain cases are quite simple but in other cases are quite complicated.

Specifically, in relation to (b) above, (i) the back-pressure idea allows a whole family of models depending on what (monotone increasing) function is used to map queue length to stage pressure; (ii) there is some subtlety and various choices in how a macroscopic fluid-like control is mapped onto discrete (in time) decisions of when the stage should be changed; and (iii) in this vein there are several different modelling choices for how within-cycle queuing dynamics should be locally time-averaged. We will explore these issues in the paper.

Schlaich and Haupt (2012) have implemented a dynamical (route-choice)- (green-time) system within VISUM software with the equisaturation policy. See Taale and van Zuylen (2001) for a review of the assignment and control problem. See also Yang and Yagar (1996).

Summary of the paper

The hEART paper will have three sections.

Section 1. STATICS.

This section will consider the three controls above from a steady state equilibrium viewpoint. This will assume that travellers are accurately routed along their cheapest routes and the three policies are precisely satisfied. So here we are concerned with consistency: are the control policies consistent with user equilibrium? It will be shown that neither the Varaiya nor the Le et al policies are certainly consistent with user equilibrium. This will be done by giving a feasible [network + demand] with no (flow, green-time) pair where the green-time satisfies the control policy and the flow is a user-equilibrium.

Finally, it will be shown - initially by considering a simple network with one OD pair and 2 alternative branches (similar to that depicted in figure 1 below) - that route choice combined with backpressure control strategies can lead to multiple user equilibrium solutions that coexist at the same input parameter values. These solutions include (flow, green time) patterns that represent an extremely inefficient use of the infrastructure. Moreover, without a more detailed dynamic analysis (see section 2), it is impossible to say a priori which

of the equilibria would be selected in practice, so the performance of such networks can be considered to be highly unpredictable.

We also provide the results of some initial numerical studies for more complicated networks - specifically, random planar graphs - which show that such coexistence effects are widespread and not just a feature of pathologically simple examples. In fact, broadly speaking, as networks grow in size, the number and structure of such coexisting equilibria can become bewilderingly complex.

Section 2. DYNAMICS.

This section will consider disequilibria. Dynamical systems, involving routeswapping, queues which grow and shrink, and green-time swapping, will be considered and their stability properties analysed for each of the three policies. In the detailed model described in section 2, route switches will follow a development of the proportional switch re-routeing method (PAP) of Smith (1984c) to imitate how travellers change routes. The whole dynamical system will not be entirely realistic as flows may exceed capacity within these systems; so the dynamics here must take place within a computer model. It will be shown that with P0 the dynamical system must be stable under certain natural conditions and that the Varaiya and the Le et al policies may or may not be stable under those conditions.

The dynamical structures which arise imply differing types of stability for some of the equilibrium (flow, green time) patterns found in Section 1. This means that the tools of bifurcation theory can be used to begin to understand how coexisting equilibria arise as parameters are swept. Specifically, in a symmetric 2 branch network, the backpressure policies can cause the desirable symmetric distribution of flow to lose stability via a subcritical pitchfork bifurcation. Dynamically, there is sometimes a region of bistability where the unstable bifurcating "branch" of solutions acts as a separatrix that divides those solutions converging to the symmetric state from those solutions converging to a large amplitude symmetry-broken alternative. The fate of dynamical trajectories in such regimes thus depends very heavily on the initial data.

Numerical bifurcation theory provides a set of tools for tracing out solution branches which in larger networks can undergo further secondary bifurcations. Tracing out branches in the graph (parameter, solution) space turns out to be the most efficient way of finding the very many competing equilibria in larger networks and we will provide some worked-through examples.

Section 3. NEAR REALISTIC AND REALISTIC DYNAMICS.

This section will show that the dynamics in section 2 may be distorted by letting a parameter tend to infinity; the dynamical system in section 3 then becomes arbitrarily close to realistic dynamics where link exit capacities are not exceeded. It will be shown that the Section 2 stability/instability results hold here too. In this section *** we hope to show *** that “in the limit” the realistic dynamics will again possess the same stability results. In any case the instability results involving the Varaiya and Le et al policies do hold in “the realistic limit”.

In this abstract we give some mathematical detail for section 1 alone.

SECTION 1. SOME DETAIL.

Here we show that the Varaiya policy is sometimes not compatible with user equilibrium. (In Varaiya (2013) route choices are not necessarily user equilibria under the max-pressure control.) We will use the simple example network in Figure 1.

Link 4 SIGNAL

ORIGIN Stage 2 2 1 0 Link 5 DESTINATION Stage 1

Links 1-3

Figure 1. A four route signal controlled network; links 1, 2 and 3 have saturation flow 1 v/sec; link 4 has saturation flow3 v/sec. Stage 1 contains links 1, 2 and 3; stage 2 contains link 4.

Consider the network in figure 1 in a steady (quasi-dynamic) state with queueing delays. Let si = the saturation flow at the link i exit (in v/sec); C = the freeflow cost/time of travel via routes 1, 2, 3 and 4 (seconds; constant); bi = the bottleneck delay at the link i exit (secs, for I – 1, 2, 3, 4); gi = the green-time at the link i exit (secs); Xi = the flow on route i (v/sec); G1 = the proportion of time that stage 1 is green; and G2 = the proportion of time that stage 2 is green. Further, assume that there is a green-time constraint. This is: G1 / G2 ≤ 4/3.

Initially we suppose vertical queueing; so that the cost of traversing route i is C + bi. This will be relaxed. Assume also that queue volumes, experienced delays and green-times are related by: b1=Qi/gisi where gi is the green-time proportion felt by link i. This equals either G1 or G2.

Since the free-flow travel times along the four routes are equal (to C secs), at a user- equilibrium all bottleneck delays will be equal.

Suppose now that there are queues on the network, that the network is in a user-equilibrium state and that the green times given to stages 1 and 2 are according to Varaiya (2013). Assume that link 5 has a very high capacity and that we think of there being zero queue on link 5 so that the backpressure is zero. (We could regard any queue on link 5 as being already at the destination.)

Then as we are at a user equilibrium all four bottleneck delays bi = Qi /sigi are equal and so: Q1 /s1g1 = Q2 /s2 g2 = Q3 /s3 g3 = Q4 /s4 g4 . Then, using the given saturation flows, Q1 / G1 = Q2 / G1 = Q3 / G1 = Q4 / 2G2. So Q1=Q2=Q3 =(Q4 /2)(G1 / G2) < (Q4 /2)(4/3)=(1/3)(2Q4) by the green-time constraint. Adding the three inequalities: Q1 + Q2 + Q3 < 2Q4 or: s1Q1 + s2Q2 + s3Q3 < s4Q4

Thus at any equilibrium stage 2 pressure = s4Q4 > s1Q1 + s2Q2 + s3Q3 = stage 1 pressure; so all green goes to stage 2; and that remains as such swaps will keep the above inequality.

The capacity of this network at equilibrium can therefore not exceed 2 v/sec at a user equilibrium when the Varaiya backpressure control is utilised. If the demand is greater than this then user equilibrium and the control policy cannot co-exist (with positive queues). A similar argument in the paper will show the same thing for the Le et al backpressure control.

References.

Aboudolas, K., Papageorgiou, M., Kosmatopoulas, E. B. 2009. Store-andforward based methods for the signal control problem in large scale urban road networks. Transportation Research Part C, 17 (2), 163 – 174. Bliemer, M. C. J., Brederode, L., Wismans, L., Smits, E. 2012. Quasi-dynamic network loading: adding queuing and spillback to static traffic assignment,