# Navigation system based routing strategies in traffic flows on networks

Adriano Festa, Paola Goatin, Fabio Vicini

► To cite this version:

Adriano Festa, Paola Goatin, Fabio Vicini. Navigation system based routing strategies in traffic flows on networks. Journal of Optimization Theory and Applications, 2023, 198 (3), pp.930-957. 10.1007/s10957-023-02250-z. hal-03712945v2

HAL Id: hal-03712945

https://hal.science/hal-03712945v2

Submitted on 16 Mar 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Navigation system based routing strategies in traffic flows on networks

Adriano Festa · Paola Goatin · Fabio Vicini

Received: date / Accepted: date

**Abstract** Navigation choices play an important role in modeling and forecasting traffic flows on road networks. We introduce a macroscopic differential model coupling a conservation law with a Hamilton-Jacobi equation to respectively model the nonlinear transportation process and the strategic choices of users. Furthermore, the model is adapted to the multi-population case, where every population differs in the level of traffic information about the system.

**Keywords** Traffic flows · Controlled systems · Macroscopic models · Road Networks

**Mathematics Subject Classification (2000)** 90B20 · 93C95 · 94C60

## 1 Introduction

The use of on-line routing systems in vehicular motion has constantly grown in popularity in the last years. At the same time, its effectiveness in solving mobility problems in big cities is controversial [17, 6, 28]. In this work, we describe a model for traffic flows on networks of roads where a nonlinear equation representing the macroscopic density of vehicles is coupled to a Hamilton-Jacobi

Adriano Festa
Politecnico di Torino
Torino, Italy
adriano.festa@polito.it

Paola Goatin
Université Côte d'Azur, Inria, CNRS, LJAD
Sophia Antipolis, France
paola.goatin@inria.fr

Fabio Vicini
Politecnico di Torino
Torino, Italy
fabio.vicini@polito.it
equation, modeling the strategic choices of agents. The model is a further development of what have been introduced in [16], including the possibility of real-time forecast of the future traffic states of the system.

Vehicle traffic models which, like ours, describe a flow of “intelligent” cars on a road network are not largely treated in literature: in the survey [5], most of the models describe a hierarchical control framework with the objective of maximizing the overall network efficiency. Our approach is different: similarly to [12], we account for “selfish” agents, which are interested in minimizing their travel cost to destination accordingly to their knowledge of the environment. This kind of interaction creates some non-trivial effects as a consequence of a competitive equilibrium between the individuals.

In this article, after a detailed description of the model, we show some tests illustrating its main features. In particular, we are able to correctly reproduce the so-called “Braess’ paradox” [7,11], and to mitigate it with an efficient routing through the network. The model is also used to show the interaction between various populations of drivers, with a different level of information about the traffic system. In this case, the proposed model, in addition to replicate some more realistic scenarios, is able to simulate some non trivial effects, as the beneficial impact of traffic information even on non-informed users and the equilibrium between routing strategies among the users.

## 1.1 Coupling Fluxes with Strategies: Hughes’ Model for Pedestrians

The framework that we are going to present takes inspiration from a model for pedestrian flows [20]. It consists in the following quasi-stationary system of partial differential equations (PDEs)

$$ \partial_t \rho - \operatorname{div}_x \left( \rho v(\rho) \frac{\nabla u}{|\nabla u|} \right) = 0, \quad x \in \Omega, \quad (1a) $$

$$ |\nabla u| = \frac{1}{v(\rho)}, \quad (1b) $$

where $\Omega$ is a bounded domain of $\mathbb{R}^n$ and $\rho = \rho(x, t)$ is a density field representing the concentration of the pedestrian at $(x, t)$. The flux term $\rho v(\rho)$ is generally used to display the fundamental diagram of traffic flow (see [19], Section 3.1.2), and it establishes a relation between the density of the crowd and its local flux. A common choice for the speed function is $v(\rho) = v_{max}(1 - \rho)$ where the term $v_{max}$ is the maximal speed at which an agent would travel in ideal environmental conditions. We recall that to avoid meaningless behaviors, $\rho \in [0, 1[$.

We give a brief modeling interpretation of (1): the density $\rho$ moves in direction $-\nabla u$ (1a) which is the optimal control of the associated eikonal equation (1b). If the cost $1/v(\rho)$ is bounded, i.e. if $\rho[t] := \rho(\cdot, t) < 1$, the solution of the eikonal equation at time $t$ is the value function of a minimal time problem and it is given by $u[t](x) = \inf\{d[t](x, y) : y \in \partial\Omega\}$, where the distance function $d[t] : \Omega \times \Omega \to \mathbb{R}^+$ is defined as follows:
$$d[t](x, y) = \inf \left\{ \int_{0}^{S} \frac{1}{v(\rho[t](\xi(s)))} ds : S > 0, \xi \in \Gamma_{x,y}^{S} \right\},$$

with $\Gamma_{x,y}^S$ the set of the absolute continuous curves in $\Omega$ such that $\xi(0) = y$, $\xi(S) = x$ and $|\dot{\xi}(s)| = 1$ a.e. in $[0, S]$.

The term $1/v(\rho)$ can be interpreted as the running cost associated to the curve $\xi(s)$ while the solution $u$ of (1) selects the curves which minimize the integral above. Hence, people are directed towards the boundary trying to avoid crowded regions. It is important to remark as for system (1) (partial) existence results available are in dimension one [1,3] or in presence of a non-zero diffusion term [24].

The adaptation of the principles above to traffic flows must take into consideration the differences between pedestrian and vehicle flows. First of all, vehicles are constrained on road networks with an orientation and any possible strategic choice may happen only at intersections. Secondly, the interactions at such junction points lead us to several modeling choices that we are going to discuss in the following.

## 2 Multi-class Traffic Flow Models on Networks

We recall the general framework describing the flow of different classes of users on a road network. Each class density $\rho^c$, $c = 1, \dots, N_c$, is characterized by specific, possibly time-dependent, route choices at junctions, depending on its degree of information about the network, which will be detailed in Section 3.

**Definition 2.1** An oriented network $\mathcal{N} = (\mathcal{I}, \mathcal{J})$ is a finite collection of points $\mathcal{J} := \{J_k\}_{k \in \mathcal{K}}$ in $\mathbb{R}^2$ connected by continuous, non self-intersecting edges $\mathcal{I} := \{I_\ell\}_{\ell \in \mathcal{I}}$, where $\mathcal{L} := \{1, \dots, N\}$ and $\mathcal{K} := \{1, \dots, M\}$. Each edge $I_\ell \in \mathcal{I}$ is parametrized by a smooth function $\pi_\ell: [0, L_\ell] \to \mathbb{R}^2$, $L_\ell > 0$, which implicitly provides the orientation of the edge.

Given $J_k \in \mathcal{J}$, $\text{Inc}(J_k) := \{i \in \mathcal{L}: J_k \in I_i, \pi_i(L_i) = J_k\}$ denotes the set of edges arriving at $J_k$. Similarly, $\text{Out}(J_k) := \{j \in \mathcal{L}: J_k \in I_j, \pi_j(0) = J_k\}$ denotes the set of edges leaving $J_k$. We define a subset $\mathcal{T} \subset \mathcal{J}$ of destination vertexes. We require that $\mathcal{T} \neq \emptyset$, i.e. the set $\mathcal{T}$ contains at least one element. For any function $f: \mathcal{I} \to \mathbb{R}$, $f_\ell: [0, L_\ell] \to \mathbb{R}$ is the restriction of $f$ to $I_\ell$, i.e. $f(x) = f_\ell(y)$ for $x \in I_\ell$, $y = \pi_\ell^{-1}(x)$.

Each class, density $\rho^c: ]0, L_\ell[ \times [0, T] \to [0, 1]$ evolves on each road $I_\ell$ according to the mass conservation equation

$$\partial_t \rho_{\ell}^{c} + \partial_{x} (\rho_{\ell}^{c} v_{\ell}(\rho_{\ell})) = 0, \quad t \ge 0, x \in ]0, L_{\ell}], \quad (2)$$

where $\rho_\ell(x, t) := \sum_{c=1}^{N_c} \rho_\ell^c(x, t)$ is the total traffic density on the road $I_\ell$. We notice that, summing up the equations (2) for $c = 1, \dots, N_c$, we obtain the classical LWR model

$$\partial_t \rho_\ell + \partial_x (\rho_\ell v_\ell(\rho_\ell)) = 0, \quad t \ge 0, x \in ]0, L_\ell], \quad (3)$$
ensuring that the total number of vehicles is also conserved.

In (2) and (3), the speed function $v_\ell: [0, 1] \to [0, V_\ell]$ is a non-increasing function such that $v_\ell(0) = V_\ell$ and $v_\ell(1) = 0$, where, without loss of generality, we have normalized to 1 the maximal traffic density on each road. Moreover, we assume that there exists a unique point $\hat{\rho}_\ell \in ]0, 1[$ such that the flux function $\rho \mapsto \rho v_\ell(\rho)$ is increasing for $\rho \in [0, \hat{\rho}_\ell[$ and decreasing for $\rho \in ]\hat{\rho}_\ell, 1]$. We set $\gamma_\ell^{\max} := \hat{\rho}_\ell v_\ell(\hat{\rho}_\ell) = \max_{\rho \in I_\ell} \rho v_\ell(\rho)$ the maximal flux allowed on the road $I_\ell$.

Solutions of (2) are intended in the following weak sense:

**Definition 2.2** A function $\rho_\ell = (\rho_\ell^1, \dots, \rho_\ell^{N_c}) \in C([0, +\infty[; \mathbf{L}_{\text{loc}}^1([0, L_\ell[; [0, 1]^{N_c}))$ is an entropy-admissible solution to (2) if for every $\varphi \in C_c^1([0, +\infty[\times]0, L_\ell[; \mathbb{R}^{N_c})$ it holds

$$ \int_0^{+\infty} \int_0^{L_\ell} (\rho_\ell \partial_t \varphi + \rho_\ell v_\ell(\rho_\ell) \partial_x \varphi) \, dxdt = 0, $$

and for every $\kappa \in \mathbb{R}$ end every $\psi \in C_c^1([0, +\infty[\times]0, L_\ell[; \mathbb{R}_+)$ it holds

$$ \int_0^{+\infty} \int_0^{L_\ell} (|\rho_\ell - \kappa|\partial_t \psi + \operatorname{sgn}(\rho_\ell - \kappa)(\rho_\ell v_\ell(\rho_\ell) - \kappa v_\ell(\kappa))\partial_x \psi) \, dxdt \geq 0. $$

Moreover, given any junction $J_k \in \mathcal{J}$, we have the following

**Definition 2.3** A collection of functions $\rho_\ell \in C([0, +\infty[; \mathbf{L}_{\text{loc}}^1([0, L_\ell[; [0, 1]^{N_c}))$, $\ell \in \text{Inc}(J_k) \cup \text{Out}(J_k)$, is a weak solution at $J_k$ if

1. for every $\ell \in \text{Inc}(J_k) \cup \text{Out}(J_k)$, $\rho_\ell$ is an entropy admissible solution to (2);

2. for every $\ell \in \text{Inc}(J_k) \cup \text{Out}(J_k)$ and a.e. $t > 0$, the function $\rho_\ell(t, \cdot)$ has bounded total variation;

3. for a.e. $t > 0$ it holds

$$ \sum_{\ell \in \text{Inc}(J_k)} \rho_\ell^c(t, 0^-) v_\ell(\rho_\ell(t, 0^-)) = \sum_{\ell \in \text{Out}(J_k)} \rho_\ell^c(t, 0^+) v_\ell(\rho_\ell(t, 0^+)), $$

for $c = 1, \dots, N_c$, where the existence of the traces at $J_k$ is guaranteed by 2.

## 2.1 Junction Conditions

Let us now focus on the dynamics at junctions. In this section, we describe what happens at a generic junction $J_k$: let us denote by $I_i$, $i = 1, \dots, n$, the incoming roads and by $I_j$, $j = n + 1, \dots, n + m$, the outgoing ones. The Riemann problem the junction J is a Cauchy problem with constant initial data on each incoming and outgoing road:

$$ \left\{ \begin{array}{l} \partial_t \rho_\ell + \partial_x (\rho_\ell v_\ell(\rho_\ell)) = 0, \\ \rho_\ell(0, \cdot) = \rho_{0,\ell} \in [0, 1], \end{array} \right. \quad \ell \in \{1, \dots, n+m\}. $$
Given any distribution matrix belonging to the set

$$ \mathcal{A} := \left\{ A = \{a_{ji}\}_{\substack{i=1,\dots,n \\ j=n+1,\dots,n+m}} : \quad 0 \le a_{ji} \le 1 \quad \forall i,j, \quad \sum_{j=n+1}^{n+m} a_{ji} = 1 \quad \forall i \right\}, \quad (4) $$

we define a generic Riemann solver at J as follows.

**Definition 2.4** A Riemann solver $RS_A$ is a function

$$ \mathcal{RS}_A: \quad [0,1]^{n+m} \quad \rightarrow \quad \prod_{\ell=1}^{n+m} [0, \gamma_{\ell}^{\max}] \\ (\rho_1, \dots, \rho_{n+m}) \quad \rightarrow \quad (\bar{\gamma}_1, \dots, \bar{\gamma}_{n+m}) $$

where $(\bar{\gamma}_1, \dots, \bar{\gamma}_{n+m}) := (\bar{\rho}_1 v_1(\bar{\rho}_1), \dots, \bar{\rho}_{n+m} v_{n+m}(\bar{\rho}_{n+m}))$ and such that

1. $(\bar{\gamma}_{n+1}, \dots, \bar{\gamma}_{n+m})^T = A \cdot (\bar{\gamma}_1, \dots, \bar{\gamma}_n)^T$;

2. for every $i = 1, \dots, n$, the classical Riemann problem

$$ \left\{ \begin{array}{l} \partial_t \rho + \partial_x (\rho v_i(\rho)) = 0, \quad t > 0, x \in \mathbb{R}, \\ \rho(0, \cdot) = \begin{cases} \rho_{0,i} & x < 0, \\ \bar{\rho}_i & x > 0, \end{cases} \end{array} \right. $$

is solved with waves with negative speed;

3. for every $j = n+1, \dots, n+m$, the classical Riemann problem

$$ \left\{ \begin{array}{l} \partial_t \rho + \partial_x (\rho v_j(\rho)) = 0, \quad t > 0, x \in \mathbb{R}, \\ \rho(0, \cdot) = \begin{cases} \bar{\rho}_j & x < 0, \\ \rho_{0,j} & x > 0, \end{cases} \end{array} \right. $$

is solved with waves with positive speed.

Moreover, we require that $RS_A$ satisfy the consistency condition

$$ \mathcal{RS}_A(\bar{\rho}_1, \dots, \bar{\rho}_{n+m}) = (\bar{\gamma}_1, \dots, \bar{\gamma}_{n+m}). $$

**Remark 2.1** Condition 1 together with the properties (4) of the distribution matrix A ensure the mass conservation through the junction

$$ \sum_{i=1}^{n} \bar{\gamma}_i = \sum_{j=n+1}^{n+m} \bar{\gamma}_j. $$

We refer to the monograph [18] for further details on Riemann solvers at junctions. In the present work, we will use the Priority Riemann Solver introduced in [13], which can handle an arbitrary number of incoming and outgoing roads, accounting for priorities among the incoming roads and maximizing the flux through the junction (a brief but detailed description of this solver is included in the Appendix A). Anyhow, the framework presented here can be applied to any generic Riemann solver with different aims like e.g., minimizing the waiting time of the vehicles queuing, modeling intersection devices as traffic lights or roundabout, etc.
Junction conditions in the multi-class cases. To extend the above approach to a multi-class framework, we generalize the multi-commodity junction solver discussed in [26] to any underlying Riemann solver $RS_A$ satisfying Definition 2.4. In particular, this allows to consider junctions with any number of incoming and outgoing roads.

We follow the procedure below:

1. **Compose the total distribution matrix.** Let the distribution matrices $A^c = \{a_{ji}^c\}_{i,j} \in \mathcal{A}$ at J be given for each class $\rho^c, c = 1, \dots, N_c$ (these coefficients will be derived in Section 3). We set

$$A := \{a_{ji}\}, \quad \text{where} \quad a_{ji} := \sum_{c=1}^{N_c} a_{ji}^c \frac{\rho_i^c}{\rho_i} \qquad (5)$$

defines a weighted distribution coefficients for the total density of the populations at the junction.

2. **Compute the fluxes.** Using the selected Riemann solver $RS_A$ corresponding to (5), we obtain the total outgoing fluxes $(\bar{\gamma}_1, \dots, \bar{\gamma}_{n+m})$.

3. **Distribute the fluxes among the various classes.** The incoming and outgoing fluxes for each class $c = 1, \dots, N_c$ are given by

$$\bar{\gamma}_i^c = \frac{\rho_i^c}{\rho_i}, \quad i = 1, \dots, n, \quad \bar{\gamma}_j^c = \sum_{i=1}^{n} a_{ji}^c \bar{\gamma}_i^c, \quad j = n+1, \dots, n+m.$$

In the rest of the article, the operators $\mathcal{A}$, $\mathcal{A}$ and $a_{j,i}$, will be noted as $\mathcal{A}^k$, $\mathcal{A}^k$ and $a_{j,i}^k$ since referred to the junction $J_k$.

## 3 Strategy Modeling on the Network

To model the route choice strategy of the vehicles belonging to a specific class, we use a potential (given by the solution of a Hamilton-Jacobi (HJ) equation), which is the value function of an optimal control problem defined on the network. We distinguish between the static case (only the current configuration of the system concurs to the choice) and dynamic (the future evolution of the system shapes the strategic choice). The theory of viscosity solutions for HJ equations on networks have been introduced in recent years, imposing appropriate transition conditions at the vertices (we refer to [8, 27, 10] for details). The case of the directed graph – where the arcs can be traveled only in one direction – can be considered a sub-case of the general one.

**Static case.** In the static case, at any $\tilde{t} \in [0, T]$ we compute the potential function $u$ knowing the current traffic state $\rho(\cdot, \tilde{t})$, that is, for each $c = 1, \dots, N_c$, the viscosity solution $u_{\tilde{t}}^c[\tilde{t}](x)$ of the problem

$$\left\{
\begin{array}{l}
\displaystyle \partial_x u_{\tilde{t}}^c(x) + \frac{1}{g^c(\rho_{\tilde{t}}(x, \tilde{t}))} = 0 \quad x \in I_{\tilde{t}}, \quad \tilde{t} \in \mathcal{L}, \\
\displaystyle \min_{\tilde{t} \in O_{\text{out}}(J_k)} u_{\tilde{t}}^c(0) = u_{\tilde{t}}^c(L_l) \quad J_k \in \mathcal{J} \setminus \mathcal{T}, \quad l \in \text{Inc}(J_k), \\
\displaystyle u_{\tilde{t}}^c(x) = 0, \quad \pi_{\tilde{t}}(L_{\tilde{t}}) = x \in \mathcal{T},
\end{array}
\right.
\qquad (6)$$
which represents the weighted distance from the position $x$ to the target set $\mathcal{T}$, minimizing the running cost $g^c: [0,1] \to \mathbb{R}^+$, which we assume to be a Lipschitz continuous function. The function $g^c$ models the influence of the traffic density (at a fixed time $\tilde{t}$) for the class of vehicles $c$ in the choice of the “shortest” path.

To compute the solutions of (6), we denote by $\Gamma_{x,z}$ the set of absolute continuous curves connecting $x$ to $z$ identified by a finite sequence $\ell_n \in \mathcal{L}$, $n = 0, ..., N_{\Gamma}$, such that there exists a $\xi \in [0, L_{\ell_0}]$ such that $\pi_{\ell_0}(\xi) = x$, $\pi_{\ell_i}(0) = \pi_{\ell_{i-1}}(L_{\ell_{i-1}})$, $i = 1, ..., N_{\Gamma}$, $\pi_{\ell_{N_{\Gamma}}}(L_{\ell_{N_{\Gamma}}}) = z$. Then the solution of (6) is given by

$$u_{\ell}^{c}(x) = \inf\{d_{c}(\pi_{\ell}(\xi), z) : z \in \mathcal{T}\},$$

where the (scaled) distance function $d_c: \mathcal{I} \times \mathcal{I} \to \mathbb{R}^+$ is

$$d_c(x, z) := \inf_{(\ell_0, \dots, \ell_{N_{\Gamma}}) \in \Gamma_{x,z}} \left\{ \int_{\xi}^{L_{\ell_0}} \frac{1}{g^c(\rho_{\ell}(\pi_{\ell}(s), \tilde{t}))} ds + \sum_{i=1}^{N_{\Gamma}} \int_{0}^{L_{\ell_i}} \frac{1}{g^c(\rho_{\ell_i}(\pi_{\ell_i}(s), \tilde{t}))} ds \right\}.$$

We observe that, in general, equation (6) could be not defined on some arcs, since a minimal path (i.e., an itinerary to reach a destination vertex in an optimal way) could be not defined in some areas of the network. To overcome this problem, we make the following hypothesis:

**H1)** For every $x \in \mathcal{I}$ there exists at least one $z \in \mathcal{T}$ such that the set $\Gamma_{z,x} \neq \emptyset$, i.e. there exists a sequence of indexes $\ell_0, ..., \ell_{N_{\Gamma}}$ such that $x \in I_{\ell_0}$, and $\pi_{\ell_{i-1}}(L_{\ell_{i-1}}) = \pi_{\ell_i}(0)$ for $i = 1, ..., N_{\Gamma}$ with $\pi_{\ell_{N_{\Gamma}}}(L_{\ell_{N_{\Gamma}}}) = z \in \mathcal{T}$.

**Dynamic case.** In the dynamic case we assume to know the traffic configuration at any $(t, x) \in [0, T] \times \mathcal{J}$. The potential function is computed backward in time starting from the solution of (6) at time $t = T$ as viscosity solution of

$$\left\{ \begin{array}{ll} -\partial_t u_{\ell}^c(t, x) + \partial_x u_{\ell}^c(t, x) + \frac{1}{g^c(\rho_{\ell}(t, x))} = 0, & x \in I_{\ell}, \ell \in \mathcal{L}, \\ \min_{\ell \in \text{Out}(J_k)} u_{\ell}^c(t, 0) = u_{\ell}^c(t, L_k), & J_k \in \mathcal{J} \setminus \mathcal{T}, l \in \text{Inc}(J_k), \\ u_{\ell}^c(T, x) = u_{\ell}^c(x), & x \in I_{\ell}, \ell \in \mathcal{L}, \end{array} \right. \quad (7)$$

for each $c = 1, ..., N_c$.

We can characterise the solution of the equation above as minimum path in a time dependent framework as value function of a backward-in-time finite horizon optimal control problem [22]. The solution of (7) is given by

$$u_{\ell}^{c}(t, x) = \inf\{d_{c}(\pi_{\ell}(\xi), z, t) : z \in \mathcal{T}\},$$
where to define the distance function $d_c : \mathcal{I} \times \mathcal{I} \times [t, T] \to \mathbb{R}^+$, we consider all the paths $\Gamma_{x,z}$ connecting $z$ to $x$ in the time interval $[t, T]$. We can parameterise such curves as $(\ell(s), \zeta(s), s)$ with $s \in [t, T]$ getting that

$$d_c(x, z, t) = \inf_{\ell \in \Gamma_{x,z}} \left\{ \int_t^T \frac{1}{g^c(\rho_{\ell(s)}(\pi_{\ell}(s), s))} ds + u_{\ell(T)}^c(\zeta(T)) \right\}.$$

We underline that at time $T$, if the agent does not reach a destination point belonging to $\mathcal{T}$, he pays the scaled distance from $\mathcal{T}$ as computed in the static case.

**Remark 3.1** There are two natural choices for the function $g$: in the case we fix $g(x, \rho) \equiv 1$, the drivers will look for the shortest path to destination regardless of the traffic conditions. This is equivalent to follow a fixed path (highlighted by road sign indications or off-line navigation systems), without any information about the traffic state. If $g(x, \rho) = v(\rho)$, agents aim to minimize the travel time to destination over its current speed selecting the fastest path to destination (e.g. using an on-line navigation system). The difference between the static and the dynamic model is that while in the static case drivers use only the information on the current traffic conditions, in the dynamic one they can forecast the traffic evolution and select the real fastest path to destination.

## 3.1 Strategy Coupling at Junctions and Equilibria

The solution of (6), respectively (7), contains information about the optimal strategy to reach the target set $\mathcal{T}$, depending on the perceived cost $g^c$. Since the arcs are oriented, route choices are possible only at junctions. In particular, this allows to define the matrix distribution coefficients in (5), coupling the density to the potential equation.

The choice of how to assign the route choices is, by any meaning, non trivial. The most basic choice is, in a Wardrop equilibrium fashion, to equally distribute the population on the roads with equal minimal potential functions. More precisely, for each junction $J_k$, calling $\bar{u}(t) = \min_{j \in Out(J_k)} u_j^c(t, 0)$, we define the distribution matrix $A_k$ of the population $c$ at $J_k$ as

$$a_{ji}^c = \frac{\psi(u_j^c(t, 0) - \bar{u}(t))}{\sum_{z \in Out(J_k)} \psi(u_z^c(t, 0) - \bar{u}(t))}.$$

A natural choice for the activation function $\psi$ is $\bar{\psi}(x) := 1$ for $x \le 0$ and $\bar{\psi}(x) := 0$ otherwise. In other words, we dynamically distribute the density along the optimal options at any junction. In particular, this was the choice made in [16].

Unfortunately, this choice is numerically non-convenient: in particular, it produces some unrealistic chattering phenomena between two (or more) equivalent paths which may make difficult finding the equilibrium states of the system. This effect may be reduced using a smooth activation function, at the
price of not computing the real equilibrium states, but an approximation of them. In particular, one option is taking $\hat{\psi}(x) = 1/(1 + e^{-\epsilon(S-2x)})$, where $S = \sum_{j \in Out(J_k)} u_j^c(t, 0)$ and $\epsilon > 0$, i.e. the logistic or soft step function centered in $S/2$. This option has the advantage of computing $\sum_{j \in Out(J_k)} a_{ji}^c = 1$ (which is mandatory to have conservation of mass through the junction) but also $\psi(S/2) = 1/2$, i.e. if two roads are equally favourable the distribution matrix splits between the two. The logistic function has been used in many different application, in particular as standard activation function in computer science [2].

Finally, we can describe the whole model for one population, here reported in the dynamic case:

$$
\left\{
\begin{array}{ll}
\partial_t \rho_\ell(t, x) + \partial_x (\rho_\ell(t, x)v_\ell(\rho_\ell(t, x))) = 0, & t > 0, x \in I_\ell, \ell \in \mathcal{L}, \\
-\partial_t u_\ell(t, x) + \partial_x u_\ell(x, t) + \frac{1}{g(\rho_\ell(t, x))} = 0, & x \in I_\ell, \ell \in \mathcal{L}, \\
\min_{\ell \in Out(J_k)} u_\ell(0) = u_l(L_l), & J_k \in \mathcal{J} \setminus \mathcal{T}, l \in Inc(J_k), \\
A_k = \{a_{ji}\}, \quad \bar{u}(t) = \min_{j \in Out(J_k)} u_j(t, 0), \\
a_{ji} = \frac{\psi(u_j(0) - \bar{u})}{\sum_{z \in Out(J_k)} \psi(u_z(0) - \bar{u})}, & x \in J_k, \\
(\tilde{\gamma}_1, \dots, \tilde{\gamma}_{n+m}) = \mathcal{R}S_{A_k}(\rho_1, \dots, \rho_{n+m}), & x \in J_k, \\
\rho_\ell(x, 0) = \rho_{0,\ell}(x), & x \in I_\ell, \ell \in \mathcal{L}, \\
\rho_\ell(x, t) = 0, & x \in \mathcal{T} \cap I_\ell, \ell \in \mathcal{L}, \\
u_\ell(T, x) = u_\ell(x), & x \in I_\ell, \ell \in \mathcal{L}, \\
\rho_\ell(\pi_\ell(0), t) = \phi_\ell(t), & \ell \in \mathcal{L} \cap \mathcal{S},
\end{array}
\right.
\tag{8}
$$

where $\rho_{0,\ell}$ and $u_\ell(x)$ are the initial/final conditions and the functions $\phi_\ell(t)$
are the inflow conditions at the 'source' vertexes $S$ of the network.

3.2 Evaluating the Efficiency

For a deeper understanding of the model, we need to recall some basic concepts
about the general efficiency evaluation of a macroscopic traffic system. To this
end, we establish a link between the macroscopic model and its microscopic
counterpart. The main concepts of this section have been borrowed from [11]
and adapted to our case.

**Definition 3.1 (Travel time)** We define the travel time between two points $y_1, y_2 \in \mathcal{I}_\ell$ where $y_1 \in \mathcal{J}$ (i.e. $y_1, y_2$ are on a same edge, with $y_1$ which is the node at the beginning of the edge) as the function $\tau_{y_1,y_2}(a_\ell)$ defined implicitly by $\xi(\tau(a_\ell)) = y_2$ where
$$ \xi \text{ solves } \begin{cases} \dot{\xi} = v_{\ell}(\rho(t, \xi(t))), \\ \xi(0) = y_1, \end{cases} \quad \text{and } \rho \text{ solves } \begin{cases} \rho_t + \partial_x(\rho v_{\ell}(\rho)) = 0, \\ \rho(t, y_1)v_{\ell}(\rho(t, y_1)) = a_{\ell}\gamma, \end{cases} $$

where $\gamma$ is the total flux on the junction $J_k \in \mathcal{J}$ and $a_\ell \in [0, 1]$ is the percentage (i.e. the coefficient of the distribution matrix $a_\ell \in A_k$) entering in $\mathcal{I}_\ell$.

If $y_1$ is an internal point of $\mathcal{I}_\ell$, the definition still holds with the trivial value $a_\ell = 1$ (all the flux remains on the same road), while in the case of two points belonging to different edges connected by a route $\Gamma_{y_1,y_2}$ composed by a finite sequence of edges $\ell_n$, with $n = 0, \dots, N_\Gamma$, we proceed setting $\hat{a} = (a_1, \dots, a_{N_\Gamma})$ corresponding to the distribution matrices coefficients related to this specific path. We underline that a sequence $\hat{a}$ identify a unique path. Therefore, the travel time in this case is

$$ \tau_{y_1,y_2}(\hat{a}) := \tau_{y_1,\pi_{\ell_n}(L_{\ell_0})}(1) + \sum_{n=1}^{N_\Gamma-1} \tau_{\pi_{\ell_n}(0),\pi_{\ell_n}(L_{\ell_n})}(a_n) + \tau_{\pi_{\ell_{N_\Gamma}}(0),y_2}(a_{N_\Gamma}). $$

Finally, we call relevant travel time the function $\tau_{y_1,y_2}(\hat{a})$ for $\hat{a}$ such that $a_i \neq 0$ for $i = 1, \dots, N_\Gamma$, i.e., excluding the paths which are not taken by any of the agents.

**Definition 3.2 (Equilibrium State)** We call state of the system a choice of all the distribution matrices $\bar{A} = \{\bar{A}_k\}_{k \in \mathcal{K}} \in \mathcal{A}^m$ at the network junctions.

A state $\bar{A}$ is an equilibrium state for a destination $\mathcal{T}$ iff for every $x \in \mathcal{I}$ and $y \in \mathcal{T}$, all the relevant travel times for every path choice $\Gamma_{x,y}$ coincide, i.e. for two paths $\bar{\Gamma}_{x,y}$, $\hat{\Gamma}_{x,y}$, the relative sequences of non null coefficients $(\bar{a}_1, \dots, \bar{a}_{N_\Gamma}) \neq (\hat{a}_1, \dots, \hat{a}_{N_\Gamma})$ sampled from the same state $\bar{A}$ give

$$ \tau_{x,y}((\bar{a}_1, \dots, \bar{a}_{N_\Gamma})) = \tau_{x,y}((\hat{a}_1, \dots, \hat{a}_{N_\Gamma})). $$

## 4 A multi-Class, Multi-Informed Traffic Flow Model and Numerical Tests

In this section, we present the full model and we perform some tests to show the main features of it. The details about the numerical implementation are deferred to the Appendix B.

One aim of our study is the capability of accounting for different levels of information in an heterogeneous population of agents. Indeed, the previous setting can be generalized to several classes of agents moving on the network following the same LWR-based dynamics. Moreover, with a straightforward generalization, each class may also have a different target set $\mathcal{T}^c$. Since for simplicity and to avoid computational burden we do not explore this possibility, we assume that the classes have the same target $\mathcal{T}$, but different strategic approaches.

Let $c = 1, \dots, N_c$, and $t \in [0, T]$. The multi-class version of (8) reads:
$$
\left\{
\begin{array}{ll}
\partial_t \rho_{\ell}^c(t, x) + \partial_x (\rho_{\ell}^c(t, x) v_{\ell}^c(\sum_c \rho_{\ell}^c(t, x))) = 0, & t > 0, x \in I_{\ell}, \ell \in \mathcal{L}, \\
-\partial_t u_{\ell}^c(t, x) + \partial_x u_{\ell}^c(x, t) + \frac{1}{g^c(\sum_c \rho_{\ell}^c(t, x))} = 0, & x \in I_{\ell}, \ell \in \mathcal{L}, \\
\min_{\ell \in \text{Out}(J_k)} u_{\ell}^c(0) = u_{\ell}^c(L_k), & J_k \in \mathcal{J} \setminus \mathcal{T}, l \in \text{Inc}(J_k), \\
A_k = \{a_{ji}\}, \quad \bar{u}^c(t) = \min_{j \in \text{Out}(J_k)} u_j^c(t, 0), \\
a_{ji} = \frac{\psi(u_j^c(0) - \bar{u}^c)}{\sum_{z \in \text{Out}(J_k)} \psi(u_z^c(0) - \bar{u}^c)}, & x \in J_k, \\
(\bar{\gamma}_1^c, \dots, \bar{\gamma}_{n+m}^c) = \mathcal{R} \mathcal{S}_{A_k}(\rho_1^c, \dots, \rho_{n+m}^c), & x \in J_k, \\
\rho_{\ell}^c(x, 0) = \rho_{0,\ell}^c(x), & x \in I_{\ell}, \ell \in \mathcal{L}, \\
\rho_{\ell}^c(x, t) = 0, & x \in \mathcal{T} \cap I_{\ell}, \ell \in \mathcal{L}, \\
u_{\ell}^c(T, x) = u_{\ell}^c(x), & x \in I_{\ell}, \ell \in \mathcal{L}, \\
\rho_{\ell}^c(\pi_{\ell}(0), t) = \phi_{\ell}^c(t), & \ell \in \mathcal{L} \cap \mathcal{S},
\end{array}
\right.
\quad (9)
$$

where $\rho_{0,\ell}^c$ and $u_{\ell}^c(x)$ are the initial/final conditions, the functions $\phi_{\ell}^c(t)$ are the inflow conditions at the 'source' vertexes $S$ of the network and the destination vertexes act as absorbing conditions imposed at the boundary (cf. [15]), motivating the choice of setting $\rho^c$ and $u_{\ell}^c$ to zero at these points.

**Remark 4.1 (A 2-population case)** We describe in detail the special case of two populations $\rho^1$ and $\rho^2$ with the same destination set ($\mathcal{T}$), but different level of information, as considered in the simulation Section 4. We fix $v_{\ell}^1(\rho) = v_{\ell}^2(\rho) = 1 - \rho$ and $g^1(x, \rho) = 1$ and $g^2(x, \rho) = 1 - \rho = v_{\ell}^2(\rho)$. In this way, the two populations' route choices – despite the two groups have the same destination – may be different at network junctions. In particular, the above choices of $g^1$ and $g^2$ model the case where the first population does not use any on-line routing device. The knowledge of the network – or the use of maps or off-line routing devices – brings the density $\rho^1$ to follow the shortest path to the destination. On the contrary, $\rho^2$ uses information on the state of the system to avoid congested regions, thus minimizing the time to destination. It is important to keep in mind that, depending on if we compute the function $u^c$ in the static or the dynamic case, we respectively do not include or include forecasting of the future states of the system.

## 4.1 Test 1 - A Simplified Network with One Population

The first test we propose is a toy model involving a simple network consisting of 5 roads and allowing two possible paths connecting the source (node 1) to destination (node 5), see Fig. 1. The two paths are the one passing by the nodes 1-2-4-5 (which has length 3) and the longer one 1-2-3-4-5 (whose length is 3.4).
<figure><img src="image_2.png" /><figcaption>Fig. 1: Simple network with 5 roads and two possible paths to reach destination; origin (green) and destination (red) junctions are differently colored; id (above) and the length (below) of the roads are reported.</figcaption></figure>

We assume that the network is empty at $t = 0$, we consider a single population with constant inflow $\phi(t) = 0.5$ at node 1 for $t \in [0, 6]$ and we set $\phi(x) = 0$ for $t \in ]6, 12]$. The space and time meshes are set to $\Delta x = 0.05$ and $\Delta t = 0.01$, respectively.

If the agents are simply-informed, i.e. $g(x, \rho) = 1$, the whole population follows the path 1-2-4-5, since it is the shortest path to destination.

Despite its simplicity, this test is useful to identify the chattering phenomenon between two options to destination mentioned in the previous section. We can compare, in Figure 2, the effect of a step activation function $\psi = \tilde{\psi}$ (Figures (a) and (b)) with respect to the smooth activation function $\tilde{\psi} = \psi$ with $\epsilon = 1$ (Figures (c) and (d)). As predictable, a smooth activation function prevents any chattering effect and the agents distribute smoothly on the two paths. In the following, where not stately differently, we assume $\psi = \tilde{\psi}$ with $\epsilon = 1$.

In Figure 3, we observe the difference between the simply-informed and the informed case ($g(x, \rho) = 1 - \rho$).

In Fig. 3a (simply informed), the agents choose the shortest path 1-2-4-5 regardless its current occupation. The path 1-2-3-4-5 is taken by a minimal part of the population since we used a smoothed activation function $\psi = \tilde{\psi}$ with $\epsilon = 1$.

In Fig. 3b (informed), the agents know the current state of the system. Therefore, they initially take the more favourable path 1-2-4-5, but later they start using also 1-2-3-4-5.

In particular, as highlighted before in Fig. 2, in absence of a smooth activation function $\psi$, the population starts to fluctuate between the two options when the value functions $u_2(t, 0)$, $u_4(t, 0)$ relative to the two different paths at junction 2 coincide. Using a smoothing activation function, this phenomenon disappears. The distance $|u_2(t, 0) - u_4(t, 0)|$ decreases till an optimal value corresponding to a certain part of the flux opting for the longer path which balances such a difference, see Fig. 5.

In Fig. 3c (highly informed), we solve the potential equation in the dynamic case (7). In this scenario, the agents can forecast the future states of the system to fully optimize their choices. In practice, in this test, the population splits between the two possible paths in a proportion which is globally optimal. The
<figure><img src="image_3.png" /><figcaption>Fig. 2: Different choices of the activation function $\psi$ on a simple informed population for a network with 5 roads (Fig. 1): time evolution of the density $\rho_2(t, 0)$ and $\rho_4(t, 0)$ at the beginning of streets 2 and 4 in the case of the step function $\dot{\psi}$ (Figures (a) and (b)) the agents choosing road 2 (whose incoming density is $\rho_2$) and road 4 (represented by $\rho_4$) switch continuously between the two option of identical value function $u_2$, $u_4$, with some oscillatory effects on the densities. In Fig. (c) and (d), the use of the smooth activation function $\hat{\psi}$ with $\epsilon = 1$.</figcaption></figure>

time to reach destination is equal and minimal for each agent starting from the same point regardless to its routing choices.

Further comparisons between the three situations are reported in Figures 4 and 5. In particular, in Fig. 5, it is possible to see how in the simply informed case the potential functions $u_2(t, 0)$ and $u_4(t, 0)$ relative to the two possible paths to destination are constant in time, while in the informed one, their difference decreases till an optimal value (equal to zero in the case of no smoothing activation function, see Fig. 2b) which is then constant until the incoming flux starts decreasing. In the highly informed case, the relationship is more complex as we highlight in the next test.
<figure><img src="image_4.png" /><figcaption>Fig. 3: Simple network with 5 roads; $\rho$ at $t = 6$ sec is depicted; $\max_{x \in I_\ell} \rho_\ell(x, 6)$ is reported below the streets.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 4: Simple network with 5 roads (Fig. 1): time evolution of the density $\rho_2(t, 0)$ and $\rho_4(t, 0)$ at the beginning of streets 2 and 4.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 5: Simple network with 5 roads (Fig. 1): time evolution of the costs $u_2(t, 0)$ and $u_4(t, 0)$ at the beginning of streets 2 and 4.</figcaption></figure>
## 4.2 Test 2 - Dealing with Braess' Paradox

We reproduce here the well known Braess' paradox, described for the first time in [7] and later reprised and studied by several authors, see e.g. in [25, 11]. The paradox highlights how a selfish (and uninformed) behaviour may worsen the overall traffic flow, so that the opening of a new, more favourable path increases the time to destination for all users. Such phenomenon has indeed been observed in real life situations [4,21].

<figure><img src="image_7.png" /><figcaption>Fig. 6: Braess' paradox network: origin (green) and destination (red) junctions are differently colored; id (above) and the length (below) of the streets are reported; constant speed streets (dashed) are marked.</figcaption></figure>

To reproduce such situation, we consider a 4-street network (composed by 6 nodes and 6 edges) and a 5-street one, where an additional road (edge 7) is open (see Fig. 6). We underline that in these networks, some edges can be travelled with constant speed $v(\rho) := 1$ (edges 1,3,4 and 6), while the others follow the usual density dependent speed law $v(\rho) := 1 - \rho$. From the modelling point of view, the former can be seen as high capacity highways (where the speed is only limited by the current law regulations), and the latter are some low capacity roads, where the traffic density strongly impacts the speed of vehicles. Comparing the two networks, we can observe as, in Fig. 6(a), the two paths to destination passing through nodes 1-2-3-5-6 and 1-2-4-5-6 have the same length. In Fig. 6(b) a new road (edge 7) is available, providing a new, more favourable path to destination 1-2-3-4-5-6, which is very sensitive to traffic congestion, since involving all the edges with non constant speed function.

To evaluate the performances of a single agent on the network, we use the notion of travel time (TT) given in Definition 3.1, adapted to the discrete case, i.e. called $\gamma(x_i, x_j, t) = (x_1 = x_i, ..., x_m = x_j) \in \Gamma_{x_i, x_j}(t)$ a non trivial path chosen by a population to navigate from $x_i$ to $x_j$, starting from $x_i$ at time $t$, where $x_k, k = 1, ..., m$, are the discretization mesh points along the path related to a sequence of non null coefficients ($a_1, ..., a_m$) corresponding to the agent's choices at every junction (if there is no junction at $x_i$ trivially $a_i = 1$)
we have

$$ TT(x_i, x_j, t) = \sum_{\gamma(x_i, x_j, t) \in \Gamma_{x_i, x_j}(t)} \sum_{k=1}^{m} (\Pi_{z=1}^{k} a_z) \frac{\Delta x}{v(\rho(x_k, t_k))}. \quad (10) $$

We stress on the fact that here, every point along a specific path $\gamma(x_i, x_j, t)$ connecting $x_i$ to $x_j$ starting at time $t$ is weighted by $\Pi_{z=1}^{k} a_z$ which estimates the percentage of agents that are using that specific segment of the path.

As before, we take a constant inflow $\phi(t) = 0.5$ at the junction 1 for $t \in [0, 6]$, we set $\phi(t) = 0$ for $t \in ]6, 15]$ and the space and time meshes are set to $\Delta x = 0.05$ and $\Delta t = 0.01$. In Fig. 7, we compare the performances of the two networks in the terms of travel time $TT(1, 6, t)$ for $t \in [0, 12]$, i.e. the time needed by a single vehicle starting node 1 at time $t$ to reach the destination node 6. For all strategic choices, we observe the appearance of the typical Braess' paradox (Fig. 7(a)). The time to destination of an agent starting from node 1 is always higher in the 5 street case (continuous red line) compared to the 4 street case (blue dotted line). Even in all the discharge phase ($t > 6$), the 4 street situation remains more favourable.

The 'paradox' is anyway mitigated if information on the state of the network is available. In the case of an informed population (knowing only the current traffic situation), Fig. 7(b) shows that the travel times in the two scenarios are closer. Anyway, since the agents are not able to forecast the future congestion on the most favourable path chosen in the 5 street network, they still create a consistent congestion in the charging phase, which deteriorates the network performances.

We highlight that the travel time on the 5 road network for the informed users is always lower than the simply informed case, i.e. having some traffic data improves the traffic fluidity. The Braess' paradox is still present in the highly-informed case depicted in Fig. 7(c), even if in a moderate measure with respect to the previous cases. This is due to the presence of the smooth activation function $\psi$: as we can observe again in Fig. 7(c), the 'paradox' tends to disappear with a reduced smoothing ($\epsilon \ge 3$). We can not analyze the limit case of a discontinuous $\psi = \bar{\psi}$, since our algorithm to compute equilibria (based on fixed point iterations) does not reach convergence (due to the oscillations reported also in Fig. 2). Further research on the most favourable choice of the activation function could be interesting in this case.

## 4.3 Test 2 - Two Populations

In real life situations, the presence on the same network of various populations with a different level of information about the route and the traffic state is very common.

Model (9) may efficiently simulate the complex interactions between the different populations to help understanding which is the optimal level of information for better performances on a specific network and how the distribution rate of the different populations affects such performances.
<figure><img src="image_8.png" /><figcaption>Fig. 7: Braess' network (Fig. 6): travel time $TT(1, 6, t)$, $t \in [0, 15]$ for different level of information. Here, the parameter $\epsilon$ of the smooth activation function $\hat{\psi}$ is set with $\epsilon = \{1, 2, 3\}$ and called, respectively, $\psi_1, \psi_2, \psi_3$.</figcaption></figure>

We consider once again the simple 4-roads and 5-roads networks used to illustrate the Braess' paradox, see Fig 6. We compare the behaviour of two populations with a different information level. To get rid of the time dependency for the travel time (10), we compare their mean travel times (MTT) on the interval $[0, T]$ defined as

$$ MTT(x_i, x_j) = \frac{1}{T} \sum_{k=1}^{[T/\Delta t]} TT(x_i, x_j, k\Delta t). $$

To make easier understanding the outcome of the tests, we restrict ourselves to the comparison of simply-informed/informed mixed population and simply-
<figure><img src="image_9.png" /><figcaption>(a) 4 streets; Simply-informed vs In-(b) 4 streets; Simply-informed vs Highly-informed</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>(c) 5 streets; Simply-informed vs In-(d) 5 streets; Simply-informed vs Highly-informed</figcaption></figure>

<caption>Fig. 8: Mean Travel Time comparison in the Braess’ network (as in Fig. 6): MTT (1,6) depending on the populations ratio $P$.</caption>

informed/highly-informed. Once again, we simulate the incoming of a constant flux of vehicles $\phi(t) = 0.5$ for $t = [0, 6]$ and $\phi(t) = 0$ for $t = [6, 15]$. This incoming flux is split between the two populations following the parameter $P \in [0, 1]$, where for $P = 0$ all the population is simply informed and for $P = 1$ all the population is informed. We highlight that, in these tests, in the case of $P = 0$ or $P = 1$ one of the two populations is not present on the network. This does not prevent us to compute the MTT since it depends on the sum of the two populations.

In Fig. 8, we show the comparison on the two networks. Looking at the 4-road network (Figures 8(a) and (b)) we observe that, in this case, both populations have almost the same mean travel times (the difference is less than
0.2%). In the simulations, we may observe the insurgence of some oscillations between the two paths in the case of informed agents, which are not present in the highly-informed case.

In the 5-road network case, the behaviour is different: in this case, the mean travel time of informed and highly-informed agents is always lower, and the situation improves for both populations as the percentage of informed or highly informed agents increases, showing that they act as ‘regulators’ of the system. Moreover, mean travel times are lower when an highly informed population is present, with respect to the merely informed case. We remark also that the 5-road network performances are always worse than corresponding the 4-road network case. This tendency has been already observed in the previous test and it can been mitigated, in the highly-informed case, by the use of a less smooth activation function $\psi$.

## 4.4 Test 3 - A Real Network

In this last test, we present, with only an illustrative purpose, a more realistic scenario, which shows the potential of the model proposed. We consider the road network of the Royal Docks area around the London City Airport, including the Borough of Newham and the east part of the Canary Wharf business area. The network, due to the intensity of the displacements, and the presence of various bottlenecks created by the Thames river meander, is particularly exposed to traffic congestion. The road data has been provided by OpenStreetMap, licensed under the Open Data Commons Open Database License (Fig.9(a)). In this scenario, we compare the network performances in presence of a different level of information of the drivers. For better clarity, we focus on three particular spots (cf. Fig. 9(b)): in Area 1 the road network crosses the Lea River concentrating the traffic flow on two main bridges; in Area 2 the Gallions Roundabout (right/bottom) has even more intense congestion effects; Area 3 is an average sample of the network.

We perform a simulation of the traffic during a peak hour for reaching the Airport (marked with a red dot on Fig. 9), starting from a low traffic initial condition (the density is set to 0.2 on the whole network) and giving a constant null inflow of vehicles $\gamma(t) = 0$ at several nodes (marked in light blue). All the vehicles have as unique target point the parking area of the Airport. The space and time meshes are set to $\Delta x = 2.0$ and $\Delta t = 0.06$, respectively. In Figures 10, 11 and 12, we show the traffic distribution on the three areas of interest at $t = 100, 200, 300$.

The results of the simulation highlight some known and less-known features of the influence of real-time information in the routing process. Surprisingly, we can observe that the traffic congestion, in the more informed models, spread on a larger area, with the effect of a faster release of the jam (cf. Fig. 10 and 12 on the access roads to the bridges (Area 1) and on the Gallions Roundabout (Area 2)). We also notice that traffic information brings traffic congestion also in some roads that are not normally affected by traffic jams in the simply-
<figure><img src="image_11.png" /><figcaption>Fig. 9: The road Network around the London City Airport, London, UK. (left) Three areas of interest (right).</figcaption></figure>

informed case (see e.g. the traffic evolution in Area 3). This has been observed in real life situations and it has been at the center of discussions after the complaints of local residents in several urban areas [17,6].

Concerning the overall efficiency effects on the network, as already speculated by others authors [25], selfish information does not globally reduce traffic jams on a complex network. At the same time, information reduces the time to reach destination for a single informed driver and even (in presence of a
<figure><img src="image_12.png" /><figcaption>Fig. 10: London Network, details at *t* = 100 sec</figcaption></figure>

mixed population) for non-informed ones. The price paid for this reduction is
a higher occupation of the network on peak hours.

5 Conclusions

We proposed a macroscopic model accounting for different routing strategies in traffic flows, aiming to reproduce some emerging behaviour in a population of drivers with different levels of knowledge about the current (and possibly future) state of the network system. We performed various tests with the purpose of showing the main features of the model and its possible use as an instrument of identification and prediction of the weaker areas of a road network. As future research, we identify one main point that is not addressed in the present work: we approximated the equilibrium points of the system using a smoothed activation function, but the existence, the nature and the convergence to the limit problem is an interesting question that deserves a deeper study.
<figure><img src="image_13.png" /><figcaption>Fig. 11: London Network, details at time 200 sec</figcaption></figure>

## Acknowledgments

The present research was partially supported by MUR grant “Dipartimenti Ec-cellenza 2018-2022” CUP: E11G18000350001, DISMA, Politecnico di Torino and through the PRIN 2020 project “Integrated Mathematical Approaches to Socio-Epidemiological Dynamics” (No. 2020JLWP23, CUP: E15F21005420006). PG was partially supported by the French government, through the 3IA Côte d’Azur Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-19-P3IA-0002.

## A The Priority Riemann Solver

In this section we recall the definition of Priority Riemann Solver given in [13, Section 3]. Given a matrix A belonging to the set of matrices (4) and a priority vector P = (p₁, ..., pₙ) ∈ ℝⁿ, with pᵢ > 0, Σᵢ pᵢ = 1, indicating priorities among incoming roads, we consider the closed, convex and non-empty set

$$ \Omega = \left\{ (\gamma_1, \dots, \gamma_n) \in \prod_{i=1}^{n} [0, \gamma_i^{\max}] : A \cdot (\gamma_1, \dots, \gamma_n)^T \in \prod_{j=n+1}^{n+m} [0, \gamma_j^{\max}] \right\}, $$

and define:

$$ \bar{h} = \sup\{h \in \mathbb{R}^+ : hP \in \Omega\}. $$
<figure><img src="image_14.png" /><figcaption>Fig. 12: London Network, details at time 300 sec</figcaption></figure>

Given Riemann data $(\rho_1, \dots, \rho_{m+n})$, we define a vector $Q = (\tilde{\gamma}_1, \dots, \tilde{\gamma}_n)$ of incoming fluxes by the following recursive procedure (see Algorithm 1 below).

– **STEP 1.** For every $i \in \{1, \dots, n\}$ define

$$h_i = \max\{h : h p_i \le \gamma_i^{\max}\} = \frac{\gamma_i^{\max}}{p_i},$$

and for every $j \in \{n+1, \dots, n+m\}$ define

$$h_j = \max \left\{ h : (A \cdot (hP))_j = h \left( \sum_i a_{ji} p_i \right) \le \gamma_j^{\max} \right\} = \frac{\gamma_j^{\max}}{\sum_i a_{ji} p_i}.$$

In other words, $h_i$ is the maximal $t$ so that $hP$ verifies the flux constraint for the $i$-th road, similarly for $h_j$.

Set $\bar{h} = \min_{i \in \{1, \dots, n\}} \{h_i, h_j\}$. We distinguish two cases:

– CASE 1. If there exists $j$ such that $h_j = \bar{h}$, then we set $Q = \bar{h}P$ and we are done.

– CASE 2. Otherwise, let $I_1 = \{i \in \{1, \dots, n\} : h_i = \bar{h}\}$ (by assumption $I_1 \neq \emptyset$). We set $Q_i = \bar{h}p_i$ for $i \in I_1$ and we go to next step.

– **STEP S.** In step $S-1$ we defined a set $I_{S-1}$ and, by induction, all components of $Q$ are fixed for $i \in J_S = I_1 \cup \dots \cup I_{S-1}$. We let $|J_S| < n$ denote the cardinality of $J_S$ and denote by $J_S^c$ the complement of $J_S$ in $\{1, \dots, n\}$. We now define $h_i$ for $i \in J_S^c$ by:

$$h_i = \max\{h : h p_i \le \gamma_i^{\max}\} = \frac{\gamma_i^{\max}}{p_i},$$

and for every $j \in \{n+1, \dots, n+m\}$ define

$$h_j = \max \left\{ h : \sum_{i \in J_S} a_{ji} Q_i + h \left( \sum_{i \in J_S^c} a_{ji} p_i \right) \le \gamma_j^{\max} \right\}.$$
We then proceed similarly to STEP 1, setting $\hbar = \min_{ij}\{h_i, h_j\}$ and distinguishing two cases:

- CASE 1. If there exists $j$ such that $h_j = \hbar$, then we set $Q_i = \hbar P_i$ for $i \in J_S^c$ and we are done.

- CASE 2. Otherwise, let $I_S = \{i \in J_S^c : h_i = \hbar\}$ (by assumption $I_S \neq \emptyset$). We set $Q_i = \hbar p_i$ for $i \in I_S$. If $J_S \cup I_S = \{1, \dots, n\}$ then we stop, otherwise we go to next step.

**Algorithm 1 Recursive definition of PRS**

Set $J = \emptyset$ and $J^c = \{1, \dots, n\} \setminus J$.

while $|J| < n$ do

$\forall i \in J^c \rightarrow h_i = \max\{h : h p_i \le \gamma_i^{max}\} = \frac{\gamma_i^{max}}{p_i}$,

$\forall j \in \{n+1, \dots, n+m\} \rightarrow h_j = \sup\{h : \sum_{i \in J} a_{ji} Q_i + h(\sum_{i \in J^c} a_{ji} p_i) \le \gamma_j^{max}\}$.

Set $\hbar = \min_{ij}\{h_i, h_j\}$.

if $\exists j \text{ s.t. } h_j = \hbar$ then

Set $Q = \hbar P$ and $J = \{1, \dots, n\}$.

else

Set $I = \{i \in J^c : h_i = \hbar\}$ and $Q_i = \hbar p_i$ for $i \in I$.

Set $J = J \cup I$.

end if

end while

## B Numerical techniques

We present the discrete version of the model, introduced in Sections 2 and 3, which uses Godunov discretization for the conservation laws [23] and an upwind method for the eikonal equation [14].

Let us consider a standard discretization of the network $\mathcal{N}$, where a generic edge $I_\ell$ is approximated by $N_\ell$ points. Setting $\delta_\ell = L_\ell/(N_\ell - 1)$, we define the space grid points $x_{\ell,h} = \pi_j((h-1)\delta_\ell)$ for $h = 1, \dots, N_\ell$, and $\Delta x_{\ell,h} := |x_{\ell,h+1} - x_{\ell,h}|$. For each junction point $J_k \in \mathcal{J}$, we denote by $\text{Inc}(J_k) = \{\ell_1, \dots, \ell_{n_k}\}$ and $\text{Out}(J_k) = \{\ell_{n_k+1}, \dots, \ell_{n_k+m_k}\}$ the indexes of incoming and outgoing roads, respectively.

For any given initial distribution $\bar{p}^c : \mathcal{I} \rightarrow [0, 1]$, the multi-class traffic flow dynamics on the network $\mathcal{N}$ is then described by following discrete system for a $\nu \in \{1, \dots, \lfloor N/\Delta t \rfloor\}$, $\Delta t > 0$, $\ell \in \mathcal{L}$, $h = 2, \dots, N_\ell - 1$ and $c = 1, \dots, N_c$.
$$
\left\{
\begin{aligned}
\rho_{\ell,1}^{c,\nu+1} &= \rho_{\ell,1}^{c,\nu} - \frac{\Delta t}{\Delta x_{\ell,1}} \left( \frac{\rho_{\ell,1}^{c,\nu}}{\rho_{\ell,1}^{c,\nu}} F(\rho_{\ell,1}^{\nu}, \rho_{\ell,2}^{\nu}) - \bar{\gamma}_{\ell,1}^{c,\nu} \right), \\
\rho_{\ell,h}^{c,\nu+1} &= \rho_{\ell,h}^{c,\nu} - \frac{\Delta t}{\Delta x_{\ell,h}} \left( \frac{\rho_{\ell,h}^{c,\nu}}{\rho_{\ell,h}^{c,\nu}} F(\rho_{\ell,h}^{\nu}, \rho_{\ell,h+1}^{\nu}) - \frac{\rho_{\ell,h-1}^{c,\nu}}{\rho_{\ell,h-1}^{c,\nu}} F(\rho_{\ell,h-1}^{\nu}, \rho_{\ell,h}^{\nu}) \right), \\
\rho_{\ell,N_{\ell}}^{c,\nu+1} &= \rho_{\ell,N_{\ell}}^{c,\nu} - \frac{\Delta t}{\Delta x_{\ell,N_{\ell}}} \left( \bar{\gamma}_{\ell,N_{\ell}}^{c,\nu} - \frac{\rho_{\ell,N_{\ell}}^{c,\nu}}{\rho_{\ell,N_{\ell}}^{c,\nu}} F(\rho_{\ell,N_{\ell}-1}^{\nu}, \rho_{\ell,N_{\ell}}^{\nu}) \right), \\
\frac{u_{\ell,h+1}^{c,\nu} - u_{\ell,h}^{c,\nu}}{\Delta x_{\ell,h}} + \frac{1}{g^c(\rho_{\ell,h}^{\nu})} &= 0, \\
u_{\ell,N_{\ell}}^{c,\nu} &= \min_{i \in \text{Out}(J_k)} u_{i,1}^{c,\nu}, \quad x_{\ell,N_{\ell}} \notin \mathcal{T}, \\
\bar{u}^{c,\nu} &= \min_{j \in \text{Out}(J_k)} u_{j,1}^{c,\nu}, \quad a_{ji}^{c,\nu} = \frac{\psi(u_{j,1}^{c,\nu} - \bar{u}^{c,\nu})}{\sum_{z \in \text{Out}(J_k)} \psi(u_{z,1}^{c,\nu} - \bar{u}_{\ell}^{c,\nu})}, \quad (11) \\
A_k^{\nu} &= \left\{ \sum_{c=1}^{N_c} a_{ji}^{c,\nu} \frac{\rho_{i,N_i}^{c,\nu}}{\rho_{i,N_i}^{c,\nu}} \right\}_{ji}, \\
(\bar{\gamma}_{\ell,1}^{\nu}, \dots, \bar{\gamma}_{\ell_{n_k}+m_k}^{\nu}) &= \mathcal{R} S A_k^{\nu} (\rho_{\ell,1}^{\nu}, \dots, \rho_{\ell_{n_k}+m_k}^{\nu}), \\
\bar{\gamma}_{i,N_i}^{c,\nu} &= \frac{\rho_{i}^{c,\nu}}{\rho_{i}^{c,\nu}} \bar{\gamma}_{i}^{\nu}, \quad i \in \text{Inc}(J_k), \quad \bar{\gamma}_{j,1}^{c,\nu} = \sum_{i=\ell_1}^{\ell_{n_k}} a_{ji}^{c,\nu} \bar{\gamma}_{i}^{c,\nu}, \quad j \in \text{Out}(J_k), \\
\rho_{\ell,h}^{c,0} &= \frac{1}{\Delta x_{\ell,h}} \int_{x_{\ell,h}}^{x_{\ell,h+1}} \bar{\rho}_{\ell}^{c}(x) dx, \\
u_{\ell,N_{\ell}}^{c,\nu} &= \rho_{\ell,N_{\ell}}^{c,\nu} = 0, \quad x_{\ell,N_{\ell}} \in \mathcal{T}^{c}, \\
\rho_{\ell,1}^{c,\nu} &= \phi(x_{\ell,1}, \Delta t \nu),
\end{aligned}
\right.
$$

where $\bar{\rho}_{\ell}^{c}$ is the initial traffic distribution on the network.

In (11), the numerical flux $F(\rho_1, \rho_2)$ is the standard Godunov flux corresponding to (3), which can be expressed as

$$F(\rho_1, \rho_2) := \min \{D_1(\rho_1), S_2(\rho_2)\},$$

where $D_{\ell}(\rho)$ and $S_{\ell}(\rho)$ are the demand and supply functions defined by

$$D_{\ell}(\rho) = \begin{cases} \rho v_{\ell}(\rho) & \text{if } \rho \in [0, \hat{\rho}_{\ell}], \\ \gamma_{\ell}^{\max} & \text{if } \rho \in [\hat{\rho}_{\ell}, 1], \end{cases}$$

$$S_{\ell}(\rho) = \begin{cases} \gamma_{\ell}^{\max} & \text{if } \rho \in [0, \hat{\rho}_{\ell}], \\ \rho v_{\ell}(\rho) & \text{if } \rho \in [\hat{\rho}_{\ell}, 1], \end{cases}$$

see for example [19], Section 5.2.3.

In order to guarantee the stability of the scheme (11) we impose that

$$\Delta t \leq \min_{\ell \in \mathcal{L}} \frac{\delta_{\ell}}{V_{\ell}}.$$

We assume that the vehicles *exit* the network once they have reached their destination. In this way, they do not contribute further to the possible congestion effects of the latter. Alternative choices are represented by some Neumann condition bounding the flux to a specific exit rate, or directly imposing some non-flux condition. In such cases, congestion could arise upstream the destination points (see [9]).

Finally, we discuss how to deal with the dynamic case. The discretization of equation (7) gives us the following backward explicit scheme

$$
\left\{
\begin{array}{l}
u_{\ell,h}^{c,nu-1} = u_{\ell,h}^{c,\nu} - \frac{\Delta t}{\Delta x_{\ell,h}} (u_{\ell,h+1}^{c,\nu} - u_{\ell,h}^{c,\nu}) - \frac{1}{g^c(\rho_{\ell,h}^{\nu})}, \\
u_{\ell,h}^{c,N} = \bar{u}_{\ell,h}^{c,\nu},
\end{array}
\right.
$$
where $\bar{u}$, is the solution of the static case (11). When we couple this equation with the other terms of (11) that remain invariate, we observe that the equation for the traffic flow is forward in time and the equation for the potential is backward. The coupling is then solved with a fixed point approach, iterating the resolution between the two equations. Despite not having any theoretical result assuring the convergence to the fixed point procedure, we observe that, in most cases, it is reached after few iterations (~ 6-8 iterations). The only case where the algorithm does not converge is when the smoothing parameter of the activation function $\dot{\psi}$ is $\epsilon > 3$. As explained before, this issue limits the application of the model and it deserves further investigation.

**Remark B.1 (Computational complexity)** The computational complexity of the proposed procedure depends, both in the static and the dynamic case, by the number of the classes, the size and the connectivity of the network considered and the discretization mesh used for numerical scheme. The resolution of the Eikonal equation is comparable to the complexity of a Breadth-first search (often called BFS) algorithm applied on the city network. The Riemann problem complexity is localized on each internal junction and it just requires small matrix multiplication of the size of the incoming and outcoming junction's roads. Finally, the resolution of the density PDEs is performed with an explicit logic, thus no linear system resolution is required. We remark that the implementation performance is not in the focus of the paper, thus no particular optimization for a better quality of the code is explored. However, despite the naive MATLAB implementation we perform, we obtain very good results in the executions times. Indeed, we obtain the static solution in the small-size problems in the order of the minute, and for the London network in the order of the hour. For the dynamic cases, as an iterative convergence is required, the computational complexity is comparable to the static case multiplied by the number of iterations required. As this number is generally low, the execution time is still under control. Finally, we want to remark that a parallel implementation can be exploited with low efforts for each class on the Riemann problems and on the density PDE resolutions thanks to the localized logic nature.

## References

1. Amadori D, Goatin P, Rosini MD (2014) Existence results for Hughes' model for pedestrian flows. J Math Anal Appl 420(1):387-406. https://doi.org/10.1016/j.jmaa.2014.05.072

2. Apicella A, Donnarumma F, Isgrò F, Prevete R, (2021) A survey on modern trainable activation functions Neural Networks 138:14-32. https://doi.org/10.1016/j.neunet.2021.01.026

3. Andreianov B, Rosini M, Stivaletta G (2021) On existence, stability and many-particle approximation of solutions of 1D Hughes model with linear costs. ArXiv Preprint, arXiv:2107.10039. https://doi.org/10.48550/arXiv.2107.10039

4. Baker L (2009) Removing roads and traffic lights speeds urban travel. Scientific American January 19. https://www.scientificamerican.com/article/removing-roads-and-traffic-lights/ Accessed 23 February 2023

5. Baskar L D, De Schutter B, Hellendoorn J, Papp Z (2011) Traffic control and intelligent vehicle highway systems: A survey IET Intell Transp Syst 5(1):38-52. https://doi.org/10.1049/iet-its.2009.0001

6. J-G B (2018) Circulation : Waze, l'appli qui agace les riverains. Le Parisien Jun. https://tinyurl.com/yckuej9h Accessed 23 February 2023

7. Braess D (1968) Über ein Paradoxon aus der Verkehrsplanung. Oper Res 12, 258-268. https://doi.org/10.1007/BF01918335

8. Camilli F, Festa A, Schieborn D (2013) An approximation scheme for a Hamilton-Jacobi equation defined on a network. Appl Num Math 73:33-47. https://doi.org/10.1016/j.apnum.2013.05.003

9. Camilli F, Festa A, Tozza S. (2017) A discrete Hughes' model for pedestrian flow on graphs. Netw Heterog 12(1):93-112. https://doi.org/10.3934/nhm.2017004
10. Carlini E, Festa A, Forcadel N (2020) A semi-lagrangian scheme for hamilton-jacobi-bellman equations on networks. SIAM J Num Anal 58(6):3165-3196. https://doi.org/10.1137/19M1260931

11. Colombo R M, Holden H (2016) On the Braess Paradox with Nonlinear Dynamics and Control Theory, J Optim Theory Appl 168(1): 216-230. https://doi.org/10.1007/s10957-015-0729-5

12. Cristiani E, Priuli FS (2015) A destination-preserving model for simulating Wardrop equilibria in traffic flow on networks. Netw Heterog 10(4):857-876. https://doi.org/10.3934/nhm.2015.10.857

13. Delle Monache ML, Goatin P, Piccoli B (2018) Priority-based Riemann solver for traffic flow on networks. Commun Math Sci 16(1):185-211. https://doi.org/10.4310/CMS.2018.v16.n1.a9

14. Falcone M, Ferretti R (2013) Semi-Lagrangian Approximation Schemes for Linear and Hamilton-Jacobi Equations. SIAM, Philadelphia, PA.

15. Festa A, Guglielmi R, Hermosilla C, Picarelli A, Sahu S, Sassi A, Silva FJ (2017) Hamilton-Jacobi-Bellman Equations, Lecture Notes in Mathematics, 2180:127-261. https://doi.org/10.1007/978-3-319-60771-9_2

16. Festa A, Goatin P (2019) Modeling the impact of on-line navigation devices in traffic flows. Proc IEEE Conf Decis Control 323-328 https://doi.org/10.1109/CDC40024.2019.9030208

17. Foderaro LW (2017) Navigation apps are turning quiet neighborhoods into traffic nightmares. The New York Times Dec 24. https://www.nytimes.com/2017/12/24/nyregion/traffic-apps-gps-neighborhoods.html Accessed 23 February 2023

18. Garavello M, Han K, Piccoli B (2016) Models for vehicular traffic on networks. American Institute of Mathematical Sciences (AIMS), Springfield, MO.

19. Garavello M, Piccoli B (2006) Traffic flow on networks. American institute of Mathematical Sciences (AIMS), Springfield, MO.

20. Hughes RL (2000) The flow of large crowds of pedestrians. Math Comput Simul 53(4):367-370. https://doi.org/10.1016/S0378-4754(00)00228-7

21. Knödel W (1969) Graphentheoretische Methoden und ihre Anwendungen. Springer, Berlin.

22. Lasry JM, Lions PL (2007) Mean field games. Jpn J Math 2:229-260. https://doi.org/10.1007/s11537-007-0657-8

23. LeVeque RJ (1992) Numerical Methods for Conservation Laws Lectures in Mathematics. ETH Zürich.

24. Mouzouni C (2020) On Quasi-stationary Mean Field Games Models. Appl Math Optim 81:655-684. https://doi.org/10.1007/s00245-018-9484-y

25. Roughgarden T, Tardos E (2002) How bad is selfish routing? J. ACM 49, 2:236-259. https://doi.org/10.1145/506147.506153

26. Samaranayake S, Reilly J, Krichene W, Lespiau J B, Delle Monache M L, Goatin P, Bayen A (2018) Discrete-time system optimal dynamic traffic assignment (SO-DTA) with partial control for horizontal queuing networks. Transp Sci 52(4): 982-1001. https://doi.org/10.1109/ACC.2015.7170811

27. Schieborn D, Camilli F (2013) Viscosity solutions of eikonal equations on topological networks. Calc Var Partial Differ Equ 46:671-686. https://doi.org/10.1007/s00526-012-0498-z

28. Thai J, Laurent-Brouty N, Bayen AM (2016) Negative externalities of GPS-enabled routing applications: A game theoretical approach. 2016 IEEE 19th International Conference on Intelligent Transportation Systems (ITSC) 595-601. https://doi.org/10.1109/ITSC.2016.7795614