Optimal signal timing signalized intersection by global optimization (OPT-I)

OPT-i An International Conference on Engineering and Applied Sciences Optimization M. Papadrakakis, M.G. Karlaftis, N.D. Lagaros (eds.) Kos Island, Greece, 4-6, June 2014 OPTIMAL SIGNAL TIMING SIGNALIZED INTERSECTION BY GLOBAL OPTIMIZATION (OPT-I) Maria Lurdes Sim˜ oes1, and Isabel M. Ribeiro2 1CEC, Faculty of Engineering of University of Porto Rua Dr. Roberto Frias s/n, 4200-465 Porto, Portugal e-mail: lurdes.simoe[email protected].pt 2CEC, Faculty of Engineering of University of Porto Rua Dr. Roberto Frias s/n, 4200-465 Porto, Portugal e-mail: iri[email protected].pt Keywords: Traffic Management, Pre-timed Control, Actuated Control, Stochastic data, Global Optimization. Abstract. Accurate measurements of signal control parameters at signalized intersections are very important for designing and operating traffic control systems. In this work, a queuing system has been modelled as a result from the characterization of the vehicles behaviour approaching and passing of a signalized intersection. This intersection is part of a network of urban traffic and two problems are formulated, distinguished by the type of control used: pretimed, semi-actuated or fully-actuated. Subsequently global optimization and complementarity can be used to determine the parameters of the control signal. This formulation includes the green times and cycle lengths that minimize the total waiting time of vehicles at the intersection. At intersections regulated by actuated control, this methodology allows us to estimate the effective green time in actuated streams as well as the length of each cycle. It should be noted that the duration of departure of vehicles when signal is green or yellow is constant. The vehicles arrivals are random, following a Poisson probability distribution. The models in question were formulated as linear programs with linear complementarity constraints (LPLCC). In the present study, the Sequential Linear Complementarity Algorithm (SLCP) was also analysed to calculate the global minimum for the LPLCC. Furthermore, several scenarios of traffic intersections are created to demonstrate the method’s efficiency, particularly to verify the accuracy of the solutions of the problems. Maria Lurdes Sim˜oes and Isabel M. Ribeiro 1 INTRODUCTION Solving the problem of severe traffic congestion has become a top priority in many cities. Since 1950, traffic engineers and researchers have used Webster’s formulation in order to determine the optimal cycle length and green split allocation at isolated intersections, regulated by traffic signals with a pre-timed control. However, this formulation has been proven to be ineffective under saturated conditions, and is thus inappropriate for the particular case of actuated control. Despite the acknowledgement of these limitations, an analytical solution capable of determining the optimal signal timing in the case of actuated control has yet to be found. Thus traffic engineers continue to rely on computer simulation to generate signal timing plans [11]. It is common knowledge that vehicles only leave the intersection during the green period and that the signal phases in actuated control are not of a fixed length. Nevertheless, this does not foster the application of the queuing theory which is restricted to traffic conditions of a simpler nature. Thus, in this work, a methodology for determining and carrying out timing decisions is presented. Timing plan parameters, including both the cycle’s length and the green times, have been optimized based on minimizing the total waiting time at the intersection in question. As such, a signalized intersection regulated by a pre-timed, semi-actuated or fully-actuated control with two phases has been analysed and adopted. The main performance measures of the signalized intersections under consideration in the selection of a phasing plan are the queue length in addition to the delay drivers are subject to. The formulation proposed by Webster to determine the optimal cycle length generates an unreasonably long cycle as the critical intersection flow ratio nears saturated conditions. Additionally, it is inappropriate whenever the intersection’s critical flow ratio is subject to saturated conditions. The critical intersection flow ratio is the sum of the flow ratio for critical movements which are characterized by the fact that the ratio of the arrival flow to the saturation flow is the highest in the intersection. The optimal cycle length formulation proposed by [12] can be expressed as follows: Co=5 + 1.5L 1−Piyci ,25 ≤Co≤120 (1) where L is the total lost time (s) and Piycirepresents the intersection critical flow ratio (veh/s). Lan [3, 4] provides us with a novel formulation for determining the optimal cycle length in pre-timed control under saturation conditions, in which a nonlinear regression analysis of the functional relationship is established between the optimal cycle lengths and the traffic flow parameters, including the intersection critical flow rates, the total lost time and the duration of the analysis period. This formulation can be expressed as: Co=a+bL +cln(T) 1 + dexp(ePiyci),25 ≤Co≤120 (2) where T(in hours) represents the duration of the analysis period and a,b,c,dand eare the model parameters. Both of the above mentioned methods begin by stating the cycle length and then move on to calculating the optimal green split allocation. It should be noted that in the case of the latter, the timing plan parameters, including both the cycle length and the green times, have been optimized based on the delay minimization criterion. Furthermore, it should be noted that the available literature offers very few methods for estimating delays, dealing instead exclusively with semi-actuated signals. Maria Lurdes Sim˜oes and Isabel M. Ribeiro Traffic signals operating with semi-actuated control have been widely used on secondary streets, since they provide flexible controls adjustable to traffic volumes, thereby reducing the vehicle’s delay. The actuated control is thus a strategy of response to important variations in the traffic conditions. The main problem to be found when using semi-actuated control is the difficulty in selecting an optimal combination of the maximum, minimum and unit extension of green time. On the other hand, the queuing theory is an alternative tool which is widely used to compute performance measures for traffic signals, in the case of customers (vehicles) arriving at a service point (intersection regulated by traffic control signals). Akelik and Lin [1, 5] have proposed analytical methods for estimating green times and cycle lengths for actuated signals. According to the available literature, semi-actuated signal operations are currently being used separately or as part of a system of coordinated traffic signals. The study of the influence of the characteristics of the arrivals and departures of traffic in the optimal performance of signalized intersections, which have this type of control, commenced shortly after the concept of actuated control was first used [1]. The need to optimize the parameters of the controller and the position of the detector, as well as to investigate the relationship between these factors has resulted in a number of studies [6, 9]. Schutter [10] have developed an algorithm to solve an Extended Linear Complementarity Problem, having subsequently applied it in order to determine the optimal timing plan in traffic control. However, the algorithm in question seems incapable of solving problems of this nature for a reasonable number of switching instants (it only appears to be effective in the case of a maximum of seven instants). Therefore, a queuing system resulting from a signalized intersection control in an urban traffic network is considered by this paper. In addition, a model that describes the evolution of the queue lengths as a function of time is introduced. The input data for the model in question are the arrival and departure rates of the vehicles to be found at the intersection. The departure rate of vehicles during green and yellow times have been found to be constant. As for the arrivals of vehicles a Poisson probability distribution has been considered. In the case of traffic control by vehicles, the green time associated with an actuated stream, is directly influenced by the time intervals between the consecutive detections of vehicles, and is limited by a maximum and minimum value. Therefore the estimation of arrival headways is fundamental to determining actuated signal timings. The model in question has been formulated as the following Linear Program with Linear Complementarity Constraints (LPLCC) (LPLCC)Minimize cTz+dTy subject to Ew =q+Mz +Ny z≥0, w ≥0 y∈Ky zTw= 0 (3) where q∈Rp,c,z∈Rn,d,y∈Rm,M,E∈Rp×n,N∈Rp×mand Ky={y∈Rm:Cy =b, y ≥0} with C∈Rl×mand b∈Rl. The manner in which Global Optimization and Complementarity can be used to attain the optimal control parameters for an isolated signalized intersection is hereby determined. Subsequently, a Sequential Linear Complementarity (SLCP) algorithm is used to calculate a global Maria Lurdes Sim˜oes and Isabel M. Ribeiro minimum for a linear LPLCC. This algorithm determines a sequence of stationary points of the LPLCC with strictly decreasing values. The final stationary point of this sequence has been proven to represent the global minimum of the LPLCC. In general, the results present in the available literature demonstrate that the SLCP algorithm is rather efficient in determining a global optimum. However, the situation is significantly more complex when it comes to establishing the achievement of this global minimum. However, since each stationary point in the sequence corresponds to a feasible solution for a given problem, the engineer is thus able to have access to a number of possible solutions (equal to the number of iterations of the algorithm SLCP) over a reasonable period of time. Under the scope of this study, we have investigated the nature of the performance of this algorithm when subjected to a number of traffic problems. The numerical results of various experiments that have been carried out reveal that it is possible, even in the specific instance of a long period of time instants, to efficiently determine the optimal control parameters for an isolated intersection. While, in the case of pre-timed control, the SLCP algorithm always finds the optimal solution in the first stationary point of sequence, when it comes to semi-actuated or fully-actuated controls, the SLCP determines various stationary points until the optimal solution is obtained. In all cases, the computational time required by the SLCP is very reduced and the attained solution corresponds to the minimum total delay of the intersection even when subjected to saturation conditions. The remainder of this chapter is organized as follows. In Section 2, the types of traffic signal control are presented. The model is then introduced in Section 3, whilst Section 4 addresses the formulations of the underlying problems. A report of the computational experiments and some conclusions are presented in the last section of this paper. 2 TRAFFIC CONTROL As far as the regulation of traffic signals is concerned, three types are considered by this paper: pre-timed, semi-actuated and fully-actuated signal operation. In the case of pre-timed traffic control, each signal phase or traffic movement is serviced in a programmed sequence that is repeated throughout the day. Main street traffic receives a fixed amount of green time followed by the yellow and red clearance intervals. The same interval timing is then repeated for the minor or side street. The amount of time it takes to service all conflicting traffic movements is referred to as the cycle length. The signal timings and cycle lengths may vary according to the time of day in order to reflect changes in traffic volumes and patterns. During peak traffic periods for example, cycle lengths may range up to 90 seconds to accommodate heavier volumes. During off-peak periods of the day, cycle lengths are more reduced as traffic volumes are much lighter, and therefore, not as much green time is required to effectively service all the movements. In the case of pre-timed signals, the pedestrian signal indications are automatically displayed in conjunction with the green signal for vehicles. Pre-timed signals can provide fairly efficient operation during peak traffic periods, assuming the signal timing settings reflect current conditions. However, during off-peak times, particularly at night, traffic on the main streets is often stopped for no particular reason due to little or no traffic, or pedestrians on the cross streets. In the case of pre-timed signals the only means of avoiding this unnecessary delay has been to program the signals to a flashing operation mode during the night period. Night flash operation was once common practice in many cities and municipalities. However, with advances in signal technology and detection devices, it has rarely been used over the last few years. Actuated signal control differs from pre-timed control in that it requires actuation by a ve- Maria Lurdes Sim˜oes and Isabel M. Ribeiro hicle or pedestrian in order for certain phases or traffic movements to be serviced. Actuation is achieved due to vehicle detection devices and pedestrian push buttons. The most common method of detecting vehicles is to install inductive loop wires in the pavement located at or near the stop line. Video detection is also used at select locations. Actuated signals are of two types: namely, semi-actuated and fully-actuated. Semi-actuated control is a traffic management resource deployed essentially at intersections where a main street intersects a secondary street. As such, a detector is installed along the secondary street. The main street is always allocated the green signal for at least a fixed minimum green time of 7−10 seconds during a signal cycle. If the detector is activated during this interval the main street remains on green mode until the minimum green time is reached. The green signal is then passed on to the secondary street until the traffic has been cleared or until the green time reaches a fixed maximum (whichever occurs first) upon which point, the green signal is transferred back to the main street. If no vehicle is detected along the minor approach, the period of green in the main street is prolonged until a vehicle is detected by the sensor located in the secondary street. This procedure is illustrated in Figure 1. Figure 1: Extension sequence in vehicle-actuated control. An actuated signal is assumed to be extremely efficient in the management of the available green time. The efficient use of actuated control requires careful selection of the phasing plan, timing design and detector configuration. In the case of semi-actuated control [6] the regulation of traffic signals is permanently adapted to the traffic demands, in real time in the intersection, in order to guarantee the highest possible level of efficiency. In the case of fully-actuated control, detector loops and pedestrian push buttons are installed at all approaches. All signal phases, including left turn arrows have preset minimum and maximum greens and will be serviced on demand only. Fully-actuated signals are most efficient in isolated locations where coordination with adjacent signals is not a concern, and where the intersecting streets have similar traffic volumes. Actuated signal control provides greater efficiency in comparison to pre-timed signals by servicing cross street traffic and pedestrians only when required. The primary disadvantage of pre-timed signals is avoided as main street traffic is not interrupted unnecessarily. This is particularly beneficial during off-peak hours. The result is fewer stops and delays to the traffic on the main streets, whilst simultaneously guaranteeing safe pedestrian crossings upon demand, which ultimately leads to a decrease in fuel consumption and pollution. Maria Lurdes Sim˜oes and Isabel M. Ribeiro 3 MODEL DESCRIPTION In this study, three models are presented. The first one is associated with a signalized intersection regulated by pre-timed control in which the randomness of the vehicle arrivals has been taken into account. The formulation of this problem is presented in [7], however the vehicle arrivals were considered deterministic. The second and third are associated with a signalized intersection regulated by semi-actuated [8] and fully-actuated control, respectively. In this section, an intersection with four traffic streams, S1,S2,S3and S4has been considered, without loss of generality. Each of the traffic streams is controlled by a traffic signal, T1, T2,T3and T4, respectively (see Figure 2). Figure 2: Sketch of a signalized intersection with four traffic streams. The intersection presented in Figure 2 is controlled by two phases (A and B). During Phase A, the traffic signals T1and T3have a green light and the same occurs in Phase B for T2and T4. In both phases, the cycle has three states: green, yellow and red. The arrival rate of vehicles in traffic stream Siat the particular time instant tis λi(t)for i= 1,2,3,4. When the traffic signal Tiis green, the departure rate in traffic stream Siat the time instant tis µi(t)and in the case of the traffic signal being yellow, the departure rate in traffic stream Siat time tis κi(t)for i= 1,2,3,4. The design of the timing plan is illustrated in Figure 3. Let t0, t1, t2, ... represent the time instants when a change in the traffic signals occurs. Figure 3: Diagram of signal timing. It has been assumed that the duration of the yellow time and the clearance time are fixed and have been set equal to the dYand dCvalues, respectively. The time instants when the traffic signals T1and T3initiate a green period and T2and T4 begin a red period are t0, t2, t4, .... The time instants when the traffic signals T1and T3initiate a red period and T2and T4begin a green period are t1, t3, t5, .... Maria Lurdes Sim˜oes and Isabel M. Ribeiro Consequently, one is lead to t2k+1 −t2k=yG+dY+dCand t2k+2 −t2k+1 =yR+dY+dC, k∈N0. Therefore, yGrepresents the green time and yRrepresents the red time in traffic signals T1and T3. A cycle length is equal to yG+yR+ 2(dY+dC). Clearly, one should then have yR, yG≥dY≥0. Furthermore, λi(t), µi(t), κi(t)≥0,∀i, t and tk< tk+1,∀k. The queue length in the traffic stream Siat instant time t,Li(t), is thus clearly equal to or greater than zero for all iand t. Whenever the traffic signal Tiis red, arrivals at traffic stream Siare verified, which are characterized by the arrival rate function λi(t). It should also be noted that there are no departures in this case. Alternatively, when the traffic signal Tiis green or yellow, both arrivals and departures occur at traffic stream Si. In these cases, the net queue growth rate at the time instant tis λi(t)−µi(t)or λi(t)−κi(t), respectively. Accordingly, for streams S1and S3, the evolution of the queue length is obtained by dLi(t) dt =           λi(t)−µi(t), t ∈[t2k, t2k+1 −dY−dC] λi(t)−κi(t), t ∈[t2k+1 −dY−dC, t2k+1 −dC] λi(t), t ∈[t2k+1 −dC, t2k+2] (4) for i= 1,3and k∈N0. Similarly, for traffic signals T2and T4, the evolution of the queue lengths in traffic streams S2and S4are obtained by dLi(t) dt =           λi(t), t ∈[t2k, t2k+1]∪[t2k+2 −dC, t2k+2] λi(t)−µi(t), t ∈[t2k+1, t2k+2 −dY−dC] λi(t)−κi(t), t ∈[t2k+2 −dY−dC, t2k+2 −dC] (5) for i= 2,4and k∈N0. The relation of the queue length between the time instants t2kand t2k+2 may be represented by the following equations: Li(t2k+2)=Li(t2k+1) + Zt2k+2 t2k+1 λi(t)dt Li(t2k+1)=Li(t2k) + Zt2k+1−dY−dC t2k (λi(t)−µi(t))dt+ +Zt2k+1−dC t2k+1−dY−dC (λi(t)−κi(t))dt +Zt2k+1 t2k+1−dC λi(t)dt for i= 1,3and k∈N0. The equations describing the relationship of the queue length at traffic streams S2and S4are obtained in a similar manner. Let us assume that, for each i∈ {1,2,3,4},¯µiand ¯κirepresent the average departure rates when the traffic signal is green or yellow, respectively. Let one further assume that µi(t) = ¯µi and κi(t) = ¯κifor all time instants tin addition to the fact that queue is not empty. In the latter case the departure rates are equal to zero. Therefore departures are considered to be deterministic. As for the arrivals distribution, a model that represents a random arrival process has been considered. The Poisson distribution has been found to be the random process which better Maria Lurdes Sim˜oes and Isabel M. Ribeiro suits the particular situation in question. It is a discrete distribution and is commonly referred to as a counting distribution, representing the count distribution of random events. The assumption of the arrival of random vehicles also implies a random distribution of the time intervals between the arrivals of the successive vehicles. The Poisson distribution can describe the probability of observing narrivals in a period from 0to twith the aid of the following expression: pn(t) = ¯ λtn n!e−¯ λt where ¯ λis the average arrival rate in vehicles per unit of time and tis the duration of the time interval over which vehicles are counted. This equation provides information as to how probability is distributed over a time interval in terms of the total number of vehicles. In a sequence of narrivals one can observe vehicles passing with a random headway distance. Due to the fact that, in the case of these approaches, the arrival and the departure rates are nonnegative values and ¯κi≤¯µi, the queue lengths will never be negative values if equations (4)-(3) are considered. Therefore, it is clear that this non-negativity condition must be included in the equations describing the evolution of queue lengths. Thus, Li(t2k+2)=max {Li(t2k+1) + λi(t2k+2) (yR+dY+dC),0} Li(t2k+1 −dY−dC)=max {Li(t2k) + (λi(t2k+1)−¯µi)yG,0} Li(t2k+1 −dC)=max {Li(t2k) + (λi(t2k+1)−¯µi)yG+ +(λi(t2k+1)−¯κi)dY,(λi(t2k+1)−¯κi)dY,0} Li(t2k+1)=max {Li(t2k) + (λi(t2k+1)−¯µi)yG+ (λi(t2k+1)−¯κi)dY +λi(t2k+1)dC,(λi(t2k+1)−¯κi)dY +λi(t2k+1)dC, λi(t2k+1)dC} for i= 1,3and k∈N0. It should be noted that according to a deterministic approach λi(tk) = ¯ λifor all k∈N0and for traffic streams S2and S4the equations can be obtained in a similar manner. 4 PROBLEMS FORMULATION If the following vectors are considered xk=[L1(tk), L2(tk), L3(tk), L4(tk)]T b1k+1 =[λ1(t2k+1)−¯µ1, λ2(t2k+1), λ3(t2k+1)−¯µ3, λ4(t2k+1)]T b2k+1 =[λ1(t2k+2), λ2(t2k+2)−¯µ2, λ3(t2k+2), λ4(t2k+2)−¯µ4]T b3k+1 =[(λ1(t2k+1)−¯κ1)dY+λ1(t2k+1)dC, λ2(t2k+1)(dY+dC), (λ3(t2k+1)−¯κ3)dY+λ3(t2k+1)dC, λ4(t2k+1)(dY+dC)]T b4k+1 =[λ1(t2k+2)(dY+dC),(λ2(t2k+2)−¯κ2)dY+λ2(t2k+2)dC, λ3(t2k+2)(dY+dC),(λ4(t2k+2)−¯κ4)dY+λ4(t2k+2)dC]T b5k+1 =[max {(λ1(t2k+1)−¯κ1)dY+λ1(t2k+1)dC, λ1(t2k+1)dC},0, max {(λ3(t2k+1)−¯κ3)dY+λ3(t2k+1)dC, λ3(t2k+1)dC},0]T b6k+1 =[0,max {(λ2(t2k+2)−¯κ2)dY+λ2(t2k+2)dC, λ2(t2k+2)dC},0, max {(λ4(t2k+2)−¯κ4)dY+λ4(t2k+2)dC, λ4(t2k+2)dC}]T then x2k+1 = max x2k+b1k+1 yG+b3k+1 , b5k+1  x2k+2 = max x2k+1 +b2k+1 yR+b4k+1 , b6k+1  Maria Lurdes Sim˜oes and Isabel M. Ribeiro for k∈N0. In this study, non-saturated intersections have been taken in consideration, which implies that the queue lengths may disappear when the traffic signal is green. Let us assume that the arrival and departure rates have been previously determined. The model then seeks an optimal cycle length and optimal green split allocation for each phase. The objective function represents the total average waiting time experienced by the vehicles in all queues: J=1 tN−t0 4 X i=1 ZtN t0 1 λi(t)Li(t)dt (6) where Nis the number of time instants and tN−t0is the time interval considered. One of the advantages of using criteria based on time averaged values is that the objective function has a finite value even if N or tNtend to infinity, provided that the queue lengths remain finite. Some additional conditions, such as the minimum and maximum durations for the red and green times or the maximum queue lengths, have been also added to the model since short cycles imply more stops, and long cycles cause longer delays. As such, they are unsuitable for the variations in the daily flow of traffic. This leads one to the following mathematical programming program: (P1) Min J s.t. gminA≤yG≤gmaxA(7) gminB≤yR≤gmaxB(8) 0≤xk≤xmax (9) x2k+1 = max x2k+b1k+1 yG+b3k+1 , b5k+1 (10) x2k+2 = max x2k+1 +b2k+1 yR+b4k+1 , b6k+1 (11) where k∈N0,gmin and gmax are the minimum green and maximum green time, respectively, in phase A(B) and xmax is the maximum queue length in each traffic stream. However, for each index k, the nonlinear constraints (10) and (11) can respectively be rewritten as    x2k+1 ≥x2k+b1k+1 yG+b3k+1 x2k+1 ≥b5k+1 (x2k+1 −x2k−b1k+1 yG−b3k+1 )T(x2k+1 −b5k+1 ) = 0 (12) and    x2k+2 ≥x2k+1 +b2k+1 yR+b4k+1 x2k+2 ≥b6k+1 (x2k+2 −x2k+1 −b2k+1 yR−b4k+1 )T(x2k+2 −b6k+1 ) = 0 (13) and thus the objective function (6) can be replaced by J=1 N 4 X i=1 1 ¯ λi!N−1 X k=1 (xk)i+(xN)i 2#.(14) Maria Lurdes Sim˜oes and Isabel M. Ribeiro [4] C.J. Lan and X. Gu, Optimal signal controls and effects of flow uncertainty, Proceedings of the 8th International IEEE Conference on Intelligent Transportation Systems, Austria, 549–554, 2005. [5] F.-B. Lin, Estimating average cycle lengths and green intervals of semi-actuated signal operations for level of service analysis, Transportation Research Record,1287, 119–128, 1990. [6] F.-B. Lin, Knowledge base on semi-actuated traffic signal control, Journal of Transportation Engineering,111(4), 398–417, 1991. [7] I.M. Ribeiro and M.L. Sim˜oes, Optimal cycle for a signalized intersection using Global Optimization and Complementarity , TOP: An Official Journal of the Spanish Society of Statistics and Operations,20(3), 779-790, 2012. [8] M.L. Sim˜oes and I.M. Ribeiro, Global Optimization and Complementarity for solving a semi-actuated traffic control problem, Procedia - Social and Behavioral Sciences,20, 390-397, 2011. [9] N.M. Rouphail, M. Anwar, D.B. Fambro, P. Sloup and C.E. Perez, Validation of generalized delay model for vehicle-actuated traffic signals, Transportation Research Record, 1572, 105–111, 1997. [10] B.D. Schutter, Optimizing acyclic traffic signal switching sequences through an extended linear complementary problem formulation, European Journal of Operational Research, 139, 400–415, 2002. [11] M.L. Sim˜oes, P. Milheiro-Oliveira and A. Pires da Costa, Modeling and simulation of traffic movements at semi-actuated signalized intersections, Journal of Transportation Engineering,136(6), 554–564, 2010. [12] F.V. Webster, Traffic Signal Settings, Road Research Laboratory 39, HMSO, London, 1958.