Model predictive control for multiclass freeway traffic Carlo Caligaris, Simona Sacone, and Silvia Siri
Abstract— The objective of the paper is to define a control framework for freeway traffic in which several vehicle classes are explicitly taken into account. The Model Predictive Control approach has been chosen for defining the proposed regulation scheme, in which both ramp metering and speed limitations are adopted as control actions. In the overall control scheme, the two types of control actions (ramp metering and variable speed limits) are determined for each vehicle class. Some simulative results are reported in the paper showing the effectiveness of the proposed approach.
I. I NTRODUCTION The design of control approaches for reducing congestion phenomena on freeways constitutes a significant research issue both for its complexity and for its wide implications. Actually, traffic congestion increases not only travel time, fuel consumption and pollution, but also the possibility of accidents. An efficient utilization of the road capacity and a balanced satisfaction of traffic demand through regulation techniques turns out to be necessary in managing congestion occurrences. Two major classes of control actions can be identified aiming at preventing and solving congestion situations in freeway systems. The first class refers to ramp metering control in which the number of vehicles entering the freeway by on–ramps is regulated ([1], [2], [3]). Ramp metering has been recognized as an effective way of relieving freeway congestion, yielding both a demand increase during peak periods and a temporary reduction of freeway capacity. The second class of control actions corresponds to the use of variable message signs where speed indications are provided to drivers. Some research works deal with the coordination of the two classes of control policies. Among the others, in [4] optimal control is approximated by neural networks in a receding–horizon scheme. The general case relevant to the regulation of a freeway network with both ramp metering and variable speed limits is faced in [5] in which a Model Predictive Control Scheme is defined and used. The contemporary presence of ramp metering actions and speed limitations in a single freeway stretch is taken into account in this work. A major feature of the proposed approach is the fact that two classes of vehicles are considered. Then, specific control actions (relevant to both ramp metering and variable speed limits) are derived for the two vehicle classes. The adopted control scheme is the one of Model Predictive Control (MPC), as already done in [6]. The MPC scheme described in this paper has already been The Authors are with the Department of Communications, Computer and Systems Science, University of Genova, Via Opera Pia 13, 16145 – Genova, Italy.
[email protected],
[email protected],
[email protected]
proposed in [7], where the simulation model (representing the real world) and the prediction model were supposed to be the same. The novelties of this paper stand in the fact that the simulation model is replaced by a microscopic model and that simulative examples are added in the paper. The microscopic model representing the real freeway system derives from the algorithm proposed in [8] which is based on the previous work by Nagel and Schreckenberg [9] but the model is here extended to consider the two classes of vehicles. This paper is organized as follows. In Section II the Model Predictive Control scheme is described. The simulation model representing the real world is reported in Section III, whereas Section IV is devoted to the discussion of some experimental results by simulation. II. T HE M ODEL P REDICTIVE C ONTROL
SCHEME
The control approach adopted in this paper for dealing with the problem of regulating traffic behaviour on freeway stretches is Model Predictive Control ([10], [11]). In a MPC scheme, at the k–th time interval, a finite–horizon optimal control problem is solved, by optimizing a suitable objective function subject to constraints on control variables and on state variables. A sequence of optimal control variables from the k-th time interval to the (k + Kp − 1)-th are derived; the first element of this sequence becomes the control action at stage k. This same scheme is then applied at time interval k + 1, by updating the data of the finite–horizon problem using new measurements; this procedure is iterated for all the following time intervals. Note that, at each time interval, only the first control values are applied, while the others are discarded and recalculated during the following iterations. Among other constraints, the finite–horizon optimal control problem to be solved at each iteration also includes state equations. Then, the state variables are constrained to fulfil the system state equations by realizing a prediction of the system behaviour over a time horizon defined as the prediction horizon Kp . In the following the various components of the MPC scheme are described. A. The prediction model The adopted prediction model comes from the macroscopic modelling theory and, in particular, it is based on the macroscopic model described in [12]. Our extension to such a model is related to explicitly considering two classes of vehicles, relevant to fast vehicles (i.e., cars and small vans) and slow vehicles (i.e., trucks and coaches). The model has already been proposed and deeply described in [7]; it is
briefly reported here for the sake of clarity. The state equations of the basic macroscopic model have been rewritten for each class of vehicles and the interactions between the two classes are taken into account by appropriately modifying the steady–state speed–density characteristic. From now on, class 1 and class 2 will refer to, respectively, fast and slow vehicles. In the following, the model state equations are reported for the three state variables, i.e., the traffic density ρi,j (k), the traffic mean speed vi,j (k) and the queue on the on–ramp li,j (k), where index i denotes the i-th freeway section, index j indicates the j-th class of vehicles and k denotes the temporal stage. Note that, as it is usual in macroscopic models, both a time discretization in K temporal stages and a space discretization in N sections are applied. The state equations are: ρi,j (k + 1) = ρi,j (k)+ T α ρi−1,j (k)vi−1,j (k) + + ∆i + (1 − 2α) ρi,j (k)vi,j (k) + − (1 − α) ρi+1,j (k)vi+1,j (k) + + ri,j (k) − si,j (k)
form (an analogous expression holds for the second class of vehicles): Vi,1 ρi,1 (k), ρi,2 (k) = n mi,1 ρi,1 (k) + c · ρi,2 (k) i,1 = Vfi,1 1 − ρi,1,max i = 1, . . . , N k = 0, . . . , K − 1 (4) where Vfi,1 denotes the “free” speed in section i for class 1, ρi,1,max is the so–called “jam density” referred to section i and to the first class of vehicles, and ni,1 , mi,1 , are real– valued positive parameters. Note that in the previous formulations a parameter c has been introduced representing the ratio between the maximum density of the i-th section, expressed as vehicles of the first class, and the maximum density of the same i-th section, expressed as vehicles of the second class (usually, it is c > 1, being the fast vehicles shorter than the slow ones): ρi,1,max c= i = 1, . . . , N (5) ρi,2,max Clearly, the only admissible pairs (ρ1 , ρ2 ) are the ones which satisfy the relation
i = 1, . . . , N j = 1, 2 k = 0, . . . , K − 1 (1)
ρi,1 (k) + c · ρi,2 (k) ≤ ρi,1,max i = 1, . . . , N k = 0, . . . , K − 1 (6) B. The control variables
vi,j (k + 1) = vi,j (k)+ T + Vi,j (ρi,1 (k), ρi,2 (k)) − vi,j (k) + τ T + vi,j (k) vi−1,j (k) − vi,j (k) + ∆i νT ρi+1,j (k) − ρi,j (k) − + τ ∆i ρi,j (k) + χj ri,j (k) T − δon vi,j (k) ∆i ρi,j (k) + χj i = 1, . . . , N j = 1, 2 k = 0, . . . , K − 1
(2)
li,j (k + 1) = li,j (k) + T (di,j (k) − ri,j (k)) i ∈ Ir j = 1, 2 k = 0, . . . , K − 1 (3) where T is the sample time interval, ∆i is the length of section i, di,j (k) is the demand for entering the ramp of section i, for vehicle class j at time k, ri,j (k) and si,j (k) are the on–ramp and off–ramp traffic volumes for section i and class j, respectively. Of course, ri,j (k) and si,j (k) are different from zero only for those sections that contain on/off–ramps; the indices of such sections make up the set Ir . Moreover, 0 ≤ α ≤ 1, τ , ν, χ and δon are parameters determined experimentally and Vi,j (ρi,1 (k), ρi,2 (k)) is the steady-state speed-density characteristic. In the adopted prediction model the steady-state speeddensity characteristic represents the interaction between the two classes of vehicles. It is then dependent on the vehicle class and, for the first class of vehicles, it has the following
As already mentioned in the Introduction, the control strategies adopted in this work are both ramp metering and speed limitations. The control variables representing ramp metering are the on–ramp traffic volumes ri,j (k), i ∈ Ir , j = 1, 2, k = 0, . . . , K − 1. Speed limitations are supposed to be displayed on variable message signs throughout the freeway stretch. Iv is the set of indices of freeway sections equipped ctrl with a variable message sign and quantities vi,j (k), i ∈ Iv , j = 1, 2, represent the speed limits imposed in section i for the j–th class of vehicles. Concerning speed indications, we have extended the approach proposed in [5] and [6] to the multi–class case, deriving the following further expression of the speed–density characteristic ctrl ctrl Vi,j (ρi,1 (k), ρi,2 (k)) = min (1 + βi,j )vi,j (k), Vi,j ρi,1 (k), ρi,2 (k) i ∈ Iv j = 1, 2 k = 0, . . . , K − 1 (7)
where (1 + βi,j ) is a factor expressing the driver noncompliance (yielding a speed higher than the displayed limit). Since the sequence of optimal control variables computed at each time interval is found by on–line solving the finite– horizon optimization problem, attention must be posed on the computational complexity of the solution algorithm for such a problem. In order to reduce the computational complexity, many MPC schemes adopt another decision horizon Kc (Kc ≤ Kp ), named control horizon. In the solution of the
finite–horizon optimization problem, control variables are computed until time interval k + Kc − 1 and, then, they are assumed to remain constant from k + Kc to k + Kp − 1 (always applying at time interval k only the first values of the determined control variables). Of course, the determination of the decision horizons Kp and Kc is a fundamental matter in the definition of MPC schemes and the computation of these values is generally made by searching a good trade– off between the computational complexity and the accuracy of the control scheme. C. The objective function The adopted control objective is the minimization of a weighted sum of the total time spent by vehicles in the freeway system (both in the freeway stretch and on the on– ramps) and of a term considering variations in the control signal.
J =T
N X 2 k+K X Xp
ρi,j (h)+T
i=1 j=1 h=k+1
+
2 k+K c −1 XX X
+
i∈Iv j=1 h=k+1
dn,m (t) dSaf ety
n
bm = of f
dm,l (t) m
dS
l
bm = on
li,j (h)·∆i +
i∈Ir j=1 h=k+1
Fig. 1.
Some variables of the simulation model
2
wi [ri,j (h) − ri,j (h − 1)] +
i∈Ir j=1 h=k+1
2 k+K c −1 XX X
2 k+K XX Xp
These cells may be either occupied or empty: clearly, every vehicle will occupy more than one cell (due to the actual length of the vehicles). We assume that faster vehicles have an occupancy of 3 cells, whereas heavy trucks occupy 8 cells. The speed is expressed as the number of cells that one vehicle can go over in one time step, being 1 second the simulated time step. The allowed maximum speeds are different for the two classes: when no control actions about speed limits are taken into account, we use v1 = 120 km/h ≃ 22 cells and v2 = 80 km/h ≃ 15 cells. On the contrary, when we want to represent the system in case of speed limits, this results as a reduction of the allowed maximum speeds.
zi
"
ctrl ctrl vi,j (h) − vi,j (h − 1) Vfi,j
#2
(8)
where wi , i ∈ Ir , and zi , i ∈ Iv , are real non–negative weighting parameters. The finite–horizon optimization problem to be solved at time interval k is related to the minimization of cost (8) with respect to the above defined set of control variables and subject to the state equations (1), (2), (3) and to some simple constraints bounding the control variables. A detailed description of the problem and of the meaning of all the constraints can be found in [7]. The resulting optimization problem is a nonlinear programming problem that can be solved by mathematical programming tools leading to local sub–optimal solutions. III. T HE S IMULATION M ODEL When evaluating the performance of the proposed control scheme in a simulative way, it is necessary to adopt a simulation model representing the dynamic behaviour of the real system. In this work, starting from the model described in [8], we have extended the microscopic cellular automaton model to the case in which two different classes of vehicles are taken into account, i.e., fast and slow vehicles. Of course, the first class is characterized by a mean speed higher than the second class. Furthermore, we consider two-lane freeway stretches and we assume that the faster vehicles can overtake the slower ones by occupying the left lane. The model also simulates on-ramps and off-ramps. In order to achieve a deeper insight into the possible rules for the two–lane microscopic models, we refer to [13]. Each lane is discretized in a fixed number of parts (cells) whose length is defined as a constant (1.5 m in our case).
The model introduced in [8], that we have implemented for our test case, has some important features that make it more accurate than the original simple model of [9]. We briefly recall these features since they are classic components of microscopic traffic theory (the meaning of the considered variables can be easily argued from Fig. 1). •
Anticipation Rule: every vehicle does not only consider the distance from the next vehicle in front, but estimates how far this vehicle will move during the time step. min f def − dS , 0 n,m = dn,m (t) + max vm min (t) = min {dm,l (t), vm (t)} − 1 vm
•
Brake Lights: a temporal range of interaction with the brake light of the next vehicle in front, i.e., tSn (t), is defined; the vehicle n reacts to bm (t) if the time to reach the back of m is less than tSn (t). thn =
•
dn,m (t) < tSn (t) = min {vn (t), h = 7s} vm (t)
Slow-to-Start Rule: the probability p that a vehicle n brakes depends on vn (t) and bm (t). if bm (t) = on and thn (t) < tSn (t) pb pe = p0 if vn (t) = 0 pd default,
It must be: p0 ≫ pd . The simulator updates the position and the speed of every vehicle for every simulated time step. The updating algorithm deals with the different parts of the model in the following order: 1) setting of initial conditions; 2) arrangement of entrances from the on–ramps; 3) check for possible lane–changes;
4) car motion; 5) arrangement of departures through the off–ramps. 1) Setting of initial conditions. In this step, executed once per simulation, we define the initial situation of the freeway by inserting a random number of vehicles on the stretches. The actual number of vehicles can be hinted by modifying the probability distribution here considered. The vehicles cannot overcome the safety distance at this point; when the car–motion is on, the safety distance is then considered for the determination of def f ; the only constraint we are interested in is the avoidance of collisions among vehicles. The on–ramps and off–ramps (described in the following paragraphs) are initialized in a very similar way. 2) On–Ramps Input. Since we are modeling a freeway, we need a detailed implementation of how vehicles enter or leave each stretch. The on–ramps are a–priori positioned in the spatial grid. When no ramp–metering is applied, on– ramps are modeled as a one–dimensional array considered as a FIFO queue, where vehicles wait for their chance to access the freeway. The queue can contain up to 200 vehicles: the number of vehicles waiting in the queue is updated at each time step and it depends on the probability pinput . The rule is explained with the following pseudo–code, to be executed for each time step: FOR vehicle = 1 to 4 IF pinput < pvalue ADD vehicle TO queue END IF END FOR where pvalue is a value that let us control the amount of vehicles accessing the queue. This means that, every second, a number of vehicles included between 0 and 4 can access the bottom of the queue. Only the first four vehicles can enter the freeway stretch in a time step: they actually do it only if there is enough room available downstream (i.e. if the freeway is not congested). We impose that a vehicle cannot enter the queue and access the freeway in the same time step. Of course, ramp–metering modifies the number of vehicles that enter the freeway in each time step according to the optimal values of the control variables. 3) Lane–Change. We need two different rules [8] to define the lane–change from the right to the left and viceversa. We also impose that heavy trucks cannot go to the left lane. One more variable is needed, i.e., ln = {straight, right, lef t} and it denotes the lane that vehicle n should occupy at the car–motion moment. The rule for moving from right to left follows; basically it checks if a vehicle slowed down by a predecessor can overtake it safely. 0. Initialization: for vehicle n find next vehicle in front m on the same lane, next vehicle in front s on the lane left to vehicle n and the next vehicle r behind vehicle s (as depicted in Fig. 2). We set ln = straight; 1. Check lane change: IF (bn (t) = of f AND dn,m (t) < vn (t)
r
s
dr,n
n
dn,m
Fig. 2.
Lane change from right to left
n
r
dn,m
dr,n Fig. 3.
m
m
s Lane change from left to right
f AND def n,s (t) ≥ vn (t) AND dr,n (t) ≥ vr (t)) SET ln = lef t END IF;
2. Do lane change: if ln = lef t, then vehicle n moves to the left lane. f The definition of the gaps def n,s (t) and dr,n (t) derives from the definition above by considering a copy of the vehicle n on its left side. Analogously, we define the rule for moving from the left lane to the right. 0. Initialization: for vehicle n find next vehicle in front s on the lane right to vehicle n, and next vehicle r behind vehicle s (as in Fig. 3). We set ln = straight; 1. Check lane change: IF (bn (t) = of f AND thn,s (t) > 3s AND (thn,m > 6s OR vn (t) > dn,m (t)) AND dr,n (t) > vr (t)) SET ln = right END IF; 2. Do lane change: if ln = right, then vehicle n moves to the right lane. 4) Car Motion. The car motion [8] is the core of the algorithm and it is based on the following rules. These steps are executed for every vehicle in each lane at each time step. 0. Initialization: for vehicle n, we find the next vehicle in front m; we also set p = pe and bn (t + 1) = of f ;
1. Acceleration: vn (t) if bn (t) = on 1 vn t + = or bm (t) = on and thn (t) < tSn (t) 3 min {vn (t) + 1, vmax } default; 2. Braking: 2 1 ef f vn t + = min vn t + , dn,m (t) , 3 3
2 IF vn t + < vn (t) 3 bn (t + 1) = on END IF;
a regular traffic condition much faster than in the no–control case. The same result for the traffic mean speed is reported in Figs. 6 and 7. 30
with probability p default,
4. Move: we update the position of each vehicle according to the speed just determined: xn (t + 1) = xn (t) + vn (t + 1).
140 120 20 100 80 10
60 40 20 5
Fig. 4.
5) Off–Ramps Output. The number of vehicles exiting a stretch is defined by means of a probability distribution pout . We do not consider advanced approaches, such as the assignment of the final destination to every simulated vehicle at the moment of its generation. Moreover, it would be possible to model the off–ramp as a finite–capacity buffer; when the buffer is full, a queue grows backward in the freeway stretch. IV. S IMULATIVE
160
section i
3. Randomization: ( max vn t + 23 − 1, 0 vn (t+1) = vn t + 32 IF p = p0 AND 2 vn (t + 1) < vn t + 3 bn (t + 1) = on END IF;
10
15 time [min]
20
25
30
Evolution of the traffic density in the no–control case.
30
140
120
100
section i
20
80
60 10 40
RESULTS
20 5
Fig. 5.
15 time [min]
20
25
30
Evolution of the traffic density by using the MPC scheme.
30
120 110 100
20 90
section i
The MPC scheme described in previous sections has been implemented within JavaT M framework integrated with the Knitro mathematical programming package for solving the finite–horizon optimization problem. In this section, some simulation results are reported to point out the effectiveness of the proposed control scheme. A freeway stretch consisting of 30 sections, each one with 1 km length, is taken into account. On-ramps and off-ramps are present in sections 3,9,15,21, and 27. There are five control variables for speed limits, and each of them acts on six subsequent sections. In particular, the variable message signs are placed in sections 1,7,13,19, and 25. The sampling time interval T is 30 seconds, the prediction horizon is Kp = 20 corresponding to 10 minutes whereas the control horizon is Kc = 10, thus equal to 5 minutes. The considered traffic situation represents a typical traffic situation in which congestion affects several successive sections. In particular, high values of traffic density and, consequently, low values of mean traffic speed are found in sections 11 to 21. Simulation results are quite satisfactory, as the control scheme drives the system to a regular traffic situation characterized by a mean traffic speed that is quite close to the “free” speed Vf = 123 km/h . In a sense, such a result may be interpreted as a stabilizing property of the proposed regulator that has been verified experimentally for a variety of initial conditions. In Fig. 4 and 5, the behaviour of the traffic density when no control action is applied and with the application of the MPC scheme are shown. It can be seen that the application of the proposed control technique drives the system state to
10
80 10
70 60 50 5
Fig. 6.
10
15 time [min]
20
25
30
Evolution of the traffic mean speed in the no–control case.
The evolution of some of the determined control variables is shown in Figs. 8, 9, 10 and 11. Note that the two control ctrl ctrl variables v7,1 (k) and v7,2 (k) take on discretized values. Finally, a comparison between the proposed MPC scheme and a corresponding one in which there is no distinction between the two vehicle classes (that is, ramp metering actions and speed limitations are the same for all vehicles) is drawn in Fig. 12. It can be noticed that the application of control actions dedicated for the two vehicle classes improves the effectiveness of the proposed control scheme. V. C ONCLUSIONS A Model Predictive Control scheme has been defined in which two control actions, i.e., ramp metering and variable
180
120
20 section i
90 80 10
70 60
traffic density [veh/km]
110 100
130 120
160 traffic mean speed [km/h]
30
140 120 100 80 60 40
110 100 90 80 70 60 50
0
5
10
15 time [min]
20
25
30
40
0
5
10
15 time [min]
20
25
50 5
15 time [min]
20
25
30
Evolution of the traffic mean speed by using the MPC scheme.
Fig. 12. Evolutions of the traffic density and of the traffic mean speed in section 16 in the no–control case (blue line), by applying the proposed multiclass control scheme (red line), and by applying a corresponding monoclass control scheme (cyan line).
120 100
[veh/h]
80 60 40 20 0
0
5
10
15 time [min]
20
25
30
Evolution of the control variable r10,1 (k).
Fig. 8.
70 60
[veh/h]
50 40 30 20 10 0
0
5
10
15 time [min]
20
25
30
Evolution of the control variable r10,2 (k).
Fig. 9.
140
[km/h]
120
100
80
60
40
0
5
10
15 time [min]
20
25
30
ctrl (k). Evolution of the control variable v7,1
Fig. 10.
90 85 80 75 70 65 60 55 50
Fig. 11.
speed limits, are coordinated. A major feature of such a control scheme is the presence of dedicated control actions for the two considered vehicle classes, corresponding to fast and slow vehicles. A further characteristic of the proposed approach is the adoption of a microscopic model, again defined for the two vehicle classes, representing the real world and used to test the effectiveness of the proposed control actions. R EFERENCES
80
[km/h]
Fig. 7.
10
0
5
10
15 time [min]
20
25
30
ctrl (k). Evolution of the control variable v7,2
[1] C.-C. Chien, Y. Zhang, and P. Ioannou, “Traffic density control for automated highway systems,” Automatica, vol. 33, no. 7, pp. 1273– 1285, 1997. [2] A. Kotsialos, M. Papageorgiou, and A. Messmer, “Coordinated and integrated control of motorway networks via nonlinear optimal control,” Transportation Research, vol. 10C, pp. 65–84, 2002. [3] T. Bellemans, B. D. Schutter, and B. D. Moor, “Model predictive control for ramp metering of motorway traffic: a case study,” Control Engineering Practice, vol. 14, pp. 757–767, 2006. [4] A. Di Febbraro, T. Parisini, S. Sacone, and R. Zoppoli, “Neural approximations for feedback optimal control of freeway systems,” IEEE Transactions on Vehicular Technology, vol. 50, pp. 302–312, 2001. [5] A. Hegyi, B. D. Schutter, and J. Hellendoorn, “Optimal coordination of variable speed limits to suppress shock waves,” IEEE Transactions on Intelligent Transportation Systems, vol. 6, pp. 102–112, 2005. [6] A. Hegyi, B. D. Schutter, and H. Hellendoorn, “Model predictive control for optimal coordination of ramp metering and variable speed limits,” Transportation Research C, vol. 13, pp. 185–209, 2005. [7] C. Caligaris, S. Sacone, and S. Siri, “Optimal ramp metering and variable speed signs for multiclass freeway traffic,” in Proc. European Control Conference 2007, Kos, Greece, 2007, pp. 1780–5. [8] S. F. Hafstein, R. Chrobok, A. Pottmeier, M. Schreckenberg, and F. C. Mazur, “A high-resolution cellular automata traffic simulation model with application in a freeway traffic information system,” ComputerAided Civil and Infrastructure Engineering, vol. 19, pp. 338–350, 2004. [9] K. Nagel and M. Shreckenberg, “A cellular automaton model for freeway traffic,” J. Phisique I, vol. 2, no. 12, pp. 2221–2229, 1992. [10] E. Camacho and C. Bordons, Model Predictive Control. Springer, Berlin, 1998. [11] D. Q. Mayne, J. B. Rawlings, C. V. Rao, and P. O. M. Scokaert, “Constrained model predictive control: Stability and optimality,” Automatica, vol. 36, pp. 789–814, 2000. [12] M. Papageorgiou, Applications of Automatic Control Concepts to Traffic Flow Modeling and Control, ser. Lecture Notes in Control and Information Sciencies. Springer-Verlag, 1983. [13] K. Nagel, D. E. Wolf, P. Wagner, and P. Simon, “Two-lane traffic rules for cellular automata: A systematic approach,” Physical Review E (Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics), vol. 58, pp. 1425–1437, 1998.
30
