# A Graph-Based Approach to the Topological Optimization of Cycling Networks for the Improvement of Safety and Comfort of Cyclists

Manuel Campero Jurado, Carlos Canudas de Wit, Giovanni de Nunzio

► To cite this version:

Manuel Campero Jurado, Carlos Canudas de Wit, Giovanni de Nunzio. A Graph-Based Approach to the Topological Optimization of Cycling Networks for the Improvement of Safety and Comfort of Cyclists. 2025. hal-05017729

HAL Id: hal-05017729

https://hal.science/hal-05017729v1

Preprint submitted on 2 Apr 2025

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
# A Graph-Based Approach to the Topological Optimization of Cycling Networks for the Improvement of Safety and Comfort of Cyclists

Manuel Campero Jurado<fnref n="1" />, Carlos Canudas-de-Wit<fnref n="2" />, Giovanni De Nunzio<fnref n="3" />

***Abstract***—This work aims to improve perceived safety and comfort of cyclists by proposing a topological optimization of existing cycling networks. We assign weights to a six-category system for bike lanes based on their segregation from motorized vehicles using the well-developed CycleRAP tool. Each bike lane is weighted based on its category and topological features. Graph theory metrics are then applied to analyze the core topological characteristics of cycling networks across various French municipalities. These metrics form the basis for estimating and predicting cyclists' perceived safety and comfort levels, as reported in local surveys. Building on this relationship, we formulate a topology optimization problem aimed at maximizing predicted safety and comfort within budgetary constraints. To tackle this complex problem, we introduce a topological optimization algorithm and compare its performance with existing algorithms to ensure reliability. This approach integrates graph theory with real-world indicators, providing a comprehensive quantitative framework to support decision-making in urban planning and resource allocation.

***Index Terms***—Cycling network, graph theory, safety, comfort, budget-constrained infrastructure optimization, heuristic optimization.

## I. INTRODUCTION

The health, ecological, and socio-economic benefits of a cyclist society are well-known, including improved cardiovascular health, increased longevity, reduced carbon footprint, decreased air pollution, lower transportation costs, reduced traffic congestion, and greater convenience and efficiency [1], [2]. As a result, public authorities have made considerable efforts to promote cycling as an alternative to driving for short distances, however, cyclists continue to face safety and comfort issues that may dissuade them from cycling [3]. It is well-established that infrastructure separating bicycles from motorized vehicles improves user perceptions of safety and comfort, encouraging increased cycling [4], [5]. High-quality cycling infrastructure has a significant impact on ridership, with great potential for growth when there are highly connected facilities [6], [7]. Given the often limited budget for infrastructure development, it is crucial to determine where to allocate resources to maximize the impact on cyclists' safety and comfort. This work presents a cycling network classification weighted using

the international assessment tool CycleRAP [8]. Additionally, it proposes a modeling and optimization framework to identify the most effective bike lane upgrades for enhancing cyclist safety and comfort.

### A. Literature Review

Our work pertains to three research streams: safety and comfort levels in cycling networks, optimization of cycling infrastructure, and the application of graph theory metrics to evaluate transportation network characteristics.

***Safety and Comfort Levels in Cycling Networks:*** Several frameworks classify cycling network roads and paths by safety and comfort. The Levels of Traffic Stress (LTS) categorize roads into four levels based on infrastructure like protected lanes, speed limits, and traffic volume [9]. Additionally, models like the Bicycle Safety Index Rating (BSIR) assess subjective perceptions of road safety, while the Bicycle Level of Service (BLOS) index evaluates ride comfort and traffic conditions [10], [11].

However, the previous categories are usually based on data and surveys that are not transferable to all regions, that is why we adopt a six-category classification system for bike lanes based on their segregation from motorized vehicles, referred to as the degree of separation (DoS) that relies entirely on OpenStreetMap (OSM) data [12], thus completely generalizable. In this system, greater segregation correlates with higher levels of safety and comfort.

***Cycling Network Optimization:*** Numerous studies explore different aspects of cycling network topology optimization, this includes upgrading specific bike lanes to achieve the dual goals of improved safety and comfort, all while adhering to resource constraints. The Bicycle Network Improvement Problem (BNIP) aims to enhance safety and reduce route deviations while staying within budget constraints. Key considerations include protected lanes, sufficient path widths, and direct routes [13], [14]. These factors are typically assessed using metrics such as the LTS and the Bicycle Compatibility Index (BCI) [9], [11].

Optimization strategies maximize bike lane usage [15], [16] which refers to increasing the total distance that cyclists travel on designated bike lanes, a metric used as a proxy for improved infrastructure usage and accessibility. Other studies emphasize improving network connectivity and optimizing societal benefit-cost ratios [17], [18]. Demand-driven models integrate car and bike networks to guide resource reallocation

<footnote n="1">¹Univ. Grenoble Alpes, Inria, 38334 Montbonnot Cedex - France
manuel.campero-jurado@inria.fr (Corresponding author)</footnote>

<footnote n="2">²Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, GIPSA-lab, 11 Rue des Mathématiques, 38400 Saint-Martin-d'Hères-Grenoble-France
carlos.canudas-de-wit@gipsa-lab.fr</footnote>

<footnote n="3">³IFP Energies nouvelles, Rond-point de l'échangeur de Solaize, BP 3,
69360 Solaize, France, giovanni.de-nunzio@ifpen.fr</footnote>
[19], while some approaches prioritize connectivity or budget-aware shortest paths [18]. Mixed-integer programming and metaheuristic approaches have been applied to optimize urban cycling networks, balancing user preferences and costs [20], [21]. Additionally, genetic algorithms and heuristics have been used to minimize travel time while adhering to budget constraints [22]. Despite their potential, these methods often lack validation against real-world perceptions of safety and comfort derived from survey data.

*Graph Theory Metrics in Cycling Networks:* Graph theory metrics offer valuable tools for analyzing and optimizing transport networks. Betweenness centrality identifies key nodes along shortest paths, highlighting critical infrastructure points [23]. Algebraic connectivity, measured by the second smallest Laplacian eigenvalue, assesses network robustness [24], while spectral radius evaluates communication efficiency [25]. Modularity helps detect network clusters, facilitating targeted interventions [24]. These metrics collectively quantify connectivity, efficiency, and resilience, aiding in network improvements such as prioritizing upgrades on critical paths, minimizing vulnerabilities, and promoting equitable access across diverse regions [26]–[28]. Additionally, graph-theoretical approaches have been used to study bike-vehicle interactions and develop network design strategies based on clustering [29], [30]. However, all their approaches often assume that changes to bike lane topology will consistently improve these metrics, overlooking the complex and non-monotonic nature of graph theory metrics.

To the best of our knowledge, no existing work systematically integrates globally aggregated graph theory metric values into a robust weighting framework for modeling perceived cycling safety and comfort. Additionally, current optimization approaches lack rigorous benchmarking against state-of-the-art algorithms. This work bridges these gaps by introducing a refined weighting methodology and systematically evaluating its optimization framework.

## B. Statement of Contributions

This paper introduces a method to optimize bike lane safety and comfort using graph theory and topology optimization. It incorporates CycleRAP scores into a novel DoS classification, identifies key graph metrics correlated with cyclist perceptions, and develops a model validated against survey data. The proposed optimization algorithm enhances cycling networks within budget constraints and diverse urban conditions. The framework is benchmarked against heuristic solvers and applied to 14 French cities, demonstrating improved safety and comfort for cyclists.

## C. Organization and Overall Methodology

The remainder of this paper is structured as follows: Section II describes the data and graph theory metrics. Section III presents the predictive model for safety and comfort. Section IV introduces the optimization framework, followed by benchmark comparisons and real-world applications in Sections V–VII. Section VIII discusses the framework’s strengths and limitations, Section IX concludes with future directions and Appendices provide supplementary information and proofs.

## II. NETWORK DATA AND FEATURES

This section outlines the data and tools used to analyze cycling networks. We introduce field survey data on safety and comfort, explain how CycleRAP assigns weights to network segments, and describe the graph metrics used to predict safety and comfort.

<figure><img src="image_2.png" /><figcaption>Fig. 1: Perceived cycling safety and comfort data in Grenoble, France.</figcaption></figure>

### A. Perceived safety and comfort data

We collect perceived safety and comfort data from the “Baromètre Vélo” (Bicycle Barometer) project [31], a satisfaction survey designed to assess and promote bicycle use in various cities and regions of France. This questionnaire, conducted every two years, collects cyclist perceptions of their cycling environment.

The survey, open to all frequent visitors of a municipality, includes around 30 questions on general impressions, safety, comfort, cycling importance, and parking. Responses are geo-referenced to identify high-risk areas, with ratings reflecting perceived safety and infrastructure quality. The survey generates global scores for municipalities, including perceived safety and comfort. Fig. 1 illustrates the “Baromètre Vélo” for Grenoble, the global scores from 3009 survey respondents are shown on the left. The red, green and blue dots also originate from the survey responses: Red dots indicate priority areas for improvement, green mark perceived improvements over the past two years, and blue represent desired bike parking. While this paper concentrates on global scores, future work will delve into the local insights offered by the survey, as represented by these colored dots.

### B. Bike lane classification and weights

The DoS classification, inspired by Geovelo<fnref n="1" />, condenses 22 bike lane types into six categories based on separation from traffic [12], emphasizing that dedicated lanes enhance safety and comfort [32]. This methodology is publicly available online<fnref n="2" />.

<footnote n="1">¹https://gitlab.com/geovelo-public/requetes_amenagements_cyclables/-/tree/master</footnote>

<footnote n="2">²https://github.com/leunamCampero/ITSC2024</footnote>
<table><caption>TABLE I: The table displays the degree of separation (DoS) with its CycleRAP Safety and Comfort Score (CSCS), cycling infrastructure category, Geovelo classification, and GTLVille data on AADT and mean speed for roads near cycling paths in Grenoble.</caption><thead><tr><th>DoS : CSCS</th><th>Description</th><th>Geovelo</th><th>AADT</th><th>Mean speed</th></tr></thead><tbody><tr><td>6: 5.23</td><td>Cycleways exclusively reserved for bikes, physically separated from cars.</td><td>7, 14</td><td>14 400</td><td>50 km/h</td></tr><tr><td>5: 4.64</td><td>Cycleways separated from motor vehicles but shared with pedestrians.</td><td>2, 10, 11, 15, 16, 17, 20</td><td>16 000</td><td>50 km/h</td></tr><tr><td>3: 2.99</td><td>Roads where cycling is allowed, no designated lanes, shared with cars (speed limit: 30 km/h).</td><td>9, 12, 13, 21, 22</td><td>960</td><td>30 km/h</td></tr><tr><td>3: 2.18</td><td>Shared roads allow cycling alongside motor vehicles, with cycling pictograms.</td><td>5, 8</td><td>3 120</td><td>30 km/h</td></tr><tr><td>2: 1.55</td><td>Roads with painted bike lanes.</td><td>1, 3, 4, 6</td><td>6 912</td><td>40 km/h</td></tr><tr><td>1: 1.00</td><td>Unmarked shared car-bike lanes.</td><td>18, 19</td><td>8 448</td><td>40 km/h</td></tr></tbody></table>

<figure><img src="image_3.png" /><figcaption>Fig. 2: CycleRAP demonstrator tool for scoring cycling facilities.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 3: Cycling network of Grenoble, France, with the CycleRAP Safety and Comfort Score (CSCS) ranging from 1 to 5.23, indicating increasing separation from motorized traffic.</figcaption></figure>

To assign weights, we use CycleRAP scores [8], which assess crash risks from infrastructure data. Using OSM and Grenoble's GTLVille platform [33], we estimate annual average daily traffic (AADT) and speed, providing inputs for the CycleRAP tool. The CycleRAP Safety and Comfort Score (CSCS) integrates infrastructure and traffic data, improving safety predictions and guiding cost-effective upgrades.

Table I summarizes the CSCS values by DoS category, aligned with the Geovelo classification, including the AADT and speed descriptions. CSCS values are normalized CycleRAP scores, ensuring higher DoS correlates with higher scores. Although well-separated lanes remain safe despite traffic, unprotected lanes become more dangerous as volume and speed increase. Fig. 2 shows the CycleRAP tool, and Fig. 3 visualizes Grenoble's bike lane categorization.

### C. Graph metrics

We introduce a mathematical framework for modeling cycling networks as graphs and define three graph theory metrics. These metrics, chosen for their monotonic properties, intuitively correspond to key network elements: nodes (intersections), edges (roads), and connected paths (bike routes).

Let the considered network be described by a weighted undirected graph $G = (V(G), E(G), W(G))$. Where, $V(G)$ represents a set of nodes (vertices), $E(G)$ the set of links (edges), and $W(G)$ the set of weights. Nodes correspond to intersections or endpoints of roads, while links correspond to the roads themselves. The CSCS represents the weight assigned to the links denoted as $\omega(u,v) = \omega_e \in W(G)$ for each $(u, v) = e \in E(G)$. We denote $d_e$ the geographical length of an edge $e$, its geographical weight will represent the product $d_e \cdot \omega_e$. To simplify, we denote $V = V(G)$, $E = E(G)$, and $W = W(G)$. When referring to any other specific graph, such as $H$, we will explicitly write its sets of nodes, edges, and weights as $V(H)$, $E(H)$, and $W(H)$, respectively.

The edge weights derived from the CSCS are entirely local. To assess perceived safety and comfort at the network level, we use metrics from graph theory, which allow for a broader assessment of safety and comfort across the entire network.

The graph theory metrics used in this study must exhibit a crucial property: monotonic behavior. Specifically, when edges move from one CSCS value in $K = \{\omega_{DoS_1} = 1, \omega_{DoS_2} = 1.55, \dots, \omega_{DoS_6} = 5.23\}$ to any equal or greater value in $K$, indicating that upgrades are discrete, e.g. from CSCS $\omega_{DoS_1}$ to $\omega_{DoS_6}$, the selected metrics must reflect this progression. The three proposed metrics satisfy this condition and correspond to key network elements: nodes, edges, and connected paths. We hypothesize a positive correlation between these metrics and perceived safety and comfort, supporting their use in our prediction model, as tested in Section III.

1) *Node strength:* In weighted graphs, node strength quantifies the strength of a node's connections. Here, edge weights represent CSCS scores, so node strength indicates how safe and comfortable an intersection is. The hypothesis is that total node strength (graph strength) correlates with perceived safety and comfort at the network level. Graph strength aggregates local measures into a global value. We use the subscript FS for metrics in a fully safe-comfortable network, where all edges have the highest CSCS value $\omega_{DoS_6}$, serving as a normalization reference.
Given $v \in V$, its local strength 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$ is defined as:

$$s_N(v) = \frac{s(v)}{s_{FS}(v)} \in [0, 1].$$

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$.

2) **Closeness centrality:** Cyclists often choose safer, more comfortable routes, even if longer. This behavior aligns with closeness centrality in weighted graphs, which measures node proximity based on shortest paths [34]. To extend this concept, we define an equivalent metric for edges.

For this purpose, we consider the line graph $L(G)$ of $G$, that is defined as the graph where the set of nodes is the original set of edges $E$. For every incident edges $e_a, e_b \in E$, an edge $e_{a,b} = (e_a, e_b) \in E(L(G))$ will be created. Let DoS($e$) the DoS assigned to the edge $e$, then we assign the following weight and geographical length to this new edge in $L(G)$, respectively: $\omega_{e_{a,b}} = \frac{1}{2} [\omega_{\text{DoS}(7-\text{DoS}(e_a))} + \omega_{\text{DoS}(7-\text{DoS}(e_b))}]$, $d_{e_{a,b}} = \frac{1}{2}(d_{e_a} + d_{e_b})$. By using the geographical weight $d_{e_{a,b}} \cdot \omega_{e_{a,b}}$ as the basis of the shortest weighted path search, this definition allows to better take into account the safety and comfort, as intended.

Let $e_a \in V(L(G)) = E$. The local closeness centrality of $e_a$, denoted by $c(e_b)$, is defined as follows:

$$c(e_a) = \frac{|E| - 1}{\sum_{e_b \in E} s\omega_{e_a, b}},$$

where $s\omega_{e_a, b}$ represents the minimum sum of geographical weights on the links between any path connecting $e_a$ and $e_b$. Additionally, $s\omega_{e_a, a} = 0$ for all $e_a \in E$. If $L(G)$ is disconnected and $e_a$ and $e_b$ belong to different connected components, then $s\omega_{e_a, b}$ is set to 0. In case $e_a$ does not have incident edges, $c(e_a)$ is set to 0. The normalized local closeness centrality of $e_a$ in $E$ is defined as:

$$c_N(e_a) = \frac{c(e_a)}{c_{FS}(e_a)} \in [0, 1].$$

And then the normalized global closeness centrality $c_G$ is defined as:

$$c_G = \frac{1}{|E|} \sum_{e_a \in E} c_N(e_a) \in [0, 1].$$

3) **Largest connected component:** This metric assumes cyclists prefer networks with extensive, interconnected, high-quality paths over isolated high-quality segments. It reflects the idea that a route's safety and comfort depend on its weakest section, as one unsafe segment can make the entire path unsuitable [35]. The metric is the ratio of (1) the total road length in the largest connected component to (2) the total road length in a fully separated network.

Formally, let $\mathcal{CG}$ be the set of connected components of $G$ sorted from the smallest to the largest one in non-decreasing order, and let $C_\gamma$ be the set of edges with CSCS greater or equal to $\gamma$ with $\gamma \in \mathcal{A} = \{\omega_{\text{DoS}_2}, \omega_{\text{DoS}_3}, \dots, \omega_{\text{DoS}_6}\}$ of a connected component $C \in \mathcal{CG}$. Let $\mathcal{H}_\gamma$ be the largest connected graph induced by $C_\gamma$. Then we define:

$$l_N(C_\gamma) = \frac{\sum_{e \in E(\mathcal{H}_\gamma)} d_e \cdot \omega_e}{\sum_{e \in E(\mathcal{H}_{FS})} d_e \cdot \omega_e} \in [0, 1],$$

where $l_N(C_\gamma) \in [0, 1] \forall \gamma \in \mathcal{A}$ and $C \in \mathcal{CG}$. Then the largest connected component metric is defined as:

$$l_G = \sum_{j=1}^{|CG|} \frac{\exp(j)}{\alpha_2} \cdot \sum_{\gamma \in \mathcal{A}} \frac{\exp(\gamma)}{\alpha_1} \cdot l_N(C_\gamma^j) \in [0, 1],$$

where $\alpha_1 = \sum_{i_1 \in \mathcal{A}} \exp(i_1)$, and $\alpha_2 = \sum_{i_2=1}^{|CG|} \exp(i_2)$ are terms used to normalize between 0 and 1. The exponential factors are used to assign greater significance to the larger connected component.

### III. MODEL DESIGN

Let $\tilde{M} \in \mathbb{R}^{n \times 3}$ be the matrix formed by the columns metrics $s_G, c_G, l_G$ and $n$ is the total number of cities or samples. The vectors $y_s \in \mathbb{R}^n$ and $y_c \in \mathbb{R}^n$ gather the data from the perceived safety and comfort obtained from “Baromètre Vélo”. The central question addressed in this section is to find a function $f(\tilde{M}, \theta)$, and a parameter set $\theta$ such that

$$f(\tilde{M}, \theta) \approx y, \quad (1)$$

with $f(\tilde{M}, \theta) = [f_s(\tilde{M}, \theta_s)^T, f_c(\tilde{M}, \theta_c)^T]^T$, with $f_s, f_c \in \mathbb{R}^n$ representing the individual predictions for perceived safety and comfort, respectively, $y = [y_s^T, y_c^T]^T$, and $\theta = [\theta_s^T, \theta_c^T]$, with $\theta_s$ and $\theta_c$ representing the parameters for predicting perceived safety and comfort, respectively.

As detailed in Section II-C, it is essential for the metrics to exhibit non-decreasing monotonic behavior. To achieve this, we introduce the set of graphs isomorphic to $G$, where the edges have a CSCS $\omega^{\tilde{G}}$ that is at least equal to the CSCS of the corresponding edges in $G$:

$$\mathbb{H} = \{ \tilde{G} : V(\tilde{G}) = V, E(\tilde{G}) = E, \forall e \in E, \omega_e \le \omega_e^{\tilde{G}} \}$$

We denote the individual metrics of a graph $G$ by the vector:

$$m_G = [s_G, c_G, l_G] \in \mathbb{R}^{1 \times 3}.$$

The model used to predict perceived safety and comfort can therefore be stated as follows:

**Problem 1.** For all $\tilde{G} \in \mathbb{H}$, find $f^*$ and $\theta^*$, such that

$$(f^*, \theta^*) = \underset{f, \theta}{\operatorname{argmin}} \|f(\tilde{M}, \theta) - y\|^2 \quad (2)$$

$$\text{under} \quad f_s(m_G, \theta_s) \le f_s(m_{\tilde{G}}, \theta_s), \quad (3)$$

$$f_c(m_G, \theta_c) \le f_c(m_{\tilde{G}}, \theta_c). \quad (4)$$
<table><caption>TABLE II: The values of $s_G$, $c_G$, and $l_G$ for fourteen municipalities in France. Safety ($y_s$) and comfort ($y_c$) values are scaled to [0, 1].</caption><thead><tr><th>No</th><th>City</th><th>s<sub>G</sub></th><th>c<sub>G</sub></th><th>l<sub>G</sub></th><th>y<sub>s</sub></th><th>y<sub>c</sub></th></tr></thead><tbody><tr><td>1</td><td>Angers</td><td>0.442</td><td>0.3575</td><td>0.1113</td><td>0.42</td><td>0.484</td></tr><tr><td>2</td><td>Annecy</td><td>0.3469</td><td>0.2887</td><td>0.0543</td><td>0.448</td><td>0.552</td></tr><tr><td>3</td><td>Bordeaux</td><td>0.4233</td><td>0.388</td><td>0.0653</td><td>0.44</td><td>0.458</td></tr><tr><td>4</td><td>Chambery</td><td>0.3939</td><td>0.3291</td><td>0.1729</td><td>0.514</td><td>0.564</td></tr><tr><td>5</td><td>Dunkerque</td><td>0.4565</td><td>0.5049</td><td>0.087</td><td>0.488</td><td>0.524</td></tr><tr><td>6</td><td>Grenoble</td><td>0.417</td><td>0.4263</td><td>0.2028</td><td>0.608</td><td>0.674</td></tr><tr><td>7</td><td>La Rochelle</td><td>0.3557</td><td>0.4275</td><td>0.1529</td><td>0.566</td><td>0.608</td></tr><tr><td>8</td><td>Le Havre</td><td>0.5504</td><td>0.4963</td><td>0.1209</td><td>0.458</td><td>0.444</td></tr><tr><td>9</td><td>Lyon</td><td>0.3453</td><td>0.4078</td><td>0.1665</td><td>0.44</td><td>0.508</td></tr><tr><td>10</td><td>Nantes</td><td>0.3507</td><td>0.3445</td><td>0.0557</td><td>0.47</td><td>0.522</td></tr><tr><td>11</td><td>Paris</td><td>0.3486</td><td>0.54</td><td>0.0537</td><td>0.412</td><td>0.462</td></tr><tr><td>12</td><td>Rennes</td><td>0.4433</td><td>0.3611</td><td>0.0426</td><td>0.48</td><td>0.534</td></tr><tr><td>13</td><td>Strasbourg</td><td>0.5326</td><td>0.6087</td><td>0.376</td><td>0.622</td><td>0.654</td></tr><tr><td>14</td><td>Tours</td><td>0.3474</td><td>0.321</td><td>0.0731</td><td>0.43</td><td>0.468</td></tr></tbody></table>

where Eq. (3)–(4) serve the purpose of ensuring the monotonie non-decreasing behavior of these models. Problem 1 is a functional optimization problem. To simplify, we restrict the function space to first-degree polynomials, avoiding the complexity of infinite-dimensional spaces. The optimal solution within this restricted space is then compared to results obtained using a machine learning approach.

### A. Linear regression approach

In this section, we start with a linear regression model due to its simplicity. We then employ statistical methods such as the P-value and t-test [36] to identify the most significant metrics for predicting perceived safety and comfort. This allows us to address the linear version of Problem 1 using only the significant metrics. Hence, the proposed form for $f(\tilde{M}, \theta)$ is:

$$f(\tilde{M}, \theta) = \begin{bmatrix} \mathbf{1}|\tilde{M} & 0 \\ 0 & \mathbf{1}|\tilde{M} \end{bmatrix} \theta = M\theta = f(M, \theta) \quad (5)$$

where $[\mathbf{1}|\tilde{M}] \in \mathbb{R}^{n \times 4}$ is the original $\tilde{M}$ matrix with an additional column of 1's placed at the beginning to introduce a bias term in the regression, and thus $\theta \in \mathbb{R}^8$. Solving Eq. (5) is equivalent to finding:

$$\theta^* = \underset{\theta \in \mathbb{R}^8}{\operatorname{argmin}} \left\| M\hat{\theta} - y \right\|^2. \quad (6)$$

1) **Retain relevant metrics:** To solve Eq. (6), we apply the least squares method [37], using $\tilde{M}$ and $y$ from Table II. This enables P-value and t-tests to assess metric significance in predicting safety and comfort, testing against the null hypothesis ($H_0$) that a metric is not a significant predictor.

With a significance level of 0.05, the critical t-value is 2.22 for $df = 10$ [38]. The hypotheses are:

* $H_0: P\text{-value} > 0.05$ and $|t\text{-value}| < 2.22$ (metric is insignificant).

* $H_A: P\text{-value} < 0.05$ and $|t\text{-value}| > 2.22$ (metric is significant).

Applying least squares to safety and comfort models (Table III), $s_G$ and $c_G$ exceed 0.05 and fall below 2.22, making them insignificant. Their localized nature may limit their broader impact. However, $l_G$ meets significance criteria, confirming its relevance for predicting safety and comfort.

<table><caption>TABLE III: Regression results for solving Eq. (6) for safety and comfort.</caption><thead><tr><th>θ<sup>*</sup></th><th>Coefficient</th><th>|t|-value</th><th>P-value</th></tr></thead><tbody><tr><td colspan="4" style="text-align: center; font-weight: bold;">Safety</td></tr><tr><td>Intercept</td><td>0.4255</td><td>4.816</td><td>0.001</td></tr><tr><td>s<sub>G</sub></td><td>-0.0063</td><td>0.026</td><td>0.980</td></tr><tr><td>c<sub>G</sub></td><td>-0.0330</td><td>0.173</td><td>0.866</td></tr><tr><td>l<sub>G</sub></td><td>0.6149</td><td>3.340</td><td>0.007</td></tr><tr><td colspan="4" style="text-align: center; font-weight: bold;">Comfort</td></tr><tr><td>Intercept</td><td>0.5940</td><td>5.980</td><td>0.000</td></tr><tr><td>s<sub>G</sub></td><td>-0.2311</td><td>0.848</td><td>0.416</td></tr><tr><td>c<sub>G</sub></td><td>-0.1316</td><td>0.614</td><td>0.553</td></tr><tr><td>l<sub>G</sub></td><td>0.7112</td><td>3.437</td><td>0.006</td></tr></tbody></table>

<figure><img src="image_5.png" /><figcaption>Fig. 4: Flowchart of the model training and testing process.</figcaption></figure>

2) **Synthetic data vault:** In current practices, the data are usually divided into training and validation sets using a ratio of 75% to 25%. By removing the columns $s_G$ and $c_G$, and selecting 10 random samples each for safety and comfort training, the matrix $M \in \mathbb{R}^{20 \times 4}$, the vector $\theta \in \mathbb{R}^4_{>0}$ in Eq. (5) and the original data $y \in \mathbb{R}^4$ in Eq. (1) are redefined according to the 10 selected samples. With the remaining 4 samples used for validation.

To improve matrix conditioning for the 10 training samples, we use the Synthetic Data Vault (SDV) method to generate synthetic data [39]. The synthetic data maintains the original distribution, ensuring similar statistical properties. By Lemma 1, linear regression is treated with non-negative least squares (NNLS), as detailed in [40]. See Fig. 4 for the process breakdown.

**Lemma 1.** After selecting significant metrics and enriching the training data using the SDV method, solving Problem 1 under the linear model structure is equivalent to find the optimal $\tilde{\theta}$:

$$\tilde{\theta} = \underset{\theta \in \mathbb{R}^4_{>0}}{\operatorname{argmin}} \left\| M\hat{\theta} - y \right\|^2 = \underset{\theta \in \mathbb{R}^4}{\operatorname{argmin}} \left\| M\hat{\theta} - y \right\|^2. \quad (7)$$

*Proof.* This equivalence can be easily demonstrated by noting that the only selected metric inherently exhibits non-decreasing monotonic behavior with respect to their CSCS values. Provided that all components of the $\theta$ parameter vector are positive semidefinite, then the linear regression
<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 5: Predicted values versus the actual values of perceived safety (right) and comfort (left). The average error is 2.23 % and 3.15 % for Auto-ML Ensemble and NNLS, respectively, for safety, and 5.99 % and 7.36 % for Auto-ML Ensemble and NNLS, respectively, for comfort.</figcaption></figure>

structure inherits non-decreasing monotonic properties of the metrics. □

## B. Comparison between the linear regression and Ensemble ML-based models

We employ NNLS using only $l_G$, as it is the only metric shown to significantly predict perceived safety and comfort, as indicated in Table III. The resulting coefficients are as follows:

$$ \tilde{\theta} = [0.41, 0.58, 0.45, 0.57]^T. \quad (8) $$

Since $l_G$ is the most correlated metric with perceived safety and comfort, we validate our linear approach by comparing its results with those from the AutoGluon Auto-ML ensemble method [41]. Auto-ML combines models like trees, neural networks, and regression to improve prediction accuracy.

Fig. 5 shows that both NNLS and Auto-ML ensemble yield similar results, effectively capturing key aspects of safety and comfort. Therefore, we select NNLS for its simplicity and acceptable performance.

# IV. NETWORK OPTIMAL DESIGN

In this section, we formulate the network-upgrade optimization problem using the identified linear regression model. Upgrading a road segment increases its CSCS value and incurs a cost per meter. CSCS values can only increase within the set $\mathcal{K}$ in discrete steps. The goal is to select edges for upgrade to maximize expected perceived safety and comfort in a cycling network $\mathcal{G}$, while staying within a fixed budget $\mathcal{B}$. We introduce the following notations:

* $\omega_0 = [\omega_1, \dots, \omega_e, \dots, \omega_{|E|}]$ are the original edge weights (CSCS) of the graph $\mathcal{G}$ to be optimized.

* $\tilde{\omega} = [\tilde{\omega}_1, \dots, \tilde{\omega}_e, \dots, \tilde{\omega}_{|E|}] \in \Omega$ are the candidate weights to be optimized, with,

$$ \Omega = \{ \tilde{\omega} \in \mathbb{N}^{|E|} : \omega_e \le \tilde{\omega}_e \le \omega_{\text{DoS}_6}, \forall e \in \{1, 2, \dots, |E|\} \}. $$

Based on the linear model structure derived above and the identified parameters, we can now define two predicted model outputs, each with different CSCS weights,

$$ \hat{y}_{\omega_0} = M_{\omega_0} \tilde{\theta}, \quad \hat{y}(\tilde{\omega}) = M_{\tilde{\omega}} \tilde{\theta} $$

with $\theta^*$ as defined in Eq. (8). $M_{\omega_0} \in \mathbb{R}^{2 \times 4}$, and $M_{\tilde{\omega}} \in \mathbb{R}^{2 \times 4}$ are matrices following similar structure as $M$, with the $s_G$ and

$c_G$ columns removed (as suggested by p-value test in previous section). They are defined as:

$$ M_{\omega_0} = \begin{bmatrix} m_{\omega_0} & 0 \\ 0 & m_{\omega_0} \end{bmatrix}, \quad M_{\tilde{\omega}} = \begin{bmatrix} m_{\tilde{\omega}} & 0 \\ 0 & m_{\tilde{\omega}} \end{bmatrix} $$

with $m_{\omega_0}$ and $m_{\tilde{\omega}}$ in $\mathbb{R}^{1 \times 2}$,

$$ m_{\omega_0} = [1, l_G], \quad m_{\tilde{\omega}} = [1, l_{G\tilde{\omega}}] $$

where $l_{G\tilde{\omega}}$ is computed in $\mathcal{G}$ with the CSCS changed to $\tilde{\omega}$. Denoting $\pi(\omega_e, \tilde{\omega}_e)$ the cost or price per meter of upgrading edge $e$ from $\omega_e$ to $\tilde{\omega}_e$, the optimization problem can now be formulated as follows:

## Problem 2 (Network-upgrade optimization problem).

$$ \omega^* = \underset{\tilde{\omega} \in \Omega}{\operatorname{argmax}} \|\hat{y}_{\omega_0} - \hat{y}(\tilde{\omega})\| \quad (9) $$

$$ = \underset{\tilde{\omega} \in \Omega}{\operatorname{argmax}} \| (M_{\omega_0} - M_{\tilde{\omega}}) \tilde{\theta} \| \quad (10) $$

$$ \text{under} \quad \sum_{e=1}^{|E|} d_e \cdot \pi(\omega_e, \tilde{\omega}_e) \le B, \quad (11) $$

Problem 2 is NP-hard, with an optimal solution complexity of $O(6^{|E|})$ (see Appendix A). The objective function and constraints are nonlinear and related to the Knapsack problem. Preliminary tests with off-the-shelf solvers on real cycling networks (Section VI) showed that they were too slow and failed to converge for large networks. To address this, we developed the MLCC (Maximize Largest Connected Component) algorithm, which approximates the solution with a reduced complexity of $O(|E||V|^4)$. For simplicity, its solution is still denoted as $\omega^*$.

## A. MLCC algorithm

The concept is to systematically update edges, prioritizing the expansion of sub-networks featuring the largest connected component with the highest CSCS. The rationality for this choice is the observation in Section III-A that $l_G$ is the only metric significantly affecting the prediction of perceived safety and comfort.

Hereafter, we call shortest CSCS path the shortest path when the basis is the geographical inverted weights $d_e \cdot \omega_{\text{DoS}(7-\text{DoS}(e))}$, where DoS($e$) as in Section II-C2. At
<figure><img src="image_8.png" /><figcaption>Fig. 6: (a) Original configuration, (b) optimal solution configuration, (c) MLCC algorithm configuration, (d) SGA configuration, (e) SGA-MLCC configuration and (f) Bayesian algorithm configuration: These configurations aim to enhance perceived safety with $i = 7$, corresponding to $\alpha_7 \approx 0.35\%$ of the total budget required for a full network upgrade ($B_{max} = 22,010€$).</figcaption></figure>

every step of the algorithm, upgrades are done according to the budget constraints. If the budget is fully used then the algorithm ends. The output is a list with the upgrades of the CSCS for each edge in E. The proposed algorithm is described below, the detailed flowchart can be found in Appendix B.

For every connected component, do:

1) Obtain a single connected component with maximum CSCS: Identify the largest connected component of edges with the highest CSCS.

1.1) If CSCS < $\omega_{DoS_6}$, then upgrade it to $\omega_{DoS_6}$;

1.2) Otherwise, if there are several connected components of $\omega_{DoS_6}$: start connecting them from largest to smallest by upgrading the connecting edges to the $\omega_{DoS_6}$ score using shortest CSCS path.

We obtain one single connected sub-network with scores $\omega_{DoS_6}$ referred to as $\hat{C}$.

2) Enlarge $\hat{C}$ with lower CSCS connected components: Denote $C_{\tilde{\gamma}}$ the largest connected component with highest score $\tilde{\gamma} < \omega_{DoS_6}$. Find the shortest CSCS path between $\hat{C}$ and $C_{\tilde{\gamma}}$, and upgrade the edges along this path. Then upgrade edges of $C_{\tilde{\gamma}}$ to the $\omega_{DoS_6}$. This process progressively enlarges $\hat{C}$ at each step. Iterate this step by considering the next largest connected component $C_{\tilde{\gamma}}$ with the highest $\tilde{\gamma} < \omega_{DoS_6}$. This iterative process continues until the budget is fully utilized or all edges are upgraded to their maximum CSCS level.

## V. BENCHMARK EXAMPLE

Our goal now is to compare the performance of our MLCC algorithm, developed to tackle Problem 2, against a straightforward benchmark example where the optimal solution is determined by exhaustively evaluating all possible combinations. Additionally, we will compare it with three solvers to measure the distances to optimality.

Let $B = \alpha \cdot B_{max}$, be the available budget for optimization, with $B_{max}$ being the budget required to reach the FS graph (with corresponding prediction $\hat{y}_{FS}$), and $\alpha \in [0, 1]$. The cost per meter to upgrade the infrastructure along an edge is set to reflect different construction costs between levels, following Cerema's cost [42] studies.

We select 10 logarithmically spaced values of $\alpha$ between 0.01 and 1 to examine the behavior of our analysis near zero.

$$ \alpha_i = 10^{(a+i \cdot \frac{b-a}{9})}, \quad i \in \{0, 1, \dots, 9\}, \quad (12) $$

where

$$ a = \log_{10}(0.01), \quad b = \log_{10}(1). \quad (13) $$

In Fig. 6a, we display our benchmark example consisting of 10 nodes and 11 edges. Figure 6 (b)-(f) compare the configurations derived from: (1) the optimal solution obtained by evaluating all 138,240 possible combinations via brute force, (2) our MLCC algorithm, (3) a standard genetic algorithm (SGA) [43], (4) the SGA initialized with the output of the MLCC algorithm (SGA-MLCC), and (5) a Bayesian optimization package in Python [44], all designed to approximate the optimal solution within a reasonable time frame. These comparisons are made to approximate the optimal solution for safety using approximately one third of the budget ($\alpha_7 \approx 0.35$). While our MLCC algorithm does not precisely reproduce the optimal solution, it exhibits strong similarities with all other algorithms. Notably, all solutions prioritize maximizing the connectivity of $\omega_{DoS_6}$ score segments rather than upgrading isolated links. This is because enhancing a single, unconnected segment to a high $\omega_{DoS_6}$ scores would inefficiently allocate the budget without significantly improving perceived safety and comfort across the network, demonstrating the MLCC algorithm's strong performance in delivering a practical and computationally efficient solution for larger networks, while acknowledging that the exact optimality gap remains uncertain. In Fig. 7a, we illustrate the improvements in normalized perceived safety and comfort across four different values of $\alpha$. At $\alpha_7$, both the optimal solution and the Bayesian algorithm achieve approximately a 29% improvement in perceived safety and comfort, whereas our algorithm achieves around 26%. Although our algorithm does not reach the optimal level, it provides a favorable outcome.

Fig. 7b shows the evolution of SGA and SGA-MLCC over 80 generations, respectively. This figure demonstrates that, in most cases, SGA-MLCC approaches the optimal solution more closely than the standard SGA. This suggests that using the MLCC results as the initial population for the SGA is a beneficial strategy. Finally, Table V presents the computation times, showing that the MLCC operates significantly faster, making it especially beneficial for large-scale, real-world cycling networks.
<figure><img src="image_9.png" /><figcaption>Fig. 7: (a) Results of solving Problem 2 using the optimal, MLCC, SGA, SGA-MLCC, and Bayesian algorithms on the benchmark network. The percentage improvement is calculated as $\% = |\hat{y}_{\omega_0} - \hat{y}(\omega^*)| \times 100/|\hat{y}_{FS} - \hat{y}_{\omega_0}|$. (b) Performance evolution of the SGA and SGA-MLCC algorithms over generations for safety with (c) providing the legend. $B_{max} = 22, 010 \text{ €}$.</figcaption></figure>

<table><caption>TABLE V: Calculation time for the benchmark example</caption><thead><tr><th rowspan="2">Algorithm</th><th colspan="9">Time</th></tr><tr><th>i = 0</th><th>i = 1</th><th>i = 2</th><th>i = 3</th><th>i = 4</th><th>i = 5</th><th>i = 6</th><th>i = 7</th><th>i = 8</th><th>i = 9</th></tr></thead><tbody><tr><td>Optimal</td><td>4.96 s</td><td>4.33 s</td><td>4.35 s</td><td>4.46 s</td><td>6.0 s</td><td>11.19 s</td><td>32.62 s</td><td>1.63 m</td><td>3.04 m</td><td>4.7 m</td></tr><tr><td>MLCC</td><td>0.014 s</td><td>0.011 s</td><td>0.011 s</td><td>0.011 s</td><td>0.011 s</td><td>0.011 s</td><td>0.011 s</td><td>0.014 s</td><td>0.012 s</td><td>0.011 s</td></tr><tr><td>SGA</td><td>6.7 s</td><td>6.99 s</td><td>7.28 s</td><td>8.39 s</td><td>8.46 s</td><td>8.72 s</td><td>7.58 s</td><td>8.91 s</td><td>9.89 s</td><td>10.6 s</td></tr><tr><td>SGA-MLCC</td><td>7.8 s</td><td>8.2 s</td><td>8.35 s</td><td>8.6 s</td><td>7.45 s</td><td>7.69 s</td><td>9.18 s</td><td>9.22 s</td><td>10.16 s</td><td>10.82 s</td></tr><tr><td>Bayesian</td><td>1.35 m</td><td>1.45 m</td><td>1.45 m</td><td>1.63 m</td><td>1.88 m</td><td>1.98 m</td><td>1.96 m</td><td>1.89 m</td><td>1.96 m</td><td>2.03 m</td></tr></tbody></table>

## VI. SIOUX FALLS AND GRENOBLE CYCLING NETWORK

To illustrate a well-known transportation research example, we use the Sioux Falls network (24 nodes, 38 edges) [45] with randomly assigned DoS values (Fig. 9).

<figure><img src="image_10.png" /><figcaption>Fig. 9: Sioux Falls cycling network</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Fig. 10: Cycling network of Grenoble, France, after being upgraded using MLCC with $\alpha_7 \approx 0.35$.</figcaption></figure>

As network size grows, computing an optimal solution becomes infeasible due to exponential complexity. For example, evaluating one configuration takes 0.009 seconds, but testing all possibilities would take over a trillion years, highlighting the need for efficient algorithms like MLCC. Appendix C shows that MLCC performs competitively, with SGA-MLCC consistently achieving the best results. Our benchmark analysis in the previous section suggests that the algorithm is relatively close to the optimal solution, and after validating it on the well-
<table><caption>TABLE VI: The cities, the number of nodes, edges, total amount of meters and the budget required to upgrade all edges to the highest possible DoS.</caption><thead><tr><th>No</th><th>City</th><th>V</th><th>E</th><th>Length m</th><th>€ B<sub>max</sub></th></tr></thead><tbody><tr><td>1</td><td>Angers</td><td>4118</td><td>4986</td><td>546854 m</td><td>307,230,491€</td></tr><tr><td>2</td><td>Annecy</td><td>2286</td><td>2628</td><td>301133 m</td><td>170,461,482€</td></tr><tr><td>3</td><td>Bordeaux</td><td>3757</td><td>4816</td><td>547433 m</td><td>291,560,346€</td></tr><tr><td>4</td><td>Chambery</td><td>1184</td><td>1244</td><td>128491 m</td><td>64,125,336€</td></tr><tr><td>5</td><td>Dunkerque</td><td>2465</td><td>3117</td><td>376446 m</td><td>196,435,124€</td></tr><tr><td>6</td><td>Grenoble</td><td>3539</td><td>5065</td><td>415213 m</td><td>236,652,715€</td></tr><tr><td>7</td><td>La Rochelle</td><td>4168</td><td>5425</td><td>489185 m</td><td>278,834,295€</td></tr><tr><td>8</td><td>Le Havre</td><td>1363</td><td>1488</td><td>371967 m</td><td>176,844,796€</td></tr><tr><td>9</td><td>Lyon</td><td>6200</td><td>9005</td><td>923783 m</td><td>58,6421,676€</td></tr><tr><td>10</td><td>Nantes</td><td>8984</td><td>11504</td><td>1106161 m</td><td>682,956,132€</td></tr><tr><td>11</td><td>Paris</td><td>17570</td><td>26664</td><td>2590580 m</td><td>1,569,036,148€</td></tr><tr><td>12</td><td>Rennes</td><td>5790</td><td>6957</td><td>732691 m</td><td>37,9182,429€</td></tr><tr><td>13</td><td>Strasbourg</td><td>4303</td><td>5066</td><td>649650 m</td><td>247,298,690€</td></tr><tr><td>14</td><td>Tours</td><td>4558</td><td>6053</td><td>591725 m</td><td>343,172,657€</td></tr></tbody></table>

known Sioux-Falls benchmark, we now extend our approach to a real case: the Grenoble cycling network.

Fig. 11a compares algorithm performance for the Grenoble network, showing that MLCC consistently outperforms others. Fig. 11b tracks SGA and SGA-MLCC performance over 80 generations, revealing that SGA-MLCC fails to surpass MLCC and ultimately converges to the same solution. Despite parameter adjustments and initial population variations, MLCC consistently yields the best performance. Table IV further demonstrates MLCC's advantage, achieving the best results with significantly lower computation time. This underscores its efficiency in solving large network problems, making it the preferred choice over heuristic methods. Fig. 10 visualizes the upgraded Grenoble cycling network using MLCC with $\alpha_7$. Extending this approach, MLCC is applied to optimize cycling networks across 14 French cities.

## VII. STUDY CASE: FOURTEEN FRENCH MUNICIPALITIES

In Fig.13, we present the results of the MLCC algorithm, highlighting outcomes for both safety and comfort across various cities. The parameterization specified in Eq.(8) leads to notable similarities among the cities. Cities such as Annecy and La Rochelle show significant improvements, approaching nearly 80% for $\alpha_8 \approx 0.6$. This is mainly due to the presence of many disconnected components in their cycling networks. The enhancement of the largest connected component has a particularly substantial impact, with almost complete network coverage leading to these high levels of perceived safety and comfort.

Conversely, cities like Angers, Bordeaux, Dunkerque, Nantes, Rennes, and Tours exhibit relatively minor improvements in safety and comfort. These networks, though containing high-quality infrastructure (high-CSCS), are often scattered and sparse, so a significant portion of the budget is spent on connecting these dispersed high-CSCS components within the larger connected component, indicating possibly inadequate planning where high-CSCS roads are intermixed with less safe and inconvenient routes.

Cities such as Grenoble, La Rochelle, Le Havre, Lyon, and Paris show considerable improvements of around 5% with $\alpha_0 = 0.1$, almost because their high-CSCS components are

relatively close to each other and sufficiently large. Connecting these components to the largest high-CSCS connected component results in significant changes, suggesting effective urban cycling planning by city authorities. On the other hand, Rennes and Strasbourg show limited improvements for the smallest values of $\alpha_i$. Although these cities have a relatively large number of edges, as shown in Table VI, they also feature extensive high-CSCS connected components that are dispersed among unsafe and uncomfortable roads. This causes the algorithm to initially allocate the budget to upgrading links to connect these components, resulting in minimal immediate improvements.

These results underscore the importance of a linked urban cycling infrastructure, where high quality, connected and continuous cycleways are critical to maximizing perceived safety and comfort. The varying degrees of success between cities reflect the effectiveness of different planning strategies. In particular, cities with more connected and integrated networks in their largest connected component experience superior improvements. Consequently, this analysis provides valuable insights for urban planners. Ensuring that high-quality cycling infrastructure is widespread and well-connected can greatly enhance the cycling experience, suggesting the need for city authorities to design more strategic networks to prioritize cohesive and integrated cycling routes.

## VIII. STRENGTHS AND LIMITATIONS OF THE PROPOSED APPROACH

This paper presents a method for classifying bike lanes using OSM data, making it applicable to any city with available OSM information. It also introduces a framework for modeling and optimizing cycling network safety and comfort, along with a computationally efficient algorithm that outperforms heuristic methods in solving real-world network problems.

Despite its strengths, the approach has certain limitations. Safety and comfort predictions are based on global averages of graph metrics, which may overlook localized issues, such as problematic intersections. The model does not currently account for cyclist behavior or flow distribution, potentially leading to inefficient upgrades. Furthermore, equity considerations, including the distribution of infrastructure across socioeconomic regions and the number of potential users, are not incorporated. Addressing fairness requires integrating factors like population density and income levels, which, while crucial for a comprehensive solution, are beyond the current scope. Future research will aim to refine the framework by incorporating localized insights, cyclist behavior, and fairness considerations.

## IX. CONCLUSIONS

In this paper, we created the CSCS category based on the CycleRAP project's bicycle scoring tool to assign weights to the DoS category, with the goal of generating overall scores that more accurately reflect cyclists' perceptions. We then applied graph theory metrics to explore the fundamental topological characteristics of cycling networks. These metrics were employed to approximate and predict the perceived
<figure><img src="image_12.png" /><figcaption>Fig. 11: (a) Results of solving Problem 2 using the MLCC, SGA, SGA-MLCC, and Bayesian algorithms on the Grenoble cycling network. The percentage improvement is calculated as $\% = |\hat{y}_{\omega_0} - \hat{y}(\omega^*)| \times 100/|\hat{y}_{FS} - \hat{y}_{\omega_0}|$. (b) Performance evolution of the SGA and SGA-MLCC algorithms over generations for safety, with (c) providing the legend.</figcaption></figure>

<table><caption>TABLE VII: Calculation time for the Grenoble cycling network.</caption><thead><tr><th rowspan="2">Algorithm</th><th colspan="10">Time</th></tr><tr><th>i = 0</th><th>i = 1</th><th>i = 2</th><th>i = 3</th><th>i = 4</th><th>i = 5</th><th>i = 6</th><th>i = 7</th><th>i = 8</th><th>i = 9</th></tr></thead><tbody><tr><td>MLCC</td><td>0.48 s</td><td>0.48 s</td><td>0.53 s</td><td>0.62 s</td><td>0.82 s</td><td>0.9 s</td><td>1.28 s</td><td>3.4 s</td><td>7.88 s</td><td>40.0 s</td></tr><tr><td>SGA</td><td>0.46 m</td><td>0.45 m</td><td>0.47 m</td><td>0.46 m</td><td>0.51 m</td><td>1.62 m</td><td>0.34 hr</td><td>1.10 hr</td><td>1.23 hr</td><td>1.20 hr</td></tr><tr><td>SGA-MLCC</td><td>0.49 m</td><td>0.53 m</td><td>0.99 m</td><td>2.74 m</td><td>6.82 m</td><td>0.28 hr</td><td>0.43 hr</td><td>1.02 hr</td><td>1.34 hr</td><td>1.54 hr</td></tr><tr><td>Bayesian</td><td>1.03 hr</td><td>1.01 hr</td><td>1.02 hr</td><td>1.01 hr</td><td>1.34 hr</td><td>1.46 hr</td><td>1.53 hr</td><td>2.48 hr</td><td>2.02 hr</td><td>2.06 hr</td></tr></tbody></table>

safety and comfort levels reported by cyclists through surveys. Subsequently, we introduced a topology optimization problem focused on maximizing the predicted levels of safety and comfort while adhering to budgetary constraints.

Considering the complexity of this optimization problem and the suboptimal performance of the heuristics used in this work on large networks, we proposed a reduced-complexity MLCC algorithm tailored for topology optimization. Our methodology provides a comprehensive quantitative framework to aid decision-making processes in urban planning and resource allocation. It was applied to 14 cities in France, utilizing real data from cyclists. The results show significant improvements with reasonable investment in cities where segments of the network with high CSCS are well-connected and not isolated or scattered.

Future work will improve safety and comfort predictions by incorporating bicycle crash data and local graph metrics. Dimensionality reduction techniques will be explored to enhance solver efficiency while maintaining predictive accuracy. Additionally, we aim to integrate local insights, cyclist behavior, and fairness considerations into the modeling and optimization framework.

## ACKNOWLEDGMENTS

This work was done in collaboration with Project FORBAC under the reference ANR-23-PEPR-002.

## APPENDIX A

**Lemma 2.** Problem 2 in Eq. (9-11) is NP-hard with computational complexity $O(6^{|E|})$.

*Proof.* For the safe of convenience, let us define $j_e \in \mathcal{R}$, where $\mathcal{R} = \{\omega_{DoS_i} - \omega_{DoS_i} | \omega_{DoS_i} \in \mathcal{K}, \tilde{i} \ge i \in \{1, \dots, 6\}\}$, then, introducing the binary variables:

$$x_{j_e, \tilde{\omega}_e - \omega_e} = \begin{cases} 1 & \text{if } j_e = \tilde{\omega}_e - \omega_e, \\ 0 & \text{otherwise,} \end{cases} \quad (14)$$

Problem 2 can be written as:

$$\omega^* = \underset{\tilde{\omega} \in \Omega}{\operatorname{argmax}} \quad ||\hat{y}_{\omega_0} - \hat{y}(\tilde{\omega})|| \quad (15)$$

$$\text{under} \quad \sum_{e=1}^{|E|} \sum_{j_e \in \mathcal{R}} d_e \cdot \pi(\omega_e, \tilde{\omega}_e) \cdot x_{j_e, \tilde{\omega}_e - \omega_e} \le B. \quad (16)$$
<figure><img src="image_13.png" /><figcaption>Fig. 13: Results of the optimization problem (MLCC algorithm) for safety (top) and comfort (bottom) for logarithmically spaced values of α. % = |ŷω₀ − ŷ(ω*)| × 100/|ŷFS − ŷω₀|.</figcaption></figure>

This means picking upgrades among the set of all possible
upgrades while respecting the budget constraint. This is a non-
linear 0-1 Knapsack problem, hence proving the NP-hardness.
Given that the graph theory metrics involved in the NNLS
are nonlinear, the problem essentially becomes combinatorial.
Computing all possible combinations until finding the optimal
solution would demand $O(6^{|E|})$ in the worst case, as we have
6 different CSCS.

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

**Lemma 3.** *MLCC algorithm is* $O(|E||V|^4)$.

Proof. The more complex operations for MLCC algorithm involve computing the largest connected component and finding the shortest paths between them. Constructing a connected component utilizes the depth-first search algorithm, which has a computational complexity of $O(|V| + |E|)$ [46]. However, for each component, the function traverses all nodes within the component, and for each node, it iterates over all its neighbors to verify whether they belong to the component according to their CSCS. Each of these operations is executed at worst in $O(|V|)$, then it would take at most $O(|V|^3 + |V||E|)$. Finding the shortest paths is solved in $O(|V|^2)$ because it uses Dijkstra's algorithm for weighted graphs [47], as in our case. Considering that in the worst scenario, each set of connected components contains $\lfloor V \rfloor/2$ elements and the process can occur at most $\lfloor E \rfloor/2$ times, the overall time complexity of this operation is at most $O(|E||V|^4)$. Consequently, the overall time complexity of the function is dominated by the $O(|E||V|^4)$ term. □

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

APPENDIX B

The flowchart in Fig. 14 refers to the MLCC algorithm
described in Section IV-A, keeping the same notation and
meaning for $\hat{C}$, $C_\gamma$, and CC for connected component.

<figure><img src="image_16.png" /><figcaption>Fig. 14: Flowchart of the MLCC algorithm.</figcaption></figure>
APPENDIX C

In Fig. 15, we present the results of the optimization algorithms for the Sioux Falls benchmark, the evolution of the genetic algorithms and Table VIII shows the computational time for each one.

<figure><img src="image_17.png" /><figcaption>Fig. 15: (a) Results of solving Problem 2 using the MLCC, SGA, SGA-MLCC, and Bayesian algorithms on the Sioux Falls cycling network. The percentage improvement is calculated as $\% = |\hat{y}_{\omega_0} - \hat{y}(\omega^*)| \times 100/|\hat{y}_{FS} - \hat{y}_{\omega_0}|$. (b) show the performance evolution of the SGA and SGA-MLCC algorithms over generations for safety with (c) providing the legend. And $B_{max} = 194,848€$.</figcaption></figure>

<table><caption>TABLE VIII: Calculation time for the Sioux Falls cycling network.</caption><thead><tr><th rowspan="2">Algorithm</th><th colspan="9">Time</th></tr><tr><th>i = 0</th><th>i = 1</th><th>i = 2</th><th>i = 3</th><th>i = 4</th><th>i = 5</th><th>i = 6</th><th>i = 7</th><th>i = 8</th><th>i = 9</th></tr></thead><tbody><tr><td>MLCC</td><td>0.08 s</td><td>0.09 s</td><td>0.08 s</td><td>0.07 s</td><td>0.08 s</td><td>0.1 s</td><td>0.1 s</td><td>0.1 s</td><td>0.14 s</td><td>0.14 s</td></tr><tr><td>SGA</td><td>25.66 s</td><td>13.04 s</td><td>12.98 s</td><td>27.6 s</td><td>14.74 s</td><td>17.91 s</td><td>29.0 s</td><td>20.96 s</td><td>23.4 s</td><td>40.14 s</td></tr><tr><td>SGA-MLCC</td><td>13.19 s</td><td>12.54 s</td><td>12.74 s</td><td>15.07 s</td><td>14.33 s</td><td>15.63 s</td><td>17.12 s</td><td>20.12 s</td><td>23.57 s</td><td>27.32 s</td></tr><tr><td>Bayesian</td><td>4.1 m</td><td>4.03 m</td><td>4.06 m</td><td>5.34 m</td><td>5.96 m</td><td>6.01 m</td><td>5.67 m</td><td>5.69 m</td><td>6.25 m</td><td>6.42 m</td></tr></tbody></table>

REFERENCES

[1] Jan Garrard, Chris Rissel, and Adrian Bauman. Health benefits of cycling. *City cycling*, 31:31–56, 2012.

[2] Thomas Götschi, Jan Garrard, and Billie Giles-Corti. Cycling as a part of daily life: a review of health perspectives. *Transport Reviews*, 36(1):45–71, 2016.

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

[4] Brendan M Lawrence, Jennifer A Oxley, David B Logan, and Mark R Stevenson. 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, 2018.

[5] Joseph Broach, Jennifer Dill, and John Gliebe. Where do cyclists ride? a route choice model developed with revealed preference gps data. *Transportation Research Part A: Policy and Practice*, 46(10):1730–1740, 2012.

[6] John Pucher, Ralph Buehler, Dafna Merom, and Adrian Bauman. Walking and cycling in the united states, 2001–2009: evidence from the

national household travel surveys. *American journal of public health*, 101(S1):S310–S317, 2011.

[7] John Pucher and Ralph Buehler. Cycling towards a more sustainable transport future. *Transport reviews*, 37(6):689–694, 2017.

[8] International Road Assessment Programme. Cyclerap, 2024. Accessed: 2024-07-10.

[9] Katie Crist, Jasper Schipperijn, Sherry Ryan, Bruce Appleyard, Suneeta Godbole, and Jacqueline Kerr. Fear factor: level of traffic stress and gps assessed cycling routes. *Journal of Transportation Technologies*, 9(01):88457, 2019.

[10] Yang Bian, Ling Li, Huan Zhang, Dandan Xu, Jian Rong, and Jiachuan Wang. Categorizing bicycling environment quality based on mobile sensor data and bicycle flow data. *Sustainability*, 13(8):4085, 2021.

[11] Tiziana Campisi, Giovanna Acampa, Giorgia Marino, and Giovanni Tesoriere. Cycling master plans in italy: The i-bim feasibility tool for cost and safety assessments. *Sustainability*, 12(11):4723, 2020.

[12] Manuel Campero Jurado, Carlos Canudas de Wit, Giovanni De Nunzio, and Rémi Mourgues. A general graph-based optimization framework for improving safety and comfort in cycling networks. In *Proceedings of the 27th IEEE International Conference on Intelligent Transportation Systems*, 2024. Accepted for publication.

[13] Bettina Schröter, Sebastian Hantschel, Caroline Koszowski, Ralph
Buehler, Paul Schepers, Johannes Weber, Rico Wittwer, and Regine Gerike. Guidance and practice in planning cycling facilities in europe—an overview. *Sustainability*, 13(17):9560, 2021.

[14] Sergio Nesmachnow and Silvina Hipogrosso. Assessment of sustainable mobility initiatives developed in montevideo, uruguay. *Urban Science*, 8(2):52, 2024.

[15] Mahmoud Mesbah, Russell Thompson, and Sara Moridpour. Bilevel optimization approach to design of network of bike lanes. *Transportation research record*, 2284(1):21–28, 2012.

[16] Heather Lauren Smith and Ali Haghani. A mathematical optimization model for a bicycle network design considering bicycle level of service. Technical report, University of Maryland, College Park, 2012.

[17] Mads Paulsen and Jeppe Rich. Societally optimal expansion of bicycle networks. *Transportation Research Part B: Methodological*, 174:102778, 2023.

[18] Jennifer Duthie and Avinash Unnikrishnan. Optimization framework for bicycle network design. *Journal of Transportation engineering*, 140(7):04014028, 2014.

[19] Christoph Steinacker, David-Maximilian Storch, Marc Timme, and Malte Schröder. Demand-driven design of bicycle infrastructure networks for improved urban bikeability. *Nature computational science*, 2(10):655–664, 2022.

[20] Antonio Mauttone, Gonzalo Mercadante, María Rabaza, and Fernanda Toledo. Bicycle network design: model and solution algorithm. *Transportation research procedia*, 27:969–976, 2017.

[21] Jisoon Lim, Kevin Dalmeijer, Subhrajit Guhathakurta, and Pascal Van Hentenryck. The bicycle network improvement problem. *Journal of Transportation Engineering, Part A: Systems*, 148(11):04022095, 2022.

[22] CS Shui and WL Chan. Optimization of a bikeway network with selective nodes. *Sustainability*, 11(23):6531, 2019.

[23] Bruno Scalzo Dees, Yao Lei Xu, Anthony G Constantinides, and Danilo P Mandic. Graph theory for metro traffic modelling. In *2021 international joint conference on neural networks (IJCNN)*, pages 1–5. IEEE, 2021.

[24] Samar Elaraby and Sherif M Abuelenin. Connectivity analysis of directed highway vehicular ad hoc networks using graph theory. *International Journal of Communication Systems*, 34(5):e4745, 2021.

[25] Armando Di Nardo, Carlo Giudicianni, Roberto Greco, Manuel Herrera, and Giovanni F Santonastaso. Applications of graph spectral techniques to water distribution network management. *Water*, 10(1):45, 2018.

[26] Xiaofan Yang, Yuanrui Zhu, Jing Hong, Lu-Xing Yang, Yingbo Wu, and Yuan Yan Tang. The rationality of four metrics of network robustness: A viewpoint of robust growth of generalized meshes. *PloS one*, 11(8):e0161077, 2016.

[27] Ali Sydney, Caterina Scoglio, Mina Youssef, and Phillip Schumm. Characterising the robustness of complex networks. *International Journal of Internet Technology and Secured Transactions*, 2(3-4):291–320, 2010.

[28] Tanya Araújo and R Vilela Mendes. Function and form in networks of interacting agents. *arXiv preprint nlin/0009018*, 2000.

[29] Mohamed Bayoumi Kamel and Tarek Sayed. The impact of bike network indicators on bike kilometers traveled and bike safety: A network theory approach. *Environment and Planning B: Urban Analytics and City Science*, 48(7):2055–2072, 2021.

[30] Meisam Akbarzadeh, Syed Sina Mohri, and Ehsan Yazdian. Designing bike networks using the concept of network clusters. *Applied network science*, 3:1–21, 2018.

[31] Le baromètre des villes cyclables. https://barometre.parlons-velo.fr/. Accessed on January 17, 2024.

[32] Jonathan Nolan, James Sinclair, and Jim Savage. Are bicycle lanes effective? the relationship between passing distance and road characteristics. *Accident Analysis & Prevention*, 159:106184, 2021.

[33] NeCS Team. Gtlville: Grenoble traffic lab. https://gtlville.inrialpes.fr/, 2024. Accessed: 2024-07-22.

[34] Edsger W Dijkstra. A note on two problems in connexion with graphs. In *Edsger Wybe Dijkstra: His Life, Work, and Legacy*, pages 287–290. Numerische Mathematik, 2022.

[35] Maaza C Mekuria, Peter G Furth, and Hilary Nixon. Low-stress bicycling and network connectivity. *San José, CA*, 2012.

[36] Richard H Browne. The t-test p value and its relationship to the effect size and p (x> y). *The American Statistician*, 64(1):30–33, 2010.

[37] Åke Björck. Least squares methods. *Handbook of numerical analysis*, 1:465–652, 1990.

[38] Jim Frost. T-distribution table. https://statisticsbyjim.com/hypothesis-testing/t-distribution-table/, 2024. Accessed: 2024-10-03.

[39] Neha Patki, Roy Wedge, and Kalyan Veeramachaneni. The synthetic data vault. In *2016 IEEE International Conference on Data Science and Advanced Analytics (DSAA)*, pages 399–410, 2016.

[40] Charles L Lawson and Richard J Hanson. *Solving least squares problems*. SIAM, 1995.

[41] Nick Erickson, Jonas Mueller, Alexander Shirkov, Hang Zhang, Pedro Larroy, Mu Li, and Alexander Smola. Autogluon-tabular: Robust and accurate automl for structured data. *arXiv preprint arXiv:2003.06505*, 2020.

[42] Alice Brauns, Alain Dalouche, Axel Lambert, Catherine Pilon, and Laura Youkana. Le marché aménagements cyclables. Printed document, 2024.

[43] Francesco Biscani and Dario Izzo. A parallel global multiobjective framework for optimization: pagmo. *Journal of Open Source Software*, 5(53):2338, 2020.

[44] F. Nogueira. Bayesian Optimization: Open source constrained global optimization tool for Python. URL https://github.com/fmfn/BayesianOptimization, 2014.

[45] Artem Chakirov. Sioux falls. *The Multi-Agent Transport Simulation MATSim*, pages 385–388, 2016.

[46] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. *Introduction to algorithms*. MIT press, 2022.

[47] Michael Barbehenn. A note on the complexity of dijkstra's algorithm for graphs with weighted vertices. *IEEE transactions on computers*, 47(2):263, 1998.

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

Manuel Campero Jurado received the B.S. degree in applied mathematics in 2019 and the M.S. in 2021 degree in mathematics from the Autonomous University of the State of Hidalgo, Mexico. He is currently pursuing the PhD. degree from the Grenoble Institute of Technology, Grenoble, France. His research interests include modeling and optimization of safety networks for cyclists.

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

Carlos Canudas de Wit received his B.S. in electronics and communications from the Monterrey Institute of Technology, Mexico, in 1980, and his M.S. and Ph.D. in automatic control from the Grenoble Institute of Technology, France, in 1984 and 1987, respectively. He is a Directeur de recherche (Senior Researcher) at CNRS, Grenoble, leading the NeCS Team (GIPSA-Lab & INRIA) on networked controlled systems. An IFAC Fellow, he has served as Associate Editor for multiple IEEE journals and was President of the European Control Association (2013–2015). He held the ERC Advanced Grant Scale-FreeBack (2016–2021). His research focuses on electric vehicles, optimal control, traffic modeling, and large-scale networks.

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

Giovanni De Nunzio received the B.S. and M.S. degrees in information and automation engineering from the University of L'Aquila, Italy, in 2007 and 2010, respectively, and the Ph.D. degree in automatic control from the Grenoble Institute of Technology (Grenoble INP), France, in 2015. He is currently a Research Engineer and an Research and Innovation Project Leader with IFP Energies nouvelles, Lyon, France. His research activities focus on modeling and control of transportation and mobility systems, advanced driver-assistance systems, graph theory, optimization, and data science.