Linear-Quadratic Model Predictive Control for Urban Traffic Networks

Advancements in the efficiency, quality and manufacturability of sensing and communication systems are driving the field of intelligent transport systems (ITS) into the twenty first century. One key aspect of ITS is the need for efficient and robust integrated network management of urban traffic networks. This paper presents a general model predictive control framework for both centralized traffic signal and route guidance systems aiming to minimize network congestion. Our novel model explicitly captures both non-zero travel time and spill-back constraints while remaining linear and thus generally tractable with quadratic costs. The end result is a central control scheme that may be realized for large urban networks containing thousands of sensors and actuators. We demonstrate the essences of our model and controller through a detailed mathematical description coupled with simulation results of specific scenarios. We show that using a central scheme such as ours may reduce the congestion inside the network by up to half while still achieving better throughput compared to that of other conventional control schemes.

section_content: Increasing population and economic activities in modern societies have led to a significant rise in the demand for mobility and transportation. Consequently, urban road networks are becoming frequently congested which creates severe economical, social, and ecological challenges. Research into traffic management systems aims to make a better use of existing network infrastructure to improve traffic conditions. Nowadays, traffic control centers receive data from remote sensors and apply control policies that respond to the prevailing traffic conditions. While real-time signal control systems responding to traffic conditions can help in alleviating congestions, optimal network-wide control strategies remain a challenge due to the combinatorial nature of the related optimization problems (see e. g., Papageorgiou, 2003). 

Historically, the SCOOT (Hunt, 1982) and SCATS (Lowrie, 1982) systems were among the earliest efforts to develop adaptive traffic control systems in the 1970s. These well-known and widely-used traffic-responsive control systems are based on heuristic optimization algorithms. In the 1980s, new optimization methods for traffic control were introduced based on rolling horizon optimization using dynamic programming -the prominent examples include OPAC (Gartner, 1983), PRODYN (Farges et al., 1983) and RHODES (Mirchandani & Head, 1998) or backtracking search on complex decision tree implemented in ALLONS-D (Porche et al., 1996). The more recent works on traffic control systems have adopted results of modern control theory. In particular, the TUC system (Diakaki et al., 1999; Diakaki, 2002) applies a multivariable feedback regulator approach to calculate in real time the signal control plans (splits) as a linear-quadratic (LQ) optimal control problem. This approach is based on the store-and-forward model of traffic network which was first proposed by Gazis and Potts (Gazis & Potts, 1963). While its simplicity enables efficient algorithms for split optimization, cycle time and offsets must be delivered by other control algorithms (Diakaki, 2003). H. M. Abdul Aziz (2012) recently presents an optimal control framework which is based on the cell-transmission-model. The model assumes discrete time, discrete space and linear relationship between density and flow. Another linear programming approach is the work of Waller & Ziliaskopoulos (2006). Their model provides robust solutions while explicitly considers constrains, however, it only focuses on single destination networks. 

Early works on traffic control systems based on the theory of Model Predictive Control (MPC) focused on the problems of ramp metering and variable speed limit control in freeway traffic management (Bellemans et al., 2002; Hegyi et al., 2003) where a free way link is geometrically divided into segments. Each segment is characterized by traffic density, mean speed and flow. Although the prediction model provides a comprehensive expression of fundamental traffic diagram on each link, its non-linearity feature is impractical in large urban networks. Aboudolas et al. (2009 Aboudolas et al. (, 2010) ) and many others such as Tettamanti et al. (2008 Tettamanti et al. (, 2010)) ; Tettamanti & Varga (2010) investigate an MPC-based approach to urban traffic control. In their approach, the store-and-forward traffic modeling is employed to represent the states of the links in an urban road traffic network. The objective of the control system is to reduce the risk of congestions by balancing the number of vehicles between links. However, their approach focuses on long term converged states of links rather than the rapid evolution of traffic phenomena inside link e. g. the wave of congestion or vehicles speed; and the travel time in the roads between intersections is ignored. Another MPC-based approach introduced by Lin et al. (2011) considers vehicles speed by estimating the time of travel through links by a non-linear non-convex prediction model. In order to overcome computational complexity this model assumes constant delay and thus leads to the model inaccuracy in light traffic. 

Our paper proposes an urban traffic control strategy to coordinate the green time split and turning fractions at intersections aiming to minimize the number of vehicles in the controlled area. The model is designed to predict the queuing dynamics through links while retaining the linearity of state evolution equations. Retaining linearity is important since the main idea behind the MPC approach is to repeatedly solve optimization problems on-line to find a near-optimal control strategy for a large network. To this end, we smartly describe and emulate real traffic behavior in the proposed MPC framework using only linear dynamics and constraints. In our framework, the roads are modeled as series of queues where the nonuniform characteristics of links are captured by different queue parameters. Travel time on the link is effectively taken into consideration by modeling the vehicles' movements from queue to queue. The turning fractions of vehicles between queues are treated as control variables, assuming full compliance from drivers with our centralized controller. The route guidance without concerning about drivers' preferences is applicable in the emergency scenarios such as disaster evacuation or in traffic scenarios with heavy congestion where exiting the controlled area is drivers' first priority. In contrast to store-and-forward models, our model can essentially adapt to changes of link conditions due to accidents and other disturbances. In short, our approach is superior than the above approaches in three aspects: we explicitly consider travel time in the road between intersections; our model unifies traffic light control and route guidance; the state prediction equation in our proposed MPC framework is linear so the model is capable to handle large network in real time control. 

The main contribution of this paper is thus a novel framework for real time control of urban traffic networks. It allows for optimization of network wide conditions by jointly considering traffic control and route guidance. The numerical comparison of our model with other control schemes shows that in general our model is superior in reducing congestion. 

The remainder of the paper is organized as follows. Section 2 describes the our discrete time MPC framework. Section 3 discusses the simulation and results. We conclude in Section 4.
section_name: Introduction

section_content: MPC is a multi-variable control method that is usually used to optimally control complex systems while explicitly considering constraints. The system dynamics are represented by a discrete time predictive model where the next state is a function of the current state, current demands (disturbance) and the current control vector with constraints. In each time instance, the optimal control problem is solved online based on the measured (estimated) current state (at time n = n 0 ) and the predictive demands over a N step finite horizon (at time n = n 0,. . ., n 0 + N -1). The result of the optimization is a sequence of control vectors over time n = n 0,. . ., n 0 + N -1 but only the first control vector (at time n = n 0 ) is applied to the system. In the next state (at time n = n 0 + 1), the optimal control problem is solved again for time horizon n = n 0 + 1,. . ., n 0 + N then only the control vector at time n = n 0 + 1 is applied and so forth. Section 2. 1 below describes our predictive model while Section 2. 2 presents our optimal control problem in detail.
section_name: Discrete Time MPC Framework

section_content: Below is a technical definition of our network model to be used as part of the MPC controller. The main attribute of the model is that it evolves in time synchronous with traffic light cycles (similarity to a cellular automaton model), yet the dynamics have been kept linear with an assumption of continuous vehicle counts. This ensures general computational tractability yet presents a model that is accurate enough to capture phenomena appearing in real urban traffic networks. Our novelty is in using linear dynamics and constraints wisely to describe and emulate real traffic behavior.
section_name: A General Controlled Network Model

section_content: Our representation of urban traffic networks is motivated by multi-class queueing networks (van Leeuwaarden et al., 2010), where classes relate to different types of network elements. We assume that time evolves in discrete steps n = 0, 1, 2,. . . corresponding to traffic light cycles. The network state vector is denoted by X(n) and the control vector is denoted by U(n). The network state maintains counts of the quantity (continuous approximation) of vehicles at different abstractions of locations based on the following 4 types of vehicle classes: delay (D), route (R), queue (Q) and sink (S ). Vehicles originate exogenously, pass through delay, route, and queue classes, then end up in sink classes upon reaching destination. On the way, vehicles are subject to routing control and traffic lights at intersections. 

Let K D, K R, K Q, K S denote the number of classes of each type respectively. Classes are indexed by k = 1,. . ., K with K = K D + K R + K Q + K S. We denote the classes of type j by K j for j ∈ {D, R, Q, S } and we number the classes as follows:

For convenience, we use the notation K { j, j ′ } to indicate the union of K j and K j ′, for j, j ′ ∈ {D, R, Q, S }, sometimes extending the notation to more indices. For example, K {D,R,Q} are all classes except the sink classes. Also for readability, let K { j, j ′ } = |K { j, j ′ } | and the same with more indexes. 

The total number of vehicles "in transit" at any time n is distributed among the K {D,R,Q} classes of type D, R and Q. We now describe the classes in more detail:

Queue classes: A queue class represents a turning direction before an intersection. Each queue has capacity, c k, k ∈ K Q, which is the maximum number of vehicles that can be in queue k, typically based on physical limitation.
section_name: Definition Of Network Elements And Control Vectors

section_content: A route class represents a portion of a multiple-lane street before queue classes where, under the assumption of full drivers' compliance, the turning rates to downstream queues can possibly be controlled. Similar to queue classes, each route class has its own capacity, c k, k ∈ K R. 

Delay classes: A delay class represents a portion of a multiple-lane street where vehicles just have one turning option to move to, its downstream D or R class. Delay classes are used to model free flow traffic. Each delay class also has its capacity, c k, k ∈ K D. 

Arrival Arrival (a) A real network segment A typical urban traffic road that connects two intersections has a number of delay classes at the beginning. This number is proportional to the length and flow characteristic of that of street. In practice the number of delay classes may be adjusted based on time of day and overall congestion level, yet for simplicity we keep it constant in this paper. The delay classes are followed by a route class and then by queue classes at a junction. The number of queue classes is the number of turning directions at the end of the street. See Figure 1 for an illustrative example. 

As time evolves, vehicle mobility is modeled by shifting the continuous approximation of vehicles from classes to other classes. This is represented by means of the network state. 

Network states: The network state for class k, x k (n), is a instantaneous continuous count of vehicles in class k ∈ K D,Q,R,S at time n. We define the vectors of network states as follows:

For convenience, we also use the notation X {i, j} to indicate [X ′ i X ′ j ] ′, for i, j ∈ {D, R, Q, S }, sometimes extending the notation to more indices. 

Links: Vehicles flowing out of a class move to downstream classes through predefined links. Only route classes may be the origin of more than one link, meaning that vehicles have to make turning decisions to move to different downstream classes at the next step. Obviously, there are no link start at sink classes. A link, j, is a directional connection between its source class, s j, s j ∈ K D,R,Q, and its destination class, d j,

We number the links j = 1,. . ., L. With each link we associate a flow rate, f j, which is the maximum number vehicles that can go from s j to d j in an unit of time. These flow rates are to be adjusted in the model based on traffic measurements. In the current paper we assume they are known. 

Within a time step we assume dynamics are occurring at a rate faster than that of our model and controller. We thus assume that at each time instant a link may be active, inactive or combination of both. For the instants during which a link is active, vehicles are assumed to move through that link at rate f j. A link is inactive means there is no vehicles move through the link. 

Time fractions: A time fraction, u j (n), is a variable that defines the fraction of a time unit during which link j is active. So the number of vehicles that leave class s j for class d j is f j u j (n). The number of vehicles that leave class k is ∑ { j:s j =k} f j u j (n). Similarly, the number of vehicles join class k is

We denote a set of all time fractions U and number them j = 1,. . ., L. Note that the time fractions determine both the flow of vehicles in the network and the effective turning rates at routing classes. 

In addition to time fractions, our framework also features a second type of control variable: green time fraction at intersections. As described below these are upper limits of the corresponding time fractions. 

Traffic intersections: We denote the set of all intersection by M and number them i = 1,. . ., M. For simplicity in this paper we assume all intersections are of the "West-East"/"North-South" type. Each intersection has two traffic light control variables u L+1+(i-1) * 2 (n), the green duration for West-East direction, and u L+1+(i-1) * 2+1 (n), the green duration for North-South direction. This seemingly complicated indexing is simply to allow setting all control variables in an ordered vector. We denote the set of all traffic light control variables by T, and number them j = L + 1, L + 2,. . ., J where J = L + 2 * M. Figure 2 contains a simple example to demonstrate how arrival rates, a k (n), and time fractions, u j (n), of current state affect the next state. Note that the network state at n = 1 may become undesirable with certain variable u(0) e. g. negative values. Thus, we introduce a number of constraints to keep a realistic network evolution in section 2. 1. 2.
section_name: Route classes:

section_content: This section describes a list of constraints that restrict the feasibility region of variables defined in the previous section. 

Non-negative control constraints: For 1 ≤ j ≤ L, the number of vehicles that move through link j at time n is a non-negative number and less than f j. If L + 1 ≤ j ≤ J, the green duration for a direction at an intersection is between 0 and 1, a traffic light cycle. Thus, we have constraints:

(1)

Traffic light cycle constraints: Sum of the green duration for West-East direction and the green duration for North-South direction at any intersection have to be less than or equal to 1, the traffic light cycle. 

(2)

Green duration constraints: The active time of a link across an intersection must be less than or equal to the corresponding green time. We define WE(i), i ∈ M, as the set of links which are active during green duration at West-East direction. Similarly, NS(i), i ∈ M, as the set of links which are active during green duration at North-South direction. Note that we ensure that WE(i) and NS(i) are disjoint sets. For i ∈ M:

(3)

Flow conflict constraints: At intersection, two links may collide, e. g. j 3 and j 5 or j 2 and j 4 in Figure 2. In that case, at most one link may be active at the same time. We define C p WE (i) to be subset of WE(i), i ∈ M, such that if j, j ′ ∈ C p WE (i), they cross each other. Hence, typically |C p WE (i)| = 2. We number the path collisions occurring at intersection i when the green traffic light is active at West-East direction by p = 1, 2,. . ., C WE (i). Similar definitions hold for C p NS (i) and C NS (i). These variables take part in the following constraints. For i ∈ M:

(4)

Note that this constraint does not take into account the link priority such as for example when turning vehicles have to give way to go-straight vehicles. Such behavior can be achieved by setting a slightly bigger flow rate for higher priority links. Further details are in section 3. 

Non-negative queue constraints: A class can only be drained if there are vehicles in it. We thus have the constraint:

Capacity constraints: Additionally, we also impose the constraints in which the number of leaving vehicles of any class will be limited by the states and capacities of its downstream classes. For k ∈ K D,R,Q :

The number of vehicles in a class k ∈ K D,R,Q in the next state is the total of the number of vehicles in this class in the current state plus the number of vehicles arriving exogenously, plus the number of vehicles arriving from other classes, and minus the number of vehicles leaving this class. Constraint (6) states that the number of vehicles in a class k in the next state can never exceed the class capacity c k. This "key constraint" allows us to model spill-backyet with a linear model! Given that the arrival rate is greater than departure rate of a road, e. g. red traffic light, and vehicles tend to move forward, this constraint causes congestion build up from downstream queues, right before intersection, up to upstream classes. 

For further illustration of constraints ( 2 ), ( 3 ) and (4) consider the example intersection in Figure 3 where the traffic light cycle constraint (2) is u 7 + u 8 ≤ 1; the green duration constraints (3) are u j ≤ u 7, j = 1,. . ., 7; and flow collision constraints (4) are u 2 + u 4 ≤ u 7, u 5 + u + 3 ≤ u 7. The latter (i. e. flow collision constraints) ensure that the controller will not guide vehicles through conflicting flows more than the amount they can handle, thus prevent unnecessary congestion.
section_name: Constraints

section_content: The network state, x k (n), k ∈ K {D,R,Q,S } is a (continuous) count of the number of vehicles in class k at time n. Hence the network state is K {D,R,Q,S } dimensional. Observe also that the state of sink classes is non-decreasing. The control U is J dimensional. 

The state evolves as follows:

Subject to the constraints appearing in (1-6) for all times n.
section_name: State Dynamics

section_content: Efficient computation and optimization using our model requires a matrix-based formulation. We present this briefly below. Our system is a constrained time-varying affine system based on matrices B, F and vectors d(n) and g(n) as defined below. We now represent the state evolution by

Where

The detailed expression of state dynamic equation which contains the matrix B and the vector d(n) are as follows:

We assume that the control U(n) is a state feedback control with full observations (it is a function of X(n)). At every time n, given X(n), the control needs to satisfy linear constraints of the form

The detailed expression of linear constraints which contains the matrix F and vector g(n) are as follows:

Here the first three rows correspond to constraints (1), the forth row corresponds to constraints (2), the fifth and sixth rows correspond to constraints (3), the seventh and eighth rows correspond to constraints (4), the ninth row corresponds to constraints (5) and the last row corresponds to constraints (6). 

Where:

• f is the vector of flow rates where element j is equal to f j. Note that f j is defined in section (2. 1. 1)

• For a vector, f, diag( f ) denotes a diagonal matrix with diagonal elements f. 

The definitions of other matrices of (10) are given in the Appendix B.
section_name: Matrix Representation

section_content: This section describes the MPC approach in detail. The controller is parameterized by a discrete time horizon N > 0, a positive semi-definite matrix Q = 1 ′ 1, of dimensions K {D,R,Q} and a vector R = -ϵ f ′, ϵ ≪ 1, of dimension K L. At time n, the controller uses the optimal solution of a quadratic programming (QP) problem in which the decision variables are the controls over the time horizon: n, n + 1,. . ., n + N -1. Given the current state X(n) and the controls U(i), i = n,. . ., n + N -1, the prediction of the state over the time horizon, denoted by X, is generated (details below) and appears in the objective and constraints of the QP. 

We partition F to [F x F u ] where F x is a K D,R,Q column matrix and F u is a J column matrix. The following is the QP formulation:

The objective function in (11) quadratically penalizes the number of vehicles in the network and linearly penalizes the control decision. Generally, the MPC model is able to serve different control objectives depending on how the positive semi-definite matrix Q is set-up. One possibility is minimizing the sum of weighted queue lengths (Aboudolas et al., 2010) by setting Q as a diagonal matrix where the diagonal elements correspond to the queue capacities. However, we would like to maximize network throughput which is equivalent to minimize the total number of vehicles in the entire network. That is why Q is all 1 matrix. Consequently, keeping vehicles in any particular class nearly has the same penalty as moving those vehicles to other classes. The only small cost difference is in term RU as is addressed later in this section. It may be argued that our objective, minimizing the sum of all queue lengths, increases the risk of spill back because the controller tries to guide vehicles to the shortest route, but we believe that the benefit of overall system performance out-weighs the risk of spill back in some network segments. Additionally, the simulations show that our MPC controller archives good congestion control in all the scenarios studied. 

Note that the above formulation does not take the sink classes into account. These may be incorporated in order to accommodate for driver routing preferences on a macroscopic scale. This is the subject of our future research. 

An attribute of our formulation is that for large queues, the linear cost is negligible in comparison to the quadratic cost, so the primary objective is to reduce the quadratic cost through the matrix Q. Only when the quadratic cost can no longer be reduced, a secondary objective achieved through the optimization is to minimize RU. Hence, we take advantage of the small linear cost to model the non-linearity dynamics of traffic flows without compromising the main objective of our QP solver. Particularly, the linear cost addresses a so-called holding back problem in the optimal traffic assignment. Holding back occurs when vehicles are held back even when there is available space in the downstream queue. The linear cost gives small incentive for vehicles to move forward, thus, it prevents the holding back issue. 

The output of the QP optimization is U = [U ′ l U ′ t ] ′. However, the only control variables are U t, the optimal green splits, and some variables u j ∈ U l, s j ∈ K R, the optimal turning rates. The other variables only serve the purpose of predicting the number of vehicles move to downstream classes. This is a further novelty of our model -as it allows to incorporate "cellular automaton" type behaviour in a model that is linear and thus tractable. For illustration, consider a road segment far away from intersections which is modeled by a sequence of D classes. The number of vehicles traveling to the downstream class in next step is determined by the biggest number of the number of vehicles currently in the upstream class, available space in the downstream class, flow rate etc. . . Thus vehicles tend to move forward if it is possible due to the small negative cost RU. This allows the MPC controller to effectivly predict future states. 

Finally, the constraints in ( 11 ) are just repetitions of (10) over the horizon.
section_name: The MPC Controller

section_content: In order to facilitate implementation, we now give the detail description of our QP. For readability, we assume in the description below that n = 0, generalization to arbitrary time (due to time varying arrivals), is straightforward and we also exclude S classes from all of the following equations. Define

We denote by Q block diagonal matrix of Q with dimensions N • K {D,R,Q}, and by R block vector that stack R N times. Multiplying S i U, i = 0,. . ., N -1, by the control vector over the whole time horizon, U, results in the control vector at the i time step. Similarly, multiplying S i X, i = 1,. . ., N, by the state vector over the whole time horizon, X, results in the control vector at the i time step. Therefore, S i U is a J • N J block matrix where

We substitute the above into (11) and obtain:

As we show in Appendix A, the QP ( 12 ) is in general convex but not strictly convex. The convexity implies it is amenable to an efficient numerical solution (i. e. feasible). The fact it may be non-strict implies that there may be multiple optimal solutions. This allows to incorporate a further secondary optimization for a refined solution if needed -catering to additional secondary objectives.
section_name: Detailed Description of the QP

section_content: In this section we demonstrate the performance of the proposed MPC controller in improving network throughput and reducing congestion under heavy traffic through two simple traffic scenarios. The first scenario focuses on controlling traffic light timings to reduce congestion at a bottleneck intersection, while the second scenario deals with routing traffic through a network consisting of bottleneck links. We conduct several simulations to obtain the performance metrics in terms of the queue lengths at each intersection and the total number of vehicles that successfully leave the network. Note that in our proposed framework both the signalization at the traffic intersections and the turning rate (i. e. routing) are represented by the same control variable (i. e. a time fraction during which vehicles leave a particular class) and thus it is sufficient to show the performance improvements through two separate scenarios focusing on either signalization or routing. 

There are few input parameters to the simulation that need to be measured or estimated based on historical data or relevant traffic models. Firstly, the average free flow speed is needed to convert the real network to the model. Our model assumes that in non-congested conditions, it takes one step (a traffic light cycle) for vehicles to move from a queue to the consecutive queue. Thus in our model, the queue is a road segment with length equal to the distance traversed by a vehicle at free low speed during one traffic light cycle. Secondly, the queues' capacity is estimated by the maximum number of average-length vehicles that can be packed into the road segment with minimum distance in between. Thirdly, the flow rates also need to be measured. Generally, flow rate is a function of link density. However, for simplicity and retaining linearity, we assume the flow rate of a particular link is a known constant. Two simulations are conducted for each scenario: A MATLAB simulation and a SUMO simulation. Figure 4 demonstrates the general simulation design. At the beginning of each traffic light cycle, the MAT-LAB or SUMO simulator reports the current state and mean exogenous arrival rate to the controller. The controller will in turn solves the QP problem in (11), returns the current control decision and waits for the state update of the next cycle. The mean arrival rates, a k (n), are deterministic and known but are perturbed by a zero-mean Gaussian noise with a relatively large variance. Thus at each time step a random noise is added to a k (n). The MATLAB simulation updates the next state based on current state, current control decision and current arrival as described in (7). The MATLAB simulation represents the ideal case where the controller has a perfect prediction of the future states except for the disturbance of arrivals. Despite the fact of reusing the linear prediction model in ( 7 ), the simulation still produces the essential congestion phenomena and basic driver behaviors. On the other hand, the SUMO simulation (SUMO) (website, 2013a) updates the next state through a microscopic traffic simulation model. The SUMO simulation is more realistic than the MATLAB simulation in modeling traffic network evolution. In SUMO simulation, the controller does not have such a good prediction of future state. The accuracy of state prediction is partly dependent on the parameter estimation (i. e. queue capacity, link capacity) which is beyond the scope of this paper. ), (7,3), (7,3), (13. 2,6), (13. 2,6) respectively. All negative arrival rates are set to zero. 

To ensure fair and comparable results, the same noise is applied for all control schemes and the controllers only have knowledge about the average (deterministic) arrival rates. The QP formulation defined in (11) is solved using CPLEX from MATLAB/TOMLAB tool box (TOMLAB) (website, 2013b) in each step of the simulation to find the optimal value and apply them for the decision variables such as green time split or turning fraction at intersections. 

Our main objective in this section is to compare the performance of the proposed MPC approach with other popular approaches under the same conditions rather than evaluate the correctness of the prediction model itself. Towards that end, in each scenario, the performance of the proposed MPC scheme is compared with that of the MPC without look ahead horizon (denoted as MPC-1 step) and a so-called local signal plan. In the MPC-1 step scheme, N is set to 1 in (11) and the controller is unable to see the effect of its current decision to the number of vehicles in the next step. In other words, the MPC-1 step scheme will push traffic forward as much as possible which represents the widely implemented algorithm in the Sydney coordinated adaptive traffic system (SCATS) (website, 2012). On the other hand, the local signal scheme allocates the green time proportionally to the queues at intersections regardless of the downstream queue conditions. Note that for this local control, in case of spill back (heavy congestion that goes beyond one link), green time may still be allocated for traffic even if the corresponding downstream link is congested, and thus is wasted as no vehicle can move further downstream. 

We now describe the detailed traffic scenarios and simulation results obtained for each of the above control schemes.
section_name: Illustrative Examples and Discussion of Results

section_content: This scenario shows the ability of the proposed MPC controller to maximize network throughput and reduce the congestion level within the network. Consider a simple scenario (Figure 5 ) with fixed routing and three intersections: top intersection, left intersection and the bottom right intersection. The main roads in the West-East and North-South directions consist of D 1. . . D 8 and D 9. . . D 18 delays, respectively, accommodate main traffic with larger arrival rates that may cause congestions at the bottom right intersection. The free flow speed is capped at 60 km/h and each queue models vehicles in a 1 km length road segment. Hence, it will take about 1 minute for vehicles to move from one queue to the next consecutive queue. The queue capacity is 135 cars per lane where the average car's length is 5m and the minimum distance between cars in a congested road is 2. 5m. The flow rates are measured by a long running SUMO simulation under heavy traffic load with an arbitrary traffic signalization. At the top and left intersections where smaller side traffic flows intersect, the optimal controller is expected to reduce the green time of the incoming traffic to the downstream link on the main roads in order to prevent congestion at the bottleneck bottom right intersection, and at the same time reserve more green time for the side traffic on link 18 and 21, respectively. 

In this scenario, both links 7 and 15 have maximum outgoing flow rate of 45 cars/cycle at the bottom right intersection. Thus at most 45 vehicles can pass through this bottleneck intersection in a single simulation step (i. e. one traffic light cycle) regardless of the control algorithms. As a result, an optimal control is to allocate green time for link 2 and 10 (Figure 5 ) so that at most 45 cars may go to bottom right intersection at every step to avoid the building up of congestion inside the network on those links of the main roads between intersections. The rest of the green time allocation is then given to links 18 and 21 enabling side traffic to move. The average number of cars arriving in each cycle for the main traffic flows is 17 cars/cycle at the ingress queues and 7 cars/cycle at the links between intersections. The added random noise has the standard deviation of 8 and 3 respectively in this scenario. These arrival rates are chosen just above the saturation point to increase the chance of congestion and spill back inside the network. The arrival rate into the side traffic flows has the mean of 13. 2 cars/cycle with noise having the standard deviation of 6. In the proposed MPC with horizon we expect to see the synchronization between the top and left intersections to cope with the variations in demands and to avoid congestion at the bottom right intersection. 

Illustrative sample trajectories of different queue lengths using different control schemes are shown in Figure 6 and Figure 7. Observe that the proposed MPC with time horizon of 10 steps (denoted by MPC-10 step scheme) has slightly better throughput (Figure 6. a and Figure 7. a) while significantly reducing congestion inside the network (Figure 6. b and 7. b) for both the MATLAB and SUMO simulations. In particular, the total queue length from D 3 to Q 7 and D 11 to Q 15 is kept well below the total capacity and almost at a constant level (Figure 6. b and 7. b). It indicates a synchronization between the top and left intersections where the controller only allows a total of about 31 cars passing through the top and left intersections heading to the bottleneck bottom right intersection in any single time step (i. e. traffic cycle). Note that there are about 14 cars arriving to D 5 and D 13 every cycle to make up the total of 45 cars/cycle which is the capacity of bottom right intersection. The rest of the traffic light cycle are allocated to the side traffic flows. At a result, it fully utilizes links across intersections in the network and minimizes congestion inside network. 

On the other hand, the local controller allocates green time based on the ingress queue lengths, Q 2 and Q 10, even if the downstream queues, D 3 and D 11, are unable to accommodate more traffic. In such a case, by wasting green time for congested flow, it actually creates more congestion at Q 18 and Q 21 (Figure 6. d and Figure 7. d). In contrast, the MPC-10 step schemes are able to keep the queues D17, Q18, D20 and Q21 stable. At the same time, the MPC-10 step scheme is also able to keep the congestion inside the network low. As a result, there is no spill back in the case of MPC-10 step control scheme. 

Furthermore, pushing traffic into D 3 and D 11 more than what the bottom right intersection can handle, as in case of the local controller and MPC-1, causes more congestion in the inner links that spills back to the top and left intersections. In overall, the unreasonable allocation of green time leads to reduce network throughput and cause unnecessary congestion. 

Similar to the local controller, the MPC without horizon (MPC-1 step) also allocates more green time to the main roads (link 2 and 10) resulting in queues building up in the inner links D3 -Q7 and D11 -Q15. However, in this case, when the spill back reaches D 3 and D 11 the the MPC-1 step would only allocate green time for side traffic (link 18 and 21). Because there is no wasting resource at any intersection, the MPC-1 step scheme has better performance in term of throughput compared to that of the local controller. However, it still has a high congestion level inside the network (Figure 6. b and 7. b). 

This scenario clearly demonstrates the concept of gating where the proposed MPC controller automatically allows an optimal amount of traffic downstream to avoid congestion inside the network but at the same times also achieves the best possible throughput.
section_name: Scenario 1: Symmetric Gating Example

section_content: This scenario demonstrates the efficiency of the proposed MPC control scheme for routing purposes. Consider a grid network where vehicles arrive at the top left edge and exit at the bottom right edge (Figure 8 ). In order to reach the destination, vehicles have to pass through one of the bottleneck links in between. With a non-optimal controller, it is likely that some bottleneck links will experience heavy congestion while others have light traffic. In this scenario, we expect that our MPC controller will find a policy (i. e. turning fractions at intersection) that reasonably balances the traffic load among all the bottleneck links, thus, reduces the overall congestions inside the network. Because the green split times at intersections do not have any impact on the network state, we set those decision variables representing the green times to some fixed values through this scenario. 

Vehicles are assumed to completely follow the turning advices from our centralized controllers at top left and middle left intersections. The bottleneck links originate from D 4, D 17 and D 23 delays and finish in D 6, D 19, D 25, respectively. Similar to the previous scenario, the free flow speed is capped at 60 km/h in normal links and 7. 2 km/h in bottleneck links. Each queue models vehicles in a 1 km road segment. Hence, it will take about 1 minute for vehicles moving from any queue to the consecutive queue. Cars' length is again set to 5 meter long and the minimum safety distance is 2. 5 meters. As a result the queue capacity is about 135 cars for all queues. We only use single lane road in this scenario. The outgoing flow rate of the bottleneck links is 7 cars/cycle which is lower (for example they have lower speed limit) than other links in the network which have the flow rate of 30 cars/cycle. The average arrival rate at the top left edge is chosen to be a less than the aggregate flow rates of all the bottleneck links, i. e. average arrival of 17 cars/cycle with added noise following the normal distribution with zero mean and standard deviation of 10. 

We show the sample trace results for different control schemes in Figure 9 and Figure 10. Our proposed MPC controller with a time horizon of 12 steps achieves better throughput and congestion control compared to that of other schemes. Observe that in both simulations, our proposed MPC scheme maintains around 14 cars at the top and middle bottleneck links where the maximum queue is 270 cars. The rest goes to the bottom bottleneck link. The proposed control scheme significantly reduces congestions thus preventing spillback inside the network. 

The MPC-1 step scheme on the other hand does not realize the congestion at bottleneck links until it spills back to the signalized intersections. Therefore, drivers are advised to turn at random under these controllers resulting in some bottleneck receiving more traffic than the others. This causes congestion to build up. In the MATLAB simulation, the effect of spillback is ignored for simplicity so vehicles are still able to move at normal rate in heavy congestion at intersections. Hence, the throughput of MPC-1 is very close to the throughput of MPC-12 which does not have any spillback (Figure 9. a). However, it is not the case in the SUMO simulation. When spillback reaches Q2 and Q3, vehicles are hardly able to move to D13 resulting in a light traffic at the middle and bottom bottleneck links. Consequently, the throughput of MPC-1 is significantly lower than MPC-12 (Figure 10. a)
section_name: Scenario 2: Routing Enabled Network

section_content: We have developed in this paper a general model predictive control framework for centralized traffic signal and route guidance systems aiming to minimize network congestion. The proposed controller mechanism is based on a finite rolling-horizon (model predictive) control scheme where both the non-zero travel time on the link and possible spill-back due to congestion are taken into account. We have provided the detailed mathematical description of the framework together with the derivation of the linear model with state dependent constraints. As a result the linearity and tractability are some of the key features of our proposed coordinated central control of large area urban networks. 

We compared the control algorithm to a simple local control signal plan and similar model predictive control scheme without look ahead. The latter is resembles current control mechanism (SCATS system) used to coordinate traffic in various urban cities around the world. We have showed via numerical experiments that using the proposed control scheme may reduce the congestion inside the network significantly while still achieving better throughput compared to that of other conventional control schemes that we studied. 

In future research we intend to incorporate state estimation into the model as well as carry out large-scale experiments on networks with hundreds of nodes. This is achievable due to the linear-quadratic structure of our framework. ).
section_name: Conclusion

section_name: Acknowledgements

section_content: This work was supported by the Australian Research Council (ARC) Future Fellowships grant FT120100723.
section_name: Acknowledgements

section_name: Appendix A. Convexity

section_content: Given that Q is all 1 matrix, we now prove that the minimized objective function f (U) = g(U) + h(U) in (12) where g

) is convex but not strictly convex. Therefore, we are likely to have more than one optimal solution. 

Let Z is a vector of dimension N × K D,R,Q (for readability, we denote K D,R,Q by K until the end of this section) where Z = B U or z i = ∑ N×J j=1 b i, j u j. Note that z, b are elements of Z, B respectively and B is a lower
section_name: Appendix A. Convexity

section_content: The followings are definitions of matrices, vectors in (10)

• S WEt is a M × 2M matrix with element (i, j) set to 1 if j = 1 + (i -1) * 2 and 0 otherwise. 

• S NS t is a M × 2M matrix with element (i, j) set to 1 if j = 1 + (i -1) * 2 + 1 and 0 otherwise. 

• S WEc is a (s × M), s = ∑ M i=1 C WE (i), block diagonal matrix where the diagonal elements are 1 vectors of dimensions C WE (i), i = 1,. . ., M

• S NS c is a (s × M), s = ∑ M i=1 C NS (i), block diagonal matrix where the diagonal elements are

NS C is a (C NS (i) × L) matrix with element (i, j) set to 1 if j ∈ C i NS and 0 otherwise.
section_name: Appendix B. Further Detailed Notation