Kun Qian

Guillaume Costeseque

Edward S Canepa

Christian G Claudel
email: christian.claudel@utexas.edu

Optimization-based queue length estimation on arterial networks using a macroscopic traffic model enforcing vehicles bounded acceleration

Keywords: Traffic Flow, Estimation, Optimal Control, Lighthill-Whitham-Richards model, Queue Length, Bounded Acceleration

come   L'archive ouverte pluridisciplinaire

Introduction

Literature review and motivation

Motivation for queue length estimation methods

Real-time accurate estimation of traffic state on networks is a major stake for efficient traffic management systems. It is particularly the case for signalized intersections where the vast majority of responsive management schemes rely on the estimation of the queue lengths. Applications include traffic signals timing for arterial traffic links and on-ramp metering on freeways.

The most obvious way to estimate queue lengths is to dispose of real-time measurements onsite of traffic-related quantities such as flows and occupancy rates. However, direct measurements make use of classical sensors as for instance electromagnetic loops or video feeds, that are costly to install and to maintain and that do not provide error-free data. With the growing use of GPS-enabled smartphones, traffic managers can have access to individual trajectories from probe vehicles that give more accurate information about the traffic velocity. Fixed-location sensor data such as loop detectors or video-based sensors are complementary to mobile traffic sensors data coming from GPS devices, cellular phones, connected vehicles and other tracking devices. Hence, the goal is to enjoy this opportunity to enrich the measurement data source for queue length estimation.

Notice that in our work, depending on a macroscopic traffic model, we focus on arterial traffic links that are defined as urban roads with a high level of service and whose intersections are mostly regulated by traffic signals.

Quick review of queue length estimation methods

Queue length estimation at signalized intersections are basically used for arterial performance measures. Starting from the historical works of Webster (1958) and Newell (1960Newell ( , 1965) ) for static queue length estimations based on statistical tools, this subject has attracted a strengthened attention in the literature over the past decade. A quite exhaustive review of the literature is available in [START_REF] Anderson | Data-Driven Methods for Improved Estimation and Control of an Urban Arterial Traffic Network[END_REF]. The prevalent families of analytical and data-driven estimation methods are:

• the input-output techniques that are based on the vehicle conservation principle. Such techniques aim at counting vehicles entering and leaving the queue and basically depend on an estimation of the initial queue length. Due to spillback effect, the counting process can take place at upstream or downstream boundaries of a link. In general, these techniques cannot correct errors due to vehicle miscounts. Some improvements have been done by incorporating fixed-location occupancy measurements, or travel time estimations obtained by re-identification techniques based on license plate readers ( A comprehensive list of all the works dealing with (discrete or continuous) macroscopic models on arterials is out of the scope of this paper. To the best of authors' knowledge, such macroscopic shockwaves approaches are mainly deterministic and do not account for behavioral or higher-order dynamics effects, including lane-specific behaviors and bounded acceleration effect. Our work falls into this category. • microscopic models that reproduce individual vehicle trajectories, encompassing lane changing maneuvers and bounded acceleration. For microscopic models based methods, interested people can refer to Valadkhani, Hong, and Ramezani (2017); Kawasaki, Hara, and Kuwahara (2019); Xie, van Lint, and Verbraeck (2018). A nature disadvantage of microscopic model-based estimation strategy is the tremendous computational requirement when applying to large scale traffic networks. • the statistical approaches with use of fixed sensors data and GPS data, encompassing the probabilistic methods in which the queue length evolution is assumed to follow a randomly distributed process under given probability distributions for the vehicle arrival and departure rates (e.g. uniform or Poisson distributions) (Viti and Van Zuylen 2010); Kalman filtering schemes and Markov chains (Ramezani and Geroliminis 2012), or Bayesian networks [START_REF] Hao | Cycle-by-cycle intersection queue length distribution estimation using sample travel times[END_REF]). For statistical learning methods based on probe data, the accuracy of the estimators are related on the penetration rate of the probe vehicles [START_REF] Hofleitner | Learning the dynamics of arterial traffic from probe data a dynamic Bayesian network[END_REF]; Ramezani and Geroliminis 2012; [START_REF] Comert | Queue length estimation from probe vehicle location and the impacts of sample size[END_REF][START_REF] Comert | Simple analytical models for estimating the queue lengths from probe vehicles at traffic signals[END_REF][START_REF] Comert | Queue length estimation from probe vehicles at isolated intersections: Estimators for primary parameters[END_REF]. It is noteworthy that such statistical techniques strongly depend on realistic vehicles arrival patterns that sparsely available which GPS data cannot provide.

In the remaining, we would like to focus on a "shockwaves-based" approach by making use of a macroscopic traffic flow model. Since we will use the same framework, we would like here to stress on the paper [START_REF] Anderson | Optimization-based queue estimation on an arterial traffic link with measurement uncertainties[END_REF] in which the optimal control framework is used for the queue length estimation on arterial streets. This framework has been previously proposed in [START_REF] Claudel | Convex formulations of data assimilation problems for a class of Hamilton-Jacobi equations[END_REF] and explicitly established in [START_REF] Canepa | Exact solutions to traffic density estimation problems involving the lighthill-whitham-richards traffic flow model using mixed integer programming[END_REF] for triangular Hamiltonian and piecewise affine conditions.

Motivation for introducing bounded acceleration

Vehicular traffic models are usually divided into two groups: microscopic and macroscopic models. The first category allows to keep track of each individual vehicle trajectory while the latter uses aggregated quantities. Microscopic approaches are well-suited for modeling vehicles behaviors at isolated intersections but not for a large-scale deployment or for real-time control applications because lots of data are required for the calibration of the model parameters. Macroscopic fluidbased models seem more promising in that direction. Estimation techniques based on two different type of methods inherit these characteristics. Our macroscopic model based estimation technique is expected to have the potential to be applied to large scale traffic state estimation. The seminal first-order LWR model described in next Section 1.2.1 is very robust but it fails to capture some traffic phenomena such as the boundedness of vehicles acceleration. Basically, when a traffic signal turns green or when drivers leave a bottleneck area, vehicles are assumed to go from zero (or very low speeds) to the maximal speed instantaneously. This leads to an overestimation of the road capacity during the time required for the acceleration. At the spatial scale of an arterial, this feature should not be neglected. The time needed for a vehicle to change its velocity is totally collapsed. However, at this spatial scale, this feature should not be neglected for queue length estimation.

To the best authors' knowledge, the only paper dealing with queue length estimation which takes into account a vehicle acceleration/deceleration reconstruction from macroscopic sense is Hao and Ban (2015). In this paper, Newell's microscopic car-following model (Newell 2002) is used to reconstruct the vehicle trajectory for the deceleration phases while an algorithm is set up for acceleration phases using the variational formulation of the fluid-based LWR model.

In the remaining of our paper, we will use the framework introduced by Anderson et al. (2013) but we will incorporate a traffic flow model that is able to reproduce the boundedness of the vehicles acceleration in a simpler way than proposed by Hao and Ban (2015). Besides, the proposed article also allows arbitrary sensor numbers and configurations to be used as part of an estimation problem.

Fluid-based macroscopic traffic models

LWR model and associated Hamilton-Jacobi equation

The seminal first order traffic flow model known as the LWR model [START_REF] Lighthill | On kinematic waves II. A theory of traffic flow on long crowded roads[END_REF]Richards 1956) reads as a scalar conservation law

∂k(t, x) ∂t + ∂q(t, x) ∂x = 0, on (0, +∞) × R, (1.1)
where k ∈ [0, κ] and q = ψ(k) ∈ [0, C] denote respectively the density and the flow of vehicles. We set κ the maximal density and k c the critical density for which the flow reaches its maximal value C, also called the capacity. The flow-density fundamental diagram (FD) is given by the function ψ : k → ψ(k) that satisfies

ψ(0) = 0 = ψ(κ) and ψ(k c ) = C.
We assume that ψ is an upper semi-continuous concave function.

For practical convenience, we consider also the following assumption:

(A0) the fundamental diagram is triangular and reads

ψ(k) = min {v f k , w(k -κ)}
where v f , w (with w < 0) and κ denote respectively the free-flow speed, the wave speed and the maximal density. The critical density k c for which the maximal flow is attained, is thus given by

k c := w w -v f κ.
Let us consider the Moskowitz function also known in the traffic engineering literature as the Cumulative Vehicle Number (CVN) or Cumulative Vehicle Curve (CVC), and defined as follows

M(t, x) = +∞ x k(t, y)dy (1.2) such that ∂M ∂x (t, x) = -k(t, x) and ∂M ∂t (t, x) = q(t, x).
It is well-known that if k is a solution of (1.1), then M defined by (1.2) satisfies (at least formally) the following homogeneous Hamilton-Jacobi Partial Differential Equation (HJ PDE)

∂M(t, x) ∂t -ψ - ∂M(t, x) ∂x = 0, on (0, +∞) × R, (1.3)
where ψ plays the role of the Hamiltonian. This Moskowitz function was first introduced in Moskowitz and Newan (1963) and used later in Newell's trilogy (Newell 1993a,b,c) and by Daganzo (Daganzo 2005a(Daganzo ,b, 2006)). For a review on the variational formulation applied to the traffic flow theory, the interested reader is referred to [START_REF] Laval | The Hamilton-Jacobi partial differential equation and the three representations of traffic flow[END_REF].

LWR model with bounded acceleration (LWR-BA)

The LWR model (1.1) has been proved to be very robust, simple and tractable for many applications. However, it is unable to capture some traffic features that are commonly observed such as traffic instabilities, stop-and-go waves or kinematic constraints of real vehicles. For instance, the LWR model can produce unrealistic vehicles acceleration (or deceleration) at the downstream of bottlenecks or traffic signals.

Historically, two macroscopic models were designed starting from the original LWR model to take into account the boundedness of traffic acceleration: while Lebacque has developed a two-phase flow model allowing for general concave fundamental diagrams but depending on a complex mathematical sound basis [START_REF] Lebacque | A TWO PHASE EXTENSION OF THE LWR MODEL BASED ON THE BOUNDEDNESS OF TRAFFIC ACCELERATION[END_REF][START_REF] Lebacque | Two-phase bounded-acceleration traffic flow model: analytical solutions and applications[END_REF], Leclercq [START_REF] Leclercq | Modélisation dynamique du trafic et applications à l'estimation du bruit routier[END_REF][START_REF] Leclercq | Bounded acceleration close to fixed and moving bottlenecks[END_REF]) has proposed a model based on a relevant partitioning of the time-space domain that rely on the assumption of a triangular flow-density FD. Recent work by [START_REF] Jin | Bounded acceleration traffic flow models: A unified approach[END_REF] on bounded acceleration and LWR model showed that LWR-BA model is equivalent to Lebacque's two-phase model and to the bounded acceleration version of Newell's car-following model as well. Some works also considered the bounded acceleration in modified cell transmission model Srivastava, Jin, and Lebacque (2015) and kinematic wave models [START_REF] Jin | Kinematic wave models of sag and tunnel bottlenecks[END_REF]. Other approaches for accounting for vehicles finite acceleration have been introduced in recent years such as Laurent-Brouty, Costeseque, andGoatin (2018, 2019) where the authors consider a coupled PDE-ODE model.

When a piecewise linear (triangular) fundamental diagram is assumed, it is noteworthy that both Lebacque and Leclercq's models are equivalent to

∂k(t, x) ∂t + ∂ (k(t, x)v(t, x)) ∂x = 0, if v(t, x) = V e (k(t, x)) ,            ∂k(t, x) ∂t + ∂ (k(t, x)v(t, x)) ∂x = 0, ∂v(t, x) ∂t + v(t, x) ∂v(t, x) ∂x = a, if v(t, x) < V e (k(t, x)) , (1.4)
where a > 0 is the maximal acceleration, assumed to be identical for all the vehicles. V e : k → V e (k) denotes the equilibrium speed-density FD such that ψ(k) = kV e (k) for any k ∈ [0, κ]. It is noteworthy that the vehicle trajectories in the bounded acceleration (BA) areas, say when v = V e (k), can be explicitly computed as parabolas (see Section 6.1). This BA phase constitutes the single difference with the original LWR model (1.1). By considering the Moskowitz function M defined previously in (1.2), the LWR-BA model (1.4) can be expressed as a Hamilton-Jacobi PDE as follows

∂M(t, x) ∂t -ψ - ∂M(t, x) ∂x = 0, if v(t, x) = V e (k(t, x)) , (1.5a)            ∂M(t, x) ∂t + v(t, x) ∂M(t, x) ∂x = 0, ∂v(t, x) ∂t + v(t, x) ∂v(t, x) ∂x = a, if v(t, x) < V e (k(t, x)) .
(1.5b)

For additional material on the bounded acceleration LWR model, the interested reader is referred to Qiu et al. (2013). It should be noticed that an extension of the methodology provided in Mazaré et al. (2011) for a family of second order models (as Lebacque's model with bounded acceleration) recast in Lagrangian coordinates is available in Costeseque and Lebacque (2014b).

Contributions

Since the rebirth of the variational approach, there is now an important literature about the application of Hamilton-Jacobi equations to traffic flow modeling. In the following table, we would like to highlight what are the contributions of our paper with respect to the relevant literature related to the chosen approach.

Hence, the main contributions of our work are:

• To give the analytical expressions of the compatibility conditions (in the sense of Claudel and Bayen (2011)) for the LWR model with bounded acceleration. These conditions read as inequalities that are then used as model constraints in the optimization framework. As a minor contribution, we also give the analytical expressions of the solutions to the LWR-BA model in the case of congested upstream boundary conditions, which have not been provided in Qiu et al. (2013). However, this is fundamental for queue estimation on arterial roads.

Organization of the paper

The remaining of the paper is structured as follows: in Section 2, the explicit solutions both for the LWR (1.1) (or equivalently (1.3)) and the LWR-BA (1.4) (or equivalently (1.5a)-(1.5b)) models under piecewise affine initial and boundary conditions are recalled. Then, in Section 3, the constrained optimization problem is presented while the constraints are explicitly derived for the two considered models. We provide some numerical examples in Section 4 and finally a discussion on our results and on the potential improvements is proposed in Section 5. More detailed expressions of solutions and proofs for the LWR (1.1) (or equivalently (1.3)) and the LWR-BA (1.4) (or equivalently (1.5a)-(1.5b)) models are attached in Appendix 6.

Explicit solutions for the LWR and LWR-BA models

In this section, we firstly present settings of the problem and provide the necessary definitions. Then, we recall explicit and exact solutions for both LWR and LWR-BA models under the assumption (A0) of a triangular fundamental diagram. With the explicit solutions, we can formulate it into a convex optimization problem with convex relaxation techniques according to the optimal control framework raised by [START_REF] Canepa | Exact solutions to traffic density estimation problems involving the lighthill-whitham-richards traffic flow model using mixed integer programming[END_REF].

As explained in Section 1.3, many of material recalled in this section come from previous literature (Mazaré et al. 2011;[START_REF] Canepa | Exact solutions to traffic density estimation problems involving the lighthill-whitham-richards traffic flow model using mixed integer programming[END_REF]Qiu et al. 2013). To save the paragraphs, we include detailed expressions and proofs in Appendix 6. In this section, we would stress the difference between the solutions to LWR equations and LWR-BA equations analytically. These theoretical differences would help explain the improvements in experimental results in later Section 4. Also, we would discuss in this section some cases about LWR-BA model that were not discussed before in Qiu et al. (2013).

Setting and piecewise affine conditions

Consider a prescribed uni-directional stretch of arterial road X := [ξ, χ] ⊂ R where ξ and χ denote respectively the upstream and downstream boundaries of the link. Assume that X has a constant number of lanes and no lateral in-or out-flows. The time domain is defined by [0, T ] with a given 0 < T < +∞.

Assume also that

(A1) The spatio-temporal domain is discretized into n discrete spatial segments [x i , x i+1 ] with i ∈ 0, n -1 , n ∈ N \ {0} and m discrete time segments [t j , t j+1 ] with j ∈ 0, m -1 , m ∈ N \ {0} such that ξ =: x 0 < x 1 < • • • < x n := χ and 0 =: t 0 < t 1 < • • • < t m := T.
Notice that we do not need to require the discrete time and spatial steps to be uniform. (A2) The initial, upstream and downstream and internal boundary conditions denoted respectively by M ini , M up , M down and c

(l)
intern are piecewise affine on the discrete space and time segments ([x i , x i+1 ]) i and ([t j , t j+1 ]) j . We define by (k i ) 0≤i≤n-1 ∈ R n + the set of initial densities, by (q j ) 0≤j≤m-1 ∈ R m + the set of upstream flows, by (p j ) 0≤j≤m-1 ∈ R m + the set of downstream flows and by M (l) , q

(l) intern 0≤l≤o-1 ∈ (R × R + )
o the set of internal boundary conditions. These values are constant but they are not known exactly. The objective of our work is to determine these constants thanks to an optimization problem that boils down to a Mixed Integer-Linear Program (MILP). This optimization problem incorporates model constraints that arise from the explicit solutions to the considered traffic flow model and data constraints coming from direct measurements. Basically, (k i ) i , (q j ) j and (p j ) j can be estimated thanks to fixed Eulerian sensors such as electromagnetic loops or video feeds. Conversely, M (l) , q (l) intern l cannot be measured experimentally by any traffic sensor. All these unknown variables will be used as part of our decision variable for the MILP introduced in Section 3.

See Figure 1.

Initial conditions

The initial densities are decomposed as piecewise constant in their respective measurement intervals

k(0, x) = k i , ∀x ∈ [x i , x i+1 ], i ∈ 0, n -1 . (2.6)
Let us define the speeds associated with the piecewise constant initial densities as follows

v (i) ini :=    v f , if k i ≤ k c , w 1 - κ k i , if k i > k c , for any i ∈ 0, n -1 .
The initial condition of the Moskowitz PDE is obtained by integrating the initial condition of the LWR PDE assuming that M ini (x 0 ) = 0 and :

∀x ∈ [x i , x i+1 ], M ini (x) = - x x0 k(y, 0)dy = - i-1 m=0 (x m+1 -x m )k m -(x -x i )k i (2.7)
and the affine, locally defined initial condition indexed by i = 0, . . . , n -1:

c (i) ini (x) = -k i x + b i , if x ∈ [x i , x i+1 ], +∞, else, (2.8
)

with b i = k i x i - i-1 m=0 (x m+1 -x m )k m allowing for the continuity of the initial conditions on [x 0 , x n ].

Upstream and downstream boundary conditions

Let the upstream and downstream flows be prescribed as piecewise constants

q(t, x 0 ) = q j , q(t, x n ) = p j , ∀t ∈ [t j , t j+1 ], j ∈ 0, m -1 . (2.9)
Similarly, the upstream and downstream boundary conditions of the Moskowitz PDE, assuming that M ini (x 0 ) = M up (0) = 0 and M ini (x n ) = M down (0) are given by:

∀t ∈ [t j , t j+1 ], M up (t) = t 0 q(x 0 , τ )dτ = j-1 m=0 (t m+1 -t m )q m + (t -t j )q j (2.10) and ∀t ∈ [t j , t j+1 ], M down (t) = M ini (x n ) + t 0 q(x n , τ )dτ = M ini (x n ) + j-1 m=0 (t m+1 -t m )p m + (t -t j )p j .
(2.11)

The associated affine, locally defined upstream boundary condition indexed by j = 0, . . . , m-1, reads c (j) up (t) =

q j t + d j , if t ∈ [t j , t j+1 ], +∞,
else, (2.12)

with d j = -q j t j + j-1 m=0 (t m+1 -t m )q m .
And for the downstream boundary, we have

c (j) down (t) = p j t + b j , if t ∈ [t j , t j+1 ], +∞, else, (2.13) with b j = M ini (x n ) -p j t j + j-1 m=0 (t m+1 -t m )p m .
It is noteworthy that upstream and downstream conditions are defined with respect to fluxes ((q j ) j and (p j ) j respectively) and that a flux is not sufficient to determine whether the traffic is in free-flow or in congested situation. It is particularly important for the upstream conditions c (j) up j because both cases (free-flow and congested) can differently affect the value of the functions M c (j) up . In the remaining of the paper, we will only treat the case of congested downstream conditions because it is the most interesting case for us: indeed, if the downstream is in free-flow, the downstream condition c (j) down only generates kinematic waves with non-negative wave speeds and thus the domain of influence of this condition is outside of the computational domain

[t 0 , t m ] × [x 0 , x n ].
For the reader convenience, we assume that at upstream boundary we observe the fluxes (q j ) j associated to the densities k

(j) up j
and the speeds v

(j) up j
. These speeds are thus deduced as follows

v (j) up =    v f , if k (j) up ≤ k c , q j q j + wκ w, if k (j) up > k c , for any i ∈ 0, n -1 .

Internal boundary conditions

An affine internal condition is mathematically defined as :

c (l) intern (t, x) = M (l) + q (l) intern (t -t (l) min ), if (t, x) ∈ D (l) , +∞, else (2.14) where 0 ≤ q (l) intern ≤ C and 0 ≤ V (l)
intern ≤ v f and the set D (l) is defined as follows

D (l) := (t, x) x = x (l) min + V (l) intern (t -t (l) min ) and t (l) min ≤ t ≤ t (l) max . .
In the above formula (2.14), the internal condition imposes an average maximal passing rate of q (l) intern on the domain defined by t

(l) min ≤ t ≤ t (l) max and x = x (l) min + V (l) intern (t -t (l) min ) where x (l) min , t (l)
min and t (l) max are known with accuracy since they can be typically measured thanks to Global Positioning Systems (GPS) for instance.

Such an internal boundary condition can represent in practice:

• a Lagrangian probe data: v( t, x) = V (l) intern ≤ v f for any ( t, x) in the domain D (l) , • a fixed bottleneck: V (l) intern = 0 and V (l) intern < v( t, x) ≤ v f for any ( t, x) in the domain D (l) , • a moving bottleneck (V (l)
intern > 0), restricting the relative capacity of the road to q (l) intern on its path [START_REF] Leclercq | Moving bottlenecks in Lighthill-Whitham-Richards model: A unified theory[END_REF]. The speed of vehicles through this condition (for any ( t, x) in the domain) is given by

v( t, x) = V (l) intern + q (l) intern k = 1 - κ k w, with k := q (l) intern + wκ w -V (l) intern . Remark 2.1 (Free flow internal boundary condition). One can see that if V (l) intern = v f ,
then the moving bottleneck is not active and it does not produce any constraint on the upstream flow. Indeed, the passing rate q (l) intern is equal to zero and no vehicle can overtake the "moving bottleneck" which moves at the maximal velocity.

Explicit Solution for the LWR model

We would quickly go through the explicit solutions for the LWR model as a preparation for our optimization framework for LWR-BA model. Detailed expressions can be found in Appendix 6 and in the paper [START_REF] Canepa | Exact solutions to traffic density estimation problems involving the lighthill-whitham-richards traffic flow model using mixed integer programming[END_REF].

Consider the LWR model expressed as an Hamilton-Jacobi PDE and given by (1.3). There exists several classes of weak solutions to first order Hamilton-Jacobi PDEs. The one we will use here is classically referred to as the Barron-Jensen / Frankowska (B-J/F) solution [START_REF] Barron | Semicontinuous viscosity solutions for Hamilton-Jacobi equations with convex Hamiltonians[END_REF][START_REF] Frankowska | Lower semicontinuous solutions of Hamilton-Jacobi-Bellman equations[END_REF]) and was previously used in the control framework of the viability theory Aubin, Bayen, and Saint-Pierre (2011). It should be noticed that whenever internal boundary conditions are not considered as part of the solution, B-J/F solutions to Hamilton-Jacobi PDEs are equivalent to viscosity solutions [START_REF] Crandall | Viscosity solutions of Hamilton-Jacobi equations[END_REF][START_REF] Lions | Generalized solutions of Hamilton-Jacobi equations[END_REF]) which is the other main class of weak solutions for HJ PDEs.

We define the Legendre-Fenchel transform ϕ of the upper semi-continuous Hamiltonian ψ as follows

ϕ (u) := sup p∈Dom(ψ) {pu + ψ(p)} .
Let us consider a lower semi-continuous function c defined on a subset of [0, T ] × [ξ, χ] and satisfying for any (t,

x) ∈ [0, +∞) × X c(t, x) = min min 0≤i≤n-1 c (i) ini (t, x), min 0≤j≤m-1 c (j) up (t, x), min 0≤j≤m-1 c (j) down (t, x), min 0≤l≤o-1 c (l) intern (t, x) .
We are now ready to require the additional boundary value condition given by

M(t, x) ≤ c(t, x), for any (t, x) ∈ Dom(c). (2.15)
Following Aubin, Bayen, and Saint-Pierre (2008); Claudel and Bayen (2010a), let us define:

• the constraint set (or environment) K := [0, +∞) × X × R with X := [ξ, χ] ⊂ R, • the (closed) target set C := {(t, x, y) ∈ [0, +∞) × X × R | y ≤ c(t,
x)} as the epigraph of the lower semicontinuous target function c(•, •), • and the auxiliary dynamical system (both Marchaud and Lipschitz)

       τ (t) = -1, x (t) = u(t), y (t) = -ϕ (u(t)) with u(t) ∈ Dom(ϕ ).
(2.16)

The viability episolution of (1.

M(t, x) = inf (u,T )∈Dom(ϕ )×[0,+∞) [c(t -T, x + T u) + T ϕ (u)] . (2.18)
Proof See Theorem 3.1 in Claudel and Bayen (2010a).

Let us denote by J the set of all initial, upstream, downstream and internal boundary conditions.

Recall that from viability theory, we have that the capture basin of a finite union of targets for a given differential inclusion F is the union of the capture basins of these targets

Capt F   K, i∈J C i   = i∈J Capt F (K, C i .)
Hence, the inf-morphism property follows:

Proposition 2.3 (Inf-morphism property). Let (c i ) i∈J ,

be a family of lower semi-continuous functions such that

c := inf i∈J c i , for all t ≥ 0, x ∈ X.
If M ci denotes the partial solution of (1.3) under the value condition

M ci (t, x) ≤ c i (t, x) for any (t, x) ∈ Dom(c i ),
then the solution of (1.3)-(2.15) is given by

M(t, x) = inf i∈J M ci (t, x), for all t ≥ 0, x ∈ X.
Under the assumptions (A0)-(A1) and (A2), it is possible to deduce explicit semi-analytic expressions of the solutions to the Hamilton-Jacobi Dirichlet problem (1.3)-(2.15). Thanks to Proposition 2.3, we can deduce that the solution to (2.17)-(2.15) is given by

M = min min 0≤i≤n-1 M c (i) ini , min 0≤j≤m-1 M c (j) up , min 0≤j≤m-1 M c (j) down , min 0≤l≤o-1 M c (l) intern on [0, +∞) × X.
We will not reproduce here the expressions of the partial solutions

M c (i) ini , M c (j) up , M c (j) down and M c (l)
intern for the LWR model (1.3) but the interested reader is referred to Claudel and Bayen (2010b); Mazaré et al. (2011). By the way, it is noteworthy that the classical partial solutions for the LWR model can be deduced from the partial solutions of the LWR with bounded acceleration that are given in the next Section, by passing to the limit when the acceleration rate goes to infinity, a → +∞. Unlike the classical solutions for the LWR model, a bounded acceleration phase is introduced (see more precisely (1.5b)) which takes into account the time laps that is needed for a vehicle to go from an initial velocity v( t, x) to the free flow speed v f , with a constant acceleration a. This duration is thus given by

Explicit Solution for the LWR-BA model

As an extension of

τ = v f -v( t, x) a .
During this BA phase, the vehicles have a parabolic trajectory described by

       ẍ(t) = a, ẋ(t) = a(t -t) + v( t, x), x(t) = a 2 (t -t) 2 + v( t, x)(t -t) + x, for all 0 ≤ t -t ≤ τ.
After the acceleration phase, we assume that the vehicles move with the free flow speed v f . The explicit solution to LWR-BA model has been studied well in Qiu et al. ( 2013). Thus, we will list the results of

M c (i) ini , M c (j) up , M c (j) down and M c (l) intern
for LWR-BA model under the assumptions (A0), (A1) and (A2) in the section 6. Below in Lemma 2.4, we analyze a case that is not studied in Qiu et al. (2013). In Section 3, we show how we adapt the optimization framework proposed by Canepa and Claudel (2012) by considering the parabolic terms caused by the bounded acceleration.

Lemma 2.4 (Solutions for the LWR-BA model for congested upstream boundary conditions).

We assume that k (j) up > k c , for a given j, say that the upstream boundary

(x = x 0 ) is congested on [t j , t j+1 ].
For any j, let us define

             v (j) up = q j k (j) up = q j q j + wκ w τ = v f -v (j) up a x a = x 0 + v (j) up τ + a 2 τ 2
Then the solution component associated with the affine upstream boundary condition (2.12) (see Figure 5) is computed as follows:

M c (j) up (t, x) =                                                                                  (i) d j + q j t j+1 -kc x -x 0 -v f (t -t j+1 ) : x ≤ x 0 + v (j) up (t -t j+1 ) + a 2 (t -t j+1 ) 2 and x ≤ xa + w(t -t j+1 -τ ) and t ≥ t j+1 (ii) d j + q j t j+1 -kc x -x 0 -v f (t -t j+1 ) -a 2 τ 2 : x ≤ xa + v f (t -t j+1 -τ ) and x ≥ xa + w(t -t j+1 -τ ) and t ≥ t j+1 + τ (iii) d j + q j t + 1 a v (j) up - v (j) up 2 + 2a(x -x 0 ) : x ≤ x 0 + v (j) up (t -t j ) + a 2 (t -t j ) 2 and x ≥ x 0 + v (j) up (t -t j+1 ) + a 2 (t -t j+1 ) 2 when t ≥ t j+1 and x 0 ≤ x ≤ xa and t j ≤ t ≤ t j+1 + τ (iv) d j + q j t -x-xa v f -τ : x ≤ xa + v f (t -t j -τ ) and x ≥ xa + v f (t -t j+1 -τ ) and x ≥ xa and t ≥ t j + τ (v) d j + q j t j : x ≤ x 0 + v f (t -t j ) and x ≥ x 0 + v (j) up (t -t j ) + a 2 (t -t j ) 2 when t ≤ t j + τ or x ≥ xa + v f (t -t j -τ ) when t ≥ t j + τ (2.19)
Proof This comes from straightforward computations. Remark 2.5. Lemma 2.4 can be seen as a special case of an internal boundary condition for a fixed bottleneck (V intern = 0) located at x = x 0 .

The optimization-based queue length estimation method

We now incorporate the previously developed explicit solutions to LWR-BA model into an optimization framework. We follow a similar approach to Canepa and Claudel (2012), though the former does not consider bounded accelerations. In this section, we consider that traffic follows a LWR-BA model, which allows us to precisely model the capacity drop during acceleration phases, when vehicles clear a bottleneck or start to accelerate after a stop. However, this extension is not a simple change in several constraints in the optimization framework in comparison to [START_REF] Canepa | Exact solutions to traffic density estimation problems involving the lighthill-whitham-richards traffic flow model using mixed integer programming[END_REF], as the LWR-BA model introduced higher order terms in the transition areas. We discuss in this section about how to include the parabolic terms into the optimization framework while retaining convexity.

The explicit solutions for the LWR-BA model under piecewise affine boundary conditions have been stated in the previous section. We are now ready to introduce our optimization problem for the estimation of the queue length. The decision variable associated with the value conditions (2.8), (2.12), (2.13) and (2.14) is defined as follows y := . . . , k i , . . . initial densities , . . . , q j , . . . (3.20)

This decision variable will allow to determine the set of the boundary values that optimize a prescribed cost function under some constraints (see for instance equations (3.31) and (3.32)). The objective function should recapture the most likely link dynamics with a general reconstruction of the averaged queuing behavior on the arterial. The constraints are presented below. We distinguish the model constraints that appear from the physical limitations due to the considered traffic flow model and the data constraints that are triggered by the measurements we have on the current traffic state, under some uncertainties due to sensor inaccuracies. These constraints are stated as convex inequality constraints in terms of the decision variable y. Remark 3.1. Equation (3.20) gives a general expression for the decision variable. All the variables which may be unknown are included in the set of decision variables. Depending on the application, we can assume that some of the variables are known and they will not serve as decision variables in this case. The flexibility in decision variables is a great advantage of this optimization-based estimation method over other ones.

Model constraints

Preliminaries

We would like to first introduce some properties as preliminaries for constructing the optimization framework. Then, the solution M of (2.17 In the next Subsections, we give the semi-analytical expressions of the compatibility conditions for the LWR-BA model (1.5a)-(1.5b) under the assumptions (A0), (A1) and (A2).

Notice that the full derivation of the set of inequalities for the LWR model (1.3) (i.e. without bounded acceleration) are provided in [START_REF] Canepa | Exact solutions to traffic density estimation problems involving the lighthill-whitham-richards traffic flow model using mixed integer programming[END_REF]. In our paper, we would like to emphasize on the difference between the optimization framework for the LWR-BA model (1.5a)-(1.5b) and the one for the LWR model (1.3) proposed in previous work [START_REF] Canepa | Exact solutions to traffic density estimation problems involving the lighthill-whitham-richards traffic flow model using mixed integer programming[END_REF].

To ease the presentation, we need to introduce the following useful notations:

• Functions describing the time-space point for which a vehicle accelerating at rate a > 0 reaches the top speed v f depending on its current time-space position ( t, x) ∈ [0, T ] × X:

           t a : ( t, x) → t + v f -v( t, x) a , x a : ( t, x) → a 2 τ 2 + v( t, x)τ + x (3.21)
• Function giving the intersection time between two straight lines described by y(t) = x 0 + v 0 (t -t 0 ) and y(t

) = x 1 + v 1 (t -t 1 ) with v 0 = v 1 : Ť : (x 0 , t 0 , v 0 ; x 1 , t 1 , v 1 ) → x 1 -x 0 + v 0 t 0 -v 1 t 1 v 0 -v 1 (3.22)
• Function giving the intersection time(s) between a straight line y(t) = x 0 + v 0 (t -t 0 ) and a parabola

y(t) = x 1 +v 1 (t-t 1 )+ a 2 (t-t 1 ) 2 , such that (v 0 -v 1 ) 2 ≥ 2a [(x 1 -x 0 ) -v 0 (t 1 -t 0 )] T± : (x 0 , t 0 , v 0 ; x 1 , t 1 , v 1 ) → t 1 + (v 0 -v 1 ) a ± 1 a (v 0 -v 1 ) 2 -2a [(x 1 -x 0 ) -v 0 (t 1 -t 0 )].
(3.23)

Initial condition (free flow)

The compatibility conditions i.e. the model constraints for free-flow initial conditions read as follows (see Figure 2):

                                                 M c (i) ini t 0 + x 0 -x i w , x 0 ≥ c (j) up t 0 + x 0 -x i w , x 0 ,
for any i, j such that

t 0 + x 0 -x i w ∈ [t j , t j+1 ], M c (i) ini t 0 + xn -x i v f , xn ≥ c (j) down t 0 + xn -x i v f , xn ,
for any i, j such that t 0 + xn -

x i v f ∈ [t j , t j+1 ], M c (i) ini t (i,l) 1 , x (i,l) 1 ≥ c (l) intern t (i,l) 1 , x (i,l) 1 , for any i, l such that t (l) min ≤ t (i,l) 1 ≤ t (l) max , M c (i) ini t (i,l) 2 , x (i,l) 2 ≥ c (l) intern t (i,l) 2 , x (i,l) 2
, for any i, l such that t

(l) min ≤ t (i,l) 2 ≤ t (l) max , (3.24)
with

                           t (i,l) 1 := Ť x i , t 0 , v f ; x (l) min , t (l) min , V (l) intern , x (i,l) 1 := x (l) min + V (l) intern t (i,l) 1 -t (l) min , t (i,l) 2 := Ť x i , t 0 , w; x (l) min , t (l) min , V (l) intern , x (i,l) 2 := x (l) min + V (l) intern t (i,l) 2 -t (l)
min .

Initial condition (congested flow)

The model constraints for congested initial conditions are given by (see Figure 3):

                                                                                                                         M c (i) ini t 0 + x 0 -x i w , x 0 ≥ c (j) up t 0 + x 0 -x i w , x 0 , for any i, j such that t 0 + x 0 -x i w ∈ [t j , t j+1 ], M c (i) ini ta + x 0 -xa w , x 0 ≥ c (j) up ta + x 0 -xa w , x 0 ,
for any i, j such that ta

+ x 0 -xa w ∈ [t j , t j+1 ], M c (i) ini ta + xn -xa v f , xn ≥ c (j) down ta + xn -xa v f ,
∈ [t j , t j+1 ], M c (i) ini t (i,l) 1 , x (i,l) 1 ≥ c (l) intern t (i,l) 1 , x (i,l) 1 , for any i, l such that t (l) min ≤ t (i,l) 1 ≤ t (l) max , M c (i) ini t (i,l) 2 , x (i,l) 2 ≥ c (l) intern t (i,l) 2 , x (i,l) 2
, for any i, l such that t

(l) min ≤ t (i,l) 2 ≤ t (l) max , M c (i) ini t (i,l) 3 , x (i,l) 3 ≥ c (l) intern t (i,l) 3 , x (i,l) 3 ,
with                                                                          ta = ta (t 0 , x i+1 ) , xa = xa (t 0 , x i+1 ) , t (i,j) 0 := T+ xn, t j , 0; x i+1 , t 0 , v (i) ini t (i,l) 1 := Ť xa, ta, v f ; x (l) min , t (l) min , V (l) intern , x (i,l) 1 := x (l) min + V (l) intern t (i,l) 1 -t (l) min , t (i,l) 2 := Ť xa, ta, w; x (l) min , t (l) min , V (l) intern , x (i,l) 2 := x (l) min + V (l) intern t (i,l) 2 -t (l) min , t (i,l) 3 := Ť x i+1 , t 0 , w; x (l) min , t (l) min , V (l) intern , x (i,l) 3 := x (l) min + V (l) intern t (i,l) 3 -t (l) min , t (i,l) 4 := T± x (l) min , t (l) min , V (l) intern ; x i+1 , t 0 , v (i) ini , x (i,l) 4 := x (l) min + V (l) intern t (i,l) 4 -t (l) min .

Upstream boundary condition (free flow)

The model constraints with respect to a free-flow upstream boundary condition are the following ones: (see Figure 4):

                         M c (j) up t j + x n -x 0 v f , x n ≥ c (j ) down t j + x n -x 0 v f , x n ,
for any j, j such that

t j + x n -x 0 v f ∈ [t j , t j +1 ], M c (j) up t (j,l) 0 , x (j,l) 0 ≥ c (l) intern t (j,l) 0 , x (j,l) 0
, for any j, l such that t

(l) min ≤ t (j,l) 0 ≤ t (l) max , (3.26) with    t (j,l) 0 = Ť x 0 , t j , v f ; x (l) min , t (l) min , V (l) intern , x (j,l) 0 = x (l) min + V (l) intern t (j,l) 0 -t (l) min .

Upstream boundary condition (congested)

For a congested upstream boundary condition, the compatibility constraints read as follows (see Figure 5):

                                                                                                                             M c (j) up ta + x 0 -xa w , x 0 ≥ c (j ) up ta + x 0 -xa w , x 0 ,
for any j, j such that ta

+ x 0 -xa w ∈ [t j , t j +1 ], M c (j) up t j + xn -x 0 v f , xn ≥ c (j ) down t j + xn -x 0 v f ,
∈ [t j , t j +1 ], M c (j) up t (j,l) 1 , x (j,l) 1 ≥ c (l) intern t (j,l) 1 , x (j,l) 1
, for any j, l such that t

(l) min ≤ t (j,l) 1 ≤ t (l) max , M c (j) up t (j,l) 2 , x (j,l) 2 ≥ c (l) intern t (j,l) 2 , x (j,l) 2
, for any j, l such that t

(l) min ≤ t (j,l) 2 ≤ t (l) max , M c (j) up t (j,l) 3 , x (j,l) 3 ≥ c (l) intern t (j,l) 3 , x (j,l) 3
, for any j, l such that t with

                                                                         ta = ta (t j+1 , x 0 ) , xa = xa (t j+1 , x 0 ) , t (j,j ) 0 = T+ xn, t j , 0; x 0 , t j+1 , v (j) up , t (j,l) 1 = Ť x 0 , t j , v f ; x (l) min , t (l) min , V (l) intern , x (j,l) 1 = x (l) min + V (l) intern t (j,l) 1 -t (l) min , t (j,l) 2 = Ť xa, ta, v f ; x (l) min , t (l) min , V (l) intern , x (j,l) 2 = x (l) min + V (l) intern t (j,l) 2 -t (l) min , t (j,l) 3 = Ť xa, ta, w; x (l) min , t (l) min , V (l) intern , x (j,l) 3 = x (l) min + V (l) intern t (j,l) 3 -t (l) min , t (j,l) 4 = T± x 0 , t j+1 , v (j) up ; x (l) min , t (l) min , V (l) intern , x (j,l) 4 = x (l) min + V (l) intern t (j,l) 4 -t (l)
min .

Downstream boundary condition

The model constraints for any downstream boundary condition are given by the following set of inequalities (see also Figure 6): , x

                                                             M c (j) down t j + x 0 -xn w , x 0 ≥ c (j ) up t j + x 0 -
(j,l) 1 ≥ c (l) intern t (j,l) 1 , x (j,l) 1
, for any j, l such that t

(l) min ≤ t (j,l) 1 ≤ t (l) max , M c (j) down t (j,l) 2 , x (j,l) 2 ≥ c (l) intern t (j,l) 2 , x (j,l) 2
, for any j, l such that t

(l) min ≤ t (j,l) 2 ≤ t (l) max , (3.28) with                                ta = ta (t j+1 , xn) , xa = xa (t j+1 , xn) , t (j,l) 1 = Ť xn, t j+1 , w; x (l) min , t (l) min , V (l) intern , x (j,l) 1 = x (l) min + V (l) intern t (j,l) 1 -t (l) min , t (j,l) 2 = Ť xa, ta, w; x (l) min , t (l) min , V (l) intern , x (j,l) 2 = x (l) min + V (l) intern t (j,l) 2 -t (l)
min .

Internal boundary condition

Finally, the compatibility conditions associated to an internal boundary condition are given by (see Figure 7):

                                                                                                                                                                 M c (l) intern t (l) min + x 0 -x (l) min w , x 0 ≥ c (j) up t (l) min + x 0 -x (l) min w , x 0 ,
for any l, j such that t

(l) min + x 0 -x (l) min w ∈ [t j , t j+1 ], M c (l) intern t (l) max + x 0 -x (l) max w , x 0 ≥ c (j) up t (l) max + x 0 -x (l) max w , x 0 ,
for any l, j such that t

(l) max + x 0 -x (l) max w ∈ [t j , t j+1 ], M c (l) intern t max a + x 0 -x max a w , x 0 ≥ c (j) up t max a + x 0 -x max a w , x 0 ,
for any l, j such that t max a

+ x 0 -x max a w ∈ [t j , t j+1 ], M c (l) intern t max a + xn -x max a w , xn ≥ c (j) down t max a + xn -x max a w , xn ,
for any l, j such that

t max a + xn -x max a w ∈ [t j , t j+1 ], M c (l) intern t max a + xn -x max a v f , xn ≥ c (j) down t max a + xn -x max a v f , xn , for any l, j such that t max a + xn -x max a v f ∈ [t j , t j+1 ], M c (l) intern t min a + xn -x min a v f , xn ≥ c (j) down t min a + xn -x min a v f , xn , for any l, j such that t min a + xn -x min a v f ∈ [t j , t j+1 ], M c (l) intern t (l) min + xn -x (l) min v f , xn ≥ c (j) down t (l) min + xn -x (l) min v f , xn ,
for any l, j such that t

(l) min + xn -x (l) min v f ∈ [t j , t j+1 ], M c (l) intern t (l,j) 0 , x (l,j) 0 ≥ c (j) down t (l,j) 0 , x (l,j) 0 ,
for any l, j such that t (l,j) 0

∈ [t j , t j+1 ], M c (l) intern t (l,j) 1 , x (l,j) 1 ≥ c (j) down t (l,j) 1 , x (l,j) 1
, for any l, j such that t (l,j) 1

∈ [t j , t j+1 ], M c (l) intern t min a + xn -x min a V (l) intern , xn ≥ c (j) down t min a + xn -x min a V (l) intern , xn , for any l, j such that t min a + xn -x min a V (l) intern ∈ [t j , t j+1 ] and V (l) intern = 0, (3.29) ≤ t (l ) max , M c (l) intern t (l,l ) 5 , x (l,l ) 5 ≥ c (l ) intern t (l,l ) 5 , x (l,l ) 5
, for any l, l such that t

(l ) min ≤ t (l,l ) 5 ≤ t (l ) max , M c (l) intern t (l,l ) 6 , x (l,l ) 6 ≥ c (l ) intern t (l,l ) 6 , x (l,l ) 6
, for any l, l such that t

(l ) min ≤ t (l,l ) 6 ≤ t (l ) max , M c (l) intern t (l,l ) 7 , x (l,l ) 7 ≥ c (l ) intern t (l,l ) 7 , x (l,l ) 7
, for any l, l such that t

(l ) min ≤ t (l,l ) 7 ≤ t (l ) max , M c (l) intern t (l,l ) 8 , x (l,l ) 8 ≥ c (l ) intern t (l,l ) 8 , x (l,l ) 8
, for any l, l such that t (3.30)

with                                                                                                                                                                                        t min a = ta t (l) min , x (l) min , x min a = xa t (l) min , x (l) min , t max a = ta t (l) max , x (l) max , x max a = xa t (l) max , x (l) max , t (l,j) 0 = T+ xn, t j , 0; x (l) min , t (l) min , V (l) intern , t (l,j) 1 = T+ xn, t j , 0; x (l) max , t (l) max , V (l) intern , t (l,l ) 1 = Ť x (l) min , t (l) min , w; x (l) min , t (l) min , V (l) intern , x (l,l ) 1 = x (l) min + V (l) intern t (l,l ) 1 -t (l) min , t (l,l ) 2 = Ť x (l) min , t (l) min , v f ; x (l) min , t (l) min , V (l) intern , x (l,l ) 2 = x (l) min + V (l) intern t (l,l ) 2 -t (l) min , t (l,l ) 3 = Ť x (l) max , t (l) max , w; x (l) min , t (l) min , V (l) intern , x (l,l ) 3 = x (l) min + V (l) intern t (l,l ) 3 -t (l) min , t (l,l ) 4 = Ť x min a , t min a , v f ; x (l) min , t (l) min , V (l) intern , x (l,l ) 4 = x (l) min + V (l) intern t (l,l ) 4 -t (l) min , t (l,l ) 5 = Ť x min a , t min a , V (l) intern ; x (l) min , t (l) min , V (l) intern , x (l,l ) 5 = x (l) min + V (l) intern t (l,l ) 5 -t (l) min , t (l,l ) 6 = Ť x max a , t max a , v f ; x (l) min , t (l) min , V (l) intern , x (l,l ) 6 = x (l) min + V (l) intern t (l,l ) 6 -t (l) min , t (l,l ) 7 = Ť x max a , t max a , w; x (l) min , t (l) min , V (l) intern , x (l,l ) 7 = x (l) min + V (l) intern t (l,l ) 7 -t (l) min , t (l,l ) 8 = T± x (l) min , t (l) min , V (l) intern ; x (l) min , t (l) min , V (l) intern , x (l,l ) 8 = x (l) min + V (l) intern t (l,l ) 8 -t (l) min , t (l,l ) 9 = T± x (l) min , t (l) min , V (l) intern ; x (l) max , t (l) max , V (l) intern , x (l,l ) 9 = x (l) min + V (l) intern t (l,l ) 9 -t (l) min .

Comparison between LWR-BA based estimation model and LWR based estimation model

The expressions of model constraints of LWR-BA model under congested flow is very different from those corresponding constraints for the LWR model (given in [START_REF] Canepa | Exact solutions to traffic density estimation problems involving the lighthill-whitham-richards traffic flow model using mixed integer programming[END_REF]). The parabolic terms inspired by considering bounded acceleration contribute to the term x a , t (i,j) 0 and t

(i,l) 4
in the constraints in comparison with the previously piece-wise linear constraints with respect to the parameters. These fix in constraints would contribute to the smooth acceleration period in estimation result. The performances of LWR-BA estimation model and LWR estimation model would be compared qualitatively in Section 4.

Luckily, the quadratic terms only occur in the parameters instead of the decision variables listed in (3.20). It indicates that the property of the optimization problem for LWR-BA model is still the same as LWR model.

Data constraints

In addition to the model constraints presented above, we consider a separate set of data constraints that arise from known measurements on traffic densities, boundary flows or travel time samples obtained thanks to probe vehicles.

We consider the additional assumption:

(A3) The data constraints are linear with respect to the decision variable y defined in (3.20) such that they can be represented in matrix form as follows

C data y ≤ d data .
The data constraints that are considered in this paper encompass

(1) Downstream boundary outflow estimation due to the red light located at x = χ p j = 0, for any j s.t.

Ω red ∩ [t j , t j+1 ] = ∅,
where the set of traffic signal timings Ω red is assumed to known. (2) Flow measurements q meas coming from fixed sensors with known errors e meas f low and located at the upstream boundary x = ξ

(1 -e meas f low )q meas (t) ≤ q j ≤ (1 + e meas f low )q meas (t), for any t ∈ [t j , t j+1 ].

(

Setting of the optimization problem

It is noteworthy that the solutions described in equations (6.34)-(6.38) associated with the adequate value conditions (2.8), (2.12), (2.13) and (2.14) are all linear in the decision variable y and all these constraints described by (3.24)-(3.30) are also linear in y. Therefore, we can represent the model constraints in the matrix form as follows

A model y ≤ b model .
These model constraints encode the limitations due to the physics of traffic flows.

We are now ready to set the optimal control problem that we will use for the queue length estimation. We follow [START_REF] Anderson | Optimization-based queue estimation on an arterial traffic link with measurement uncertainties[END_REF]. Notice that the optimization framework was previously proposed in Claudel and Bayen (2011); [START_REF] Canepa | Exact solutions to traffic density estimation problems involving the lighthill-whitham-richards traffic flow model using mixed integer programming[END_REF]. It reads as follows

Maximize g(y)

subject to

A model y ≤ b model , (model constraints), C data y ≤ d data , ( data constraints).
(3.31)

The objective function g : y → g(y) can be any convex piecewise affine function of the decision variable. In our case, since we aim at maximizing the downstream outflows, the cost function is defined as follows

g(y) = (0 R n , 0 R m , 1 R m , 0 R o ×R o ) • y T = m-1 j=0 p j .
(3.32)

Solving the optimization problem (3.31) leads to an optimal solution denoted by

y * := k * 1 , . . . , k * n , q * 1 , . . . , q * m , p * 1 , . . . , p * m , M (1) * , q (1) inter * , . . . , M (o) * , q (o) inter * = argmax y g(y)
that can be used to compute the traffic states M and k = -∂M ∂x thanks to the explicit solutions (6.34)-(6.38). The queue lengths are then deduced by computing at each time step the extremal points of the set

Q ε (t) := (α, β) ξ ≤ α < β ≤ χ, |k(t, z) -κ| ≤ ε, ∀z ∈ [α, β]
where ε > 0 is a prescribed sensitivity parameter.

Network implementation

We now present the implementation of our estimation framework to the case of an arterial road by considering it as a particular network. More precisely, we will consider the road not as a set of isolated single links as it has been done in Li, Canepa, and Claudel (2014b,a) for a general setting, or in [START_REF] Anderson | Optimization-based queue estimation on an arterial traffic link with measurement uncertainties[END_REF] for queue estimation on arterials; but as an oriented graph made of a series of links (the edges) linked by a junction (the vertex). For a presentation of the general framework, the interested reader is kindly referred to [START_REF] Canepa | Networked traffic state estimation involving mixed fixed-mobile sensor data using Hamilton-Jacobi equations[END_REF]. Without loss of generality, we will restrain ourselves to the case of two links with one intermediary junction. The junction is assumed to be point-wise, say it has no storage capacity. It is worth mentioning that this approach is also equivalent to considering the junction as a fixed bottleneck and thus to add an internal condition with the appropriate flow conditions. Moreover, to take into account the lateral inflows and outflows at the junctions due to the turning movements to and from other roads (see Figure 8) we assume that there are one on-ramp and one off-ramp at each junction.

The upstream and downstream flows on the main section and the inflow and outflow at the junction are denoted respectively by f in , f out , f ramp in and f ramp out . We assume that there exists a matrix A := (α i,j ) i,j that distribute the flows using allocation parameters 0 ≤ α i,j ≤ 1 for any 1 ≤ i, j ≤ 2:

f out f ramp out = A f in f ramp in .
We have the obvious relation

f out + f ramp out = f in + f ramp in .
If we denote by Ω red the set of all times for which the traffic light on upstream link is red, then the input flow f in (t) is given as follows

f in (t) = 0 if t ∈ Ω red .
When t / ∈ Ω red , then the flow f in is undefined and will be set by a junction model. We assume that at the junction the total flow is maximized, that leads us to consider a junction model written as an optimization problem under constraints (see for instance Costeseque and Lebacque (2014a) and references therein) as follows max f out (3.33a) subject to

       0 ≤ f in ≤ δ -f ramp in 0 ≤ f out ≤ σ -f ramp out f out = f in + f ramp in -f ramp out .
(3.33b)

The constraints (3.33b) express the non-negativity of flows and the demand-supply upper bounds denoted by δ and σ. The maximization of the total flow through the junction imposes that at least one of the inequalities in (3.33b) becomes an equality to the respective upper bound, adding additional integer variables to the problem. It is noteworthy that the flow on the downstream section is a mixture of flows coming from the upstream and from the lateral inflow. The bounded-acceleration phase can occur for vehicles that are starting after their traffic light turns green. The traffic light phases from upstream section and for the imaginary on-ramp are generally different, meaning that the flow downstream is composed by vehicles that may be at the maximal free-flow speed v f while some others are still accelerating with a speed v < v f . It is also necessary to consider if there is a queue that have spilled over the downstream link by adding a Boolean variable.

Numerical examples

Presentation of the NGSIM data

The trajectory data is made publicly-available thanks to the Next Generation Simulation (NGSIM) project (NGSIM 2006) led by the U.S. Federal Highway Administration. These data were collected on an arterial street, namely the Lankershim Boulevard in Los Angeles, California, encompassing 4 intersections equipped with traffic signals (see Figure 9). The detailed trajectory data of 2,442 vehicles (with a time resolution of 10 samples per second) originate from five high-definition cameras, monitoring a 1,600-foot stretch of road from 08:28 a.m. to 09:00 a.m. on Thursday June 16, 2005.

The monitored section of Lankershim Boulevard encompasses 5 blocks and 4 signalized intersections. Following [START_REF] Anderson | Optimization-based queue estimation on an arterial traffic link with measurement uncertainties[END_REF], we will test our algorithm on 4 different links that are highlighted on Figure 9: link 2 Northbound (NB), link 2 Southbound (SB), link 3 Southbound and link 4 Northbound. These links are representative of typical link geometries. Link 2SB is the simplest case: it has 3 lanes with no possible turn movements. Link 2NB is composed with 5 lanes (downstream) including 1 designated left-turn lane, 1 dedicated right-turn lane and 1 permissive right-turn lane. Link 3SB expands from 3 to 6 lanes (downstream) among which there are 2 dedicated left-turn lanes, 1 right-turn pocket and 3 through-lanes. Finally, link 4NB is made of 4 lanes with an intermediate entry-exit point and a small left-turn pocket downstream.

The signal timing plans are given in the NGSIM Lankershim Boulevard database. We can thus compute the red signal times.

From the NGSIM data, we extract vehicle counts for each upstream link position and these counts are converted to averaged flow measurements. We also use a set of randomly-selected trajectories for end-to-end travel times measurements.

Settings and results

For the calibration of our fundamental diagram, we have selected the following numerical values

       v f = 15.64 m.s -1 35 miles.h -1 w = -6.7 m.s -1 -15 miles.h -1 κ = 0.125 veh.m -1 200 veh.mile -1
It is noteworthy that the jam density κ is here intended as a maximal value per lane. Hence, depending on the link, it should be multiplied accordingly by the number of lanes.

The optimization problem is solved thanks to the CPLEX solver from IBM used as a blackbox on our MATLAB toolbox. We then re-inject the optimal decision variable y * into the LWR solver1 and into the LWR-BA solver2 . We recall that the level-sets of the function M give the individual and averaged trajectories of vehicles as long as one can assume that the vehicles cannot overtake each other and stay ordered. The estimated traffic state and the averaged trajectories for both the LWR model with and without the bounded acceleration are compared to the observed trajectories on link 2NB (see Figure 13), link 2SB (Figure 14), and on link 3SB (Figure 15). As all the estimation is done based on true data instead of simulation, we only have noisy measurements instead of exact value of true states. Thus, it's not reasonable to compare the results between our method and previous method quantitatively as we have no clue of the real true value. We would compare and analyze the results with graphs.

Influence of the acceleration parameter

To illustrate the influence of the bounded acceleration parameter a, we investigate the performance of the estimation algorithm in two extreme cases of acceleration rate. When a → +∞, the LWR-BA model tends towards the LWR model. Thus, choosing an acceleration rate of a = 10 6 m.s -2 should return a similar estimation result as the LWR model (without BA). In the second test, we set the acceleration parameter to a very low value of a = 0.1 m.s -2 , which is much smaller than the actual maximal acceleration of a vehicle. All results presented in this section are based on the same time period on link3-southbound from data (NGSIM 2006). The corresponding trajectory data is plotted in Figure 10.

In Figure 11, the estimated trajectories (in black) and estimated queue length (in red) are shown to be identical in two cases. This indicates that the BA-LWR model will tend to the LWR model for extreme acceleration rates. It can be noticed that in the period from 0 to 50 seconds, these two models seem to differ. This is caused by a discontinuity over the data in this period.

In Figure 12, we can see that a low acceleration rate will greatly reduce the throughput of the intersection, resulting in longer queues.

The cases illustrated above illustrate the influence of the acceleration parameter, and the relationship between models with and without BA. For the following case studies, we set the acceleration rate back to a reasonable level of a = 1 m.s -2 .

Comparison with previous results

In case studies in this subsection, we assume all vehicles with the bounded acceleration rate a = 1 m.s -2 . In this section, we only illustrate parts of estimation result. Interested readers are referred to the results files3 for more estimation results. Through the illustration in this section, we would qualitatively analysis the pros through considering bounded acceleration in queue estimation.

The results are illustrated through qualitative comparisons with previous works. In estimation tasks, true states are not available under true data cases. Thus, any quantitative results such as Maximum Absolute Error (MAE) cannot be available for comparison.

The results of the estimation procedure in [START_REF] Anderson | Optimization-based queue estimation on an arterial traffic link with measurement uncertainties[END_REF] are not totally satisfying since the method only gives an insight on the averaged dynamics of traffic flow on the multi-lanes section. Moreover, the variability due to the presence of specific left or right-turn lanes (or left or right-turn pockets) is difficult to handle. However, data constraints coming from at least 5% travel times data enable to make more precise estimation of queue lengths. On link 2 Northbound, there was an overestimation of the queues in all of the through lanes due to turning movements as pointed out in [START_REF] Anderson | Optimization-based queue estimation on an arterial traffic link with measurement uncertainties[END_REF]. This has motivated a reduction of the inflow by 24% since from direct computations from the data, it had an estimated 20% of the vehicles that have turned right and 4% that have turned left over the 30-minutes study period.

Such inflow reduction have been done from an estimated percentage of turning vehicles directly on the data. In our paper, the same idea to mitigate the problem of overestimation in turning lanes is followed. Queue length estimation with and without bounded acceleration are presented together for comparison (see Figure 13). In lane 2, estimation of queue lengths with bounded acceleration considered shows a great improvement in precision. It indicates that the improved model with bounded acceleration is closer to true states. From the lane 2 case in Figure 13, we can observe that considering bounded acceleration would reduce the estimated number of arrival vehicles. Comparing to the true arrival rate, we can observe that the estimation without considering bounded acceleration is slightly overestimated and the model considering bounded acceleration gives the arrival rate close to true data. We can observe this in other cases too 3 . There is not a definite answer because the core part of our estimation, the optimization solver, is kind of a black box. One thing is certain that the estimated trajectories are much smoother and closer to true trajectories in pattern because the constraints regarding to bounded acceleration that we have added in optimization model. Meanwhile, although there is no clue that the method used in [START_REF] Anderson | Optimization-based queue estimation on an arterial traffic link with measurement uncertainties[END_REF] will cause systematically overestimation or underestimation, it still makes sense that the result achieved here is better. In [START_REF] Anderson | Optimization-based queue estimation on an arterial traffic link with measurement uncertainties[END_REF] where bounded acceleration is not considered, the acceleration procedure is considered to be completed instantly which is unrealistic.

On link 2 southbound (see Figure 14) which is a simple geometry without any downstream turn movements, the estimation of queue length is done following the "average" trajectory of lanes which means we consider the similar vehicle density and flow pattern in each lane. As a result, both methods with and without bounded acceleration considered fail in both lane 1 and lane 3. According to analysis, extremely heavy traffic goes to these two lanes which means that evenly distribution assumption is broken. As [START_REF] Anderson | Optimization-based queue estimation on an arterial traffic link with measurement uncertainties[END_REF] has mentioned, this extreme situation is not expected under the assumption that the distribution of vehicles in each lane is supposed to be even. To overcome this drawback, we need to use monitoring data of each lane to do estimation. However, this will cause other problems like lane-changing-sensitivity and the inaccuracy in turn-ratio estimation. However in lane 2 which has a vehicle amount close to average, the new method shows a similar success in improving the precision.

On link 3 Southbound which is composed of 6 lanes with one right turn and 2 dedicated left-turn lanes, only the 3 through-lanes are considered. The result (see Figure 15) indicates similar improvement in precision that considering bounded acceleration brings. In lane three, both methods fail to recognize a queue that was happening from time 150. It's because of the same reason that the evenly distribution assumption is broken. At that time point, much more vehicles go to lane 3, so "average" queue lengths estimation cannot represent this specific lane.

Conclusion and perspectives

This paper presents an optimization-based framework for queue length estimation on arterials that is running on a modified macroscopic traffic flow model. The main progress made over previous work is that vehicles bounded acceleration is included into the optimal control framework. It is shown through comparison over the same test data (NGSIM 2006) that the precision of queue length estimation is improved thanks to this enhanced framework. As average trajectories over all lanes are considered here, the present method performs poorly in estimating queue lengths in specific lanes with unexpected heavy traffic. In most cases, this framework shows a good precision. Comparing to other traditional estimation techniques, such as particle filter, traffic-based estimation methods, our method won't suffer from restrictions due to dramatically increasing computational cost when extended to large scale networks.

Among the scientific perspectives of this work, we aimed at addressing the aspect of bounded vehicle deceleration. Basically, deceleration process is observed at shock waves that naturally arise from the inf-morphism property and not from kinematic waves like for the acceleration process. Deceleration also depend on the immediate downstream conditions. There is an asymmetry between both processes. Thus this would not be straightforward to adapt our framework to the case of bounded deceleration.

Another interesting direction of research is to consider uncertainties on the fundamental diagram parameters namely the free-flow speed v f , the jam wave speed w and the maximal density κ and to do Monte Carlo simulations. Monte Carlo simulations help to find the value closest to actual value which helps bring a better estimation outcome.

Improved queue length estimation precision can also provide a better pre-step for the optimal control of traffic light on arterial links which helps keep queue length at a reasonable level. Future work can be done to develop optimal control method of traffic light based on this estimation algorithm. where k 2 is the upper solution of Q(k) -kV and assuming that there exists an index j ∈ 0, m-1 such that t (l) min = t j and t (l) max = t j+1 (q (l) intern = q j , M (l) = d j + t j q j , k 2 = k (j) up and v = v (j) up or resp. q (l) intern = p j , M (l) = b j + t j p j and v = v (j) down ), then passing to the limit in (6.38), one can recover the expressions of the partial solution for congested upstream boundary conditions (2.19) (resp. for downstream boundary conditions (6.37)).

(l) intern = q (l) intern such that k c ≤ k 2 ≤ κ, say k 2 = q (l) intern + wκ w -V (l) intern and v = Q(k 2 ) k 2 = w 1 - κ k 2 and                                    T 2 (t, x) = (V (l) intern -v) + (V (l) intern -v)

  Liu, Wu, and Michalopoulos 2008; Wu et al. 2009; Vigos, Papageorgiou, and Wang 2008). • the traffic model-based estimation methods that are based on traffic models which include: • macroscopic models, giving birth to the so-called "shockwaves-based" approach (Stephanopoulos, Michalopoulos, and Stephanopoulos 1979; Michalopoulos, Stephanopoulos, and Stephanopoulos 1981) that rely for instance on the LWR model (see Section 1.2.1) or horizontal queuing models. A tentative list of some recent references in that direction encompasses Skabardonis and Geroliminis (2008); Liu et al. (2009); Ban, Hao, and Sun (2011); Cheng et al. (2012); Hao et al. (2013); Anderson et al. (2013); Ramezani and Geroliminis (2015); Hao, Ban, and Whon Yu (2015); Hao and Ban (2015); Adacher and Tiriolo (2018); Shirke, Bhaskar, and Chung (2019).

  Mazaré et al. (2011), Qiu et al. (2013) give the explicit solutions for the LWR model with bounded acceleration (1.4) or (1.5a)-(1.5b) for its HJ PDE expression, under the value conditions (2.15).

Proposition 3 . 2 (

 32 Compatibility conditions). Claudel and Bayen (2011) Let us consider a family of value conditions c j that are lower semi-continuous functions defined on subsets of [0, T ] × [ξ, χ] and let us define their minimum c(t, x) := min j∈J c j (t, x).

  )-(2.15) (or (1.5a)-(1.5b) and (2.15)) verifies M(t, x) = c(t, x), for any (t, x) ∈ Dom (c) , if and only if the following set of compatibility conditions M ci (t, x) ≥ c j (t, x), for all i, j ∈ J, and (t, x) ∈ Dom(c j ) are satisfied. Proof See Proposition 3.6 in Claudel and Bayen (2011).

  intern going to zero (for any0 ≤ l ≤ o -1) such that x (l) min = x (l) max = x 0 (or respectively = x n ) and q (l) intern = vk 2 = w(k 2 -κ)

Figure 1 .

 1 Figure 1. Illustration of all the conditions that are applying on our computation domain [x 0 , xn] × [t 0 , tn].

Figure 2 .

 2 Figure 2. Domain of influence of the initial condition c (i) ini when 0 ≤ k (i) ini ≤ kc.

Figure 3 .

 3 Figure 3. Domain of influence of the initial condition c (i) ini when kc < k (i) ini ≤ κ.

Figure 4 .

 4 Figure 4. Domain of influence of the upstream boundary condition c (j) up when 0 ≤ k (j) up ≤ kc.

Figure 5 .

 5 Figure 5. Domain of influence of the upstream boundary condition c (j) up when k (j) up ≥ kc.

Figure 6 .

 6 Figure 6. Domain of influence of the downstream boundary condition c (j) down .

Figure 7 .

 7 Figure 7. Domain of influence of the internal boundary condition c (l) intern .

Figure 8 .

 8 Figure 8. Schematic representation of turning movements at an intersection as a one-by-one junction with on-and off-ramps.

Figure 9 .

 9 Figure 9. Schematic representation of the Lankershim Boulevard, Los Angeles, CA, USA.

Figure 10 .

 10 Figure 10. Measured trajectory data on link 3, Southbound (NGSIM 2006).

Figure 11 .

 11 Figure 11. Comparison of estimated trajectories and queue lengths on link 3, Southbound, using classical LWR model (top) and LWR-BA model with acceleration rate a = 10 6 m.s -2 (bottom).

Figure 12 .

 12 Figure 12. Comparison of estimated trajectories and queue lengths on link 3, Southbound, using classical LWR model (top) and LWR-BA model with acceleration rate a = 0.1m.s -2 (bottom).Here there are some wrongly labeled queues on the upstream side in the bounded acceleration case. It's because of the unrealistic acceleration rate we set here combining that we judge a queue with a prescribed sensitivity parameter ε = 0.01κ.

Figure 13 .

 13 Figure 13. Queue estimate comparisons on link 2, Northbound, a = 1m.s -2

Figure 14 .

 14 Figure 14. Queue estimate comparisons on link 2, Southbound, a = 1m.s -2

•

  To apply the optimization-based estimation method to the case of queue

estimation on LWR model LWR-BA model

	Analytical solutions	Mazaré et al. (2011)	Qiu et al. (2013)
	under piecewise affine conditions		except for congested upstream
			boundary conditions
	Compatibility conditions	Canepa and Claudel (2012)	This paper
	(or model constraints)
	Optimization-based queue	Anderson et al. (2013)	This paper
	estimation on arterials

Table 1 .

 1 Synthetic view of the relevant literature and of our contributions

	arterial roads, including the extension to networks as first proposed in Canepa and Claudel
	(2017).
	• To qualitatively compare the effects of bounded acceleration on queue estimation, from real
	data.

  •) is the lower envelope of the capture basin Capt (2.16) (K, C).

	3)-(2.15) is thus given by
	M(t, x) :=	inf	y,	(2.17)
		(t,x,y)∈Capt (2.16) (K,C)
	meaning that the graph of M(•, Theorem 2.2 (Generalized Lax-Hopf formula). The viability episolution M associated with a
	target C := Epi(c), for a given lower semi-continuous function c and defined in (2.17)-(2.15) can
	be expressed by

  portation Research Board (2099): 30-38. 2 Xie, Xu, Hans van Lint, and Alexander Verbraeck. 2018. "A generic data assimilation framework for vehicle trajectory reconstruction on signalized urban arterials using particle filters." Transportation research part C: emerging technologies 92: 364-391. 26.1.6. Internal boundary conditionWe define the following auxiliary variables:The solution component associated with the affine internal boundary condition (2.14) (see Figure7) is expressed by:M (l) + vk 2 (t 1 -t (l) min ) -v f k 2 t 1 + (x (l) min -x + τ v + aτ 2 2 + (t -τ )v f )k 2 : x ≤ x a,min + v f (t -t a,min ) and x ≥ xa,max + v f (t -ta,max) and x ≥ x a,min + V ≥ x a,min + v f (t -t a,min ) and x ≤ x

	(ii)	                             M (l) -vk 2 t x (l) max = x τ = x ≥ x (l) min + w(t -t (l) min + V (l) (l) (l) intern t (l) max -t (l) min (l) min ) and min ) and x ≤ x (l) max + w(t -t (l) max ) and v f -V intern (l) t ≥ t min a x a,min = x (l) min + V (l) intern τ + a 2 τ 2 t a,min = t (l) (l) min + (x (l) min -x + tv)k 2 + k 2 a 2 T 2 4 : x ≥ x (l) max + w(t -t (l) max ) and min + τ x a,max = x (l) max + V (l) intern τ + x ≤ xa,max + w(t -ta,max) and a 2 τ 2 t a,max = t (l) max + τ x ≤ x (l) max + V (l) intern (t -t (l) max ) + a (l) max ) 2 and 2 (t -t (l) t ≥ t max
	(iii) M (l) -vk 2 t (l) min + (x : x ≤ x (l) min + V (l) intern (t -t (l) min -x + tv)k 2 + k 2 a 2 T 2 2 (l) min ) + a 2 (t -t (l) min ) 2 and x ≤ x a,min + V (l) intern (t -t a,min ) and x ≥ x (l) max + V (l) intern (t -t (l) max ) + a (l) max ) 2 and 2 (t -t x ≥ x (l) min + V (l) intern (t -t (l) min ) and (l) t ≥ t min
	t ≥ t min + τ (l) (iv) (l) intern (t -t a,min ) and	(6.38)
	(v)
		(l) max + τ
	(vi) M (l)
		: x ≥ x x ≤ x (l) min + V intern (t -t (l) (l) min ) + a 2 (t -t (l) min ) 2 and (l) min + v f (t -t (l) min ) and 0 ≤ (t -t (l) min ) ≤ τ
		or
		x (l) min + v f (t -t (l) min ) and t ≥ t (l) min + τ

intern (t -t M (l) + vk 2 (t 2 -t (l) min ) -v f k 2 t 2 + (x (l) min -x + τ v + aτ 2 2 + (t -τ )v f )k 2 : x ≥ xa,max + v f (t -ta,max) and

x ≤ xa,max + w(t -ta,max) and t ≥ t

  2 + 2a(x -x (t, x) = (w -v) + (w -v) 2 + 2a(x -x , v where the function T+ is defined in (3.23).• t 1 is the time for which both straight linesx where the function Ť is defined in (3.22). • t 2 is the time for which both straight lines x ) andx -τ (v -v f ) -a 2 τ 2 intersect. We have that t 2 (t, x) = Ť x -τ v -a 2 τ 2 , t -τ, v f ; x (Degenerate cases).It is noteworthy that letting V

												(l) min -V	(l) intern (t -t (l) min ))
												a
				max -w(t -t (l) max )) T 4 (l) a
												(6.39)
				t 1 (t, x) =	1 v f -V intern (l)	x	(l) min -V	(l) intern t (l) min -x + τ v +	aτ 2 2	+ (t -τ )v f
				t 2 (t, x) =	1 v f -w	x (l) max -wt (l) max -x + τ v +	aτ 2 2	+ (t -τ )v f .
	It is noteworthy that:
	• T 2	defines	the	time		for	which	the	curves	x + V	(l) intern t	and
	x	(l) min + v t -t (l) min + a 2 t -t (l) min	2	intersect.	We have that T 2 (t, x)	=
	T+ x, t, V	(l) intern ; x	(l) min , t (l) min , v where the function T+ is defined in (3.23).
	• T 4	defines	the		time			for	which	the	curves	{x + wt}	and
	x max + v t -t (l) (l) max + a 2 t -t (l) max	2	intersect. We have that T 4 (t, x)	=
	T+ x, t, w; x	(l) max , t (l)
												(l) min + V	(l) intern (t -t (l) min )
	and	x -τ (v -v f ) -a 2 τ 2			intersect.	We	have	that	t 1 (t, x)	=
	Ť x -τ v -(l) min , t (l) min , V	(l)
												(l) max + w(t -t (l)
												(l) max , t (l) max , w where the func-
	tion Ť is defined in (3.22).
	Remark 6.1

max a 2 τ 2 , t -τ, v f ; x intern max

Available at http://traffic.berkeley.edu/project/downloads/lwrsolver.

Available at https://utexas.box.com/s/ipm7fgucobsgu7nszxea49sx80i3p1nx.

https://utexas.box.com/s/ipm7fgucobsgu7nszxea49sx80i3p1nx

Acknowledgements

The authors are sincerely grateful to Professor Alexandre Bayen from UC Berkeley for discussions on the topic, to Dr. Leah Anderson for providing lots of insights on her Matlab toolbox and on Lankershim Blvd NGSIM dataset. G. Costeseque is grateful to Inria Sophia-Antipolis Méditerranée, France, for its support and hospitality during the early stage of this paper. This research is partially supported by the National Science Foundation under Grant No.1636154.

search Board . 2 Liu, Henry X, Xinkai Wu, Wenteng Ma, and Heng Hu. 2009. "Real-time queue length estimation for congested signalized intersections." Transportation research part C: emerging technologies 17 (4): 412-427. 2 Mazaré, Pierre-Emmanuel, Ahmad H Dehwah, Christian G Claudel, and Alexandre M Bayen. 2011. alytical and grid-free solutions to the Lighthill-Whitham-Richards traffic flow model." Transportation Research Part B: Methodological 45 (10): 1727-1748. 5, 6, 11, 12 Michalopoulos, Panos G, Gregory Stephanopoulos, and George Stephanopoulos. 1981. "An application of shock wave theory to traffic signal control." Transportation Research Part B: Methodological 15 (1): 35-51. 2 Moskowitz, Karl, and L Newan. 1963. "Notes on freeway capacity." Highway Research Record (27). 4 Newell, Gordon F. 1993a. "A simplified theory of kinematic waves in highway traffic, part I: general theory." Transportation Research Part B: Methodological 27 (4): 281-287. 4 Newell, Gordon F. 1993b. "A simplified theory of kinematic waves in highway traffic, Part II: Queueing at freeway bottlenecks." Transportation Research Part B: Methodological 27 (4): 289-303. 4 Newell, Gordon F. 1993c. "A simplified theory of kinematic waves in highway traffic, Part III: Multidestination flows." Transportation Research Part B: Methodological 27 (4): 305-313. 4 Newell, Gordon Frank. 1960. "Queues for a fixed-cycle traffic light." The Annals of Mathematical Statistics 31 (3): 589-597. 2 Newell, Gordon Frank. 1965. "Approximation methods for queues with application to the fixed-cycle traffic light." Siam Review 7 (2): 223-240. 2 Newell, Gordon Frank. 2002. "A simplified car-following theory: a lower order model." Transportation Research Part B: Methodological 36 (3): 195-205. 3 NGSIM. 2006. "Next generation simulation." Federal Highway Administration, http://ops.fhwa.dot. gov/trafficanalysistools/ngsim.htm. 25, 26, 28, 42 Qiu, Shanwen, Mohannad Abdelaziz, Fadl Abdellatif, and Christian G Claudel. 2013. "Exact and gridfree solutions to the Lighthill-Whitham-Richards traffic flow model with bounded acceleration for a class of fundamental diagrams." Transportation Research Part B: Methodological 55: 282-306. 5, 6, 12 Ramezani, Mohsen, and Nikolas Geroliminis. 2012. "On the estimation of arterial route travel time distribution with Markov chains." Transportation Research Part B: Methodological 46 (10): 1576-1590. 2, 3 Ramezani, Mohsen, and Nikolas Geroliminis. 2015. "Queue profile estimation in congested urban networks with probe data." Computer-Aided Civil and Infrastructure Engineering 30 (6): 414-432. 2 Richards, Paul I. 1956. "Shock waves on the highway." Operations research 4 (1): 42-51. 3 Shirke, Chaitrali, Ashish Bhaskar, and Edward Chung. 2019. "Macroscopic modelling of arterial traffic: An extension to the cell transmission model." Transportation Research Part C: Emerging Technologies 105: 54-80. 2 Skabardonis, Alexander, and Nikolas Geroliminis. 2008. "Real-time monitoring and control on signalized arterials." Journal of Intelligent Transportation Systems 12 (2): 64-74. 2 Srivastava, Anupam, Wen-Long Jin, and Jean-Patrick Lebacque. 2015. "A modified cell transmission model with realistic queue discharge features at signalized intersections." Transportation Research Part B: Methodological 81: 302-315. 5 Stephanopoulos, Gregory, Panos G Michalopoulos, and George Stephanopoulos. 1979. "Modelling and analysis of traffic queue dynamics at signalized intersections." Transportation Research Part A: General 13 (5): 295-307. 2 Valadkhani, Amir Hosein, Yang Hong, and Mohsen Ramezani. 2017. "Integration of loop and probe data for traffic state estimation on freeway and signalized arterial links." In 2017 IEEE 20th International Conference on Intelligent Transportation Systems (ITSC), 1-6. IEEE. 2 Vigos, Georgios, Markos Papageorgiou, and Yibing Wang. 2008. "Real-time estimation of vehicle-count within signalized links." Transportation Research Part C: Emerging Technologies 16 (1): 18-35. 2 Viti, Francesco, and Henk J Van Zuylen. 2010. "Probabilistic models for queues at fixed control signals." Transportation Research Part B: Methodological 44 (1): 120-135. 2 Webster, Fo Vo. 1958. Traffic signal settings. Technical Report. 2 Wu, Jingcheng, Xia Jin, Alan Horowitz, and Daqing Gong. 2009. "Experiment to improve estimation of vehicle queue length at metered on-ramps." Transportation Research Record: Journal of the Trans-

and

, for any l, l such that t (l ) min ≤ t (l,l ) 6. Appendix

Detailed Solution Expressions for the LWR-BA model

Initial condition (free flow)

If 0 ≤ k i ≤ k c , the solution component associated with the affine initial condition (2.8) (see Figure 2) is expressed by:

Initial condition (congested flow)

If k c ≤ k i ≤ κ, the solution component associated with the affine initial condition (2.8) (see Figure 3) is expressed by:

where the auxiliary variables are given by

Notice that T 4 (t, x) defines the time for which the curves {x + wt} and

ini t + a 2 t 2 intersect. We have in particular that T 4 (t, x) = T+ (x, 0, w; x i+1 , 0, v ini ) where the function T+ is defined in (3.23).

Upstream boundary condition (free flow)

We assume that k (j) up ≤ k c , for a given j, say that the upstream boundary (x = x 0 ) is in freeflow on [t j , t j+1 ]. Then the solution component associated with the affine upstream boundary condition (2.12) (see Figure 4) is expressed by:

(6.36)

Upstream boundary condition (congested)

Please refer to Section 2.

Downstream boundary condition

As previously described in Section 2.1.2, we only consider congested downstream boundary conditions that have a domain of influence that belongs to our computation domain

We define

down < v f , then the solution component associated with the affine downstream boundary condition (2.13) (see Figure 6) is expressed by:

Notice that (iv) in (6.37) is outside of the computational domain.