The thesis presents the results of research on distributed and coordinated control method for freeway ramp metering. The freeway traffic is represented by the Cell-Transmission Model. The primary control objective is to provide uniform distribution of vehicle densities over freeway links. Density balancing is a new traffic objective. On the microscopic level, it can be perceived as equalizing the average inter-distance between vehicles. The equal inter-distance can be attractive to the driver's point of view. It can potentially reduce the number and intensity of acceleration and deceleration events and therefore, it can make a travel more safety and comfortable while decreasing fuel consumption and emissions. In addition, the objective takes into account standard traffic metrics like Total Travel Distance and Total Travel Spent. For the controller, a distributed modular architecture is assumed.

It enables to compute the optimal decisions by using only local state information and some supplementary information arriving from the neighbouring controllers. A designed distributed architecture provides modularity and functional symmetry, i.e., each of the controllers can be perceived as a module realizing the same computational procedure. This type of architecture can be convenient for system assembling and maintenance.

The contributing part begins with the analysis on equilibrium sets of the Cell-Transmission Model. The goal of this study is to derive the conditions that assure the existence and the uniqueness of the balanced equilibrium states. The next step is to find a set of inputs such that the resulting equilibrium state is balanced. In the set of balanced equilibria, we are interested in the selection of the point that maximizes the Total Travel Distance. It is shown that for a steady state the optimizer of the Total Travel Distance can be regarded as an equivalent to the optimizer of the commonly used in traffic objective where the Total Travel Distance is weighted with the Total Travel Time. The optimal balanced state together with the corresponding control input can be used as the set point for a design of robust closed-loop system. In the sequel, the implementation aspects and limitations of the proposed method are discussed. Finally, several case studies are presented to support the analysis results and to examine the effectiveness of the proposed method.

The major part of the thesis aims on a design of an optimal controller for balancing the traffic density. The optimization is performed in a distributed manner by utilizing the controllability properties of the freeway network represented by the Cell-Transmission Model.

By using these properties, the set of subsystems to be controlled by local ramp meters are identified. The optimization problem is then formulated as a non-cooperative Nash game.

The game is solved by decomposing it into a set of two-players hierarchical and competitive games. The process of optimization employs the communication channels matching the switching structure of system interconnectivity. By defining the internal model for iv the boundary flows, local optimal control problems are efficiently solved by utilizing the method of the finite horizon Linear Quadratic Regulator. The developed control strategy is then tested via numerical simulations on the macroscopic model in two scenarios for uniformly congested and transient traffic. The alternative approach of balancing employs the theory of multi-agent systems. Each of the controllers is provided with a feedback structure assuring that the states within its local subsystem achieve common values by evaluating consensus protocol. Under these structures, an optimal control problem to minimize the Total Travel Spent is formulated. The distributed controller based on the Nash game is validated via Aimsun micro-simulations. The testing scenario involves the traffic data collected from the south ring of Grenoble. The tests are carried on to expose capabilities, but also disadvantages of the designed control strategy.

CHAPTER 1 Introduction

This chapter contains the introduction and the background of the study presented throughout this thesis. We will begin with a general overview on the topic of the freeway traffic control. Next, the objectives of the thesis will be specified together with the scope of the conducted research. In the sequel, a review of the corresponding literature along with the author's original contributions will be presented. Finally, the thesis structure will be given.

Subject of the Thesis

Freeway traffic management is nowadays one of the most important factors impacting on economics, environment and the quality of our daily life. As reported by the 2012 TTI's 2012 Urban Mobility Report [START_REF] Schrank | annual urban mobility report[END_REF], only in the United States urban areas, the traffic congestion caused 5.5 billion hours of traffic delays resulting in 2.9 billion gallons of wasted fuel, producing 56 billions lbs of the carbon dioxide. The total cost due to this congestion was estimated at the amount of 121 billions of dollars. For comparison, the travel delay in 2000 and 2005 was respectively 4.5 and 5.9 billion hours. By following the statistics, we can conclude with the following two facts. The first one is that the traffic demand is still increasing (which is a natural consequence of the Globalization and human needs).

The second is that the recent years have brought a promising improvement, particularly in the areas where the Intelligent Transportation Systems have been put into practice. In the context of freeway traffic, these systems rely on a specialized sensing, ramp metering and variable speed limiting instrumentation performing control policies that through many years have resulted in shortened travel delays, reduced pollution, decreased number of accidents and many other expected benefits.

This thesis are focused on the freeway traffic management by using coordinated ramp metering. Ramp meters (or ramp signals) together with the signal controllers are used to control the flow entering freeways through the on-ramps (see Fig. 1.1). The signals used are usually red and green only, no yellow. The simplest control policy, brought from the urban traffic, is based on the fixed time metering plans. The idea behind this operation is to break up vehicle platoons into single-vehicle entries. This can potentially benefit in accident reductions by providing a smooth merging of the mainstream and the on-ramp flows. The strategy is simple in the implementation, since it does not require information of the traffic state. However, from the perspective of the overall freeway volume, this strategy does not bring a desired performance. The fixed time metering is therefore usually implemented only under light traffic congestion as an initial operating strategy. When the traffic becomes congested, a responsive (closed-loop) control methods are performed.

In simple, a closed-loop metering control system can be schematically represented as shown in Fig. 1.2. A freeway is equipped with a set of sensors collecting the information of the flow and its velocity. This information, after a relevant processing, is given to the controllers that based on their heuristic or optimal polices compute the control decisions.

These decisions are then translated into traffic signals and sent to the ramp meters. The full setup, among many other hardware and software instruments, contains repeaters, access points, transmitters, data collection points, state estimators and flow predictors.

For the sensors, the most common in use nowadays are the self-calibrating magnetic sen- 1.2. Objectives and scope of the thesis 3 sors, equipped with the wireless communication and dedicated for 10 years of usage. The heuristic (experience-based) ramp metering controllers usually regulate the local traffic states around desired set points, while the optimal ones compute their coordinated decisions by optimizing a given performance index. The metering control systems can be implemented through centralized or distributed architectures, as will be discussed in the next section.

Ramp metering is used extensively in the United States, Germany, Netherlands, France, Italy, Japan, Australia, New Zealand and South Africa. Only in California, in August 2013, there was a total of 2751 existing ramp metering locations, with another 1835 locations planned [START_REF] Wang | Ramp metering status in california[END_REF]. As reported by the UK Department for Transport [3], thanks to ramp meters, the average travel time for passing the junction falls by 13 percent while downstream speed increases by 7.5 percent. Long-term evaluations of sites overseas have also found reductions in accidents and emissions. All these benefits generate a strong motivation for continuing of the development and implementation of the ramp metering systems.

The thesis has been conducted in the context of the project HYCON 2: "Highlycomplex and networked control systems", funded by the Seventh Framework Programme (FP7). HYCON 2 is currently leading over 20 academic and industrial institutions in the field of the control of complex, large-scale and networked dynamical systems. The project is assessing and coordinating both, fundamental and applied research, from fundamental analytical properties of complex systems to control design methodologies with networking, self-organizing and system-wide coordination. HYCON2 is leading several applications domains to motivate, integrate, and evaluate research in the networked control.

One of these domains concerns ground transportation. The HYCON 2 traffic show case application corresponds to the operation of the south ring of Grenoble. The major goal of this show case is to provide a rich set of the traffic data to validate the prediction and control algorithms. A task force was build based on the participation of INRIA Rhone-Alpes, UNIVPAVIA, INRETS-LCPC, ETHZ, US, UNIVAQ, TU and TUDELF. The experimental platform is set up in the Grenoble Traffic Lab [4]. The subject of this thesis is located within the freeway traffic control with an effort to apply the methods of the networked control systems. The validation of the developed control strategies will be performed with the use of the HYCON 2 traffic show case.

Objectives and scope of the thesis

The primary objective of this research is to design an efficient and easy for the implementation distributed ramp metering control method for balancing freeway vehicle density. The goal of this control is to provide a safety and environment-friendly vehicle flow on a freeway. Density balancing is a new traffic objective, and it can be perceived as equalizing the average inter-distance between vehicles. The equal inter-distance can be b a attractive to driver's point of view. It can potentially reduce the number and intensity of acceleration and deceleration events and therefore, it can make a travel more safety and comfortable, while decreasing fuel consumption and emissions. We also believe that the balanced density may increase the capacity of a freeway. Naturally emerging question is for the level of the balanced density that provides also effective flow of the traffic volume.

In the thesis, we will tend to balance the traffic density at the levels that optimizes standard traffic freeway metrics, i.e.: Total Travel Distance and Total Travel Spent. We will also investigate the impact of density balancing on the propagation of shock waves.

For the controller, we will assume a distributed architecture (see Fig. 1.3b). In contrast to the centralized controller (see Fig. 1.3a), a designed distributed architecture will allow us to compute the optimal decisions by using only local state information and some supplementary information arriving from the neighbouring controllers. The total length of the communication channels will be then reduced. As a result, also the probability of the information lose will be decreased. Instead of solving time consuming global optimization problem, a distributed setup will enable us to formulate a corresponding game problem that can be resolved and implemented on-line by performing set of local optimizations of reduced size. A designed distributed architecture will provide modularity and functional symmetry, i.e., each of the controllers will be perceived as a module realizing the same computational procedure. This type of architecture is convenient for system assembling and maintenance. In the case of failure, only the malfunctioning module needs to be replaced. In addition, a modular decentralization plays an important role for safety. Suppose a malfunction of the central computer computing the optimal decision for every controller.

An incorrect signal is then sent to whole system. In modular control architecture, this risk is reduced to local failures. Modular controllers are also strategically for a design of the accompanying hardware and software architecture that is inherently distributed.

The final purpose of the research is to test the proposed control strategy under different traffic conditions. To verify the balancing performance, the tests will be first executed on a macroscopic model. Then, the controller will be integrated with a microscopic simulator operating in the Grenoble Traffic Lab and tested on the model of the Grenoble 1.3. Review of the previous research south ring. The tests will be carried on to expose capabilities but also disadvantages of the designed control strategy.

The scope of the thesis includes the following points:

• Literature review, to settle the problem among the existing methods,

• Mathematical representation of the freeway traffic together with definition of the control inputs,

• Studies on the equilibrium sets, to explore the feasibility of density balancing,

• Review of the existing optimal control methods from the perspective of the freeway systems,

• Controllability analysis in freeway links,

• Definition of the dynamic system partitioning, to provide an architecture eligible for distributed Nash game based optimization,

• Formulation of the game problem for traffic density balancing,

• Solution of the posed problem,

• A proposal of an alternative approach based on consensus protocol,

• Case studies with the use of a micro-simulator,

• Summary of the results and proposal of the future extensions.

Review of the previous research

In this section, we will review the literature related to the subject of the thesis. Only selected work on ramp metering methods and optimization in traffic systems will be presented here. A number of specific references will appear throughout the thesis while discussing particular topics.

Ramp metering methods in freeway traffic systems

History of freeway ramp metering is dated back to 1960s, when the first forms of ramp control were applied in Chicago, Detroit and Los Angeles areas [START_REF] Arnold | Ramp metering: A review of the literature[END_REF]. Since then, a variety of both heuristic and optimal strategies have been developed. An interesting survey was presented by Papageorgiou in [START_REF] Papageorgiou | Freeway ramp metering: An overview[END_REF].

The most simplistic ramp metering systems employ the fixed-time strategies. They are design by means of analysing the historical demand profiles and implemented without using the real-time measurements. Fixed-time strategies are usually activated only in the peak-hours. Proposed by Wattleworth [START_REF] Wattleworth | Peak-period analysis and control of freeway system[END_REF] policy was to regulate the entering flows such to provide that the mainstream flow at each of the sections does not exceed the capacity.

Few variants of this idea were presented in [START_REF] Wang | On a ramp-flow assignment problem[END_REF], [START_REF] Schwartz | Integrated control of freeway entrance ramps by threshold regulation[END_REF] and [START_REF] Wang | Computer model for optimal freeway on-ramp control[END_REF]. As pointed out in [START_REF] Papageorgiou | Freeway ramp metering: An overview[END_REF],

Chapter 1. Introduction due to the absence of real-time measurements, the fixed-time strategies may overload the mainstream flow resulting in congestion. On the other hand, if the expected (through the historical data) demand is overestimated, then the ramp metering may lead to freeway underutilization.

A variety of existing ramp metering systems are based on local (isolated) or coordinated regulators using real-time measurements. The goal is to keep the traffic state closed to some pre-defined values. Masher et al. [START_REF] Masher | Guidelines for design and operating of ramp control systems[END_REF] suggested demand-capacity strategy which states that, under the free flow condition, the metering flow at each of the on-ramps should be such that the local mainstream flows (measured downstream to the on-ramps) reach the capacity. In the case of the congestion, the entering flow should be switched to the minimum admissible value. In the occupancy strategy [START_REF] Masher | Guidelines for design and operating of ramp control systems[END_REF], we read control law that is analogous to demand-capacity strategy, but here the mainstream flow is estimated by means of the occupancy information. Introduced by Papageorgiou et. al [START_REF] Papageorgiou | Alinea: a local feedback control law for on-ramp metering[END_REF] ALINEA is a local feedback ramp-metering strategy. ALINEA was shown to be a remarkably simple, highly efficient and easy for implementation, and due to these facts, it became one of the most commonly used ramp metering strategy. The idea is to regulate the local vehicle density at the set point that is usually represented by the critical density. As a result, the local (downstream to the on-ramp) flow is meant to be kept around the capacity. It was shown [START_REF] Papageorgiou | Alinea local ramp metering: Summary of field results[END_REF] that ALINEA is not very sensitive to the choice of the regulator parameter. Chu and Yang [START_REF] Chu | Optimization of the alinea ramp-metering control using genetic algorithm with micro-simulation[END_REF] elaborated a method to tune the operational parameters of the ALINEA. Based on the genetic algorithms, the authors were optimizing four parameters, including the update cycle of the metering rate, a constant regulator, the location and the desired occupancy of the downstream detector station. The optimal set of parameters was minimizing the total vehicle travel time.

The idea of local regulation was extended into the multivariable regulators that instead of local state information use all available mainline measurements (see, for example, [START_REF] Papageorgiou | Modeling and real-time control of traffic flow on the southern of boulevard peripherique in paris-part ii[END_REF] [16], [START_REF] Benmohamed | Feedback control of highway congestion by a fair on-ramp metering[END_REF]). METALINE [START_REF] Papageorgiou | Alinea: a local feedback control law for on-ramp metering[END_REF] can be perceived as a multivariable extension of the ALINEA.

The metering rate of each ramp is computed based on the change in measured occupancy of each freeway segment under METALINE control, and the deviation of occupancy from critical occupancy for each segment. Like the ALINEA algorithm, the METALINE algorithm is theoretically robust and easy to implement. The main challenge to the success operation of METALINE is the proper choice of the control matrices and the target occupancy vector [START_REF] Jin | Evaluation of on-ramp control algorithms[END_REF]. Another extension of the ALINEA is a coordinated strategy called HERO, proposed by Papamichail et al. [START_REF] Papamichail | Hero coordinated ramp metering implemented at the monash freeway[END_REF]. HERO employs a feedback regulator where the target is the critical occupancy for throughput maximization which is regarded more robust than targeting a pre-specified capacity value. As reported by the authors, HERO outperforms uncoordinated local ramp metering and approaches the efficiency of sophisticated optimal control methods.

Review of the previous research 7

A wide group of metering systems are based on cooperative strategies. They are usually realized through two steps. The first step is to compute the metering rates by using isolated strategies. The second step is to adjust these rates based on system-wide information to avoid both, congestion at the bottleneck and spillback at critical ramps. As reported in [START_REF] Jin | Evaluation of on-ramp control algorithms[END_REF], the coordinated strategies, which are usually performed in ad hoc manner, are still sensitive to heavy traffic conditions and may arise undesirable states. One of the coordinated ramp metering strategies is the helper ramp algorithm proposed by Lipp et al. [START_REF] Lipp | Benefits of central computer control for the denver ramp metering system[END_REF]. In this algorithm, a freeway is split into several sections consisting of one to several on-ramps. In the first (isolated) decision step, each meter selects one of six available metering rates based on localized upstream mainline occupancy. In the second step (coordinated), if a ramp grows a long queue and is classified as critical, its metering rate is sequentially distributed to its upstream ramps. To the coordinated strategies we can also include the linked-ramp algorithm suggested by Banks [START_REF] Banks | Effect of response limitations on trffic-responsive ramp metering[END_REF]. In this algorithm, the local decisions are made based on the demand-capacity strategy. The coordinating adjustment is similar to that of the helper algorithm, i.e., whenever a ramp's metering rate is in one of its lowest three metering rates, then the upstream ramp is required to meter in the same rate or less, and, if necessary, the further upstream ramps are also required to do so.

Several fuzzy logic controllers were also studied for the ramp metering applications.

Fuzzy logic algorithms aim to convert the experimental knowledge about a traffic system into fuzzy rules. The traffic conditions as occupancy, flow rate, velocity and ramp queue are split into categories, such as small, average and large. Then, a set of rules are designed to relate traffic conditions with the metering rates. For the interesting results, the reader is referred to the papers [START_REF] Meldrum | Freeway traffic data prediction using artificial neural networks and development of a fuzzy logic ramp metering algorithm[END_REF], [START_REF] Liang | Freeway ramp control based on genetic pi and fuzzy logic[END_REF] and [START_REF] Jiang | Fuzzy self-adaptive pid controller for freeway ramp metering[END_REF].

Optimization in traffic systems

Most of the optimal controllers in traffic systems rely on the decisions obtained by the optimization of macroscopic models. These are represented in continuum or discrete forms governed by partial differential or discrete dynamical equations, respectively. Depending on the model representation and the structure of the objective function a relevant dynamical optimization solver is applied. The most frequent is use are the solvers based on the receding horizon (or model predictive) schemes allowing to the update the information of the boundary conditions. A common objective for freeway system optimal control is to decrease the time of travel incurred by all drivers while maximizing the traffic flow (see, for example, [START_REF] Ghods | An efficient optimization approach to realtime coordinated and integrated freeway traffic control[END_REF]). For this purpose, the relevant metrics like Total Travel Spent, Total

Travel Distance and Total Input Volume were introduced. They are often combined with some additional terms that penalize abrupt variations in ramp metering and speed limiting signals [START_REF] Hegyi | Optimal coordination of ramp metering and variable speed control-an mpc approach[END_REF]. General objectives such as congestion, pollution, and energy reduction are also in order [27][28].

Chapter 1. Introduction

Comprehensive studies on infinite dimensional optimization can be found in the excellent books of Lions [START_REF] Lions | Optimal Control of Systems Governed by Partial Differential Equations[END_REF], Fattorini [START_REF] Fattorini | Infinite Dimensional Optimization and Control Theory[END_REF]. Optimal control problems over a finite time horizon for hyperbolic dynamical systems are investigated in the book of Lasiecka and

Triggiani [START_REF] Lasiecka | Control Theory for Partial Differential Equations[END_REF]. For the traffic optimization, Jacquet et. al in [START_REF] Jacquet | Optimal control of scalar one-dimensional conservation laws[END_REF], [START_REF] Jacquet | Optimal control of systems of conservation laws and application to non-equilibrium traffic control[END_REF] and [START_REF] Jacquet | Optimal ramp metering strategy with an extended lwr model: Analysis and computational methods[END_REF] based on the theory of nonlinear hyperbolic partial differential equations and calculus of variations.

To evaluate gradients for the optimization procedure, the authors suggested to introduce the adjoint system by using the weak formulation of the conservation law. In [START_REF] Li | Optimal control of scalar conservation laws using linear/quadratic programming: Application to transportation networks[END_REF], Li et. al used an equivalent to conservation law formulation based on a Hamilton-Jacobi equation.

By using piecewise representation of density-flow relations, the authors posed a finite time horizon problem of controlling the traffic state on a network link as a Linear Program.

Most of the optimal control policies in freeway traffic are based on the optimization of discrete (in space and time) macroscopic models. Zhang et. al [START_REF] Zhang | Some general results on the optimal ramp control problem[END_REF] proposed to optimize a finite difference representation of the continuum LWR model. The suggested difference scheme depends on the traffic wave directions, and, as it was reported, it is stable and capable of capturing shocks. Proposed by the authors optimal control solution was based on the Pontryagin Maximum Principle. It was shown that if the optimal ramp metering problem is linear in the objective function and the state equation, and the set of admissible controls is determined by box constraints, then the optimal controls are of the bang-bang type. Gomes and Horowitz [START_REF] Gomes | Optimal freeway ramp metering using the asymmetric cell transmission model[END_REF] proposed to optimize the assymetric Cell Transmission

Model. The formulated optimal control problem captures both free flow and congested conditions, and takes into account upper bounds on the metering rates and on the on-ramp queue lengths. It was shown that under certain conditions a near-global solution to the resulting nonlinear optimization problem can be found by solving a single linear program.

In [START_REF] Muralidharan | Optimal control of freeway networks based on the link node cell transmission model[END_REF], Muralidharan and Horowitz performed the optimization on the link-node Cell Transmission Model. The suggested approach searches for solutions represented by a combination of ramp metering and variable speed control. The corresponding nonlinear problem was relaxed to a linear program. Then, the authors presented an approach to map the solution of the linear optimization to the solution of the original optimal control problem. They also proved that the solution derived from this approach is optimal for the original optimal control problem.

The optimal freeway controllers are usually implemented through the centralized architectures (see, for example, [START_REF] Jacquet | Optimal control of systems of conservation laws and application to non-equilibrium traffic control[END_REF]). The optimization methods used in such architecture suffer from a lack of scalability. The computational time increases exponentially with the size of the system, and thus the tractable length of freeway is usually limited to several kilometers. Moreover, the centralized optimization solvers require permanent and complete state information and this may not be attainable due to numerous package loses.

These issues are faced by implementing distributed optimization methods. A dual decomposition method was proposed by Sun et al. in [START_REF] Sun | A dual decomposition method for sector capacity constrained traffic flow optimization[END_REF] to control the traffic flow in the 1.4. Contributions airspace system. Distributed controller's architecture in freeway traffic flow control was investigated by Ferrara et al. in [START_REF] Ferrara | Freeway networks as systems of systems: an event-triggered distributed control scheme[END_REF], where the authors isolated freeway clusters and defined collaborative mechanisms to achieve a desired performance of the overall system.

Distributed and centralized model predictive control schemes for freeway traffic control were compared in [START_REF] Frejo | Global versus local mpc algorithms in freeway traffic control with ramp metering and variable speed limits[END_REF]. The authors demonstrated that a distributed controller exhibits the performance comparable with a centralized one, and it is less sensitive to model uncertainties. In this paper, based on the Nash game formulation, we will design a distributed optimal controller to regulate freeway traffic flow. The major contribution is the establishment of the dynamically adapting system division allowing for efficient solution of the distributed optimization problem.

Contributions

The list presented below summarizes the major contributions of this thesis:

• Introduction of the density balancing as a new freeway traffic objective, supported with physical interpretation,

• Analysis on the set of equilibrium points for Cell-Transmission Model in the context of balanced states,

• Design of the optimal balanced equilibrium points,

• Definition of the dynamical scheme of the system partitioning for the distributed optimization problem,

• Solution of the Nash game problem by decomposition into two-player Stackelberg (leader-follower) and competitive games,

• Definition of the consensus protocols for the freeway traffic links,

• Derivation of the state feedback control structures to provide consensus protocols,

• Microscopic validation of the designed control method.

The main contributions have been published in the following papers:

Thesis structure

The structure of the thesis is organized as follows (see also Fig. 1.4):

Chapter 2. Macroscopic Representation of the Freeway Traffic.

In this part, the fundamental mathematical models of the freeway traffic will be presented.

We will begin with a continuum model represented by the scalar conservation law. Then, we will move toward a discrete model upon which the control methodology, developed in the sequel of the thesis, will be based. A special attention will be put to the models of merging flows.

Chapter 3. Analysis on the Sets of Equilibrium Points for the Cell-Transmission

Model.

This chapter is to analyse the structures of steady states for a freeway system represented by the Cell-Transmission Model. The analysis will be carried on the the context of balanced states. The first task will be to derive conditions that assure the existence and the uniqueness of balanced equilibrium states. The next step will be to find a set of control inputs such that the resulting equilibrium state is balanced and it maximizes the Total Travel Distance. In the sequel, we will implement numerically the idea of optimal state balancing. We will discuss the major aspects and limitations of this implementation. We will introduce a mathematical representation of the part of the south ring of Grenoble.

We will also study in brief a method for calibration of the merging parameter. Finally, we will present several case studies to support the analysis results and to examine the effectiveness of the proposed idea.

Chapter 4. Optimal Control in Traffic Engineering.

This chapter studies the fundamental optimal control techniques in applications to freeway traffic problems. At first, the finite horizon optimal control problem will be formulated.

Basic solution properties and the necessary optimality condition will be given. In the sequel, we will study a general problem of optimal control for the Cell-Transmission Model.

The last section will be to introduce the idea of distributed optimization via solving a Nash game. This idea will be brought into traffic system in the control design presented within In this chapter, a design of a distributed optimal control method for balancing of freeway traffic density will be presented. The optimization will be performed in a distributed manner by utilizing the controllability properties of the freeway network represented by the Cell Transmission Model. By using these properties, we will identify the subsystems to be controlled by local ramp meters. The optimization problem will be then formulated as a non-cooperative Nash game as introduced in the Chapter 4. The game will be solved by decomposing it into a set of two-players hierarchical and competitive games. The process of optimization will employ the communication channels matching the switching structure of system interconnectivity. By defining the internal model for the boundary flows, local optimal control problems will be efficiently solved by utilizing the method of Linear Quadratic Regulator. The developed control strategy will be tested via numerical simulations on the macroscopic model in two scenarios for uniformly congested and transient traffic. The validation with the use of the microscopic simulator will be presented in the Chapter 7. Throughout this chapter, we will use the Cell-Transmission Model as introduced in the Chapter 2.

Chapter 6. Freeway Density Balancing via Consensus Protocols.

This parts will present an alternative approach of freeway density balancing. The approach Chapter 1. Introduction will utilize the consensus protocols. It will adopt the solution method of the distributed game problem presented in the Chapter 5. The difference will be at the level of the local optimal control problems. Here, instead of minimizing the balancing metric, we will design feedback control structures providing that the states in the local subsystems achieve common values by evaluating consensus protocols. Under these structures, we will formulate an optimal control problem to minimize the Total Travel Spent. The chapter will present only the methodology. Implementation and validation are dedicated for future works.

Chapter 7. Balancing of the Freeway Traffic Density: Microscopic Validation.

The aim of this chapter is to examine the control method presented in the Chapter 5.

A performance of the designed optimal density balancing will be tested through the simulations carried on with the use of Aimsun micro-simulator. A case study will involve real traffic data collected on the south ring of Grenoble. At first, we will discuss the implementation aspects. In particular, we will focus on the setting of the distributed controller by describing the functionality of the single modules. Next, we will verify the efficiency of the control method by comparison to uncontrolled (open-loop) case. Firstly, we will examine the optimized metrics, i.e., the balancing and the travelling time metrics. In the sequel, a number of non-optimized traffic measures will be verified.

CHAPTER 2

Macroscopic Representation of the Freeway Traffic

In this chapter, the fundamental mathematical models of the freeway traffic will be presented. We will begin with a continuum model represented by the scalar conservation law. Then, we will move toward a discrete model upon which the control methodology, developed in the sequel of the thesis, will be based. A special attention will be put to the models of merging flows. The chapter will complete a state-space model representation together with the establishment of the control input constraints.

The Lighthill-Whitham-Richards Model

The simplest continuum model of the traffic flow was developed by Lighthill and Whitham [START_REF] Lighthill | On kinematic waves ii: A theory of traffic flow on long crowded roads[END_REF] and Richards [START_REF] Richards | Shockwaves on the highway[END_REF]. This first order model, referred later as LWR, is based on the scalar vehicle conservation law. A freeway section stretched between the points y1 and y2. The inflow and the outflow are denoted by φ(y1, t) and φ(y2, t), respectively. The density inside the section is described by the distribution ρ(y, t).

The conservation of vehicles states that the rate of change in the number of vehicles is equal to the difference between inflow and outflow.

Thus, the conservation law (2.1) can be represented in the form of the partial differential equation:

∂ t ρ(y, t) + ∂ y φ(y, t) = 0 . (2.3)
By introducing the distribution of the flow velocity v(y, t), the traffic flow is given by: φ(y, t) = ρ(y, t)v(y, t) .

(2.4)

It is assumed that the drivers adjust their velocity with respect to the density. The relation between v and ρ may be given in a differential form:

v = V (ρ) (2.5)
or in an algebraic form:

v = V (ρ) . (2.6)
The model utilizing the dynamical relation (2.5) was first proposed by Payne in [START_REF] Payne | Models of freeway traffic and control[END_REF]. LWR model is stated under the static relation (2.6) assuming that vehicles tend to travel at an equilibrium speed for all locations and all times. In another words, there is lack of inertia in the speed adjustment. Based on this assumption, the flow (2.4) can be represented by: φ(y, t) = Φ(ρ(y, t)) .

(2.7)

Then, LWR model is written as follows:

∂ t ρ + ∂ y Φ(ρ) = 0 . (2.8)
In the traffic engineering, the relation Φ(ρ) is called the Fundamental Diagram, and it is assumed to be concave. In the literature, there is a variety of functions describing the Fundamental Diagram. By introducing the free flow speed v f and the jam density ρ, Greenshield (GS) [START_REF] Greenshield | A study of traffic capacity[END_REF] and Greenberg (GB) [START_REF] Greenberg | An analysis of traffic flow[END_REF] (see Fig. 2.2a) proposed:

Φ GS (ρ) = ρ v f - ρ 2 v f ρ , Φ GB (ρ) = ρ v f ln ρ ρ .
(2.9)

Commonly used are also piece-wise linear diagrams given in the triangular or trapezoidal (see Fig.

Solution methods

From the mathematical point of view, LWR model (2.8) is represented by non-linear scalar partial differential equation of hyperbolic type. In the simplest case, when over a considered section length the flow is such that ∂ y Φ(ρ) = a ∂ y ρ (a-constant), the model can be rewritten in the following linear form:

∂ t ρ + a ∂ y ρ = 0 . (2.10)
Now suppose we are given the initial condition ρ(y, 0). Solution to (2.10) can be obtained analytically by applying the method of characteristics [START_REF] Evans | Partial Differential Equations[END_REF]. The method yields:

ρ(y, t) = ρ(y -at, 0) . (2.11)
The solution (2.11) represents wave travelling downstream (if a > 0) or upstream (if a < 0). This fact will be utilized in the Chapter 5 in the analysis on the controllability.

Among the numerical schemes suitable for solving (2.8), one of the most common in use is the Godunov method [START_REF] Godunov | A difference method for the numerical calculation of discontinuous solutions of hydrodynamic equations[END_REF]. The Godunov scheme predicts correctly the propagation of shock waves avoiding oscillating behaviours. The method is based on solving Riemann problems forward in time. Solutions to Riemann problems are relatively easy to compute and lead to conservative methods. In the Godunov scheme, a space region is divided into set of finite volumes of the length ∆y i . Let us assume that the volume i is located between the coordinates y i-1/2 and y i+1/2 . Then, the density inside each a volume i at time t is represented by the following average:

ρ i (t) = 1 ∆y i y i+1/2 y i-1/2
ρ(y, t) dy .

(2.12)

By integrating (2.8) over spacial interval [y i-1/2 , y i+1/2 ], we obtain:

ρi (t) = 1 ∆y i Φ(ρ(y i-1/2 , t) -Φ(ρ(y i+1/2 , t)) . (2.13)
Let us now introduce the discrete time t(k) = k ∆t with the step ∆t. The exact time integration of (2.13) yields to the following density update:

ρ i (k + 1) = ρ i (k) + 1 ∆y i t(k+1) t(k) Φ(ρ(y i-1/2 , t) -Φ(ρ(y i+1/2 , t)) dt . (2.14)

Chapter 2. Macroscopic Representation of the Freeway Traffic

The Godunov scheme applies the Forward Euler method that reduces (2.14) into full discrete form:

ρ i (k + 1) = ρ i (k) + ∆t ∆y i Φ(ρ(y i-1/2 , k)) -Φ(ρ(y i+1/2 , k)) . (2.15)
The values of the intermediate densities ρ(y i-1/2 , k) and ρ(y i+1/2 , k) are obtained by solving the local Riemann problem:

(2.8) under ρ(y, k) =    ρ i-1 (k) if y < y i-1/2 ρ i (k) if y > y i-1/2
(2.16) and

(2.8) under ρ(y, k) =    ρ i (k) if y < y i+1/2 ρ i+1 (k) if y > y i+1/2 , (2.17)
respectively. By introducing the speed of the shock wave corresponding to the interface between the cells i -1 and i:

s(k) = Φ(ρ i (k)) -Φ(ρ i-1 (k)) ρ i (k) -ρ i-1 (k) , (2.18)
under a concave relation Φ(ρ), solution to (2.16) is as follows:

ρ(y i-1/2 , k) = ρ i-1 (k) if ∂ ρ Φ(ρ i-1 (k)) ≥ 0 , ∂ ρ Φ(ρ i (k)) ≥ 0 , ρ(y i-1/2 , k) = ρ i (k) if ∂ ρ Φ(ρ i-1 (k)) < 0 , ∂ ρ Φ(ρ i (k)) < 0 , ρ(y i-1/2 , k) = ρ i-1 (k) (s > 0) or ρ i (k) (s < 0) if ∂ ρ Φ(ρ i-1 (k)) ≥ 0 , ∂ ρ Φ(ρ i (k)) < 0 , ρ(y i-1/2 , k) = ρ s (k) if ∂ ρ Φ(ρ i-1 (k)) < 0 , ∂ ρ Φ(ρ i (k)) ≥ 0 . (2.19)
Here in the last case we observe the transonic rarefaction with the sonic point ρ s (see [START_REF] Leveque | Numerical Methods for Conservation Laws[END_REF]). Solution to (2.17) is carried on in analogous way.

The Cell-Transmission Model

In the control design, we will utilize the Cell-Transmission Model (CTM) proposed by Daganzo [START_REF] Daganzo | The cell transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory[END_REF]. The model can be perceived as the Godunov scheme for (2.8) under the assumption that the Fundamental Diagram is given in a triangular form presented in Fig. 2.3.

According to CTM, a freeway is represented as a sequence of n cells as demonstrated in Fig. 2.4. Each cell is assumed to have at most one on-ramp and one off-ramp. The total number of on-ramps is m. The on-ramp demands are assumed to be controlled parameters. Throughout this thesis, we assume the same number of lanes for each cell. The following notation for the Cell-Transmission Model will be used:

CTM notation ρ [veh/km] -
L [km] -cell length. S D ρ 1 φ 1 φ 2 ρ n φ n+1 s 1 s n l 2 u 2 r 2 u m l m ρ 2 r m φ n r 1 u 1 l 1 D1 D2 Dm

The governing equation

Let i = 1, 2, ..., n and j = 1, 2, ..., m be the index for the cells and on-ramps, respectively.

We associate each on-ramp flow r j to the cell i according to a freeway architecture. Then, the evolution of the Cell-Transmission Model is described by the following difference equations:

ρ i (k + 1) = ρ i (k) + ∆t L i [φ i (k) + r j (k) -φ i+1 (k) -s i (k)] , i = 1, 2, ..., n , l j (k + 1) = l j (k) + ∆t Dj (k) -r j (k) , j = 1, 2, ..., m , (2.20)
where the initial state:

ρ i (k = 0) , l j (k = 0) (2.21)
is given for all i and all j. Time step ∆t between instants k and k + 1 must be taken to fulfil the stability condition of the numerical scheme. The condition is referred as the Courant-Friedrichs-Lewy condition [START_REF] Courant | On the Partial Differential Equations of Mathematical Physics[END_REF]. It applies to finite difference schemes for wide class of systems of hyperbolic type exhibiting wave-like behaviours. The principle behind the condition is that if a wave is moving across a discrete spatial grid and we are willing to compute its amplitude at discrete time steps of equal length, then this length must be less than the time for the wave to travel to adjacent grid points. In the case of the CTM, the Courant-Friedrichs-Lewy condition is given as follows:

v i ∆t L i ≤ 1 for all i . (2.22)
In general, the Courant-Friedrichs-Lewy is only the necessary condition. For CMT, it is also the sufficient one (for details see [START_REF] Leveque | Numerical Methods for Conservation Laws[END_REF]).

Throughout this thesis, a cell i will be said to be in the free flow state if ρ i ≤ ρ cr i . Otherwise, it will be said to be in the congested state.

The models of merging flows

Before giving the explicit formulas for φ, r and s in (2.20), a few facts on the existing models for merging and diverging of traffic flows will now be recalled. Unlike in the case of diverging, where the widely accepted is the hypothesis that the flow entering the off-ramp is a portion of the total flow leaving the section, merging phenomenon is much more challenging to describe. A variety of merge models have been introduced and used in traffic control design. A brief review is given below.

Let us first introduce Demand D i and Supply S i functions:

D i (k) = min βi v i ρ i (k), F i , S i (k) = min {w i (ρ i -ρ i (k)), F i } . (2.23)
Here the split ratio parameter βi is defined as βi = φ i+1 /(φ i+1 + s i ). D i corresponds to the traffic volume willing to enter a cell i + 1. S i can be interpreted as the amount of (2.26)

In [START_REF] Newell | A simplified theory on kinematic waves in highway traffic part i, ii and iii[END_REF], Newel proposed analogous to Daganzo model with the assumption that on-ramp vehicles can always enter the mainstream. Newel model is represented by (2.25), (2.26) by setting full priority for the on-ramp demand, i.e. by setting p = 1.

As demonstrated above, oversimplified merge models can reproduce unrealistic situations, where the sum of upstream flows is allowed to exceed downstream supply or the Chapter 2. Macroscopic Representation of the Freeway Traffic whole on-ramp demand can enter a freeway. Sophisticated models, which for example take into account the dynamics of cars entering a mainline (see, for instance, [START_REF] Leclercq | Capacity drops at merges: An endogenous model[END_REF]), are very challenging for tuning and applying to optimal control design. The Daganzo model

(2.25), (2.26) is a good compromise between accuracy and complexity, and will be used throughout this thesis in the control design. The study on how to determine the merging parameter p will be presented in the chapter 3.

Let us now write down the Daganzo merge model for our CTM setting. We define the function mid {•} that returns the middle value, i.e. for example mid {a, b, c} = a if b ≤ a ≤ c or c ≤ a ≤ b . Then, the flows φ and r in (2.20) are computed as below:

if D i-1 (k) + u j (k) ≤ S i (k) : φ i (k) = D i-1 (k) , r j (k) = u j (k)
otherwise :

φ i (k) = mid {D i-1 (k), S i (k) -u j (k), (1 -p j ) S i (k)} , r i (k) = mid {u j (k), S i (k) -D i-1 (k), p j S i (k)} .
(2.27)

In case of the absence of on-ramp, the mainstream flow is computed as follows:

φ i (k) = min {D i-1 (k), S i (k)} . (2.28)
For the off-ramp flows s, we assume:

s i (k) = 1 -βi βi φ i+1 (k) .
(2.29)

State space representation, the bounds of the state and the control input

For convenience of the further studies we will rewrite the governing equation of CTM in a state-space form. By introducing the state vector:

x = [ρ 1 , ρ 2 , ..., ρ n , l 1 , l 2 , ..., l m ] ⊺ (2.30)
and taking on-ramp demands as the controlled input vector:

u = [u 1 , u 2 , ..., u m ] ⊺ (2.31)
we can represent the governing equation (2.20) in the form of a switched system:

x(k + 1) = x(k) + ∆t (A s x(k) + B s u(k) + C s (k)) , s = s(x(k), u(k)) , s ∈ S .
(2.32)

The variable s switches the system mode according to the laws given in (2. The state space X ⊂ R n+m is non-negative and it is upper bounded by the storage capacities of the mainstream and on-ramp lanes, i.e. for the states representing vehicle densities the bound is equal to the jam density ρ while the states corresponding to the queue lengths must not exceed the storage capabilities of the on-ramps lj :

0 ≤ x i ≤ ρ , i = 1, 2, ..., n , 0 ≤ x i ≤ lj , i = n + 1, n + 2, ..., n + m , j = i -n .
(2.33)

To determine the set of the admissible controls U ⊂ R m , we need to take a closer look on its physical constraints. The on-ramp vehicles flow in only one direction, and thus the controlled on-ramp demand must not be negative. For the upper bound, the requirement is that the controlled demand at each time step can not exceed the so called virtual demand denoted here by u max . Thus, we have:

0 ≤ u j (k) ≤ u j max (k) , j = 1, 2, ..., m , k = 1, 2, ... . (2.34)
The virtual demand results from the external on-ramp demand and the flow produced by the queueing vehicles (see Fig. 2.6). Commonly used formula (see, for example, [START_REF] Zhang | Some general results on the optimal ramp control problem[END_REF]) for the virtual demand is given by:

u j max (k) = Dj (k) + 1 ∆t l j (k) . (2.35)
The weak points of the formula (2.35) emerge in the cases of short time step ∆t. It is assumed that all vehicles can be served into mainstream during the time period [0, ∆t]. This is clearly not feasible, if the queue is long enough. The flows produced by the external demand and the queuing vehicles are assumed enter a freeway simultaneously, which is also not realistic. Below, an alternative formulation of the virtual demand will be proposed. It will be based on simple dynamics capturing vehicle accumulation in a queue and respecting realistic vehicle insertion of vehicles from a queue into mainstream.

Let us consider the following setup. A time interval for which we want to compute

u max is [0, ∆t].
We assume that we posses the information of both, the initial number of vehicles in the queue l(t = 0) and the external demand D, measured in some reasonable Chapter 2. Macroscopic Representation of the Freeway Traffic distance behind the queue. It is also assumed that D is constant for the considered time interval and it does not exceed the capacity of the on-ramp. By ∆t ′ we will denote the time needed to allocate l(t = 0) vehicles from queue into mainstream. For simplicity we can approximately assume:

∆t ′ = l(t = 0) φ q , (2.36)
where φ q stands for the estimated flow produced by the queuing vehicles. Depending on time ∆t ′ , we can distinguish the following three cases:

Case 1: ∆t ′ = 0 meaning that there is no queuing vehicles, and therefore the virtual demand u max is simply equal to the external demand.

Case 2: ∆t ′ ≥ ∆t corresponds to the situation, where the virtual demand is created only by the vehicles queuing on-ramp.

Case 3: Finally, if 0 < ∆t ′ < ∆t, then the virtual demand results from both vehicles queuing on-ramp and the external demand. We introduce here ∆t ′′ -the time needed to remove the whole queue into mainstream. Since D > 0, vehicles feed the queue, and thus ∆t ′′ > ∆t ′ . To determine ∆t ′′ , we can use the vehicle conservation law. In this case, we have:

0 = l(t = 0) + ∆t ′′ 0 D -φ q dt (2.37)
and thus:

∆t ′′ = l(t = 0) φ q - D , (2.38)
where it is assumed that φ q -D > 0.

Summarizing the cases 1-3, the virtual demand for (2.34) can be computed as follows:

u j max (k) =            Dj (k) if ∆t ′ (k) = 0 , φ q if ∆t ′ (k) ≥ ∆t , φ q ∆t ′′ (k) ∆t + Dj (k) 1 - ∆t ′′ (k) ∆t if 0 < ∆t ′ (k) < ∆t , (2.39)
where:

∆t ′ (k) = l j (k)/φ q and ∆t ′′ (k) = l j (k)/(φ q -Dj (k)).
CHAPTER 3

Analysis on the Sets of Equilibrium Points for the Cell-Transmission Model

This chapter is to analyse the structures of steady states for a freeway system represented by the Cell-Transmission Model. The results presented here can be perceived as selfcontained. In particular, the design of the optimal steady states can be treated as a starting point for a development of a controller stabilizing the system around a designed set point. This type of controllers are not in the scope of this thesis. Nevertheless, the presented here analysis on structures of equilibrium states will bring crucial information on the feasibility and optimality of optimal control strategies studied within the following chapters.

Introduction

The part of work presented here aims at characterizing equilibrium points for a freeway system in view of the density balancing, but also to find conditions under which this balancing may be possible. An extensive analysis on the steady states in freeway traffic was already presented in [START_REF] Gomes | Behavior of the cell transmission model and effectiveness of ramp metering[END_REF]. By using the Cell-Transmission Model the authors proved that the freeway traffic is open-loop stable system, i.e. for every fixed boundary condition and fixed control input the system converges to some equilibrium state. They also showed that in general this equilibrium state may not be unique. These results are crucial for our studies on balanced steady states.

In this chapter, a method for a design of balanced steady states on a freeway will be presented. Our first task is to derive conditions that assure the existence and the uniqueness of balanced equilibrium states. The next step is to find a set of control inputs such that the resulting equilibrium state is balanced. For the set of balanced equilibria, we are interested in the selection of the point that maximizes the Total Travel Distance. It will be shown that for a steady state the optimizer of the Total Travel Distance can be regarded

Chapter 3. Analysis on the Sets of Equilibrium Points for the Cell-Transmission Model

as an equivalent to the optimizer of the commonly used in traffic objective where the Total Travel Distance is weighted with the Total Travel Time. The optimal balanced state together with the corresponding input can be used as the set point for a design of robust closed-loop system. In the sequel, we will implement numerically the idea of optimal state balancing. We will discuss the major aspects and limitations of this implementation. We will introduce a mathematical representation of the part of the south ring of Grenoble.

We will also study in brief a method for calibration of the merging parameter. Finally, we will present several case studies to support the analysis results and to examine the effectiveness of the proposed idea of balancing.

The author contributions related to this chapter were presented in the papers [START_REF] Pisarski | Analysis and design of equilibrium points for the celltransmission traffic model[END_REF][57] [START_REF] Pisarski | Optimal balancing of traffic density: Application to the grenoble south ring[END_REF].

Set of equilibrium points for the Cell-Transmission Model

Throughout this chapter, we will consider CTM as demonstrated in Fig. 3.1. In comparison to the model presented in the Chapter 2, here we omit the queues. The state of the system is now represented by the vector:

x = [ρ 1 , ρ 2 , ..., ρ n ] ⊺ . (3.1)
The governing equation preserves the previous form:

x(k + 1) = x(k) + ∆t A s(k) x(k) + B s(k) u(k) + C s(k) (k) , s(k) = f (x(k), u(k)) , s ∈ S . (3.2)
This section is to define a convenient representation of sets of equilibrium points for CTM.

Introduced here forms will be used later for the analysis and the optimization. We begin with a formal definition:

Definition 3.2.1
The equilibrium set ∆ for CTM described by (3.2) is a set of pairs (x * , u * ) that under fixed boundary conditions solve the following equilibrium equation:

A s x * + B s u * + C s = 0 , s = f (x * , u * ) , s ∈ S . (3.3) S D ρ 1 φ 1 φ 2 ρ n φ n+1 s 1 s n u 2 r 2 u m ρ 2 r m φ n r 1 u 1 Figure 3.1:
The Cell-Transmission Model used in the studies on equilibrium points.

Set of equilibrium points for the Cell-Transmission Model 25

Notice that vectors C s become constant, when boundary conditions have fixed values, i.e.: D(k) = D and S(k) = S. Physically, a steady state is reached when for every cell, the total flow entering and leaving are equal. By ∆ x and ∆ u we denote the set of equilibrium density and equilibrium on-ramp demand, respectively.

Remark 3.2.1

Notice that if we included queues to the state vector, then according to (2.20) the steady state would be uniquely determined by the external on-ramp demand D. In that case, the analysis on the one element set ∆ would become trivial.

We will now show how ∆ can be described by introducing a relevant set of inequalities.

First, we decompose ∆ into subsets that correspond to the modes of the system. For every mode s ∈ S we define the following set:

∆ s = {(x * , u * ) : A s x * + B s u * + C s = 0 , s = f (x * , u * )} . (3.4)
We have:

∆ = m s=1 ∆ s . (3.5)
The function f results from min{•} and mid{•} terms in (2.23) and in the merging model (2.25), (2.26). Therefore, by introducing a relevant set of inequalities, we can rewrite every ∆ s as follows:

∆ s = {(x * , u * ) : A s x * + B s u * + C s = 0 , K s x * + M s u * + N s ≤ 0} . (3.6)
The matrices K s , M s and the vector N s are constant and of size resulting from the conditions that identify mode s. To illustrate how to build the representation (3.6), we give below an example for the case of a two-cell system. We consider the mode s = 1 that corresponds to the following traffic situation:

D + u * 1 ≤ S 1 , D 1 + u * 2 ≤ S 2 , D 2 ≤ S (3.7)
Then, by using (2.25), (2.26) we write the equilibrium equation as follows:

D + u * 1 = 1 β1 D 1 , D 1 + u * 2 = 1 β2 D 2 . (3.8) Model
For the case of free flow (v i x * i ≤ F i ) we have D i = v i x * i and S i = F i . Therefore, we obtain:

∆ 1 = {(x * , u * ) : -v 1 0 β1 v 1 -v 2 x * 1 x * 2 + 1 0 0 1 u * 1 u * 2 + D 0 = 0 ,          w 1 0 β1 v 1 w 2 0 β2 v 2 v 1 0 0 v 2          x * 1 x * 2 +          1 0 0 1 0 0 0 0 0 0          u * 1 u * 2 +          D -w 1 ρ1 -w 2 ρ2 - S -F 1 -F 2          ≤ 0} .
(3.9)

Let us now recall an important property of the relation between the sets ∆ x and ∆ u .

In the paper [START_REF] Gomes | Behavior of the cell transmission model and effectiveness of ramp metering[END_REF], it was shown that in general the mapping ∆ u -→ ∆ x is not one-toone. The authors provided an example, where for some fixed input demand the resulting equilibrium vehicle density was not a single point. It was represented by a set of points instead. For such a case, a design of a desired equilibrium is not feasible, since a steady state may depend on the initial state. In this work, we will consider only the modes for which a fixed input demand results in a unique equilibrium vehicle density. Therefore, according to the previous definition, we will consider the modes for which the matrices A s are invertible.

The problem of steady states balancing

In this section, we will characterize the set of balanced steady states and formulate a related balancing problem. Let us first introduce the set of admissible balanced vehicle density:

C = c : 0 ≤ c ≤ min{ρ i } n-1 i=0 . (3.10)
By a balanced traffic state we mean a distribution of vehicle density such that its values stay as close as possible to some c ∈ C for a whole considered part of a freeway (see Fig.

3.2)

. Formal definition of balanced equilibria for CTM can be written as follows:

Definition 3.3.1
The set of balanced equilibria ∆ B is a set of points (x * , u * ) ∈ ∆ such that for some norm • :

(x * , u * ) = argmin x -c1 , c ∈ C . (3.11)
Here 1 stands for all-ones vector. In particular, we will say that a steady state is exactly balanced if x * = c1. By analogy to the set ∆, we denote by ∆ xB and ∆ uB the set of balanced equilibrium densities and the set of corresponding input demands, respectively. We formulate the problem of balancing of traffic steady states as follows:

Problem 3.3.

(Steady state balancing problem)

For a fixed boundary condition find a set of on-ramp demands such that the resulting steady state is balanced (According to the Definition 3.3.1, we search for the points u * ∈ ∆ uB ).

The remaining is the choice for the number c. This number should be selected so that the state c1 optimizes the traffic with some relevant objective. The commonly used objective trades-off between maximization of the Total Travel Distance (TTD) and minimization of the Total Travel Time (TTT) (see, for example, [START_REF] Gomes | Optimal freeway ramp metering using the asymmetric cell transmission model[END_REF]). Below, we will establish a reasonable selection for the weighting parameter for this trade-off when the system operates on the steady states.

Consider the objective function to be minimized given as follows:

J = α (-TTD) + (1 -α) TTT , (3.12)
where α ∈ [0, 1]. For the total freeway length n i=1 L i and for some time interval T , TTD and TTT are defined as follows:

TTD = n i=1 L i 0 T 0 φ(y, t)dy dt , TTT = n i=1 L i 0 T 0 ρ(y, t)dy dt . (3.13)
Here, as in the Lighthill-Whitham-Richards model, presented in the Chapter 2, φ(y, t)

and ρ(y, t) respectively stands for the space-time distribution of flow and vehicle density.

Note that in (3.13) we take into account only the total travel time incurred by drivers during their travel on mainstream while the queuing time (computed based on the queue lengths) is omitted on purpose. This is due to the fact that in order to formulate our

Chapter 3. Analysis on the Sets of Equilibrium Points for the Cell-Transmission Model

optimization problem, we need to represent (3.13) for the steady states. If we took the state vector composed of both mainstream vehicle density and queue lengths, then the steady state would be uniquely determined by the external on-ramp demands, and thus optimization problem would become trivial. The queuing time can be indirectly reduced by the maximization of the on-ramp service. This in turn corresponds to the maximization of the mainstream flow that determines the supply for on-ramp flows. Therefore, we can assume that TTD compensates the omitted queuing time term.

For a steady state ρ * (y) the objective function (3.12) is represented by:

J = -α T n i=1 L i 0 Φ(ρ * (y))dy + (1 -α) T n i=1 L i 0 ρ * (y)dy . (3.14)
Here for every point y the relation Φ(ρ * (y)) is assumed according to the Fundamental Diagram (Fig. 2.3). Let us consider the solution to (3.14) for a single cell. If this cell is a b in the free flow state, then TTD and TTS terms are antagonistic and the solution depends on the choice of the weighting parameter α as depicted in Fig. 3.3a. However, there is no rationality supporting the idea of reducing density while the system operates in the free flow mode and the most fair selection for α is such that maximizes the flow, i.e. α = 1.

Φ(ρ) Φ(ρ) α → 0 ρ cr ρ cr ρ ρ α → 1 α ∈ [0, 1]
In the congested state, the maximization of flow and the minimization of density are the mutual objectives. In this case, the optimal state for (3.14) is independent of the choice of α and it is equal to the critical density (see Fig. 3.3b). From this simple analysis, it follows that for a single cell the objective (3.14) can be reduced to the term that maximizes the traffic flow. Concerning the global system instead of a single cell, a similar analysis would be much more complicated, since the objective function is not separable. However, we can reasonably assume α = 1. Consequently, in the sequel the number c will be selected such to maximize the Total Travel Distance. The pair (x * , u * ) that corresponds to such a selection will be called the optimal equilibrium point.

The exactly balanced steady states 29

The exactly balanced steady states

In this section, we study the structure of the set ∆ in terms of the model parameters. The goal is to derive the conditions that guarantee the existence of exactly balanced equilibria. The analysis will be performed for the mode of the system that corresponds to the case, where all cells are in the free flow state. As will be shown later, this mode provides that the system is fully actuated and eligible for design of the exactly balanced equilibria. In the other modes, the system is supposed to be balanced in the sense given by Definition 3.3.1, i.e. by performing corresponding optimization problem. This study will be presented in the section 3.5.

Fully Actuated Free Flow Mode

We investigate the system mode that provides one-to-one relation between the sets ∆ x and ∆ u . This mode is of our special interest for two reasons: it provides unique steady-states, it enable us to derive compact formulas for computing the points u * ∈ ∆ uB . To hold one-to-one property, we require for both matrices A s and B s to be invertible. By checking the Daganzo merge model (2.27), we can observe that the matrix B s is invertible iff the following conditions are satisfied:

D + u * 1 ≤ S 1 , D i-1 + u * i ≤ S i , i = 2, 3, ..., n . (3.15)
Under this assumption the equilibrium equation in (3.3) is represented by:

D + u * 1 = 1 β1 D 1 , D i-1 + u * i = 1 βi D i , i = 2, 3, ..., n -1 , D n-1 + u * n = 1 βn min D n , S (3.16)
To ensure the invertibility of A s , we need to impose additional conditions, i.e.:

D n ≤ S , βi v i x * i ≤ F i , i = 1, 2, ..., n .
(3.17)

Under (3.17) we can now rewrite the system (3.16) as follows: Proof. From (3.17) we have:

D + u * 1 = v 1 x * 1 , βi-1 v i-1 x * i-1 + u * i = v i x * i , i = 2, 3, ..., n .
D n ≤ S . (3.20)
Inserting D n by using the system (3.16) we obtain:

βn D n-1 + βn u * n ≤ S . (3.21)
Repeating this substitution from D n-1 to D 1 we obtain (3. [START_REF] Papamichail | Hero coordinated ramp metering implemented at the monash freeway[END_REF]).

The condition:

βi v i x * i ≤ F i , i = 1, 2, ..., n . (3.22)
is satisfied for the case, where all cells are in the free flow mode (v i x * i ≤ F i for all i). To see this, we recall the assumption βi ≤ 1. Then, we can write:

βi v i x * i ≤ v i x * i ≤ F i , i = 1, 2, ..., n . (3.23)
Finally, based on (3.15), (3.17) and (3.23) can formulate the sufficient condition under which the equilibrium equation is described by the mapping Γ.

Proposition 3.4.2. Let x * be some equilibrium state for the free flow state. Then, there exist the mapping Γ if the following conditions hold:

D + u * 1 ≤ F 1 , βi-1 v i-1 x * i-1 + u * i ≤ F i , i = 2, 3, ..., n , βn v n x * n ≤ S .
(3.24)

Remark 3.4.1

For the design of the exactly balanced equilibria, we will consider only the case where all cells are in the free state. As it was shown in the paper [START_REF] Pisarski | Analysis and design of equilibrium points for the celltransmission traffic model[END_REF], for the congested states, the conditions (3.15)-(3.17) drive to contradiction. As a result, the congested states stay underactuated, and thus the exact balancing may not be feasible.

Operating on the mode that corresponds to the condition (3.24) we will now ask for the additional requirements that must be met, in order to reach by the system an exactly balanced steady state.

Since we consider the free flow case, for the admissible balanced densities we consider only these c ∈ C that satisfy the condition:

c ≤ min F i v i n i=1 . (3.25)
Then, the set of exactly balanced equilibrium points can be defined as a set of pairs (u * , c) that solve the equations:

D + u * 1 = v 1 c , βi-1 v i-1 c + u * i = v i c , i = 2, 3, ..., n .
(3.26)

Respecting real freeway scenarios, we have to assume no-negative input demands (u * i ≥ 0 for all i). Then, we can formulate the necessary condition for the existence of balanced equilibria.

Proposition 3.4.3. There exists a balanced free equilibrium point only if :

βi-1 v i-1 ≤ v i , i = 2, 3, ..., n .
(3.27)

Proof. Let us assume βi-1 v i-1 > v i for i = 2, 3, ..., n. Then, (3.26) is a contradiction under u ≥ 0. Remark 3.4.2
A practical fact rises up with the Proposition 3.4.3. In order to design an exactly balanced equilibrium point, we may need to apply the variable speed limiting, where the speed limits depend on actual values of the split ratios so to guarantee that the condition (3.27) is satisfied.

Below we will give an explicit description of the balanced equilibrium set. To design a steady state x * = c1, one can easily find a corresponding on-ramp demand vector u * by solving the equations () a and () b .

∆ xB = {x * = c1 : c ≤ min F i v i n i=1 , c = D + u * 1 v 1 a , u * ∈ ∆ uB }, (3.28)
∆ uB = {u * ∈ U : u * 1 ≤ v 1 min F i v i n i=1 -D , u * i ≤ (v i -βi-1 v i-1 ) min F i v i n i=1 , D + u * 1 v 1 = u * i v i -βi-1 v i-1 b , i = 2, 3, ..., n }. (3.29)
The structure of the set of steady states in the case of two-cell system is shown in Fig. 3.4. The grey trapezium stands for the set ∆ x (the construction of this set is extensively studied in [START_REF] Pisarski | Analysis and design of equilibrium points for the celltransmission traffic model[END_REF]). It contains the set ∆ xB lying on the blue line. We can observe that the balanced equilibria are contained in the set ∆ x only if the slope of the red line is grater than 1. This statement is equivalent to the Proposition 3.4.3.

Chapter 3. Analysis on the Sets of Equilibrium Points for the Cell-Transmission Model

1 x * 1 β1 D v 2 D v 1 F 2 v 2 x * 2 v 2 β1 v 1 F 1 v 1 ∆ x ∆ xB

The optimal balanced steady states

As demonstrated in the last section, the exact balance requires strong conditions on cell parameters and boundary conditions. In most of the cases, we should rather consider the generalized balancing problem, as defined by (3.11). For this purpose, we will now introduce the corresponding optimization problems. The optimization will be executed in two steps. At the first step, we look for the exactly balanced state that maximizes TTD. According to the definition of balance, we search for an optimal value of c so that TTD is maximized. We denote this optimal value as c * . The second step is to determine the optimal equilibrium density x * and the optimal on-ramp demand u * such that x * tends to the state c * 1. Note that at both steps we solve static optimization problems, since we consider equilibrium states only.

Here we will pose the first optimization problem to determine the value of c * . Under the assumption that the system is in a steady state, for the total freeway length n i=1 L i and for some time interval T , TTD -as defined in (3.13) -takes the following form:

TTD = T n i=1 φi L i , (3.30)
where φi stands for the mean flow for the cell i. According to the triangular fundamental diagram (Fig. 2.3) we rewrite (3.30) in the following form:

TTD = T n i=1 min {v i ρ i , w i ( ρi -ρ i )} L i .
(3.31)

The optimal balanced steady states

Then, c * is a solution of the following problem:

Problem 3.5.1 (The optimal exactly balanced state search)

Find c * = argmax c∈C J 1 (c) , J 1 (c) = n i=1 min {v i c, w i ( ρi -c)} L i . (3.32)
The second step is to find the input vector u * such that the corresponding steady state

x * is the closest to c * 1 when considering the quadratic norm. As it was shown before, the set of equilibrium points for CTM can be described by the set of systems of linear equations and inequalities. The problem can be stated as follows:

Problem 3.5.2 (The optimal balanced steady state search)

Find (x * , u * ) = argmin x∈X ,u∈U J 2 (x) , J 2 (x) = (x -c * 1) T Q 1 (x -c * 1) + γ x T Q 2 x under A s x + B s u + C s = 0 , K s x + M s u + N s ≤ 0 , s ∈ S . (3.33)
Here, S is the set of modes, for which there exists a solution and it is unique for x * . The first term in the objective function corresponds to the distance of the steady state vector from c * 1 while the second one measures the dispersion of the balance. Q 1 is assumed to be positive-defined symmetrical and it weights the priorities for the on-ramps. Q 2 is the Laplacian matrix that is given in the form:

Q 2 (i, j) =    n -1 if i = j -1 otherwise .
(3.34)

The objective function terms are weighted by the parameter γ > 0.

Solution of the Problem 3.5.1

The idea here is to transform the Problem 3.5.1 into set of simple linear programs. We can observe that the objective function J 1 can return 2 n linear modes. Let then j = 1, 2, ..., 2 n be the index for a sequence of those modes. For every mode we need to specify the set of c under which the mode j is valid. This can be done by introducing set of relevant inequalities given in the form:

η j c + γ j ≤ 0 , η j = (η j,1 , η j,1 , ..., η j,n ) , γ j = (γ j,1 , γ j,1 , ..., γ j,n ) .
(3.35) Model

For example:

J 1 = c n i=1 v i L i (3.36)
if:

(v i + w i )c -w i ρi ≤ 0 , i = 1, 2, ..., n . (3.37)
The Problem 3.5.1 can be rewritten as follows:

Find c * j = argmax c∈C c Θ j + Ψ j under η j c + γ j ≤ 0 , j = 1, 2, ..., 2 n . (3.38)
Here Θ j and Ψ j stand for relevant sum of (3.32). Notice that the sign of η j,i is determined as follows:

η j,i > 0 in the case of v i c ≤ w i ( ρi -c) , η j,i < 0 in the case of v i c ≥ w i ( ρi -c) . (3.39)
This fact is used for building up the computational algorithm presented in the Appendix.

Solution of the Problem 3.5.2

The Problem 3.5.2 consists of a large number of sub-problems. Therefore, the reason for the convex formulation was not only for the solution uniqueness, but also for reasonably short computational time. The problem can be efficiently solved by introducing the Lagrange Dual Problem.

Let us first specify the set S appearing in the Problem 3.5.2. To provide the existence of the optimal pair (x * , u * ) so that x * is unique, the set S must exclude the modes such that A s is singular or B s is null matrix. Then, for every s ∈ S we can write:

x = A -1 s (B s u + C s ) . (3.40)
By using (3.40), the Problem 3.5.2 can reformulated so that, instead of searching for the pair (x * , u * ), we are looking for the optimal input only. Let us introduce:

W s = A -1 s B s , V s = A -1 s C s . (3.41)
Then, the Problem 3.5.2 can be written as follows:

Find u * = argmin u∈U J2 (u) , J2 (u) = (W s u + V s -c * 1) T Q 1 (W s u + V s -c * 1) + γ (W s u + V s ) T Q 2 (W s u + V s ) under K s (W s u + V s ) + M s u + N s ≤ 0 , s ∈ S .
(3.42)

The problem represented by (3.42) consists of convex objective function and the affine constraints that fulfil Slater's condition (for details see [START_REF] Boyd | Convex Optimization[END_REF]). Thus, by introducing the Lagrangian:

3.6. Implementation Aspects 35 L(u, λ) = J2 (u) + λ T (K s (W s u + V s ) + M s u + N s ) (3.43)
and the Lagrange Dual Function:

q(λ) = min u∈U L(u, λ) , (3.44)
we can solve the Lagrange Dual Problem:

λ * = argmax λ 0 q(λ) (3.45)
and recover the optimal input by using:

u * = argmin u∈U L(u, λ * ) . (3.46)
The alternate method is based on the fact that the pair (u * , λ * ) is the saddle point of the Lagrangian (3.43). Therefore, the optimal input can be found by performing the following updates:

u + = u -α 1 ∇ u L , and u ∈ U , λ + = λ + α 2 ∇ λ L
, and λ 0 .

(3.47)

Here α 1 and α 2 are small positive numbers. The convergence of the procedure (3.47) is assured by the convexity of J2 .

Implementation Aspects

Unlike in the case of the Problem 3.5.1, where under the assumption that for a certain time the cell parameters remain constant and the computation can be performed off-line, the solution of the Problem 3.5.2 is supposed to be updated every reasonable time period, since the boundary conditions can vary rapidly. Therefore, concerning the fact that the number of sub-problems to be solved is related to 8 n (total number of all possible modes generated by the Daganzo merge model), we need to investigate the computational capabilities of the software we developed.

The computational program consists of two major parts. The first part is to introduce the constraints, and therefore to create the matrices A, B, K, M and the vectors C, N for all considered modes of the system. For that purpose, we introduced relevant combinatorial procedures that allowed us to generate the full set of matrices for all possible modes.

At this level we also discard the modes that do not meet the previously mentioned conditions for existence and uniqueness of solutions. This significantly reduces the number of optimization sub-problems. At the same time, we discarded the modes for which the inequalities in (2.27) including cell capacities and boundary conditions contradict. The second part is to solve the remained optimization sub-problems. These are formulated as This is a significant limitation. However, for a freeway with almost uniformly distributed parameters, we can use the model with a reduced number of cells, and then the proposed method can be applied to the length of several kilometers. Notice that the computations were performed for the system where the input and the state vector are of the same size.

In general, most of the cells are not equipped with on-ramps. Then, the total number of system modes, and thus the number of sub-problems to be solved, radically decreases.

In the numerical examples presented in the next section, we will consider a seven cell model containing four on-ramps. In such a case the total number of possible modes is 8 6 , i.e. eight times smaller than in the fully actuated case. Notice also that all computations were performed by using a single computer. Since the general optimization problem is decomposed into independent sub-problems, it is possible to reduce a computational time by splitting the program on different machines and executing simultaneous computations.

Case studies

This part demonstrates numerical solutions of the optimal balancing under different traffic scenarios. For this purpose, we calibrate the Cell Transmission Model to represent a part of the south ring of Grenoble. The first examples will consider free flow cases, where we will show how the optimal solutions reflect the system properties highlighted in the analysis. Further examples will concern the optimal balanced states under the presence of a downstream bottleneck.

CTM calibration

The Grenoble South Ring is a two lane highway that connects the city of Grenoble in the north-east to south-west linking the highways A41 and A480. At the present moment, the ring is equipped with data collection system based on magnetic sensors. Ramp metering In order to build the CTM representation, we specified 7 cells, as depicted in Fig. 3.5.

Case studies

The cell parameters were tuned by using the real data collected at the freeway boundaries Several numerical experiments were executed to calibrate the merging parameter p.

In Aimsun, we created a model of merging junction (see Fig. Each simulation was performed for two hours. During the second hour, when we observed a stead state, the entering flows were measured by the virtual sensors. We considered five different lengths of merging zone (from 60 to 140 meters). The drivers' behavior at the Aimsun micro-simulator was changed by setting the lane changing cooperation parameter which may vary from 0% to 100%. 0% corresponds to extremely egotistic driving, where on-ramp vehicles occasionally enter mainstream. By increasing the parameter we can observe more driver's cooperation and the will to change the lanes so to enable the on-ramp vehicles join a freeway. The results are presented in the Table 3.3. The mapping from lane changing cooperation parameter to p is not linear, but it is clearly increasing.

Surprising may be the fact that in some cases p decreases when the merging zone becomes longer. In cases of 100% of cooperation we can observe the saturation point, where p ≈ 0.25. This can be intuitively explained as follows. Among two mainstream lanes the left one is taken by the vehicles travelling from upstream while the right one is to be shared by the upstream and the on-ramp demands with the same priority. Therefore, the flow entering via on-ramp is approximately equal to 1/4 of the total downstream supply.

For the Grenoble South Ring, where the merging zones lengths vary from 120 to 140 me- ters, and the drivers exhibit an average willingness to cooperate, we assume p i = 0.2 for i = 1, 3, 5, 7.

Let us consider the following traffic scenario. The boundary conditions are D = 3000

[veh/h] and S = 5000 [veh/h] for mainstream demand and supply, respectively. Note that the boundary supply exceeds the capacity of the final cell. For the split ratios we assume β1 = 0.9, β3 = 0.9, β5 = 0.85, β7 = 0.82 . To avoid long on-ramps queues, we assume that the demand served into freeway for each on-ramp must be greater than In the second case we adjust the free flow velocities so to hold the balancing con- ing speed limits on the VSL panels. We assume here that for each cell the average speed is equal to the limit indicated by VSL panel. Thus, the desired set of free flow velocities can be adjusted by setting equivalent set of speed limits. For the optimal set of inputs for this case see Table 3.2 (the row indicated by VSL). The system evolution is depicted in Fig. 3.8. The uniform green color along the horizontal direction (at the time 180 [s])

u min =
indicates the exactly balanced steady state. Since the required speed limits vary from one cell to another, this case does not seem to be realistic. Then, the question arises: Is there a practically realizable set of speed limits that can provide better balanced state than in the first case? The answer is positive as it is shown in the next example.

The third case (uniform VSL) is under the assumption that the speed limits for each of the cell is set to the same value, i.e. 80 [km/h]. Note that under this velocity the balancing condition is not fulfilled. Comparing the color distributions in the plots 3.7 and 3.9, we conclude that the assumed uniform speed limit results in a better balance accuracy, than we observed in the case without speed limiting. Even more precise balance is obtained when the speed limit is set to 70 [km/h]. However, reduced velocity implies a decrease of the total flow. One of the future direction could be to pose optimization problem to find a piecewise uniform distribution of speed limits resulting in best balance accuracy while keeping high value for TTD.

Congested Case

In this part, we consider the state balancing for congested traffic conditions. We simulate the presence of downstream bottleneck by decreasing boundary supply:

S = 2500 [veh/h].
For the demands and the split ratios we use the same values, as in the previous examples. [veh/km] and u * = (500, 0, 300, 0, 700, 0, 300) [veh/h], respectively. Note that in this case, the solution is not unique for u * , i.e. to reach the optimal x * , we can select any ues for input demands (most of them are equal to the minimum admissible value). This is a natural consequence of the fact that the optimal density we want to target is much lower than the one that would normally result from the traffic conditions under a bottleneck. If we desire more vehicles to be served in the on-ramps, we can either increase the lower bound for the input or, instead of taking the optimal c * , specify an appropriately higher value for c. In the Table 3.5, we demonstrate exemplary solutions for different congested desired balanced states. As we expected, larger c requires higher input values.

Still remaining is the question of the accuracy of balanced steady states acquired by the proposed method. In particular, we might be interested in the parameters that have the biggest impact on this accuracy. Unfortunately, this problem can not be resolved explicitly.

Intuitively, the larger equilibrium set, the higher probability of finding a desired point within or close to it. The size of equilibrium set can be naturally correlated with the distance between the lower and the upper input bound. However, even if we increase this distance, we can not assure that a desired points lies close to the equilibrium set, since its structure is also determined by the boundary conditions and the cell parameters.

Appendix

Algorithm 1: Computational procedure for the Problem 3.5.1

Input : for i = 1, 1, .., n : v i , w i , ρi , l i for j = 1, 2, .., 2 n : Θ j , Ψ j , η j Output: c * begin k ←-0; for j ←-1 to 2 n do for i ←-1 to n do if η j,i < 0 then c - i ←- w i ρi v i + w i ; end if η j,i > 0 then c + i ←- w i ρi v i + w i ; end end if min {c + i } n i=1 ≥ max {c - i } n i=1 then k ←-k + 1; if Θ j ≥ 0 then c * k ←-min {c + i } n i=1 ; else c * k ←-max {c - i } n i=1 ; end end end c * ←-c * 1 ; for j ←-2 to k do if J 1 (c * j ) ≥ J 1 (c * ) then c * ←-c * j ; end end end CHAPTER 4

Optimal Control in Traffic Engineering

The study of the dynamic optimization problems goes back to 1950s. In that time, two important advances were made. One was Bellman's Principle of Optimality and the corresponding Dynamic Programming, formulated by Richard Bellman in 1957 [START_REF] Bellman | Dynamic Programming[END_REF]. Dynamic Programming is a procedure that reduces the search for the optimal control to finding the solution of a partial differential equation (the Hamilton -Jacobi -Bellman Equation) [START_REF] Vinter | Optimal Control[END_REF].

The other was the the Maximum Principle formulated by Pontryagin in 1962 [START_REF] Pontryagin | The Mathematical Theory of Optimal Processes[END_REF]. The Maximum Principle is a set of necessary conditions for a control function to be optimal.

Based on these theories, numerous computational methods were developed during 1960s and 1970s [START_REF] Bryson | Applied Optimal Control[END_REF] and put into practice in various engineering applications.

In this chapter, the fundamental optimal control techniques in application to freeway traffic will be studied. At first, the finite horizon optimal control problem will be formulated. Basic solution properties and the necessary optimality condition will be given. In the sequel, we will study a general problem of optimal control for the Cell-Transmission Model. The last section will be to introduce the idea of distributed optimization via solving a Nash game. This idea will be brought into traffic system in the control design presented within the next chapter.

Finite horizon optimal control problem

Most of the optimization traffic problems are formulated as the finite time horizon optimal control problems and solved sequentially according to the receding horizon scheme (briefly presented in the section 4.5). This optimization technique enables to take into account change of both, model parameters and boundary conditions. Since the freeway control inputs are bounded (see the section 2.2.3), i.e., the system is not fully controllable, the optimal control problems are formulated with free-endpoint state. Consider a dynamical system represented by:

ẋ(t) = f (x(t), u(t)) , x(0) = x 0 , u ∈ U . (4.1)
The free-endpoint finite time horizon optimal control problem is formulated as follows:

Problem 4.1.1 (Finite time horizon optimal control problem)

Find u * = argmin u∈U J = t f 0 f 0 (x, u) dt under ẋ(t) = f (x(t), u(t)) , x(0) = x 0 . (4.2)
The existence of the optimal control u * can be verified by means of the classical Weierstrass

Theorem [START_REF] Sundaram | A First Course in Optimization Theory[END_REF]. The theorem states that any continuous function described on a compact domain takes its minimum and maximum value. For the Problem 4.1.1, the existence of the minimizer u * is not fully provided by the continuity of J and the compactness of U . Instead of the compactness of U , it is required that compact is the set of points reachable from x 0 using controls that take values in U [START_REF] Liberzon | Calculus of Variations and Optimal Control Theory[END_REF]. For nonlinear systems, explicit computation of reachable sets is usually not feasible. Instead, we can rely on the Filippov's theorem [START_REF] Filippov | [END_REF] which states that the reachable set for (4.1) is compact if the set {f (x, u) :

u ∈ U } is compact and convex.

The necessary optimality condition

In this section, we will derive the first order necessary optimality condition for the Problem 4.1.1. The derivation will be carried out by using the calculus of variations. In the sequel, the definition of the functional derivative will be given. Based on the functional derivative, the steepest descent method to determine the optimizer u * will be presented. Finally, we will discuss the major difficulties when solving the optimal control problems for the Cell-Transmission Model.

Let us consider the functional J as defined in (4.2). For every control u, we have:

J(u + δu) -J(u) = δJ(u)δu + r J (u, δu) . (4.3)
Here, δu and δJ stands for the first variation of control and objective functional, respectively, and r J (u, δu) = o(δu), i.e.: r J (u, δu)/ δu → 0 as δu → 0. The first order necessary condition for optimality of u = u * is that the first variation of the objective functional is equal to zero:

δJ(u) = 0 . (4.4)

The necessary optimality condition 47

To represent the condition (4.4) for the Problem 4.1.1, we first introduce the adjoint state p, and then rewrite the objective functional as follows:

J = t f 0 f 0 + p T ( ẋ -f ) dt , (4.5)
Next, we introduce the Hamiltonian of the following form:

H(x, p, u) = p T f (x, u) -f 0 (x, u) . (4.6)
Then the objective functional is represented by:

J = t f 0 p T ẋ -H dt . (4.7)
Infinitesimal change δu causes the variations of the functions δx, δ ẋ, δp. This results in the following increment of the objective functional:

δJ δu = t f 0 - ∂H ∂u δu - ∂H ∂x ⊺ δx + p ⊺ δ ẋ + ẋ - ∂H ∂p ⊺ δp dt . (4.8) Since: ∂H ∂p = f (x, u) , (4.9)
the last term in (4.8) vanishes. Now, under the assumption:

δ ẋ = d dt (δx) , (4.10)
the integration by parts yields:

δJ δu = t f 0 - ∂H ∂u δu dt - t f 0 ṗ + ∂H ∂x ⊺ δx dt + [p ⊺ δx] t f 0 . (4.11)
Respecting the fact that the state trajectory is fixed at the boundary condition, i.e.: δx(0) = 0 and by setting:

ṗ = - ∂H ∂x , p(t f ) = 0 . (4.12)
we finally get:

δJ δu = t f 0 - ∂H ∂u δu dt (4.13)
Summarizing, the first order necessary optimality condition for the Problem 4.1.1 is written as follows:

∂H ∂u = 0 , H = p T f -f 0 , ẋ = ∂H ∂p , x(0) = x 0 , ṗ = - ∂H ∂x , p(t f ) = 0 . (4.14)
The condition 4.14 can be effectively used only in the cases where the Problem 4. Finally, we have the terminal condition:

p * (t f ) = 0 . (4.19)
For proofs see, for example, [START_REF] Evans | An Introduction to Mathematical Optimal Control Theory[END_REF], [START_REF] Macki | Introduction to Optimal Control Theory[END_REF], [START_REF] Athans | Optimal Control: An Introduction to the Theory and its Applications[END_REF].

Solution Methods

As demonstrated in (4.14), the optimality condition consists of the Two Point Boundary Value Problem. To solve this problem, the shooting [START_REF] Stoer | Introduction to Numerical Analysis[END_REF] and the relaxation [START_REF] Press | Numerical Recipes in C: The Art of Scientific Computing[END_REF] methods can be applied. In the shooting method, the idea would be to find the initial condition for the adjoint state such that its terminal condition if fulfilled. The usual methods for finding roots may be employed here, such as the bisection method or Newton's method.

Relaxation method implements another approach. The time domain is represented as a set of points creating mesh. The dynamical equations are transformed into the finite difference equations. An iterative procedure is adjusting all the state and adjoint state values on the mesh to bring them into successively closer agreement with the finite-difference equations together with the boundary conditions. In many cases, shooting and relaxation methods are combined together. Both methods exhibit good performance in the case of low dimensional problems excluding solutions that are highly oscillatory or not smooth.

To solve the necessary optimality condition, we can also employ a wide range of gradient based methods. Below, we will give a solution procedure based on the method of steepest descent. Before we do it, we will now define the gradient for the Problem 4.1.1.

From (4.13) we have:

δJ = t f 0 - ∂H ∂u dt . (4.20)

Solution Methods 49

The first variation δJ is the quantity that carries the information on how the functional changes, when the whole control trajectory changes by a small amount. To derive the gradient, we need to extract the information on how the functional changes, when the control value at any given time τ ∈ [0, t f ] changes by a small amount. The gradient corresponding to time τ denoted by ∇ u(τ ) J can be computed as follows:

∇ u(τ ) J = t f 0 - ∂H ∂u δ(t -τ ) dt . (4.21)
Here δ(•) is the Dirac delta function. From (4.21), we conclude that: Step 1 Initialize: u * = u ini and assume ε as small positive number.

∇ u(τ ) J = - ∂H ∂u | t=τ . ( 4
Step 2 Solve the state equation (4.1) by substituting: u = u * .

Step 3 Solve the adjoint state equation (4.12) by backward integration. Use u = u * and the corresponding state.

Step 4 Compute the descent directions: -∇ u(τ ) J = ∂H ∂u | t=τ .

Step 5 Update the control values: u * (τ ) = u * (τ ) -λ ∇ u(τ ) J. Here the step size λ > 0 is taken such to provide that u * ∈ U . Optionally perform the line search by solving the problem: λ * = arg min λ J(u * (τ ) -λ ∇ u(τ ) J) and update the control values by setting λ = λ * .

Step 6 Repeat Steps 2-5 until the terminal condition is met: ||∇ u(τ ) J|| < ε.

The necessary optimality condition results in u * being a local minimizer. If the structure of the objective J is not well identified, then it may be essential to run the Procedure

Find u * = argmin J = 1 2 t f 0 x ⊺ Q x + u ⊺ R u dt under ẋ = Ax + Bu , x(0) = x 0 .
(4.23)

Chapter 4. Optimal Control in Traffic Engineering

Here the set of admissible control is unbounded, the symmetric matrices Q and R are assumed to be positive semi-definite and positive definite, respectively. The necessary optimality condition (4.14) results as follows:

u = R -1 B ⊺ p , ẋ = Ax + Bu , x(0) = x 0 , ṗ = -A ⊺ p + Qx , p(t f ) = 0 . (4.24)
By defining K(t) : K(t f ) = 0 and setting:

p(t) = -K(t) x(t) , for all t ∈ [0, t f ] , (4.25)
the adjoint state equation takes the form:

ṗ = A ⊺ K x + Qx . (4.26)
The control is rewritten as:

u = -R -1 B ⊺ K x . (4.27)
From (4.25) we know that:

ṗ = -Kx -K ẋ . (4.28)
Combining (4.26), (4.28), the state equation and (4.27), we can compute the matrix K by backward integration of:

A ⊺ K + K A -KBR -1 B ⊺ K + Q = -K , K(t f ) = 0 , (4.29)
referred as the Riccati differential equation. Identical result can be derived by using Bellman's Principle of Optimality (see, for instance, [START_REF] Evans | An Introduction to Mathematical Optimal Control Theory[END_REF]).

The optimal control problem for CTM

In this section, we will discuss the finite horizon problem under the governing equation of CTM. Solution methodology is briefly presented with the emphasis on the computational difficulties due to the switching system structure.

The finite time horizon optimal control problem for CTM can be written as follows:

Problem 4.4.1 (Finite horizon optimal control problem for CTM)

Find u * = argmin u∈U J = k=t f k=0 f 0 (x(k), u(k)) ∆t under x(k + 1) = x(k) + ∆t f s (x(k), u(k), k) , x(0) = x 0 .
(4.30)

The optimal control problem for CTM 51

Here f s is a switched function generated by the the governing equation (2.32). For simplicity, let us assume that the governing equation is given in the autonomous form, i.e. its right hand side function does not depend explicitly on time. This form can be derived by extending the state vector with the component representing time, i.e. by introducing:

x ext (k + 1) = x ext (k) + 1 , x ext (0) = 0 . (4.31)
Then, the boundary conditions being represented by time series can be approximated by relevant functions of this state component. By using the extended state vector x = [x, x ext ] ⊺ and the extended right hand side function fs = [f s , 1] ⊺ , we can rewrite the dynamical equation in the Problem 4.4.1 as follows:

x(k + 1) = x(k) + ∆t fs (x(k), u(k)) , x(k = 0) = [x 0 , 0] ⊺ . (4.32)
There exists a variety of methods for solving the problems of optimal control of switched systems. Some of them can be applied to generally stated problems like the Problem 4.4.1, but the most efficient are those dedicated to a certain groups of problems, where, for instance, a sequence of switched modes does not depend on the control decision and can be precisely identified. Several computational algorithms for optimization of continuous time switched systems are compared in [START_REF] Branicky | Algorithms for optimal hybrid control[END_REF]. A general study on the existence of optimal control for switched systems is presented in [START_REF] Branicky | A unified framework for hybrid control: Model and optimal control theory[END_REF]. Below, we will consider the Problem 4.4.1 for two cases that are the most representative in freeway traffic.

The first case concerns the traffic scenarios with homogeneous states, namely where an optimized freeway section is either in the free flow or the congested state. In such a case, if the boundary conditions do not change rapidly, we can assume that for a reasonably short time horizon, the system will keep the same mode. Then, the Problem 4.4.1 can be treated analogously to 4.1.1. The necessary optimality condition under discrete state and adjoint state takes the following form: The second case concerns the transient traffic. Transient traffic refers to the situations in which we observe the congestion either expanding or contracting. In particular, we can encounter the shock waves caused by the instantaneous drops of capacity. The result of the shock wave propagation is that the system (4.32) switches its modes rapidly. Depending on the length of the time horizon and the expected system behaviour, one can adopt

∂H ∂u = 0 , H = p T fs -f 0 , x(k + 1) = x(k) + ∆t ∂H ∂p , x(k = 0) = [x 0 , 0] ⊺ , p(k + 1) = p(k) -∆t ∂H ∂ x , p(k = t f ) = 0 .

52

Chapter 4. Optimal Control in Traffic Engineering a relevant switched system optimization techniques. For CTM the switching variable is not a decision parameter (it depends on the state and the control), and thus the methods based on the Maximum Principle (for example, [START_REF] Sussmann | A maximum principle for hybrid optimal control problems[END_REF] and [START_REF] Piccoli | Necessary conditions for hybrid optimization[END_REF]) can be employed. For more general problems of optimal control of switched systems (under non-determined switching sequence) a suboptimal solution was proposed in [START_REF] Shaikh | On the optimal control of hybrid systems: Optimization of switching times and combinatoric schedules[END_REF]. In the case of piecewise-affine systems and quadratic objective functions, the method based on solving the Hamilton-Jacobi-Bellman equation was developed in [START_REF] Rantzer | Piecewise linear quadratic optimal control[END_REF]. In the most general cases, an optimal control problem for a switched system can be formulated as a mixed-integer programming problem (see, for example, [START_REF] Papadimitriou | Combinatorial Optimization: Algorithms and Complexity[END_REF]).

Receding horizon control scheme

The efficiency of the optimal controllers is highly dependent on the knowledge of the optimized system. For the best performance, it is required to have well developed mathematical model together with precisely estimated parameters and boundary conditions. In the case of the finite horizon optimization, this requirements must be met at least within a considered time horizon. In the traffic systems, a precise prediction of both, the model parameters and the boundary conditions can be made only few minutes ahead. Thus, the most reliable for traffic optimization is a method that allows on a permanent model update. This method is the receding horizon control, often referred also as the model predictive control.

The receding horizon control method is formulated as a finite horizon optimization to be repeated on-line. The basic principle of the method is demonstrated in Fig. 4.1. Based on the measured (or estimated) current state and the predicted evolution of the exogenous signals (the boundary conditions in the traffic systems), the controller determines the optimal input over the control/prediction horizon. From the sequence of the optimal decisions, only the first one is applied to a system, while for the next time sample the procedure is repeated. A fundamental theory underlying the receding control scheme is [START_REF] Bellman | Dynamic Programming[END_REF] which states that: "An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision".

In case of the completely deterministic systems, it can be verified that the solution of the receding horizon method is equivalent to the one obtained by using computationally heavy dynamic programming. Thus, one the major ideas behind the receding horizon method is to determine an optimal feedback controller by executing open-loop optimization. The receding horizon control scheme in the traffic optimization is commonly executed with the following steps: Step 2 Solve a finite time optimal control problem over the time period [k, k + T ].

Step 3 Apply the optimal decision u * (k).

Step 4 Increment time sample k = k + 1 and continue with the Step 1.

Distributed optimization via non-cooperative Nash game

In this section, we will formulate a non-cooperative Nash game problem. The goal is to demonstrate that for a wide group of systems this formulation allows on solving an optimization problem in a distributed manner. In particular, we will be interested in the systems that are interconnected through the line graphs. As it will be shown in the next chapter, the line graphs also apply to the Cell-Transmission Model.

Let us consider again the Problem 4.1.1. In the general case, where the objective functional depends on the whole state vector and the system dynamics is not separable, the solution is performed through a centralized controller's architecture (see Fig. 1.3a).

By using decomposition methods, the problem can be solved in a distributed manner only under some special structures of the system and the objective functional (see, for example, [START_REF] Rantzer | Dynamic dual decomposition for distributed control[END_REF] and [START_REF] Rantzer | Distributed control of positive systems[END_REF]). An alternative method for distributed optimization is to solve a corresponding Nash game discussed below.

Let us consider a set of subsystems {S j }, each with one control input u j and its controllable state vector x j . For each of the subsystems we associate the objective J j . The subsystems are interconnected, and thus J j may be also affected by some of the other control inputs. Consider the system interconnected according to the directed graph as depicted in Fig. 4.2. An arrow from S i to S j indicates that subsystem S i affects subsystem S j . In this case, we have the following objective dependencies:

S 1 S 2 S 3 S 4
J 1 (u 1 ) , J 2 (u 2 , u -2 {u 1 , u 3 , u 4 }) , J 3 (u 3 , u -3 {u 1 , u 4 }) , J 4 (u 4 , u -4 {u 1 , u 3 }) . (4.34)
Here by u -j we denote the set of control decisions except u j that affects the objective J j . Note that u i ∈ u -j if there is a directed path from S i to S j in the interconnectivity graph. Under the introduced setting, the non-cooperative Nash game problem is stated as follows:

Problem 4.6.1 (Non-cooperative Nash game)

Find {u * j } such that ∀j : u * j = argmin J j (u j , u * -j ) . (4.35)
The set of decisions {u * j } is called the Nash Equilibrium and this is the strategy such that no unilateral deviation in decision by any single player is profitable for that player. For extensive studies on the Nash equilibrium solution concept a reader is refereed to [START_REF] Basar | Dynamic Noncooperative Game Theory[END_REF].

To guarantee that the Nash equilibrium exists, every objective function J j needs to be continuous in all its arguments and strictly convex in u j .

To demonstrate that the Nash equilibrium search for the system represented by Fig. 4.2 can be resolved in a distributed manner, let us now write the solution procedure: Procedure 4.6.1 (Solution of the Nash game for the system depicted in Fig. 4

.2)

Step 1 Guess u * 4 and assume ε 2 , ε 3 , ε 4 as small positive numbers.

Step 2 Find u * 1 = argmin J 1 (u 1 ) and send the solution to S 2 and S 4 . S 4 conveys the solution to S 3 .

Step 3 Find u * 3 = argmin J 3 (u 3 , {u * 1 , u * 4 }) and send the solution to S 2 and S 4 .

Step 4 Find u * 2 = argmin J 2 (u 2 , {u * 1 , u * 3 , u * 4 }). Step 5 Find u * 4 = argmin J 4 (u 4 , {u * 1 , u * 3 }
) and send the solution to S 3 . S 3 conveys the solution to S 2 .

Step 6 Repeat Steps 3-5 until ∆ J 2 < ε 2 , ∆ J 3 < ε 3 , ∆ J 4 < ε 4 (∆ J j stands for incremental change of norm of the objective function J j ).

The games concerned with the line graphs will be studied in details in the next chapter in the context of the optimization of the Cell-Transmission Model. The directions on the graph will be determined by the system mode. Note that in case of the system represented by the graph Fig. 4.3a, the solution procedure does not contain any iterated steps which significantly reduces computational effort. In such a case, we will say that there is hierarchy imposed in the game. As it will be shown, the hierarchical games play a major role in the problems related to freeway traffic.

CHAPTER 5

Nash Game Based Distributed Control Design for Balancing of Freeway Traffic Density

In this chapter, a design of a distributed optimal control method for balancing of freeway traffic density will be presented. The optimization will be performed in a distributed manner by utilizing the controllability properties of the freeway network represented by the Cell Transmission Model. By using these properties, we will identify the subsystems to be controlled by local ramp meters. The optimization problem will be then formulated as a non-cooperative Nash game as introduced in the Chapter 4. The game will be solved by decomposing it into a set of two-players hierarchical and competitive games. The process of optimization will employ the communication channels matching the switching structure of system interconnectivity. By defining the internal model for the boundary flows, local optimal control problems will be efficiently solved by utilizing the method of Linear Quadratic Regulator. The developed control strategy will be tested via numerical simulations on the macroscopic model in two scenarios for uniformly congested and transient traffic. The validation with the use of the microscopic simulator will be presented in the Chapter 7. Throughout this chapter, we will use the Cell-Transmission Model as introduced in the Chapter 2.

Introduction

As demonstrated in the literature review presented in the Chapter 1, several distributed control techniques were already considered to control freeway traffic flow. Those that realize optimal polices are usually based on decomposition methods and distributed model predictive control. In this thesis, based on the Nash game formulation, a distributed op-Traffic Density timal controller will be proposed. The choice of this formulation is not only to provide an efficient solution method reliable for large scale freeway networks, but also to introduce a sort of intuitive notion of traffic optimization, where the control inputs can be perceived as the players that depending on their local traffic state perform either hierarchical or competitive games to achieve their desired performance. As it will be shown, the key in providing efficient solution of the distributed optimization problem lies within the establishment of the dynamically adapting system division.

The control objective, similarly to the one introduced in the Chapter 3, will be to balance traffic density in the freeway links. In this setting, we will tend to balance the traffic density at the level that reduces the Total Travel Spent. We will also investigate the impact of density balancing on the propagation of shock waves.

A Nash game based approach for freeway traffic optimization was reported in [START_REF] Portilla | Nonlinear model predictive control based on game theory for traffic control on highways[END_REF].

The authors utilized the mechanism of the distributed predictive control based on game theory (GT-DMPC, introduced in [START_REF] Giovanini | Game approach to distributed model predictive control[END_REF]) pointing on computational complexity and slow convergence of the optimization procedure when applied to a large scale traffic network.

The convergence problem may result from an arbitrary and static system division assumed by the authors. As we will demonstrate, in the case of an arbitrary system division, there is a risk of loss of controllability, and therefore the uniqueness of the optimal solution. We will also show that, due to the presence of the switched interfacing flows, it is forbidden to split a freeway system in an arbitrary manner. In contrast to [START_REF] Portilla | Nonlinear model predictive control based on game theory for traffic control on highways[END_REF], we will design a dynamical partitioning scheme that will be adapting the local subsystems according to the actual traffic state such to provide the controllability of the inputs involved in the game problem. The controllability analysis will also allow us to decompose the overall game problem and solve it by performing a sequence of simple two-player games.

Controllability of the freeway links

The goal in characterizing of the subsystems for the Nash game problem will be to provide that each of the control inputs involved in the game problem can affect its local subsystem.

This fact is often neglected in the optimization of control systems while the controllability analysis is crucial for the well-posed optimization problem (that meets existence, uniqueness and continuity properties) providing the convergence of the solution algorithms. Indeed, in the case that some of the inputs involved in the optimization process can not affect the objective function, an iterative procedure may search for the solution on the flat regions and never fulfil a terminating condition. As will be demonstrated, lose of controllability may occur in the freeway traffic system. The notion of controllability used in this work refers to the local controllability [85][86]. Since, the set of admissible control input is bounded (see the section 2.2.3), we can not provide full controllability. Instead, we will say that a state is controllable if there is an input that can affect it by changing this state

Controllability of the freeway links 59

within some neighbourhood. The results presented below will be utilized not only in the system partitioning, but they will also determine the methodology for solving the game problem.

Let us first introduce the notion of the freeway links. By a link we will mean any freeway section, composed of a group of cells, that is separated by two successive on- referred as the mixed state links, will be composed of the cells of both modes, assuming that the state is structured according to the two cases presented in Fig. To verify the controllability of the considered links, let us consider again governing equation of LWR model written in the following form: Then, the solution to (5.1) is represented as follows:

∂ t ρ + ∂ ρ Φ(ρ) ∂ y ρ = 0 . ( 5
ρ(y, t) = ρ(y -vt, 0) for a link in the free flow state , ρ(y, t) = ρ(y + wt, 0) for a link in the congested state .

(5.

2)

The solution (5.2) represents the wave propagating downstream or upstream under the free flow or the congested state, respectively. As a consequence, in order to control a link in the free flow state, we need to place a controller at the upstream bound (Fig. 5.1a).

For a congested link, a controller is supposed to be located at the downstream bound (Fig. 5.1b). In the case of the link containing successively located free flow and congested section (Fig. 5.2a), the state dynamics is under control of both inputs. In the situation with the reverse state (Fig. 5.2b), a link stays uncontrollable.

The controllability results presented here are also valid for a wide class of discrete representations of the conservation law. In particular, for the Cell Transmission Model, the analogous results may be easily verified by means of the controllability matrix [START_REF] Kailath | Linear Systems[END_REF].

System partitioning and state information pattern

In the section 5.4, we will pose a Nash problem, where each of the control input will tend to optimize its local subsystem. Here, we will establish a method for selection of these subsystems by defining an input-state assignment. We assume that each of the inputs receives a full state information of the two surrounding links as demonstrated in Fig. 5.3. Let us define x j as a part of the state vector x that is assigned to the input u j :

x j = ρ j 1 , ρ j 2 , ..., ρ j n j , l j ⊺ . (5.
3)

The assignment of the subsystem x j to u j is made on the base of the following controllability rule: x j is composed of the states of the closest controllable for u j link. In the case where both surrounding links are controllable (congested upstream and free flow downstream), we select the congested link. Besides the controllability, we also require that the partitioning provides that:

Each of the boundary flows for the link x j is uniquely determined by only one subsystem (x j or its neighbour). (The statement will be later refereed as the separation principle).

System partitioning and state information pattern

61

F F F u j u j+1

x j x j+1 φ j φ j+1

x j-1

C C C

φ j φ j+1

x j-1 x j x j+1 u j u j-1 The assignment in the case of the homogeneous state links is presented in Figs. [START_REF] Arnold | Ramp metering: A review of the literature[END_REF].4 and 5.5.

The total number of cells assigned to the input u j is denoted by n j . Note that in both cases the separation principle is fulfilled. Indeed, for the free flow case we have φ j = D(x j-1 ), φ j+1 = D(x j ). For the congested case we have φ j = S(x j ), φ j+1 = S(x j+1 ) (Here the notation D(x j ) and S(x j ) stands for the demand and the supply corresponding to the link x j ). The uniqueness of the boundary condition is crucial for setting the distributed game problem. We will be able to decouple the dynamics of the subsystems and solve the local optimization problems, where the controllers will optimize their subsystems with respect to given boundary conditions.

In the case of the mixed state links, the separation principle results in the subsystem selection as depicted in Fig. 5.6. Note that φ j+1 may be switched between demand of the free flow section and supply of the congested section according to the model of the interfacing flow:

φ j+1 = min {D(x j ), S(x j+1 )} .
(5.4)

In this case, the dynamics for these sections must be solved jointly. The subsystem selection for the mixed state links will be denoted by x j, j+1 and will be meant to be optimized by both inputs u j and u j+1 . The presence of switching interfacing flows follows the statement that the structure of system division can not be fixed.

We will now give the explicit dynamical representations of the subsystems discussed above. We assume that inside each of the links, the cell parameters v, w and ρ are equal.

We also assume that in each of the links, there is only one off-ramp (with associated split ratio βj ), and it is placed in the last cell of the link. This assumption will later

F C F C u j u j+1 φ j φ j+1 φ j+2
x j, j+1

x j x j+1 become significant for the method of solving optimal control problem, where we will use an autonomous form of the dynamical equations. Note that this assumption meets most of the existing freeway architectures, where off-ramps are located just before on-ramps.

By introducing the inverted cell lengths matrix:

L j inv = diag (1/L j 1 , 1/L j 2 , ..., 1/L j n j , 1) (5.5)
and the matrices:

A f = v j L j inv           -1 0 1 -1 0 . . . . . . . . . 1 -1 0 0 • • • 0 0 0           , B f = L j inv           1 0 . . . 0 -1           , C f = L j inv           1 0 . . . 0 0           , D f = L j inv           0 0 . . . 0 1           , (5.6)
the dynamical equation of the free flow state link is represented by:

x j (k + 1) = x j (k) + ∆t(A f x j (k) + B f u j (k) + C f Dj (k) + D f Dj (k)) .
(5.7)

Here by Dj (k) we will denote the mainstream demand for the link j. Note that according to the assumed merging model (2.27), the system (5.7) is valid only if:

u j (k) ≤ F j -Dj (k) for all k , (5.8)
where F j stands for the flow capacity of the link j. Similarly, by introducing:

A c = w j L j inv           -1 1 0 -1 1 0 . . . . . . . . . -1 0 0 • • • 0 0 0           , B c = L j inv           0 0 . . . 1 βj -1           , C c = L j inv           0 0 . . . 1 0           , D c = L j inv           0 0 . . . 0 1           , (5.9)
the dynamics of the congested state link is governed by:

x j (k + 1) = x j (k) + ∆t(A c x j (k) + B c u j (k) + C c (w j ρj - 1 βj Sj (k)) + D c Dj (k)) , (5.10)
where Sj (k) stands for the mainstream supply for the link j. Respecting the merging model (2.27) the system (5.10) is valid under the condition:

u j (k) ≤ p Sj (k) for all k .
(5.11)

Here p Sj is the supply available for the on-ramp demand. To write down the dynamical equation of the controllable mixed state link, we introduce the following matrices:

A f c (k) = A f (k) A c (k) , B ′ f = B f 0 , C ′ f = C f 0 , D ′ f = D f 0 , B ′ c = 0 B c , C ′ c = 0 C c , D ′ c = 0 D c .
(5.12)

Here the system matrix A f c is composed of the switching matrices A f (k) and A c (k) preserving the structures of A f and A c except for the rows corresponding to the interfacing flow φ j+1 (k) = min {D(x j (k)), S(x j+1 (k))}. The sizes of A f (k) and A c (k) are being adjusted according to the position of the congestion wave. The controlled mixed state links are governed by the following dynamical equation:

x j, j+1 (k + 1) = x j, j+1 (k) + ∆t A f c (k)x j, j+1 (k)+ + ∆t B ′ f u j (k) + C ′ f Dj (k) + D ′ f Dj (k) + + ∆t B ′ c u j+1 (k) + C ′ c (w j ρj -Sj+1 (k)) + D ′ c Dj+1 (k) .
(5.13) For (5.13), we assume:

u j (k) ≤ F j -D j (k) , u j+1 (k) ≤ p S j+1 (k) for all k . (5.14)
The uncontrollable links, as depicted in Fig. 5.2b, evolve according to the following dynamics:

x(k + 1) = x(k) + ∆t A cf (k)x(k) , (5.15)
with the switching matrix

A cf = diag(A c (k), A f (k)).

Optimization Problem

A freeway partitioned according to the scheme presented in the previous section is now ready for optimization. The goal is to formulate an optimal control problem that can be solved by following the state information pattern presented in the previous section.

For the solution procedure, we allow that each of the controllers communicates under the topology presented in Fig. 5.7a. As it will be found later, this topology captures all information channels involved during the solution for different state combinations 5.7bd. The optimization problem will be formulated as a non-cooperative game introduced in the Chapter 4.

boundary flow. Thus, to solve the game problem, there is no need to transfer all optimal decisions, but instead the neighbouring controllers will exchange their optimal demand/supply informations. The Problem 5.4.1 then will be decomposed and solved by performing a sequence of two-player games. The games will be either hierarchical or competitive depending on the state (homogeneous or mixed) inside the link between the players. Each of these games will be executed by solving the local optimal control problems discussed in the section 5.5.

Non-Cooperative Game for the homogeneous state links

Let us consider the homogeneous state links in the free flow and the congested state as depicted in Fig. 5.8a and Fig. 5.8b, respectively. A decision taken by any of the inputs propagates in accordance to the direction of travel of traffic wave (downstream for the free flow state case and upstream for the congested state case). It therefore follows that for the homogeneous state links, among two of the neighbouring inputs there is only one that can affect the state of the other. The Nash game for such pair of inputs has the controllability imposed hierarchy. This sort of game is referred as hierarchical or the Stackelberg game. By defining the subsystems S j and S j+1 as the pairs (u j , x j ) and (u j+1 , x j+1 ), respectively, the interconnectivity graph for the free flow case can be represented as depicted in Respecting the interconnectivity graph, the local objective functions takes the following forms:

J j (u j , x j (u j )) , J j+1 (u j+1 , x j+1 (u j , u j+1 )) (5.18) Traffic Density in the case of the free flow state links and:

J j (u j , x j (u j , u j+1 )) , J j+1 (u j+1 , x j+1 (u j+1 )) (5.19) in the case of the congested state links. In the sequel, we will use the explicit notations, i.e. J j (u j ) instead of J j (u j , x j (u j )) and J j (u j , u j+1 ) instead of J j (u j , x j (u j , u j+1 )).

The Stackelberg game enables to reach the Nash Equilibrium by executing only one local optimization for each of the players. Formally, the Nash equilibrium for the Stackelberg two-player game in the free flow state case is written as follows:

Problem 5.4.2 (Two-player Stackelberg game, free flow case)

u * j = argmin J j (u j ) , u * j+1 = argmin J j+1 (u * j , u j+1 ) . (5.20)
Here the player j is the leader and player j + 1 is the follower. Similarly, for the congested state case the Stackelberg game is:

Problem 5.4.3 (Two-player Stackelberg game, congested case)

u * j = argmin J j (u j , u * j+1 ) , u * j+1 = argmin J j+1 (u j+1 ) , (5.21)
with j + 1 as the leader and j as the follower. The procedures to solve Problem 5.4. Step 1 Find u * j = argmin J j (u j ),

Step 2 Find u * j+1 = argmin J j+1 (u * j , u j+1 ), Procedure 5.4.2 (Solution steps for the Problem 5.4.3)

Step 1 Find u * j+1 = argmin J j+1 (u j+1 ),

Step 2 Find u * j = argmin J j (u j , u * j+1 ),

Non-Cooperative Game for the mixed state links

Now we will consider the case of the mixed state link (see Fig. 5.10). Here, the two neighbouring inputs compete with each other in optimizing a dynamically coupled link.

Decision of the player j may influence the value of objective function of the player j + 1 and vice versa.

Optimization Problem 67

By defining the subsystems S j and S j+1 as the pairs (u j , x j, j+1 ) and (u j+1 , x j, j+1 ), respectively, the interconnectivity graph for the mixed state case can be represented as depicted in Fig. 5.11.

F C

Direction of the control decision propagation u j u j+1 The Nash game problem for such a case is written as follows:

Problem 5.4.4 (Two-player competitive game)

u * j = argmin J j (u j , u * j+1 ) , u * j+1 = argmin J j+1 (u * j , u j+1 ) . (5.22)
We can solve the Problem 5.4.4 by executing the following procedure:

Procedure 5.4.3 (Solution steps for the Problem 5.4.4)

Step 1 Initialize u * j = u ini , assume ε 1 , ε 2 as small positive numbers,

Step 2 Find u * j+1 = argmin J j+1 (u * j , u j+1 ),

Step 3 Find u * j = argmin J j (u j , u * j+1 ),

Step 4 Repeat Steps 2, 3 until ∆ J j < ε 1 , ∆ J j+1 < ε 2 (∆ J j stands for the incremental change of the norm of the objective function J j ).

Illustrative Examples

Here we will present two illustrative examples on how the overall game Problem 5.4.1 is meant to be executed along several links of a freeway. In both examples, we will consider six controlled on-ramps dividing a freeway into five links. For two different freeway states, we will demonstrate how the Problem 5.4.1 is decomposed into two-player games and solved through corresponding procedures.

F C C F F F 1 2 3 5 Link Nr. 4 S D u 1 u 2 u 3 u 5 u 6 u 4 x 1
x 3 x 4,5 x 2

x 6 For the Example 1, let us consider the following scenario. The first three upstream links are fully in the free flow state. The congestion begins inside the fourth link, and it stretches downstream the rest of a freeway. For such a state, the inputs u 1 , u 2 , u 3 and u 6

will optimize the links 1,2,3 and 5, respectively. The inputs u 4 and u 5 will compete for the link 4. The interconnectivity graph corresponding to this case is shown in Fig. 5.14. Step 1 u 1 optimizes J 1 with respect to the given boundary demand D. Next, u 1 sends to u 2 the information of the optimal boundary demand flow for the subsystem x 2 . This demand corresponds to the optimal decision of the u 1 and is denoted by D * 1 . Similarly, u 6 optimizes J 6 with respect to the boundary supply S and sends to u 5 the information of the corresponding optimal supply flow S * 6 .

Sta Sta Sta Sta Com

Step 2 u 2 optimizes J 2 with respect to D * 1 and sends D * 2 to u 3 .

Step 3 u 3 optimizes J 3 with respect to D * 2 and sends D * 3 to u 4 .

Step 4 First u 4 guesses the optimal solution u * 4 and sends it to u 5 with the information of D * 3 . Next, u 5 optimizes J 5 with respect to u * 4 , D * 3 , S * 6 . The optimal solution u * 5 together with S * 6 is then sent to u 4 that similarly optimizes J 4 with respect to u * 5 , D * 3 , S * 6 and sends u * 4 to u 5 . The procedure is terminated when u 4 and u 5 reaches the Nash equilibrium. For the Example 2, let us consider the reverse state as depicted in Fig. 5.15. In this case, the inputs u 2 , u 3 , u 4 and u 5 will optimize the links 1,2,3 and 5, respectively. The inputs u 1 and u 5 stay uncontrolled. The interconnectivity graph corresponding to such a case is shown in Fig. 5.16. The subsystems S 2 , S 3 and S 4 are involved into Stackelberg games, while the isolated S 5 is meant to optimize its state independently. Step 1 u 5 optimizes J 5 with respect to the demand D4 that is computed by solving the dynamical equation for the uncontrollable link 4 (see 5.15). Similarly, by solving the same dynamical equation, u 4 computes S5 and optimizes J 4 . Next, u 4 sends S * 4 to u 3 .

1 2 3 5 Link Nr. 4 C C C C F F S D u 1 u 2 u 3 u 5 u 6 u 4 x 4 x 3 x 2 x 5

Sta Sta

Step 2 u 3 optimizes J 3 with respect to S * 4 and sends S * 3 to u 2 .

Step 3 u 2 optimizes J 2 with respect to S * 3 .

Local optimal control problem

In this section, we will provide an explicit solution for the Nash game problem. Namely, we will focus of the following problems: Find u * j = argmin J j that appear in the Procedures 5.4.1-5.4.3 (the problem of finding u * j+1 = argmin J j+1 in the mixed state case is treated analogously).

Control objectives

As stated in the introduction, our primal objective is to balance vehicle density. Since we use a non-cooperative game formulation, the balancing will be performed at the level of individual subsystems (freeway links). We will not utilize any predefined reference values. Instead, we will require that the resulting balanced density reduces travelling time acquired by the drivers associated to a subsystem. Therefore, for the local objective functions we will weight two metrics that correspond to the density balancing and the travelling time.

Let us introduce the Laplacian matrix associated to the subsystem x j :

Lap j (i, ī) =    n j -1 if i = ī , - 1 otherwise .
(5.23)

For the assumed structure of the state vector x j = ρ j 1 , ρ j 2 , ..., ρ j n j , l j ⊺ , the total dispersion of the vehicle density over the time interval [0, T ] can be measured by the following metric:

||x j || Lap = T k=0 i = ī (ρ j i (k) -ρ j ī (k)) 2 = T k=0 (x j (k)) ⊺ Lap j 0 0 0 x j (k) . (5.24)
The travelling time in freeway traffic is commonly computed by using the Total Travel Spent (TTS) metric defined as follows:

T T S = ∆t T k=0 n j i=1 ρ j i (k)L j i + l j (k) . (5.25)
The goal in minimizing TTS is to reduce the number of vehicles in both, the mainstream and in the queues. Reduced number of vehicles in the mainstream results in increased travel velocity, and thus shortened travelling time. Reduced number of vehicles in the queue directly results in shortened queuing time. Note that TTS is a trade-off. Decreased queue lengths increase the mainstream density and vice versa. For the sake of the adopted solution method, discussed below, we will use the quadratic objective function. By using the cell lengths matrix L j = diag (L j 1 , L j 2 , ..., L j n j ) the quadratic function corresponding to TTS can be written in the following form:

||x j || T T S = ∆t 2 T k=0 (x j (k)) ⊺ (L j ) 2 0 0 0 x j (k) + l 2 j (k) = ∆t 2 T k=0 (x j (k)) ⊺ (L j ) 2 0 0 1 x j (k) . (5.26)
Finally, by introducing a weighting number γ 1 , we can pose the local optimal control problem, where the goal is to minimize the weighted sum of the metrics (5.24) and (5.26):

Problem 5.5.1 (Local optimal control problem)

Find u * j = argmin J j J j = ∆t 2 T k=0 (x j (k)) ⊺ Lap j + γ 1 (L j ) 2 0 0 γ 1 x j (k)
Subject to (5.7), (5.8), (2.34) for the free flow state link (5.10), (5.11), (2.34) for the congested state link (5.13), (5.14), (2.34) for the mixed state link .

(5.27)

Note that in the case of the mixed state links, each of the controllers tends to optimize only its controllable section, i.e. for the link x j,j+1 , u j minimizes J j (x j ) and u j+1 minimizes

J j (x j+1 ).
The receding horizon scheme (Procedure 4. Therefore, the algorithm for solving a single Problem 5.5.1 has to enable us to terminate defined as:

z 1 (k) = z(k), z 2 (k) = z(k -1),...,z n(k) = z(k + 1 -n).
Then, by introducing:

A z = 1 ∆t        1 -α 1 α 2 • • • α n 1 -1 . . . . . . 1 -1        (5.31)
(5.29) can be written as:

z(k + 1) = z(k) + ∆t A z z(k) , (5.32)
with the initial condition:

z 1 (0) = z(0), z 2 (0) = z(-1),..., z n(0) = z(1 -n).
The form of (5.32) will now enable us to merge the flows into the dynamics of our local systems.

Let us first consider the free flow state link. We introduce AR model vectors z Dj , z Dj representing Dj and Dj , respectively. The extended state vector of the free flow state link will be defined as:

y j = x j , z Dj , z Dj ⊺ . (5.33)
The dynamical equation of the free flow state link (5.7) is represented as follows:

y j (k + 1) = y j (k) + ∆t Āf y j (k) + Bf u j (k) . (5.34)
Here Āf has a block diagonal structure composed of A f and two matrices A z . The vector Bf is build upon B f . Similarly, by introducing:

y j = x j , z Sj , z Dj ⊺ , (5.35)
where now z Sj refers to Sj , we can represent the governing equations for the congested state link (5.10):

y j (k + 1) = y j (k) + ∆t Āc y j (k) + Bc u j (k) . (5.36)
In the case of the mixed state link, we introduce the extended state vector as:

y j, j+1 = x j, j+1 , z Dj , z Dj , z Sj+1 , z Dj+1 ⊺ , (5.37)
where z Dj , z Dj , z Sj+1 and z Dj+1 corresponds to Dj , Dj , Sj+1 and Dj+1 , respectively. The dynamics (5.13) is now represented by:

y j, j+1 (k + 1) = y j, j+1 (k) + ∆t Āfc (k)y j, j+1 (k) + Bf u j (k) + Bc u j+1 (k) . (5.38)
A practical advantage arising from the use of AR model is that of significantly reduced amount of data needed to be exchanged by the controllers during the optimization process.

The full information of the interfacing flows { Dj } and { Sj } is now stored within the set of parameters {α i }. In practice, it is sufficient to use 4-5 parameters to represent flow time series of 30-50 values.

Point Boundary Value Problems:

∂H ∂u * j = 0 , H = p T Āfc y j, j+1 + Bf u * j + Bc u * j+1 - 1 2 (y j, j+1 ) ⊺ Q j y j, j+1 + γ 2 (u * j ) 2 ,
y j, j+1 (k + 1) = y j, j+1 (k) + ∆t Āfc (k)y j, j+1 (k) + Bf u * j (k) + Bc u * j+1 (k) , y j, j+1 (0) = y 0 , p(k + 1) = p(k) -∆t ∂H ∂y j, j+1 , p(T ) = 0 .

(5.42)

when searching for u * j , and:

∂H ∂u * j+1 = 0 , H = p T Āfc y j, j+1 + Bf u * j + Bc u * j+1 - 1 2 (y j, j+1 ) ⊺ Q j+1 y j, j+1 + γ 2 (u * j+1 ) 2 ,
y j, j+1 (k + 1) = y j, j+1 (k) + ∆t Āfc (k)y j, j+1 (k) + Bf u * j (k) + Bc u * j+1 (k) , y j, j+1 (0) = y 0 , p(k + 1) = p(k) -∆t ∂H ∂y j, j+1 , p(T ) = 0 .

(5.43)

when searching for u * j+1 . Notice that the convex formulation of the Problem 5.5.2 provides the existence of the Nash equilibrium for the game problem 5.4.1.

Study Cases

The developed control method will be tested on the CTM model of the south ring of Grenoble. For the optimization, we chose the western section of the ring of the length 6.07 [km]. On the considered direction, i.e. from east to west, this section is equipped with 4 on-ramps and 3 off-ramps (all of them are one lane) as demonstrated in Fig. 5.17.

The estimated model parameters are summarized in the table 5.1. For the split ratios we assume β1 = 0.82, β2 = 0.80, β2 = 0.80. The merging parameters p = 0.25 are assumed to be identical for each of the links.

In this study, we will consider two scenarios: one for uniformly congested traffic, and the other for transient traffic. In the first case, be means of previously defined metrics, we will examine the performance of the control method under steady congested boundary conditions. In the second case, we will begin the simulation of the free flow traffic with link 3 link 2 link 1 drop of downstream capacity. The goal will be to investigate the impact of state balancing on the propagation of the shock wave. Both cases will be evaluated with the time step of 5 seconds. We assume 20 time steps for the control/prediction horizon in the receding horizon scheme. Control decision will be updated every time step. We will demonstrate the results through a comparison of the optimal solutions (referred as closed-loop) with the evolution of the open-loop system, i.e. when the on-ramp demand stays uncontrolled.

Uniformly congested traffic

In this case, the initial values for density were randomly selected from the interval [170, 210]

[veh/km]. The initial queue lengths were set to l j = 10 [veh] for all j. In accordance to the information pattern introduced in the section 5.3, the controllers u 2 , u 3 and u 4 under the congested state will optimize the links 1, 2 and 3, respectively. The simulations will be carried over the time interval of 20 minutes under the following steady boundary conditions: S = 3100 [veh/h], Dj = 800 [veh/h] for all j. The state plots will be given only for the link 1. Trajectories for the other links do not exhibit any qualitative differences. Each of the links was split into 5 cells of the same length.

The on-ramp flow in the entrance 2 and the corresponding evolutions of the vehicle densities in the link 1 are depicted in Figs. 5.19 and 5.18, respectively. We can observe that the closed-loop system rapidly converges to a common value. To demonstrate better the convergence rate, Fig. 5.20 compares the evolutions of the balancing metric defined as: The comparison of the balancing metric ||x j || Lap (as defined in (5.24)) is presented in the table 5.2. Each value represents the metric computed in the closed-loop case divided by the metric in the case of open-loop system. For each of the links, the balancing metric was decreased more than 40 percent. (as defined in (5.26)) is decreased by 2-3 percent for each of the links. The weighted sum of the balancing and the travelling time metrics was reduced by 7-8 percent.

||x j || Lap (k) = (x j (k)) ⊺ Lap j 0 0 0 x j (k) . ( 5

Transient traffic

Transient traffic refers to the situations in which we observe the congestion either expanding or contracting. In particular, we can encounter the shock waves caused by the instantaneous drops of capacity. Based on the Rankine-Hugoniot conditions, the traffic shock wave speed is given by the formula:

v shock = Φ(ρ + ) -Φ(ρ -) ρ + -ρ - , (5.45)
where ρ + and ρ -denotes the densities on the right and left side of the wavefront. We are now interested in how the designed density balancing may impact on the shock wave propagation. Let us consider the following situation. A link is fully in the balanced free flow state (with some dispersion) and the downstream density of this link is equal to ρ -. The demand flow corresponding to such a density is Φ(ρ -). Assume that an instantaneous drop of capacity occurs just in front of the considered link. The capacity drop can be perceived as the flow Φ(ρ + ) corresponding to the density ρ + . It can be observed (see That means that the balancing is trying to keep ρ -smaller, and thus to reduce the difference Φ(ρ + ) -Φ(ρ -), but also to enlarge the difference ρ + -ρ -. From (5.45), it follows that in this case, we should expect a slowdown of the shock wave. This observation is only intuitive, and it is based on a continuum model. The impact of the balancing on the congestion propagation for the case of the Cell-Transmission model requires rigorous analysis that is out of the scope of this thesis and is dedicated for future works.

Φ(ρ)

ρ ρ - ρ + Φ(ρ + ) -Φ(ρ -) ρ + -ρ -
To support the intuitive observation, we consider the following scenario. We initialize the simulation with some free flow state and on-ramp boundary flows Dj = 600 [veh/h] for all j. For the first 150 time steps we reproduce the capacity drop by setting S = 2800 [veh/h]. During this time, we will observe a shock wave propagating upstream. For the time steps 151-400, we will set S = 3800 [veh/h] that will bring the system back to the free flow state. In this setting, the controller 1 will optimize the free flow section 1 by solving the hierarchical game. The other controllers will be involved into both, the hierarchical and the competitive games, since the sections 2 and 3 will be under the mixed states. To better capture the movement of the congestion wave, we divided each of the links into 8 cells. CHAPTER 6

Freeway Density Balancing via Consensus Protocols

In this chapter, an alternative approach of freeway density balancing will be presented.

The approach will utilize the consensus protocols. It will adopt the solution method of the distributed game problem presented in the previous chapter. The difference will be at the level of the local optimal control problems. Here, instead of minimizing the balancing metric (see the Problem 5.5.1), we will design feedback control structures providing that the states in the local subsystems achieve common values by evaluating consensus protocols. Under these structures, we will formulate an optimal control problem to minimize TTS metric (5.26). The chapter will present only the methodology. Implementation and validation are dedicated for future works.

We will begin with introducing the fundamental results on consensus protocols for discrete dynamical systems. Next, we will demonstrate how these protocols can be designed for the case of the freeway links. A modified system partitioning scheme, relevant to the new approach, will be then given. Next, we will show how this new partitioning impacts on the method of solving of the distributed Nash game problem. Finally, we will formulate a local optimal control problem, and we will discuss solution method.

Consensus protocols in discrete dynamical systems

In networks of dynamical systems (or agents), consensus refers to an agreement regarding a certain quantity of interest that depends on the state of all agents [START_REF] Olfati-Saber | Consensus and cooperation in networked multi-agent systems[END_REF]. In particular, this agreement may concern the state values itself. A consensus protocol is an interaction rule that determines the information exchange between the agents. A comprehensive theoretical framework on consensus problems can be found, for instance, in [START_REF] Olfati-Saber | Consensus problems in networks of agents with switching topology and time-delays[END_REF] and [START_REF] Olfati-Saber | Consensus protocols for networks of dynamic systems[END_REF]. Here, we will focus only on the fundamental results providing a framework for the problem of freeway density balancing.

Let us consider a linear dynamical system given in the form:

x(k + 1) = A x(k) . (6.1)
Let c be a real number. We say that the system (6.1) solves consensus problem (or that the system (6.1) is a consensus protocol) if and only if there exists an asymptotically stable equilibrium x * satisfying x * = c1, where 1 stands for the all ones vector. The necessary and sufficient condition for the system (6.1) to be a consensus protocol is that matrix A has a single eigenvalue of 1 with the corresponding eigenvector 1, and all other eigenvalues are located in the unit circle. Of special interest reflecting this spectral property is the family of matrices called stochastic matrices.

A is a stochastic matrix if it is a square matrix of nonnegative real numbers, with each row summing to 1. It follows from the definition that for a stochastic A we have:

A 1 = 1 . (6.2)
Therefore, stochastic A has always eigenvalue of 1 with the corresponding eigenvector 1.

To verify that the other eigenvalues of stochastic A are inside the unit circle, let us denote the entries of A n×n by a ij , and define:

∆ = max i n j=1,j =i a ij . (6.3)
By following the Gershgorin theorem [START_REF] Horn | Matrix Analysis[END_REF], all eigenvalues of A in the complex plane are located in a closed disk with the center placed at (1 -∆) + 0i and the radius ∆. Since 0 ≤ ∆ ≤ 1, it is easy to verify that all eigenvalues of A lie inside the unit circle. To guarantee that the system:

x(k + 1) = A x(k) (6.4) solves the consensus problem, it is required that A has a single eigenvalue of 1. This property can be verified by checking the connectivity of the corresponding directed graph.

Any stochastic matrix can be associated to the directed graph. The entry a ij is a positive number, if in the corresponding directed graph the node i receives the information for the node j. Otherwise, it is equal to zero. We say that a directed graph has a spanning tree if and only if there exists a node having a directed path to all other nodes. The necessary and sufficient condition for stochastic A to have a single eigenvalue of 1 is that the corresponding graph has a spanning tree.

Consensus protocols for the freeway links

In this section, we will show that for the homogeneous state links we can design feedback controls providing that the dynamics solve the consensus problems. The goal will be to determine the set of feedback gains admissible for consensus. In particular, we will be interested in the set assuring that consensus is solved under variable gains. It is crucial for the optimal design implemented through the receding horizon scheme.

Let us first recall the dynamics of the free flow link as introduced in the Chapter 5. By introducing:

A f = v j L j inv           -1 0 1 -1 0 . . . . . . . . . 1 -1 0 0 • • • 0 0 0           , B f = L j inv           1 0 . . . 0 -1           , C f = L j inv           1 0 . . . 0 0           , D f = L j inv           0 0 . . . 0 1           , (6.5)
the free flow link is governed by:

x j (k + 1) = x j (k) + ∆t(A f x j (k) + B f u j (k) + C f Dj (k) + D f Dj (k)) . (6.6)
For the sake of the further studies, we will decompose the state vector x j into xj and l j , where:

xj = ρ j 1 , ρ j 2 , ..., ρ j n j ⊺ . (6.7)
Le us define Lj inv = diag (1/L j 1 , 1/L j 2 , ..., 1/L j n j ) and:

Āf = v j Lj inv        -1 1 -1 . . . . . . 1 -1        , Bf = Lj inv        1 0 . . . 0        , Cf = Lj inv        1 0 . . . 0        . ( 6.8)
Now (6.6) is represented by:

xj (k + 1) = xj (k) + ∆t( Āf xj (k) + Bf u j (k) + Cf Dj (k)) , l j (k + 1) = l j (k) + ∆t( Dj (k) -u j (k)) . (6.9)
Since our goal is to design a consensus protocol to balance mainline density, we will focus only on the dynamics for the vector xj . We define the feedback gain vector p j = p j 1 , p j 2 , ..., p j n j

⊺

. Under the assumption that the control takes the form:

u j (k) = v j (p j ) ⊺ xj -Dj (k) , (6.10)
mainline dynamics is written as follows:

xj (k + 1) =               1 1 . . . 1        + ∆t v j Lj inv        -1 + p j 1 p j 2 • • • p j n j 1 -1 . . . . . . 1 -1        +        xj (k) . (6.11)

Chapter 6. Freeway Density Balancing via Consensus Protocols

Let us now define:

Āf (p j ) =        1 1 . . . 1        + ∆t v j Lj inv        -1 + p j 1 p j 2 • • • p j n j 1 -1 . . . . . . 1 -1        . (6.12)
To guarantee that the system:

xj (k + 1) = Āf (p j ) xj (k) (6.13)
solves the consensus problem, we need to verify if Āf (p) is stochastic and its corresponding graph has a spanning tree. To provide that Āf (p) has nonnegative entries, we set: .14) Note that thanks to the Courant-Friedrichs-Lewy condition (see 2.22), the diagonal elements for the rows 2, 3, ..., n j are always nonnegative. Each row of Āf (p) is summing to 1 iff:

∆t v j L j 1 (p j 1 -1) + 1 ≥ 0 , p j i ≥ 0 , i = 2, 3, ..., n j . ( 6
n j i=1 p j i = 1 . (6.15)
The conditions (6.14) and (6.15) guarantee that the matrix Āf (p) is stochastic. Now we will demonstrate that the corresponding directed graph has a spanning tree. Consider the i=1 p j i = 1, this graph has a spanning tree with the root in the node 1. Therefore, under (6.14) and (6.15) the system (6.13) solves the consensus problem.

The analysis for the case of the congested link can be carried out in analogous way. By assuming the control:

u j (k) = βj w j (p j ) ⊺ xj -βj w j ρj + Sj (k) , (6.16)
the mainline dynamics is represented by:

xj (k + 1) =               1 1 . . . 1        + ∆t w j Lj inv        -1 1 -1 1 . . . . . . p j 1 p j 2 • • • -1 + p j n j        +        xj (k) . (6.17)
We can easy verify that the matrix:

Āc (p j ) =        1 1 . . . 1        + ∆t w j Lj inv        -1 1 -1 1 . . . . . . p j 1 p j 2 • • • -1 + p j n j        (6.18)
is stochastic under the conditions:

∆t w j L j n j (p j n j -1) + 1 ≥ 0 , p j i ≥ 0 , i = 1, 2, ..., n j -1 , n j i=1 p j i = 1 . (6.19)
The directed graph corresponding to Āc (p j ) (see Fig. 6.2) has a spanning tree in the node n j .

Consensus protocol under varying feedback gains

The consensus conditions derived in the previous section apply only for the systems operating on constant feedback gains. In our setting, we will use the receding horizon scheme, to provide that the systems apart form converging to a common density are realizing some optimal policies. For that purpose, we will now study the consensus problem under variable gains. Instead of p j we will now consider p j (k) and the close loop systems representing respectively free flow and congested link:

xj (k + 1) = Āf (p j (k)) xj (k) , (6.20
)

xj (k + 1) = Āc (p j (k)) xj (k) , (6.21)
where Āf and Āc are defined as in before. Our goal is to determine the set P j f (P j c ) such that for any sequence p j (1), p j (2), ..., where ∀k : p j (k) ∈ P j f (∀k : p j (k) ∈ P j c ), the system (6.20) ((6.21)) solves the consensus problem.

Let us first introduce the notion of the Stochastic Indecomposable and Aperiodic (SIA) matrix. A stochastic matrix A is said to be indecomposable and aperiodic if:

lim n→∞ A n = 1 c ⊺ , (6.22)
where 1 is the vector of all ones and c is the vector with nonnegative entries summing to one. From Lemma 5 in [START_REF] Liu | Consensus of multi-agent networks with aperiodic sampled communication via impulsive algorithms using position-only measurements[END_REF], it follows that for A to be SIA it is sufficient that it is stochastic with positive diagonal elements and its corresponding graph has a spanning tree. Now in Theorem 5 in [START_REF] Coppersmith | Conditions for weak ergodicity of inhomogeneous markov chains[END_REF], we read that for a compact set of SIA matrices {A i } with nonzero diagonal elements, the product A n A n-1 ... A 1 converges exponentially to a rankone matrix 1 c ⊺ . Therefore, to assure that the system (6.20) solves consensus problem, it is sufficient to provide that for every p j (k) ∈ P j f the matrix Āf (p j (k)) is SIA with nonzero diagonal elements and the set { Āf (p j (k))} is compact. Now let ε be a small positive number and assume:

P j f = p j (k) : ∆t v j L j 1 (p j 1 (k) -1) + 1 ≥ ε , p j i (k) ≥ 0 , i = 2, 3, ..., n j , n j i=1 p j i (k) = 1 . (6.23)
Then, we can verify that p j (k) ∈ P j f guarantees that every Āf (p j (k)) has non-zero diagonal entries (Courant-Friedrichs-Lewy condition provides that the diagonal entries for the rows 2, 3, ..., n j are positive) and its corresponding directed graph has a spanning tree, and thus Āf (p j (k)) is SIA. Moreover, the set { Āf (p j (k))} is compact (provided by the compactness of P j f ).

Similarly, if we assume:

P j c = p j (k) : ∆t w j L j n j (p j n j (k) -1) + 1 ≥ ε , p j i (k) ≥ 0 , i = 1, 2, ..., n j -1 , n j i=1 p j i (k) = 1 , (6.24)
then { Āc (p j (k))} is a compact set of SIA matrices with non-zero diagonal entries, and thus (6.21) solves consensus problem under p j (k) ∈ P j c . Both sets P j f and P j c will be used in the formulation of the local optimal control problems, presented in the section 6.4.

System partitioning

In this section, we will introduce system partitioning scheme suitable for design of the consensus protocols. Namely, the scheme will provide that each of the local subsystems will be driven either by (6.20) or by (6.21).

Similarly to the partitioning scheme introduced in the previous chapter, the assignment of the state vector xj to the control input u j is made on the controllability rule: xj is composed of the states of the closest controllable for u j link. In the case where both surrounding links are controllable (congested upstream and free flow downstream), we select the congested link. Besides the controllability, here we also require that: The assignment in the case of the homogeneous state links is presented in Figs. [START_REF] Papageorgiou | Freeway ramp metering: An overview[END_REF].3 and 6.4 and it is equivalent to the one presented in the previous chapter. It is easy to very that in the free flow case, the subsystem selection provides that its dynamics can be represented by (6.20). The upstream boundary flow φ j = Dj ( Dj stands for the demand for the subsystem j) can be cancelled by the substitution (6.10), and the downstream boundary flow φ j = Dj+1 depends on the state xj . In the case of the congested link, the substitution (6.16) cancels the flow φ j+1 = Sj ( Sj stands for the supply for the subsystem j), while φ j = Sj-1 depends on the state xj .

In the case of the controllable mixed links, the subsystem selection is shown in Fig. 6.5.

For the control input u j we associate the free flow section excluding the downstream cell.

This selection assures that the downstream boundary flow is uniquely determined by the state xj . If we selected the whole free flow section, then, as a result of the switching flow φ j+1 = min{ Dj+1 , Sj }, it might happen that the downstream boundary flow is equal to the supply, and thus the dynamics of the subsystem j would contain exogenous input. Similarly, for the control input u j+1 we select the congested section excluding the upstream cell. Note that for the mixed state links the defined partitioning completely separates the subsystems. This will have an impact on the solution method of the game problem as discussed in the next section.

Nash game for the consensus problem in the freeway links

Here, Nash game will be formulated analogously to the Problem 5.4.1. Each of the subsystems (u j , xj , l j ) (here xj is selected according to the scheme presented in the previous section) has associated objective J j (u j , xj , l j ). Let u -j be the set of the decision of the controllers that may influence the state xj , excluding the decision of u j . The objective functions can be represented by J j (u j , u -j ). The Nash game is now formulated as follows: Problem 6.4.1 (Nash game for the consensus problem in the freeway links)

Find {u * j } such that ∀j : u * j = argmin J j (u j , u * -j ) .

Here, the local optimal control problems are given by: Problem 6.4.1 (Local optimal consensus problem for the free flow subsystem)

Find u * j = argmin J j = ∆t 2 T k=0 n j i=1 (L j i xj i (k)) 2 + (l j (k)) 2 + γ(u j (k)) 2 Subject to xj (k + 1) = Āf (p j (k)) xj (k) , l j (k + 1) = l j (k) + ∆t( Dj (k) -u j (k)) , u j (k) = v j (p j (k)) ⊺ xj -Dj (k) , (5.8)
, (2.34), p j (k) ∈ P j f . Problem 6.4.2 (Local optimal consensus problem for the congested subsystem)

Find u * j = argmin J j = ∆t 2 T k=0 n j i=1 (L j i xj i (k)) 2 + (l j (k)) 2 + γ(u j (k)) 2 Subject to xj (k + 1) = Āc (p j (k)) xj (k) , l j (k + 1) = l j (k) + ∆t( Dj (k) -u j (k)) , u j (k) = βj w j (p j (k)) ⊺ xj -βj w j ρj + Sj (k) , (5.11), (2.34), p j (k) ∈ P j c .
The game problem is formulated in the way that was introduced in the Chapter 5. The difference appears at the level of local optimal control problems. Here, instead of minimizing the weighted sum of balancing and the Total Travel Spent metrics, we tend to minimize the total travel spent term only. The balancing is provided by the constraints establishing the consensus protocols. The regularization term (u j (k)) 2 is introduced to provide strict convexity of the local problems and the existence of the Nash equilibrium.

Sketch of the solution

The game problem 6.4.1 is meant to be treated analogously to the method presented in the Chapter 5. Here, we will only focus on the differences resulting from the new scheme of subsystem selection.

As demonstrated in the Chapter 5, the game can be solved by performing a sequence of two-player games. Since the new system partitioning is identical in the case of the homogeneous state links, the Stackelberg games for the consensus problem take the form of the Problem 5.4.2 (for the link in the free flow state) and 5.4.3 (for the link in congested state). The games can be solved by executing the Procedure 5.4.1 and 5.4.2, respectively.

In the case if the mixed state links, the new subsystem selection (see Fig. where each of the subsystems solves its local problem independently.

To solve the local problems 6.4.1 and 6.4.2, we can use quadratic programming solvers, for instance, Ipopt (see [95]). To provide a descend direction, the gradient can be derived by introducing the adjoint state. Note that it may occur that for some time periods, the set defined by the constraints in the problems 6.4.1 and 6.4.2 may be empty. That means that due to the control constraints, the consensus structure is not feasible. In such cases, we let the system to operate in the open-loop. The implementation of the presented method as well as the analysis on how the temporary lose of the consensus structure may impact on system performance are dedicated for future works.

CHAPTER 7

Balancing of the Freeway Traffic Density: Microscopic Validation

The aim of this study is to examine the control method presented in the Chapter 5. A performance of the designed optimal density balancing will be tested through the simulations carried on with the use of Aimsun micro-simulator. A case study will involve real traffic data collected on the south ring of Grenoble. At first, we will discuss the implementation aspects. In particular, we will focus on the setting of the distributed controller by describing the functionality of the single modules. Next, we will verify the efficiency of the control method by comparison to uncontrolled (open-loop) case. Firstly, we will examine the optimized metrics, i.e., the balancing and the travelling time metrics. In the sequel, a number of non-optimized traffic measures will be verified.

Aimsun representation of the south ring of Grenoble

Selected for this study part of south ring of Grenoble is a two lane freeway linking the motorway A41 with A480 from the north-east to the south-west. It is 10.5 km long, and it contains 11 inputs (1 mainstream input and 10 on-ramps) and 10 outputs (1 mainstream output and 9 off-ramps). On the considered direction it serves over 45000 vehicles everyday. The speed limit is established at 90 km/h, while during the heavy congestion it is reduced (by using the variable speed limiting panels) to 70 km/h. Depending on the traffic state travelling time (for the whole south ring) may vary from 15 up to 50 minutes.

The selected freeway was created as an Aimsun model serving for the prediction and control simulating platform for the Grenoble Traffic Lab. The geometry of designed model respects the details of the mainline and the junctions of the real freeway. The Aimsun view of the created model is depicted in Fig. 7.1. Apart from the ring mainline, the on-ramps and the off-ramps, also a set of side road network were created, in particular, those that were performed (see the results presented in the Table 3.3). In the cases where the parameter was set below 50%, we observed that due to egoistic behavior of the mainline vehicles, the on-ramp vehicles were cumulated in the right lane and only occasionally were enabled to join mainstream. This phenomenon can significantly reduce the efficiency of the ramp metering strategies and it should be avoided. On the other hand, when the cooperation was set to 100% (corresponding to full cooperation) we noticed that the mainstream vehicles clearly slow down to give the priority to the entering ones. To reflect the reality, we established the cooperation at 80%. Of special importance are also the parameters that determine the constraints in the vehicle dynamics. In particular, the acceleration/deceleration rates that significantly influence the behavior in the heavy congestion as well as the dynamics of the vehicles queuing and leaving on-ramps. Finally, we can set the average vehicle length and the minimum vehicle inter-distance, and thus we are able to determine the jam density.

Implementation of the ramp meters

Among 11 available ring inputs, all 10 on-ramps were selected to be equipped with the ramp metering systems (mainline upstream demand is treated as the uncontrolled bound- Based on measured flow information, we are able to count on-ramp vehicles located between the detectors. In the control algorithm, all vehicles counted between the on-ramp detectors are assumed to be in the queue. Thus, to avoid the overestimation of the queue lengths, the distance between the detector can not be too large. On the other hand, if the distance between the detectors is to small, then the queue lengths may be underestimated.

In our setting, the on-ramp sensor's inter-distance is established so to be able to fit at most 50 vehicles.

Ramp meter signalling is set to operate on 15 seconds cycles. For each of the cycles, the controller will return its decisions in terms of the duration of the green light. The preliminary simulations showed that during 15 seconds cycle at most 8 queuing vehicles can be served into mainline. Thus, the upper bound for each of the control input is set to 1920 [veh/h]. It is evident that in this setting, the available control values are quantized and the optimal control defined on the complete space needs to be approximated. As a consequence, we can expect some losses of performance. An important difficulty is concerned with the presence of different types of vehicles (cars and trucks) possessing different acceleration characteristics. As a result, by setting the same green light duration, we can obtain different input flows. In real freeway system, this issue can be resolved by applying vehicle counter (based on the measurement of the detector located right after ramp metering signal). Lack of an equivalent tool in Aimsun is a significant limitation.

Simulation results

Under the presented scenario a set of simulations were carried on. Here we will demonstrate a comparison between open-loop (uncontrolled) and closed-loop (under the controller designed in the Chapter 5) cases. We will be interested in the performance in terms of the optimized metrics. We will show that there is a correlation between density balancing and fuel consumption. Next, we will verify a set of non-optimized metrics taking into account both, the mainstream and its local urban network. The results related to the mainstream will be displayed for the links ordered as shown in Fig. 7.10.

At the beginning let us compare the evolution of vehicle densities over mainstream as depicted in Figs. 7.11 and 7.12. Under the considered scenario, the traffic is mostly congested and several times reaches the jam densities, in particular, in the downstream links 8 and 9, where the capacity is dropped down, due to turns and speed limits.

Upstream links 1 and 2 become congested due to distance placement of the output (the first off-ramp is located at the end of the link 2) and high demands in the on-ramps 2 and 3. Heavy congestion in the link 4 mostly results from short lack of the output. Comparing Figs. 7.13 and 7.13 are to compare the evolution of the on-ramp queues. We can observe that in both cases the queue lengths can be related to the corresponding rates of mainstream congestion (determining the supply for the entering flow) and the magnitudes of the on-ramp demands. The most crowded entries are the ones indicated by the numbers 1,2,5,8 and 9. As we can expect, in most of the time instants, the metering case results in longer queues. Nevertheless, the loss from the open-loop case is kept at the acceptable rate for each of the on-ramps.

In Fig. 7.15, we demonstrate the comparison of the balancing metric defined in (5.24).

For each of the links, the value of this metric was successfully decreased. The best balancing performance was reached within the links in which the off-ramps are located just before the on-ramps. For the links where the output is placed in the middle the state becomes ruptured, and thus, precise balancing is not feasible.

Balancing metric comparison

Open-loop Closed-loop

Fuel consumption comparison

Open-loop Closed-loop In Fig. 7.16, we show the comparison of the fuel consumption computed with the use of the microscopic model presented by Treiber and Kesting in [START_REF] Treiber | Traffic Flow Dynamics[END_REF]. The model takes into account both, velocity and acceleration. In the closed-loop case, the averaged (over time and mainline length) fuel consumption was decreased by 4.2 percent. The comparison of 7.16 to 7.15 testifies that there is a relation between the balancing and the fuel consumption metrics. In the links 1,2,4 and 6, where the balancing metric was most successfully reduced (70-85 percent), we can also observe that the fuel consumption was significantly decreased (7-8 percent).

Finally, we will examine a set of non-optimized metrics to justify how the proposed control method impacts on the traffic flowing over the mainline, but also over the neighboring urban network. Each of the Aimsun simulations returns a variety of statistics based on the state of all vehicles appearing in the simulation. Some of the metrics take into account also so called virtual queues, i.e., the vehicles cumulated behind the visible parts of the entrances. In Fig. 7.17, we compare the following metrics:

• Total Travel Distance (TTD) -as defined in (3.13). Increased by 2 percent (in the closed-loop case). • Total Time Spent (TTS) -time spent during the travel, including the queuing time.

Reduced by 5 percent.

• Delay time -time spent in on the queues, including the virtual queues. Reduced by 18 percent.

• Number of Stops -total number of stops of all vehicles. Increased by 2 percent as the consequence of the ramp metering.

• Average Velocity -average velocity of all vehicles averaged over time. Increased by 3 percent.

• Average Density-vehicle density averaged over time and space. Decreased by 4 percent.

• Fuel Consumption -average fuel consumption of all vehicles. Decreased by 2 percent.

Based on the presented results, we can conclude that the density balancing has also a positive impact on the standard traffic metrics. In particular, the fuel consumption in the mainline was significantly decreased. On the other hand, ramp metering enforces vehicles to stop and go which in turn costs some additional fuel in the entrances. Nevertheless, the global consumption over the whole Grenoble south ring network was reduced. For the time spent, the obtained 5 percent of improvement is also a notable value. Still open is the problem of selection of the weighting factor between the balancing and the TTS metric (γ 1 in the Problem 5.5.1). In our choice, the priority was not to allow to build up long queues. However, some test were also carried on to verify the traffic states when for selected entrances we allow to reach the maximum storage capacity (some of the ring entrances extended with local side roads allow to store up to 150 queuing vehicles).

The resulting states were more beneficial for the mainline, where the vehicles travelled smoother and the average velocity was increased by 7-8 percent. Under this condition also the balancing metric was successfully reduced. However, the delay time caused by the queuing was significantly increased by 12 percent.

CHAPTER 8

Conclusions and Future Directions

The aim of this thesis was to design, implement and validate a distributed control method for optimal balancing of vehicle density over a freeway. This chapter summarizes and concludes the contributions of the thesis. A number of potential extensions is then proposed.

In the Chapter 3, we have studied the sets of equilibria for freeway traffic represented by the Cell Transmission Model. We have elaborated a methodology that allows us to compute the optimal set point such that the steady state, represented by the vehicle density, is balanced along a freeway. A proposed optimization method has a limitation in size of the tractable system, when performed on a single computer. Nevertheless, the general problem has been decomposed into simple quadratic problems that potentially can be solved in parallel. In the analysis, we have limited our attention to the case that provides one-toone mapping between inputs and equilibrium states. This case requires two conditions to be satisfied. First, total demand weighted with split ratios must not exceed supply for the downstream boundary. Second, all cells are in the free flow mode. Under these conditions, we have shown that the balanced state exists only if the additional relation between free flow velocities and split ratios holds. This suggests that in practical design of balanced equilibria, we may need to use both ramp metering and variable speed limiting, where speed limits depend on actual values of the split ratios.

In the Chapter 5, we have presented a method for distributed optimal balancing of vehicle distribution over freeway via use of ramp meters. In this method, the controllability has been taken as the principle underlying both, the system partitioning and the topology of the information exchange. As we have demonstrated, the selection of the controllable subsystems strictly depends on the traffic state. This fact is often ignored in the methods of freeway traffic optimization while the controllability is a crucial factor in the convergence 104 Chapter 8. Conclusions and Future Directions of numerical procedures. To execute the optimization under the assumed information patterns, we have formulated a non-cooperative Nash problem. It follows that this formulation is not only convenient for a design of distributed optimization scheme process, but, under the defined balancing objective, it may also cause the slow down of the congestion propagation.

In the Chapter 6, an alternative method for density balancing has been proposed. The method uses fundamental properties of dynamical systems built upon the stochastic ma- The following points are dedicated for future works:

• Analysis on the case presented in section 5.6.2, i.e., how the balancing may impact on the slowdown of the shock wave.

• Studies on alternative variants in the controller's architecture. Namely, the task would be to consider the cases where a module contains not only one but a group of ramp meters. Each of these modules would be involved in the analogous game problem. We would be interested in how different choices of the modules impacts on the optimality in terms of globally defined metrics.

• Comparison to the existing controllers, in particular, to those operating in similar decentralized structures.

• Implementation of the balancing via consensus protocols.

• Studies on how the proposed idea of balancing can be brought into urban traffic.

One of the potential application may concern large roundabouts. The goal would be to balance the state of the circulating flow.

Figure 1 . 1 :

 11 Figure 1.1: Ramp signals on a California freeway. Source: http://www.mtc.ca.gov.

Figure 1 . 2 :

 12 Figure 1.2: Scheme of a closed-loop metering control system.

Figure 1 .

 1 Figure 1.3: Centralized (a) vs distributed (b) controller's architecture.

1 .

 1 Pisarski D., Canudas-de-Wit C.: Optimal Balancing of Traffic Density: Application to the Grenoble South Ring. Proceeding of the IEEE European Control Conference, pp 4021-4026 (2013) 2. Pisarski D., Canudas-de-Wit C.: Optimal Balancing of Road Traffic Density Distributions for the Cell Transmission Model. Proceeding of the IEEE Conference on Decision and Control, pp 6969-6974 (2012) 3. Pisarski D., Canudas-de-Wit C.: Analysis and Design of Equilibrium Points for the Cell-Transmission Traffic Model. Proceeding of the IEEE American Control Conference, pp 5763-5768 (2012) Chapter 1. Introduction The following papers have been submitted for journal publishing: 1. Pisarski D., Canudas-de-Wit C.: Nash Game Based Distributed Control Design for Balancing of Traffic Density over Freeway Networks, submitted to Transactions on Control of Network Systems (2014) 2. Pisarski D., Canudas-de-Wit C.: Steady State Balancing in Freeway Traffic Systems, submitted to Transportation Research Part B (2013)

Figure 1 . 4 :Chapter 5 .

 145 Figure 1.4: Schematic organization of the thesis.

Figure 2 . 1 :

 21 Figure 2.1:A freeway section stretched between the points y1 and y2. The inflow and the outflow are denoted by φ(y1, t) and φ(y2, t), respectively. The density inside the section is described by the distribution ρ(y, t). The conservation of vehicles states that the rate of change in the number of vehicles is equal to the difference between inflow and outflow.

Figure 2 . 2 :

 22 Figure 2.2: The Fundamental Diagrams: Greenberg (a) and its trapezoidal approximation (b).

FFigure 2 . 3 :

 23 Figure 2.3: The triangular fundamental diagram used in CTM. The shape is determined by the parameters: v -free flow velocity, w -congestion wave speed, ρ -jam density.

Figure 2 . 4 :

 24 Figure 2.4: Freeway representation in CTM. A considered section is divided into n cells. Each cell can be accompanied with at most one on-ramp and one off-ramp.

Figure 2 . 5 :

 25 Figure 2.5: The flows merging at a freeway entrance. The merge model determines the rate of the flows φ and r under given demands D, u and supply S.

Figure 2 . 6 :

 26 Figure 2.6: The maximum control input (the virtual demand) resulting from external demand and vehicles queuing on-ramp.

Figure 3 . 2 :

 32 Figure 3.2: A part of a freeway and the corresponding distribution of vehicle density (green bars). Ramp meters coordinate the traffic so to achieve a uniformly distributed vehicle density.

Figure 3 . 3 :

 33 Figure 3.3: Single section solution for (3.14) in the case of the free flow (a) and the congested (b) state. The grey dot represents the optimal equilibrium density. The placement of this point results from the choice for the parameter α as indicated by the arrows.

(3. 18 )

 18 Let us define Γ as the one-to-one mapping ∆ u -→ ∆ x as written in (3.18). Based on (3.15)-(3.17) we can formulate the necessary condition for the existence of Γ in terms of boundary conditions, split ratios and control inputs. Chapter 3. Analysis on the Sets of Equilibrium Points for the Cell-Transmission Model Proposition 3.4.1. There exist the mapping Γ only if :

Figure 3

 3 Figure 3.4: The set of free flow equilibrium states for the case of a two-cell system. The grey trapezium is for the set ∆x. The blue line indicates the balanced states. A part of this line contained in ∆x represents the set ∆xB.

Figure 3 . 5 :

 35 Figure 3.5: Google Maps view on the Grenoble South Ring and the cell division used in CTM.

  3.6), and we simulated a Chapter 3. Analysis on the Sets of Equilibrium Points for the Cell-Transmission Model

  on-ramp demands (D + u > S). Under the additional conditions D ≥ (1 -p)S, u ≥ pS satisfied, we measured the flows r and φ and computed the merging parameter by using the formula p = r/(φ + r) (derived from the Daganzo model).

Figure 3 . 6 :

 36 Figure 3.6: On-ramp and mainstream flow merging experiment: sensors placement.

  300 [veh/h]. On the other hand, the external demands enable us to produce the maximum admissible input u max = 1600 [veh/h]. The initial state is represented by the vector x ini = (50, 43, 40, 45, 50, 68, 70) [veh/km]. The goal is to find a set of input demands such that the system will be driven to the free flow balanced steady state with vehicle density c = 55 [veh/km]. The Problem 3.5.2 was solved for three different cases. For every case, the weighting parameter in the objective function was γ = 0.1 .

Figure 3 . 7 : 40 Chapter 3 .

 37403 Figure 3.7: Space-time distribution of vehicle density under the optimal input for the calibrated model.

Figure 3 . 8 :

 38 Figure 3.8: Space-time distribution of vehicle density for the case of speed limits providing the exact balance.

  dition. By using (3.26) we can determine the required set of velocities, that is: v = (80, 72, 80, 72, 80, 68, 80) [km/h]. In practice, this adjustment can be realized by introduc-

3. 7 . Case studies 41 Figure 3 . 9 :

 74139 Figure 3.9: Space-time distribution of vehicle density for the case of uniform VSL (80 [km/h]).

Figure 3 . 10 :

 310 Figure 3.10: Space-time distribution of vehicle density under the presence of bottleneck.

u 1 ∈

 1 [300, 1600] and u 3 ∈ [648, 1600] . The system evolution from the initial state x ini = (140, 150, 110, 100, 120, 140, 180) is presented in Fig. 3.10. The steady state is clearly more unbalanced than in the free flow cases. The previous example demonstrates how the presence of bottleneck enforces low val-Chapter 3. Analysis on the Sets of Equilibrium Points for the Cell-Transmission Model

. 22 )

 22 To solve the Problem 4.1.1, one can follow the following steps: Procedure 4.3.1 (Steepest descent method for the Problem 4.1.1)

(4. 33 )

 33 Instead of solving the Two Point Boundary Value Problem (4.33), one can use the gradient method by performing the Procedure 4.3.1.

Figure 4 . 1 :

 41 Figure 4.1: Principle of the receding horizon control scheme for the freeway traffic optimization.

4. 6 .

 6 Distributed optimization via non-cooperative Nash game 53 the Bellman's Principle of Optimality

Procedure 4. 5 . 1 (

 51 Receding horizon control)Step 1 At time sample k, estimate the state x(k) and predict the evolution of the boundary conditions in the time period [k, k + T ].

Figure 4 . 2 :

 42 Figure 4.2: A generic interconnectivity graph. An arrow from Si to Sj indicates that subsystem Si affects subsystem Sj.

Figure 5 . 1 :

 51 Figure 5.1: Homogeneous state links under their control inputs. The links are controllable by the inputs denoted by the bold arrows.

5 . 2 .

 52 More complex internal state structures are very rarely observed through the real traffic data.

Figure 5 . 2 :

 52 Figure 5.2: Mixed state links under their control inputs. The links are controllable by the inputs denoted by the bold arrows.

. 1 )Chapter 5 .

 15 Now consider a link for which the relation Φ(ρ) is determined by the triangular fundamental diagram (given by: φ(ρ) = vρ if ρ ≤ ρ cr , and φ(ρ) = w(ρ -ρ) otherwise. See Fig 2.3) with v and w being constant along this link. Depending on the internal state of the link, we can have either ∂ ρ Φ(ρ) = v (for a section in the free flow state) or ∂ ρ Φ(ρ) = -w (for a section in the congested state). Now suppose we are given the initial condition ρ(y, 0). Nash Game Based Distributed Control Design for Balancing of Freeway Traffic Density

Figure 5 . 3 :

 53 Figure 5.3: State information pattern. Each of the controllers receives the density information of two neighbouring links.

Figure 5 . 4 :

 54 Figure 5.4: System partitioning in the cases of the homogeneous free flow state link.

Figure 5 . 5 :

 55 Figure 5.5: System partitioning in the cases of the homogeneous congested state link.

Figure 5 . 6 :

 56 Figure 5.6: System partitioning in the case of the mixed state link.

Figure 5 . 8 :

 58 Figure 5.8: Propagation of the control decisions in the case of the homogeneous state links.

Fig. 5 .Figure 5 . 9 :

 559 Fig. 5.9a. The graph representing the congested case is shown in Fig. 5.9b. a b

1 (

 1 Solution steps for the Problem 5.4.2)

Figure 5 . 10 :Figure 5 . 11 :

 510511 Figure 5.10: Propagation of the control decisions in the case of the mixed state links.

Figure 5 . 12 :

 512 Figure 5.12: Best response curves and the Nash Equilibria. The arrows represent the procedure steps for finding the Nash Equilibria in the case of the free flow state Stackelberg game (a), the congested state Stackelberg game (b) and the mixed state competitive game (c).

Figure 5 .

 5 Figure 5.13: A section of a freeway used in the Example 1.

Figure 5 . 14 :

 514 Figure 5.14: The interconnectivity graph for the Example 1. Sta and Com stands for Stackelberg and competitive game, respectively.

Figure 5 .

 5 Figure 5.15: A section of a freeway used in the Example 2.

Figure 5 . 16 :Procedure 5 . 4 . 5 (

 516545 Figure 5.16: The interconnectivity graph for the Example 2. Sta stands for Stackelberg game.

5 . 1 )

 51 requires solving of the Problem 5.4.1 at each time step which in practice is assumed to be less than 15 seconds. During this time, the Procedures 5.4.1-5.4.3 may demand for the solution of the Problem 5.5.1 up to several dozen times, depending on the freeway length and number of the mixed state links.

Figure 5 .

 5 Figure 5.17: A three link section of the south ring of Grenoble used in the simulations.

Figure 5 . 18 :

 518 Figure 5.18: Evolution of the mainstream state in the link 1 (each of the curves represents one cell).

Figure 5 . 19 :

 519 Figure 5.19: Comparison of the on-ramp flows in the entrance 2.

Figure 5 . 20 :

 520 Figure 5.20: Evolution of the balancing metric for the link 1. The closed-loop system evidently improves the convergence rate.

Figure 5 . 21 :

 521 Figure 5.21: Evolution of the queue length in the entrance 2.

Figure 5 . 22 :

 522 Figure 5.22: The idea of shock wave slow down via density balancing. The circles indicate the density values.

Fig. 5 .

 5 Fig. 5.22) that the balancing strategy is trying to keep the downstream density value (the circle moving up on the free flow line) close to the values of the upstream distribution.

Figure 5 . 23 :

 523 Figure 5.23: Space-time distribution of vehicle density in the case of open-loop system. The green area corresponds to the free flow state.

Figure 5 .

 5 Figure 5.24: Space-time distribution of vehicle density in the case of closed-loop system. Dashed line stands for the open-loop profile. Indicated slope corresponds to the shock wave speed (lower the slope-higher the speed).

Figure 6 . 1 :

 61 Figure 6.1: Graph representation of the closed loop system in the case of the free flow link.

Figure 6 . 2 :

 62 Figure 6.2: Graph representation of the closed loop system in the case of the congested link.

Figure 6 . 5 :

 65 Figure 6.5: System partitioning in the case of the mixed state link.

  6.5) implies that the subsystem are separated. Thus, instead of the competitive game, we now have the following problem: Problem 6.4.3 (The optimization problem for the mixed state links) u * j = argmin J j (u j ) , u * j+1 = argmin J j+1 (u j+1 ) . (6.25)

  ary condition). The ramp metering signals are located at the end of the entrances as shown in Figs. 7.3 and 7.4. In addition, each of the on-ramps is equipped with two detectors (measuring flow and velocity), one located right after ramp metering signal and the other placed in the reasonable distance behind.

Figure 7 . 3 :

 73 Figure 7.3: Aimsun view on the on-ramp equipped with the ramp meter.

Figure 7 .

 7 Figure 7.4: 3D Aimsun views on the on-ramps equipped with the ramp meters.

Figure 7 . 5 :

 75 Figure 7.5: API developed to provide communication between Matlab and Aimsun.

Figure 7 . 9 :

 79 Figure 7.9: Evolution of the on-ramp demands (in [veh/h] over time steps).

Figure 7 . 10 :

 710 Figure 7.10: Order of the Grenoble south ring links used throughout the simulation results.

Figure 7 .

 7 Figure 7.11: Space-time distribution of vehicle density in the closed-loop case.

Figure 7 .Chapter 7 .

 77 Figure 7.12: Space-time distribution of vehicle density in the open-loop case.

Figure 7 . 13 :

 713 Figure 7.13: On-ramp queue lengths over time in the closed-loop case.

Figure 7 . 14 :

 714 Figure 7.14: On-ramp queue lengths over time in the open-loop case.

Figure 7 . 15 :

 715 Figure 7.15: Comparison of the balancing metric.

Figure 7 . 16 :

 716 Figure 7.16: Comparison of the fuel consumption.

Figure 7 . 17 :

 717 Figure 7.17: Comparison of not-optimized metrics.

  trices. It has been demonstrated that under certain structures of state feedback control a freeway link is driven to a common density value. Under these structures an optimal control problem has been formulated to reduce travelling time. The main obstacle that should be taken into implementation is caused by a possibility of temporary lose of required feedback structure, due to the control constraints.In the Chapter 7, a validation of the designed (in Chapter 5) controller has been presented. The controller has been implemented through Matlab under which a relevant program simulating distributed architecture has been designed. The controller has been then plugged to the Aimsun micro-simulator. The simulated scenario has been based on real traffic data collected from south ring of Grenoble. We have examined both, the balancing metric (optimized) and a set of standard traffic metrics (not optimized). The results have shown that the balancing has a positive impact on the traffic flow, in particular, by smoothing the vehicle dynamics, it can potentially increase the average velocity (and thus, reduce the travelling time) and reduce the fuel consumption (and related emissions). The proposed modular architecture enables to proceed the optimization for long freeway sections in the real-time.

1.5. Thesis structure

	Chapter 2		Chapter 4
	Macroscopic Representation	Optimal Control
	of the Freeway Traffic		in Traffic Engineering
	Chapter 3	Chapter 5
	Analysis on the Sets of Equilibrium	Nash Game Based Distributed Control
	Points for CTM	Design for Balancing of Freeway Density
	Chapter 6
	Freeway Density Balancing
	via Consensus Protocols
		Chapter 7
		Balancing of Freeway Traffic
		Density: Microscopic Validation

Table 3 .

 3 1: Computational times for the Problem 3.5.2 for different number of freeway cells. problems so that efficient solvers could be here applied. In our programs, we used Matlab quadprog function. Exemplary computational times for different number of freeway cells are presented in the Table3.1 (we used here a personal computer with Core 2 Duo processor: 1.4GHz, 2GB RAM). Assuming that calculations need to be repeated not less than every one or two minutes, the system should not exceed 7 cells.

	nr. of cells nr. of sub-problems computational time [s]
	4	185	1
	5	853	3
	6	3820	11
	7	16829	55
	8	73439	260
	the convex quadratic

Table 3 .

 3 2: CTM parameters for the Grenoble South Ring.

		0.96	81	21	280
	2	0.51	85	20	280
	3 *	0.59	86	20	280
	4	0.65	82	22	280
	5 *	0.64	76	21	280
	6	0.56	82	23	280
	7 *	0.80	79	23	280
	technology is planned to be installed by the end of 2014. For the steady states optimiza-

cell nr. L [km] v [km/h] w [km/h] ρ [veh/km] 1 * tion, we chose the western part of the ring of the length 4.7 [km]. On the considered direction, i.e. from east to west, it is equipped with 4 on-ramps and 4 off-ramps (all of them are one lane).

Table 3 .

 3 3: The merging parameter p with respect to different length of the merging zone and various drivers' behavior.

	Merging zone		Lane changing cooperation
	length [m]	5%	25%	50%	75% 100%
	60	0.096 0.119 0.170 0.213 0.251
	80	0.100 0.120 0.164 0.214 0.250
	100	0.093 0.115 0.163 0.217 0.251
	120	0.119 0.125 0.189 0.231 0.251
	140	0.121 0.151 0.207 0.241 0.255
	downstream bottleneck such that the supply was exceeded by the sum of mainstream and

Table 3 .

 3 4: Optimal inputs and the corresponding steady states for free flow cases.

					cell number
			1	2	3	4	5	6	7
	Calib.	u * [veh/h]	1600 -403 -442 -418
	model	x * [veh/km]	56	48 52 49 59 46 53
	VSL	u * [veh/h]	1400 -440 -440 -660
		x * [veh/km]	55	55 55 55 55 55 55
	uniform	u * [veh/h]	1581 -356 -625 -405
	VSL80 x * [veh/km]	57	51 55 50 58 49 54
	uniform	u * [veh/h]	1031 -403 -496 -334
	VSL70 x * [veh/km]	57	52 57 52 58 50 54

Table 3 .

 3 5: Optimal inputs and the corresponding steady states for different desired balanced vehicle density.

	c[veh/km]	1	2	cell number 3 4 5	6	7
	140	u * [veh/h] x * [veh/km] 144 152 137 163 143 173 147 300 -300 -300 -609
	150	u * [veh/h] x * [veh/km] 160 167 152 175 143 173 147 300 -300 -573 -609
	160	u * [veh/h] x * [veh/km] 172 177 152 175 143 173 147 300 -510 -573 -609

  a function of state and/or adjoint state. The example of such a case is the Linear Quadratic Regulator problem, briefly studied in the next section. For more general optimal control problems, given below generalized necessary optimality condition formulated by Pontryagin[START_REF] Pontryagin | The Mathematical Theory of Optimal Processes[END_REF] should be considered.

	Theorem 4.2.1. (Pontryagin Maximum Principle, L. S. Pontryagin, 1962).
	Assume u * is optimal control and x * is the corresponding trajectory. Then, there exists a
	function p * such that:
		ẋ * =	∂H ∂p	,	(4.15)
		ṗ * = -	∂H ∂x	,	(4.16)
	and:
	H(x , u) ,	t ∈ [0, t f ] .	(4.17)
	In addition,
	the mapping	t → H(x

1.1 is stated with H being smooth enough, i.e. where ∂H/∂u = 0 leads to a control that is explicitly given as * , p * , u * ) = max u∈U H(x * , p * * , p * , u * ) is constant. (4.18)

Table 5 .

 5 1: The Cell-Transmission Model parameters used in the simulations.

		v [km/h] w [km/h] ρ [veh/km] link length [km]
	link 1	82	20	280	1.57
	link 2	78	21	280	1.66
	link 3	80	20	280	2.84

Table 5 .

 5 2: Metric comparison. Each value represents the quotient: (metric for closed-loop case)/(metric for open-loop case).||x j || Lap ||x j || T T S ||x j || Lap + γ 1 ||x j || T T S has a positive impact on the travelling time. However, to justify the Total Travel Time, we need to check also the states in the queues. The controlled Traffic Density on-ramp flow (see Fig. 5.19) is lower than in the open-loop case, and thus the queue is being released slower as depicted in Fig. 5.21. As a result, in the steady state, there is still 4 vehicles queuing. Nevertheless, the overall travelling time computed by the norm ||x j || T T S

	link 1	0.58	0.97	0.92
	link 2	0.56	0.98	0.93
	link 3	0.45	0.98	0.92
	From Fig. 5.18, we can observe that the closed loop system keeps lower mainstream
	density values which

  System partitioning in the cases of the homogeneous congested state link.

	6.3. System partitioning
	φ j	φ j+1
	xj-1	xj	xj+1
	F	F	F
	u j	u j+1
	Figure 6.3: System partitioning in the cases of the homogeneous free flow state link.
	φ j	φ j+1
	xj-1	xj	xj+1
	C	C	C
	u j-1	u j
	Figure 6.4:

The boundary flow of the side of the control input can be cancelled by the substitution

(6.10)

if xj is in the free flow state or

(6.16)

if xj is in the congested state, and the boundary flow of the opposite side is determined by the state xj .

ACKNOWLEDGEMENTS

The research leading to results presented in this thesis has received funding from:

European Union Seventh Framework Programme [FP7/2007-2013] under grant agreement n 0 257462 HYCON2 Network of excellence.

Part of the work presented in the thesis was performed during the author's visit in the Transportation Systems Control Laboratory (UC Berkeley Mechanical Engineering and PATH laboratory). This 3 months visit was funded by:

INRIA's programme Explorateur and Rhone-Alpes Region programme Explora Doc.

The communication required to perform the Procedure 4.6.1 is that of sending and conveying the optimal decisions in the Steps 2,3 and 5. It is easy to verify that the topology of this communication follows the system interconnectivity. Let us now consider the systems, where the interconnectivity is represented by the line graphs as shown in Fig. 4.3a,b. In these cases, we have the following objective dependencies:

case a: J 1 (u 1 ) , J 2 (u 2 ,

{u 1 , u 2 , u 4 }) , J 4 (u 4 ) .

(4.36)

To solve the corresponding Nash games, one can execute the following procedures:

Procedure 4.6.2 (Solution of the Nash game for the system depicted in Fig. 4.3a)

Step 1 Find u * 1 = argmin J 1 (u 1 ) and send the solution to S 2 . S 2 conveys the solution to S 3 and S 3 conveys the solution to S 4 .

Step 2 Find u * 2 = argmin J 2 (u 2 , {u * 1 }) and send the solution to S 3 . S 3 conveys the solution to S 4 .

Step 3 Find u * 3 = argmin J 3 (u 3 , {u * 1 , u * 2 }) and send the solution to S 4 .

Step 4 Find

Procedure 4.6.3 (Solution of the Nash game for the system depicted in Fig. 4.3b)

Step 1 Guess u * 3 and assume ε 2 , ε 3 as small positive numbers.

Step 2 Find u * 1 = argmin J 1 (u 1 ) and send the solution to S 2 . S 2 conveys the solution to S 3 . Find u * 4 = argmin J 4 (u 4 ) and send the solution to S 3 . S 3 conveys this solution to S 2 .

Step 3 Find u * 2 = argmin J 2 (u 2 , {u * 1 , u * 3 , u * 4 }) and send the solution to S 3 .

Step 4 Find u * 3 = argmin J 3 (u 3 , {u * 1 , u * 2 , u * 4 }) and send the solution to S 2 .

Step 5 Repeat Steps 3 and 4 and until ∆ J 2 < ε 2 , ∆ J 3 < ε 3 . Let us now introduce the game setting applicable for the freeway traffic. For each of the controllable ramp-metering control inputs u j (referred later also as the players), we define local objective function J j (u j , x j ) that explicitly depends on the control u j and its assigned state vector x j . Note that x j may be also influenced by some of the other controllers through the boundary conditions (this will be specified in the following section by defining system interconnectivity graphs). Let u -j be the set of the decision of the controllers that may influence the state x j , excluding the decision of u j . The objective function can be now represented by J j (u j , u -j ). Throughout this chapter, we consider the optimization problem stated as the following non-cooperative game:

Problem 5.4.1 (Game problem for freeway traffic optimization)

Find {u * j } such that ∀j : u * j = argmin J j (u j , u * -j ) .

(5.16)

As will be shown later, the conditions for the existence of the Nash equilibrium (J j continuous in all its arguments and strictly convex in u j ) will be fulfilled in our setting of the local optimal control problems.

We will demonstrate that, for the freeway traffic, the problem Problem 5.4.1 can be solved under the communication channels represented by the graph shown in Fig. 5.7a.

The key is that the identical line graph represents system interconnectivity for CTM. In that case of CTM, the arrows would indicate the directions in which a decision propagates affecting the system. Now assume that a subsystem j is affected by more than one decision from each of the directions. For example, let:

(5.17)

In practice, for a subsystem j, the decisions u j-2 and u j-1 will be embedded into its upstream boundary flow. Similarly, u j+1 and u j+2 will be embedded into j's downstream

Optimization Problem Traffic Density

the computation in less than 0.1 of a second. This fact supports the idea of quadratic formulation of the Problem 5.5.1. Regarding the size of our problem, the most efficient quadratic programming (QP) solvers enable to find a solution within few milliseconds (for detailed study see, for example, [START_REF] Wang | Fast model predictive control using online optimization[END_REF]). This time may vary depending on the initial values and the termination condition. In some cases, due to limited time, it might be necessary to terminate the computation before the optimal solution is found. In this work, instead of adopting QP solvers, we will present a solution method based on the finite horizon Linear Quadratic Regulator (LQR). To solve LQR problem, only the backward integration of the Riccati difference equation needs to be performed. Regarding the size of our problem, the computational time required for such a procedure can be neglected.

Internal model of the boundary flows

In order to reformulate the Problem 5.5.1 as LQR problem, at first we will transform the dynamical equations (5.7), (5.10), (5.13) into autonomous form (with the right hand side independent explicitly on time). For that purpose, we will utilize a simple autoregressive (AR) model that allows to build up a linear dynamical representation of the evolution of the boundary and the interfacing flows:

By using this representation and an extended state vector, the governing equations will take a required autonomous form.

Let us consider the following AR model:

where the initial values z(0), z(-1),..., z(1-n) are assumed to be given as current and past measurements and the set α is estimated mostly based in historical data. By evaluating the AR model, we obtain a short-term forecasting. In our setting, we consider reverse problem.

We assume that at each time instant the prediction of the boundary flows are given over the time horizon T . By using this information and the the set of initial values, we calibrate AR models by using the method of least squares. The prediction of the boundary flows D, S, { Dj } may be obtained by using, for instance, non-parametric regression or neural network based methods. The interfacing flows { Dj }, { Sj } are evaluated by using the dynamical equations (5.7), (5.10) and (5.13).

In order to represent AR model in the standard dynamical form of z(k

we introduce the following state vector:

LQR problem

Having the autonomous representation of the dynamical equations we are ready to reformulate the Problem 5.5.1 into LQR problem. Let us first introduce the matrix:

Here, for the extended state vector y j , the sub-matrix Lap j + γ 1 (L j ) 2 and the scalar γ 1 will correspond to the state vector x j , while 0 will refer to uncontrollable states z Dj , z Dj , (z Sj+1 , z Dj+1 ). Consider then the problem:

Subject to (5.34) in the case of the free flow state link (5.36) in the case of the congested state link

(5.38) in the case of the mixed state link .

Note that Q j is positive semi-definite. To assure the convexity of the problem, we introduced the strictly positive term with the weighting number γ 2 . The reader can easily observe that the Problems 5.5.1 and 5.5.2 are equivalent, except for the set of constraints (5.8), (5.11), (5.14), (2.34) that were omitted in LQR formulation. In the implementation, the solution to the Problem 5.5.2 will be saturated with the bounds determined by these constraints. By using the necessary optimality condition, the solution to the Problem 5.5.2 is as follows:

where K(k) is the solution to the Riccati difference equation: c )) are supposed to be inserted. In the case of the mixed state link, for a reasonably short time horizon T , the matrix Āfc can be assumed to be constant. All the results presented in this thesis will rely on this assumption. In order to take into account the switches of Āfc , one can consider applying the necessary optimality condition (4.33), and then solving the following Two are attached to the ring (see, for example, Fig. 7.2). The goal here was to provide an information on how the tested control strategy may affect the local urban traffic (in the simulation results we will analyse the traffic measures taking into account both, the ring and its local side road network).

Having the geometry ready, the next step in the creation of the Aimsun model is to adjust the parameters of the micro-simulator. Aimsun enables to tune a variety of the parameters that determine the dynamics of the traffic flow. Among them, one of the most significant one is the parameter that specifies the free flow velocity. It can be adjusted separately for each of the road sections by changing the value of the maximum admissible speed. The second crucial parameter is the lane changing cooperation. It specifies the drivers' behavior when passing the junctions, i.e., it determines the cooperation during merging and diverging. In order to adjust this parameter, a set of the basis simulations

Implementation of the ramp meters

However, simulations showed that the obtained error is acceptable.

All of the controller's procedures were designed by the author of this thesis in Matlab.

The procedures require traffic state information (mainline density and queue lengths) and return ramp metering control decisions (given as duration of the green light). The communication between Matlab and Aimsun (see Fig.

Realization of the distributed controller

In this section, we will present a brief sketch on how the designed distributed controller is implemented. In particular, we will focus on how the game problem 5.4.1 is solved from the perspective of a single controller. For a set of different traffic states, we will write a set of simplified procedures that each of the controllers is meant to follow. As we will demonstrate, every controller performs analogous steps, and thus the assumption on the functional symmetry (see Chapter 1) is fulfilled.

Before we specify the procedures, let us recall the information patterns of our controller:

• Each of the controllers receives the information of the state of the two neighboring links,

• Each of the controllers exchanges information with his two neighbors.

To solve the game problem 5.4.1, each of the controllers u j needs to perform the following steps:

• Select the state vector x j to be optimized (according to the scheme presented in the section 5.3),

• Receive the information of the boundary condition (conditions),

• Proceed the optimization of x j (by solving the Problem 5.5.2),

• Send the information of the boundary condition (conditions). Now we will specify these steps for considered 16 surrounding state cases as depicted in Fig. 7.6. The procedures listed in the table 7.1 concern the steps to be executed by the control input denoted by u j . The state selection here corresponds to downstream or upstream link. In the cases, where both links are controllable, we select the congested one. The boundary conditions (b. c.) are meant to be received (sent) from (to) a relevant neighboring controller (or controllers) according to the communication required in solving F C u j u j u j u j u j u j u j u j (u j-1 ) (u j+1 ) u j u j u j u j u j u j u j u j