# Maximizing Safety in Cycling Networks through Optimal and Gradual Upgrading

Manuel Campero Jurado$^{a*}$, Carlos Canudas-de-Wit$^{a,b*}$, Giovanni De Nunzio$^c$

$^a$ Univ. Grenoble Alpes/ Inria/ GIPSA-lab, 38334 Montbonnot Cedex- France
manuel.campero-jurado@inria.fr

$^b$ CNRS/ Grenoble INP, 11 Rue des Mathématiques, 38400
Saint-Martin-d'Hères-Grenoble-France
carlos.canudas-de-wit@gipsa-lab.fr

$^c$ IFP Energies nouvelles, Rond-point de l'échangeur de Solaize, BP 3, 69360 Solaize, France
giovanni.de-nunzio@ifpen.fr

* Corresponding author

*Extended abstract submitted for presentation at the Conference in Emerging Technologies in Transportation Systems (TRC-30)*
*September 02-03, 2024, Crete, Greece*

April 28, 2024

Keywords: Cycling transport network, soft modes, micro-mobility, optimization.

## 1 INTRODUCTION

Transport networks support mobility and urbanization, but globalization brings environmental issues such as carbon emissions and air pollution. Encouraging eco-friendly modes like bicycles yields economic and social benefits (Yang *et al.* (2018)). Despite benefits, safety concerns persist, potentially hindering widespread bicycle adoption (Fishman *et al.* (2012)). Studies on motorized vehicles and bicycles sharing routes (Yuan *et al.* (2019)) reveal that most accidents result from inadequate separation between lanes (Lindman *et al.* (2015)). Segregated infrastructure enhances safety (Lawrence *et al.* (2018)).

Our approach, leveraging graph theory metrics, comprehensively assesses cycling network safety during cyclist link upgrades. Unlike conventional indicators confined to road segments (Mesbah *et al.* (2012)), we analyze network connectivity based on topology and segment-specific safety information using graph theory metrics. We apply them to Grenoble's cycling network using public data. Our optimization objective is to maximize overall metrics throughout a gradual safety enhancement process, for which we have developed an algorithm.

## 2 Cycling Safety Definition and Problem Formulation

### 2.1 Safety weight assignment

Our analysis is made in city of Grenoble, France. We assume linear weights for the links within the bicycle network only based on infrastructure characteristics and it will be called **degree of separation (DoS)** with the assumption that a higher DoS indicates a safer road. The city features four types of roads: $G_4$, the most segregated and exclusive for roads with DoS 4; then $G_3$, $G_2$, and $G_1$ with DoSs 3, 2, and 1 respectively. Here, $G_1$ includes roads that are mixed with motorized traffic.
Consider a weighted undirected graph $G = (V, E, W)$, with $G = G_1 \uplus G_2 \uplus G_3 \uplus G_4$. The operator $\uplus$ unites node and edge sets, with weights $G_1, G_2, G_3$, and $G_4$ have distinct edge sets, each without overlap. The set of nodes is denoted by $V$, $E$ represents links, and $W$ holds weights, for each $e \in E$, $\omega_e$ means the weight of the edge $e$. Nodes are intersections or endpoints, while links are the roads, DoSs are weights on links, higher values indicating greater safety and comfort.

## 2.2 Problem formulation

Beginning with the weighted graph $G$, our objective is to incrementally elevate the DoS of edges from $k$ to $k+1$ for $k = 1, 2$, or $3$. Instantaneous transformation of all roads within a sub-network is impractical, necessitating a gradual approach. Safety upgrades target links within $G_k$. We define $\eta$ as a graph theory metric assessing overall safety in $G$ (see Section 3). Edges in $G_k$ are divided into $n$ sets, $S_1, S_2, \dots, S_n$, ensuring that the difference in the number of elements between each set is at most one. Using $\eta(h_1+p_1, h_2+p_2, \dots, h_n+p_n)$, we represent the sequential upgrade of proportions (i.e, number of elements) in sets $S_1, S_2$, and so on, until $S_n$. We assume elements within $S_r$ are sorted, and $(h_r + p_r)|S_r|$ implies selecting initial elements corresponding to the proportion $h_r + p_r$ in $S_r$, where $|S_r|$ is the cardinality of $S_r$ for all $r = 1, 2, \dots, n$.

The optimization problem we aim to solve is given by:

$$ 
\begin{array}{ll}
\max_{h_r, p_r} & \mathbf{J} = \eta(h_1 + p_1, h_2 + p_2, \dots, h_n + p_n) - \eta(0, 0, \dots, 0) \\
\text{s.t} & \displaystyle\sum_{r=1}^{n} (h_r + p_r) |S_r| \le \text{Budget}, \\
& h_r \in \{0, 1\}, p_r \in [0, 1] \quad \forall r = 1, 2, \dots, n, \\
& h_r + p_r \le 1, \quad \forall r = 1, 2, \dots, n, \\
& t_r \in \{0, 1\}, t_r \ge p_r, \quad \forall r = 1, 2, \dots, n, \\
& \displaystyle\sum_{r=1}^{n} t_r \le 1,
\end{array}
$$

We assume that the cost of improving a road is unitary and independent of the current DoS $k$. Therefore, the Budget is equal to the number of roads to be upgraded from DoS $k$ to $k+1$. By imposing the last four constraints, we guarantee that at most a single proportion value deviates from 0 or 1. This means that at most once the total or zero elements of a set may not be taken at all.

## 3 Metrics

Given $v \in V$, its **local strength** (Barthélemy et al. (2005)) is defined as $s(v) = \sum_{e \in A_v} w_e$, with $A_v \subset E$ the set of adjacent edges to $v$. The **normalized local strength** of $v$ in $G$ is defined as $s_N(v) = \frac{s(v)}{s_{FS}(v)} \in [0, 1]$, where $s_{FS}$ is defined as the local strength of node $v$ in a hypothetical **fully-safe network** equal to $G$ but where all the edges have the highest DoS. The **normalized global strength** $s_G$ is then defined as $s_G = \frac{1}{|V|} \sum_{v \in V} s_N(v) \in [0, 1]$, where $|V|$ indicates the cardinality of $V$. Here $s_G$ is one of our $\eta$ to maximize. A similar definition is doing by the **closeness centrality metric** $c_G$, where for $v \in V$, the **local closeness centrality** (Kansky & Danscoine (1989)) of $v$ in $G$ is defined as $c(v) = \frac{|V|-1}{\sum_{u \in V} l_{u,v}}$, where $l_{u,v}$ is the shortest path between node $v$ and $u$ where the weight also is the lowest possible (for this metric it is necessary to invert the weight of the links) and finally we define a global metric **largest connected component** as follow, let $C_{\omega_0}$ be the set of edges with DoS greater or equal to $\omega_0$, with $\omega_0 \in \mathbb{N} \cup \{0\}$ and $\omega_0 \le \max \omega_{(v_1, v_2)}$ for all $(v_1, v_2) \in E$. Let $\mathcal{H}$ be the largest connected graph induced by $C_{\omega_0}$, and $|V_{\mathcal{H}}|$
<figure><img src="image_1.png" /><figcaption>Figure 1 – In the top row, edges of G1, G2, and G3 are presented, colored by the Si sets from Algorithm LCC with k = 1, 2, 3 and n = 20 for the 3 cases. In the middle row, gradual improvements of metrics sG, cG, and dG are plotted against upgraded links in Si for G1, G2, and G3, respectively. The color bar below the x-axis indicates Si. In the bottom row, the increase in upgrading is plotted using a greedy algorithm.</figcaption></figure>

be the number of nodes of $\mathcal{H}$, $\mathcal{H}_{FS}$ is defined as $\mathcal{H}$ but considering the fully-safe network instead of the original $\mathcal{G}$. Then we define: $d_{\mathcal{G}} = \frac{|V_{\mathcal{H}}| + \sum_{e \in E_{\mathcal{H}}} \omega_e}{|V_{\mathcal{H}_{FS}}| + \sum_{e \in E_{\mathcal{H}_{FS}}} \omega_e} = \frac{|V_{\mathcal{H}}| + \sum_{e \in E_{\mathcal{H}}} \omega_e}{|V_{\mathcal{H}_{FS}}| + \max_{e \in E} \omega_e |E_{\mathcal{H}_{FS}}|} \in [0, 1]$.

# 4 Optimization Algorithm and Results

We created the Algorithm LCC to build sets $S_i$ basing in maximizing the largest connected component and sorted them in the inner of the sets according their betweenness centrality (Liu et al. (2019)). Once that we have these sets, the choice of proportions is as follows for all $r = 1, 2, \dots, n$:

$$h_r + p_r = \begin{cases} 1 & \text{if } \sum_{q=1}^{r} |S_q| \le \text{Budget}, \\ \alpha \in (0, 1] & \text{if } \sum_{q=1}^{r-1} |S_q| + \alpha |S_r| = \text{Budget}, \\ 0 & \text{if } \sum_{q=1}^{r} |S_q| > \text{Budget}. \end{cases} \quad (1)$$

With $\sum_{q=1}^{0} |S_q| := 0$. The primary aim of Algorithm LCC is to maximize the size of the largest connected component with a DoS of $k + 1$.

In Fig. 1 (g), (h), and (i), we employ a greedy approach where we create sets of the same size as $S_i$ and fill them with edges in an order determined solely by betweenness centrality, with proportions of the sets as in eq. (1). Nevertheless, when obtaining the proportions for the sets $S_i$ through the use of eq. (1) and Algorithm LCC, consistently exhibit more favorable outcomes, as depicted in Fig. 1 (d), (e), and (f), in this last scenario, given a hypothetical budget of 250 edges (vertical red line). In the two scenarios, the connected component metrics manifest more pronounced variations in their values.
References

Barthélemy, Marc, Barrat, Alain, Pastor-Satorras, Romualdo, & Vespignani, Alessandro. 2005. Characterization and modeling of weighted networks. *Physica a: Statistical mechanics and its applications*, **346**(1-2), 34-43.

Fishman, Elliot, Washington, Simon, & Haworth, Narelle. 2012. Barriers and facilitators to public bicycle scheme use: A qualitative approach. *Transportation research part F: traffic psychology and behaviour*, **15**(6), 686-698.

Kansky, Karl, & Danscoine, Pascal. 1989. Measures of network structure. *FLUX Cahiers scientifiques internationaux Réseaux et Territoires*, **5**(1), 89-121.

Lawrence, Brendan M, Oxley, Jennifer A, Logan, David B, & Stevenson, Mark R. 2018. Cyclist exposure to the risk of car door collisions in mixed function activity centers: A study in Melbourne, Australia. *Traffic injury prevention*, **19**(sup1), S164-S168.

Lindman, M, Jonsson, S, Jakobsson, L, Karlsson, T, Gustafson, D, & Fredriksson, A. 2015. Cyclists interacting with passenger cars; a study of real world crashes. *Pages 9–11 of: 2015 IRCOBI Conference Proceedings*.

Liu, Weiyan, Li, Xin, Liu, Tao, Liu, Bin, et al. 2019. Approximating betweenness centrality to identify key nodes in a weighted urban complex transportation network. *Journal of Advanced Transportation*, **2019**.

Mesbah, Mahmoud, Thompson, Russell, & Moridpour, Sara. 2012. Bilevel optimization approach to design of network of bike lanes. *Transportation research record*, **2284**(1), 21-28.

Yang, Xu-Hua, Cheng, Zhi, Chen, Guang, Wang, Lei, Ruan, Zhong-Yuan, & Zheng, Yu-Jun. 2018. The impact of a public bicycle-sharing system on urban public transport networks. *Transportation research part A: policy and practice*, **107**, 246-256.

Yuan, Kai, Knoop, Victor L, & Hoogendoorn, Serge P. 2019. Multi-class traffic flow on a partially space-shared road. *Transportmetrica B: Transport Dynamics*, **7**(1), 1505-1520.