A special class of triple starlike trees characterized by Laplacian spectrum

1.   Introduction

Macroscopic traffic flow models based on fluid-dynamics equations have been introduced in the transport engineering literature since the mid-fifties of last century, with the celebrated Lighthill, Whitham [11] and Richards [13] (LWR) model. Since then, the engineering and applied mathematical literature on the subject has considerably grown, addressing the need for more sophisticated models better capturing traffic flow characteristics. Indeed, the LWR model is based on the assumption that the mean traffic speed is a function of the traffic density, which is not experimentally verified in congested regimes. To overcome this issue, the so-called "second order" models (e.g. Payne-Whitham [12,15] and Aw-Rascle-Zhang [3,16]) consist of a mass conservation equation for the density and an acceleration balance law for the speed, thus considering the two quantities as independent.

More recently, "non-local" versions of the LWR model have been proposed in [5,14], where the speed function depends on a weighted mean of the downstream vehicle density to better represent the reaction of drivers to downstream traffic conditions.

Another limitation of the standard LWR model is the first-in first-out rule, not allowing faster vehicles to overtake slower ones. To address this and other traffic heterogeneities, "multi-class" models consist of a system of conservation equations, one for each vehicle class, coupled in the speed terms, see [4] and references therein for more details.

In this paper, we consider the following class of non-local systems of $M$ conservation laws in one space dimension:

where

and we assume:

$\mathbf{(H1)}$ The convolution kernels $\omega_i\in {{\mathbf{C}}^{\mathbf{1}}}([0, \eta_i]; \mathbb{R}^+)$, $\eta_i>0$, are non-increasing functions such that $\int_{0}^{\eta_i}\omega_i(y)\mathinner{{\rm{d}}{y}} = J_i$. We set $W_0: = \max_{i = 1, \ldots, M}\omega_i(0)$.

$\mathbf{(H2)}$ $v_i^{\max}$ are the maximal velocities, with $0<v_1^{\max}\leq v_2^{\max}\leq \ldots\leq v_M^{\max}$.

$\mathbf{(H3)}$ $\psi: \mathbb{R}^+\rightarrow \mathbb{R}^+$ is a smooth non-increasing function such that $\psi(0) = 1$ and $\psi(r) = 0$ for $r\geq 1$ (for simplicity, we can consider the function $\psi(r) = \max\{1-r, 0\}$).

We couple (1) with an initial datum

Model (1) is obtained generalizing the $n$-populations model for traffic flow described in [4] and it is a multi-class version of the one dimensional scalar conservation law with non-local flux proposed in [5], where $\rho_i$ is the density of vehicles belonging to the $i$-th class, $\eta_i$ is proportional to the look-ahead distance and $J_i$ is the interaction strength. In our setting, the non-local dependence of the speed functions $v_i$ describes the reaction of drivers that adapt their velocity to the downstream traffic, assigning greater importance to closer vehicles, see also [7,9]. We allow different anisotropic kernels for each equation of the system. The model takes into account the distribution of heterogeneous drivers and vehicles characterized by their maximal speeds and look-ahead visibility in a traffic stream.

Due to the possible presence of jump discontinuities, solutions to (1), (5) are intended in the following weak sense.

Definition 1.1. A function $\boldsymbol{\rho} = (\rho_1, \ldots, \rho_M)\in ({{\mathbf{L}}^{\mathbf{1}}}\cap{{\mathbf{L}}^\infty })([0, T[\, \times \mathbb{R}; \mathbb{R}^M)$, $T>0$, is a weak solution of (1), (5) if

for all $\varphi\in\mathbf{C}_{c}^{\mathbf{1}} (]-\infty, T[\, \times \mathbb{R}; \mathbb{R})$, $i = 1, \ldots, M$.

The main result of this paper is the proof of existence of weak solutions to (1), (5), locally in time. We remark that, since the convolution kernels $\omega_i$ are not smooth on $\mathbb{R}$, the results in [1] cannot be applied due to the lack of ${{\mathbf{L}}^\infty }$-bounds on their derivatives.

Theorem 1.2. Let $\rho_i^0(x) \in \left( \mathbf{BV}\cap{{\mathbf{L}}^\infty }\right)( \mathbb{R}; \mathbb{R}^+)$, for $i = 1, \ldots, M$, and assumptions (H1) - (H3) hold. Then the Cauchy problem (1), (5) admits a weak solution on $[0, T[\, \times \mathbb{R}$, for some $T>0$ sufficiently small.

In this work, we do not address the question of uniqueness of the solutions to (1). Indeed, even if discrete entropy inequalities can be derived as in [5,Proposition 3], in the case of systems this is in general not sufficient to single out a unique solution.

The paper is organized as follows. Section 2 is devoted to prove uniform ${{\mathbf{L}}^\infty }$ and BV estimates on the approximate solutions obtained through an approximation argument based on a Godunov type numerical scheme, see [8]. We have to point out that these estimates heavily rely on the monotonicity properties of the kernel functions $\omega_i.$ In Section 3 we prove the existence in finite time of weak solutions applying Helly's theorem and a Lax-Wendroff type argument, see [10]. In Section 4 we present some numerical simulations for $M = 2$. In particular, we consider the case of a mixed flow of cars and trucks on a stretch of road, and the flow of mixed autonomous and non-autonomous vehicles on a circular road. In this latter case, we analyze two cost functionals measuring the traffic congestion, depending on the penetration ratio of autonomous vehicles. The final Appendix contains alternative ${{\mathbf{L}}^\infty }$ and $\mathbf{BV}$ estimates, based on approximate solutions constructed via a Lax-Friedrichs type scheme, which is commonly used in the framework of non-local equations, see [1,2,5].

2.   Godunov type approximate solutions

First of all, we extend $\omega_i(x) = 0$ for $x>\eta_i$. For $j\in \mathbb{Z}$ and $n\in \mathbb{N},$ let $x_{j+1/2} = j \Delta x$ be the cell interfaces, $x_j = (j-1/2)\Delta x$ the cells centers and $t^n = n\Delta t$ the time mesh. We aim at constructing a finite volume approximate solution $\boldsymbol{\rho}^{\Delta x} = \left(\rho_1^{\Delta x}, \ldots, \rho_M^{\Delta x}\right)$, with $\rho_i^{\Delta x}(t, x) = \rho_{i, j}^n$ for $(t, x)\in C^n_j = [t^n, t^{n+1}[\times ]x_{j-1/2}, x_{j+1/2}]$ and $i = 1, ..., M.$

To this end, we approximate the initial datum $\rho_i^0$ for $i = 1, ..., M$ with a piecewise constant function

Similarly, for the kernel, we set

so that $\Delta x \sum_{k = 0}^{+\infty}\omega_i^k = \int_0^{\eta_i}\omega_i(x) \mathinner{{\rm{d}}{x}} = J_i$ (the sum is indeed finite since $\omega_i^k = 0$ for $k\geq N_i$ sufficiently large). Moreover, we set $r^n_{j+k} = \mathop \sum \limits_{i = 1}^M \rho_{i, j+k}^n$ for $k\in \mathbb{N}$ and

We consider the following Godunov-type scheme adapted to (1), which was introduced in [8] in the scalar case:

where we have set $\lambda = \frac{\Delta t}{\Delta x}$.

2.1.   Compactness estimates

We provide here the necessary estimates to prove the convergence of the sequence of approximate solutions constructed via the Godunov scheme (7).

Lemma 2.1. (Positivity) For any $T>0,$ under the CFL condition

the scheme (7) is positivity preserving on $[0, T]\times \mathbb{R}.$

Proof. Let us assume that $\rho_{i, j}^n\geq 0$ for all $j\in \mathbb{Z}$ and $i\in{1, ..., M}.$ It suffices to prove that $\rho_{i, j}^{n+1}$ in (7) is non-negative. We compute

under assumption (8).

Corollary 1. ($\mathbf{L^{1}}$-bound) For any $n\in \mathbb{N}$, under the CFL condition (8) the approximate solutions constructed via the scheme (7) satisfy

where ${\left\|{\rho_i^n}\right\|}_{1}: = \Delta x \sum_j {\left|{\rho_{i, j}^n}\right|}$ denotes the $\mathbf{L^{1}}$ norm of the $i$-th component of $\rho^{\Delta x}$.

Proof. Thanks to Lemma 2.1, for all $i\in\{1, ..., M\}$ we have

proving (10).

Lemma 2.2. (${{\mathbf{L}}^\infty }$-bound) If $\rho_{i, j}^0\geq 0$ for all $j\in \mathbb{Z}$ and $i = 1, ..., M$, and (8) holds, then the approximate solution $\boldsymbol{\rho}^{\Delta x}$ constructed by the algorithm (7) is uniformly bounded on $[0, T]\times \mathbb{R}$ for any $T$ such that

Proof. Let $\bar\rho = \max\{\rho_{i, j-1}^n, \rho_{i, j}^n\}.$ Then we get

and

where ${\left\|{{ \boldsymbol{\rho}}}\right\|}_\infty = {\left\|{(\rho_1, \ldots, \rho_M)}\right\|}_\infty = \max_{i, j}{\left|{\rho_{i, j}}\right|}$. Let now $K>0$ be such that ${\left\|{{{ \boldsymbol{\rho}}}^{\ell}}\right\|}_\infty\leq K$, $\ell = 0, \ldots, n$. From (11) and (12) we get

which implies

with $C = M K v_M^{\max} {\left\|{\psi'}\right\|}_\infty W_0$. Therefore we get that ${\left\|{{ \boldsymbol{\rho}}(t, \cdot)}\right\|}_\infty \leq K$ for

where the maximum is attained for $K = e {\left\|{{ \boldsymbol{\rho}}^0}\right\|}_\infty$.

Iterating the procedure, at time $t^m$, $m\geq 1$ we set $K = e^m {\left\|{{ \boldsymbol{\rho}}^0}\right\|}_\infty$ and we get that the solution is bounded by $K$ until $t^{m+1}$ such that

Therefore, the approximate solution remains bounded, uniformly in $\Delta x$, at least for $t\leq T$ with

Remark 1. Figure 1 shows that the simplex

is not an invariant domain for (1), unlike the classical multi-population model [4]. Indeed, let us consider the system

where $r$ and $v_i$ are as in (2) and (3), respectively. We have the following:

Lemma 2.3. Under the CFL condition

for any initial datum $\boldsymbol{\rho}_0\in \mathcal{S}$ the approximate solutions to (13) computed by the upwind scheme

with $\mathbf{F} ( \boldsymbol{\rho}_j^n, \boldsymbol{\rho}_{j+1}^n) = \boldsymbol{\rho}^n_j \psi(r^n_{j+1})$, satisfy the following uniform bounds:

Proof. Assuming that $\boldsymbol{\rho}_j^n\in \mathcal{S}$ for all $j\in \mathbb{Z}$, we want to prove that $\boldsymbol{\rho}_j^{n+1}\in \mathcal{S}$. Rewriting (14), we get

Summing on the index $i = 1, \ldots, M$, gives

Defining the following function of $\boldsymbol{\rho}_j^n$

we observe that

if $\lambda \leq 1/v_{M}^{\max} {\left\|{\psi}\right\|}_\infty$ and

for $\boldsymbol{\rho}_j^n\in \mathcal{S}$ such that $r^n_j = \sum_{i = 1}^M \rho^n_{i, j} = 1$. Moreover

if $\lambda\leq 1/ v_M^{\max}\left({\left\|{\psi}\right\|}_\infty+{\left\|{\psi'}\right\|}_\infty\right)$. This proves that $r_j^{n+1}\leq 1$. To prove the positivity of (14), we observe that

if $\lambda\leq 1/ v_M^{\max} {\left\|{\psi}\right\|}_\infty$.

Lemma 2.4. (Spatial $\mathbf{BV}$-bound) Let $\rho_i^0\in \left( \mathbf{BV}\cap{{\mathbf{L}}^\infty }\right) ( \mathbb{R}, \mathbb{R}^+)$ for all $i = 1, ..., M.$ If (8) holds, then the approximate solution $\boldsymbol{\rho}^{\Delta x}(t, \cdot)$ constructed by the algorithm (7) has uniformly bounded total variation for $t\in [0, T]$, for any $T$ such that

where $\mathcal{H} = {\left\|{{ \boldsymbol{\rho}}}\right\|}_\infty\, v_M^{\max} W_0 M\left(6 M J_0 {\left\|{{ \boldsymbol{\rho}}}\right\|}_\infty{\left\|{\psi''}\right\|}_\infty +{\left\|{\psi'}\right\|}_\infty\right)$.

Proof. Subtracting the identities

and setting $\Delta^{n}_{i, j+1/2} = \rho_{i, j+1}^n-\rho_{i, j}^n$, we get

Now, we can write

Observe that assumption (8) guarantees the positivity of (19). The term (20) can be estimated as

with $\xi_j \in {\mathcal I}\left( \Delta x\sum_{k = 0}^{+\infty} \omega_i^k r_{j+k}^n, \Delta x\sum_{k = 0}^{+\infty}\omega_i^k r_{j+k+1}^n\right)$ and $\tilde\xi_{j+1/2}\in {\mathcal I}\left(\xi_{j}, \xi_{j+1}\right)$, where we set ${\mathcal I} (a, b) = \left[\min\{a, b\}, \max\{a, b\}\right]$. For some $\vartheta, \mu\in [0, 1]$, we compute

By monotonicity of $\omega_i$ we have

Taking the absolute values we get

Let now $K_1>0$ be such that $\sum_{j}{\left|{\Delta^\ell_{\beta, j}}\right|}\leq K_1 \text{ for } \beta = 1, \ldots, M$, $\ell = 0, \ldots, n$. Taking the absolute values and rearranging the indexes, we have

where $\mathcal{H} = {\left\|{{ \boldsymbol{\rho}}}\right\|}_\infty\, v_M^{\max} W_0 M\left(6 M J_0 {\left\|{{ \boldsymbol{\rho}}}\right\|}_\infty{\left\|{\psi"}\right\|}_\infty +{\left\|{\psi'}\right\|}_\infty\right).$ Therefore, by (12) we get

with $\mathcal{G} = \, v_M^{\max} {\left\|{\psi'}\right\|}_\infty W_0 M {\left\|{{ \boldsymbol{\rho}}}\right\|}_\infty.$ We thus obtain

that we can rewrite as

since $\mathcal{H}\geq \mathcal{G}$ and it is not restrictive to assume $K_1 \geq 1$. Therefore, we have that $\mathinner{{\rm{TV}}}(\rho_i^{\Delta x})\leq K_1$ for

where the maximum is attained for some $K_1 < e \left( \mathinner{{\rm{TV}}}(\rho^0_i)+1\right) -1$ such that

Therefore the total variation is uniformly bounded for

Iterating the procedure, at time $t^m$, $m\geq 1$ we set $K_1 = e^{m } \left( \mathinner{{\rm{TV}}}(\rho^0_i)+1\right)-1$ and we get that the solution is bounded by $K_1$ until $t^{m+1}$ such that

Therefore, the approximate solution has bounded total variation for $t\leq T$ with

Corollary 2. Let $\rho_i^0\in \left( \mathbf{BV}\cap{{\mathbf{L}}^\infty }\right)( \mathbb{R}; \mathbb{R}^+)$. If (8) holds, then the approximate solution $\boldsymbol{\rho}^{\Delta x}$ constructed by the algorithm (7) has uniformly bounded total variation on $[0, T]\times \mathbb{R}$, for any $T$ satisfying (16).

Proof. If $T\leq \Delta t,$ then $\mathinner{{\rm{TV}}} (\rho_i^{\Delta x}; [0, T] \times \mathbb{R} )\leq T \mathinner{{\rm{TV}}}(\rho_i^0).$ Let us assume now that $T> \Delta t.$ Let $n_T\in \mathbb{N} \backslash \{0\}$ such that $n_T \Delta t< T \leq (n_T+1) \Delta t$. Then

We then need to bound the term

From the definition of the numerical scheme (7), we obtain

Taking the absolute values and using (12) we obtain

Summing on $j$, we get

which yields

that is bounded by Corollary 1, Lemma 2.2 and Lemma 2.4.

3.   Proof of Theorem 1.2

To complete the proof of the existence of solutions to the problem (1), (5), we follow a Lax-Wendroff type argument as in [5], see also [10], to show that the approximate solutions constructed by scheme (7) converge to a weak solution of (1). By Lemma 2.2, Lemma 2.4 and Corollary 2, we can apply Helly's theorem, stating that for $i = 1, \ldots, M$, there exists a subsequence, still denoted by $\rho_i^{\Delta x}$, which converges to some $\rho_i\in ({{\mathbf{L}}^{\mathbf{1}}}\cap \mathbf{BV})([0, T]\times \mathbb{R}; \mathbb{R}^+)$ in the $\mathbf{L^{{1}}_{loc}}$-norm. Let us fix $i\in\{1, \ldots, M\}.$ Let $\varphi\in\mathbf{C}_c^{{1}}([0, T[\, \times \mathbb{R})$ and multiply (7) by $\varphi(t^n, x_j).$ Summing over $j\in \mathbb{Z}$ and $n\in\{0, \ldots, n_T\}$ we get

Summing by parts we obtain

Multiplying by $\Delta x$ we get

By $\mathbf{L^{{1}}_{loc}}$ convergence of $\rho_i^{\Delta x}\to \rho_i,$ it is straightforward to see that the terms in (23), (24) converge to

as $\Delta x \to 0.$ Concerning the last term (25), we can rewrite

By (12) we get the estimate

Set $R>0$ such that $\varphi(t, x) = 0$ for ${\left|{x}\right|}>R$ and $j_0, \, j_1\in \mathbb{Z}$ such that $-R\in \, ]x_{j_0-\frac{1}{2}}, x_{j_0+\frac{1}{2}}]$ and $R\in\, ]x_{j_1-\frac{1}{2}}, x_{j_1+\frac{1}{2}}],$ then

which goes to zero as $\Delta x \to 0.$

Finally, again by the $\mathbf{L^{{1}}_{loc}}$ convergence of $\rho_i^{\Delta x} \to \rho_i$, we have that

4.   Numerical tests

In this section we perform some numerical simulations to illustrate the behaviour of solutions to (1) for $M = 2$ modeling two different scenarios. In the following, the space mesh is set to $\Delta x = 0.001$.

4.1.   Cars and trucks mixed traffic

In this example, we consider a stretch of road populated by cars and trucks. The space domain is given by the interval $[-2, 3]$ and we impose absorbing conditions at the boundaries, adding $N_1 = \eta_1/\Delta x$ ghost cells for the first population and $N_2 = \eta_2/\Delta x$ for the second one at the right boundary, and just one ghost cell for both populations at the left boundary, where we extend the solution constantly equal to the last value inside the domain. The dynamics is described by the following $2\times 2$ system

with

In this setting, $\rho_1$ represents the density of trucks and $\rho_2$ is the density of cars on the road. Trucks moves at lower maximal speed than cars and have grater view horizon, but of the same order of magnitude. Figure 2 describes the evolution in time of the two population densities, correspondent to the initial configuration

in which a platoon of trucks precedes a group of cars. Due to their higher speed, cars overtake trucks, in accordance with what observed in the local case [4].

4.2.   Impact of connected autonomous vehicles

The aim of this test is to study the possible impact of the presence of Connected Autonomous Vehicles (CAVs) on road traffic performances. Let us consider a circular road modeled by the space interval $[-1, 1]$ with periodic boundary conditions at $x = \pm 1$. In this case, we assume that autonomous and non-autonomous vehicles have the same maximal speed, but the interaction radius of CAVs is two orders of magnitude grater than the one of human-driven cars. Moreover, we assume CAVs have constant convolution kernel, modeling the fact that they have the same degree of accuracy on information about surrounding traffic, independent from the distance. In this case, model (1) reads

with

Above $\rho_1$ represents the density of autonomous vehicles, $\rho_2$ the density of non-autonomous vehicles and $\beta\in [0, 1]$ is the penetration rate of autonomous vehicle. Figure 3 displays the traffic dynamics in the case $\beta = 0.9$.

As a metric of traffic congestion, given a time horizon $T>0$, we consider the two following functionals:

where $\bar x = x_0\approx 0.$ The functional $J$ measures the integral with respect to time of the spatial total variation of the total traffic density, see [6]. The functional $\Psi$ measures the integral with respect to time of the traffic flow at a given point $\bar x$, corresponding to the number of cars that have passed through $\bar x$ in the studied time interval. Figure 4 displays the values of the functionals $J$ and $\Psi$ for different values of $\beta = 0, \; 0.1, \; 0.2, \ldots, \; 1.$ We can notice that the functionals are not monotone and present minimum and maximum values. The traffic evolution patterns corresponding these stationary values are reported in Figure 5, showing the $(t, x)$-plots of the total traffic density $r(t, x)$ corresponding to these values of $\beta$.

Acknowledgments

The authors are grateful to Luis M. Villada for suggesting the non-local multi-class traffic model studied in this paper.

Appendix A.   Lax-Friedrichs numerical scheme

We provide here alternative estimates for (1), based on approximate solutions constructed via the following adapted Lax-Friedrichs scheme:

with

where $\alpha\geq 1$ is the viscosity coefficient and $\lambda = \frac{\Delta t}{\Delta x}.$ The proofs are very similar to those exposed for Godunov approximations.

Lemma A.1. For any $T>0,$ under the CFL conditions

the scheme (33)-(32) is positivity preserving on $[0, T]\times \mathbb{R}.$

Lemma A.2. (${{\mathbf{L}}^\infty }$-bound) If $\rho_{i, j}^0\geq 0$ for all $j\in \mathbb{Z}$ and $i = 1, ..., M$, and the CFL conditions (34)- (35) hold, the approximate solution $\boldsymbol{\rho}^{\Delta x}$ constructed by the algorithm (33)- (32) is uniformly bounded on $[0, T]\times \mathbb{R}$ for any $T$ such that

Lemma A.3. ($\mathbf{BV}$ estimates) Let $\rho_{i}^0\in \left( \mathbf{BV}\cap{{\mathbf{L}}^\infty }\right)( \mathbb{R}, \mathbb{R}^+)$ for all $i = 1, ..., M$. If (35) holds and

then the solution constructed by the algorithm (33)-(32) has uniformly bounded total variation for any $T$ such that

where $\mathcal{D} = {\left\|{{ \boldsymbol{\rho}}}\right\|}_\infty\, \, v_M^{\max} W_0 M\left(3M J_0 {\left\|{{ \boldsymbol{\rho}}}\right\|}_\infty{\left\|{\psi"}\right\|}_\infty +2{\left\|{\psi'}\right\|}_\infty\right)$.