# A General Graph-based Optimization Framework for Improving Safety and Comfort in Cycling Networks

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

**Abstract**— In this work, graph theory metrics are used to analyze the fundamental topological features of cycling networks in various municipalities throughout France. These metrics serve as a basis for approximating and predicting the perceived safety and comfort levels reported by cyclists in these areas through surveys. Expanding on this relationship, we formulate a topology optimization problem aimed at maximizing the predicted perceived safety and comfort while adhering to budgetary constraints. Due to the complexity of this problem, we propose a novel topology optimization algorithm. This innovative approach aligns graph theory concepts with real-world indicators, providing a general quantitative framework to support decision making in urban planning and resource allocation.

**Index Terms**— Cycling transport network, graph theory, safety, comfort, optimization.

## I. INTRODUCTION

Despite significant efforts by public authorities to promote cycling as an alternative to car use for short distances, safety and comfort concerns still hinder bicycle (bike) adoption [1]. Reducing car speed limits in shared lanes is a common approach but may not be sufficient [2]. Infrastructure that separates bike and car lanes is more effective in enhancing safety and comfort [3]. Empirical evidence shows that cities with extensive cycling infrastructure have higher levels of bike commuting [4]. Given budget constraints for infrastructure development, it is crucial to determine where to allocate resources to maximize cyclist safety and comfort. This paper addresses this issue.

The problem at hand has been addressed in the literature along various directions. One common approach for bike network optimization resorts to maximization of travel distance. In [5] authors have expanded the cycling networks by maximizing the overall societal benefit-cost ratio of adding bicycle infrastructure. This involves assessing anticipated benefits versus construction and maintenance costs to determine economic feasibility. Another approach consists of increasing the network graph connectivity. In [6], an optimization framework is proposed to minimize the cost of network improvements, focusing on enhancing connectivity by ensuring that all origin-destination pairs are connected with paths meeting specified criteria for bicycling level of service. However, it is unclear whether these changes

are best suited to increase cyclists' perception of safety or comfort. Other approaches resort to graph theoretical tools. For instance, in [7], graph theory metrics are utilized to examine their positive or negative correlation with the combined bike-vehicle traffic, and a method for designing a bike network based on network clustering is proposed. Nevertheless, it is often assumed that topological changes in bike lanes cause positive changes in the metrics and thus in the network, overlooking the complex non-monotonic behavior of graph theory metrics.

In this study, we use graph theory metrics to analyze the core features of cycling networks in various French municipalities. These metrics help to estimate and predict cyclists' perceived safety and comfort levels through surveys (illustration example in Fig. 1). This work proposes a topology optimization problem to enhance these perceptions within budget limits, integrating graph theory with practical benchmarks for urban planning.

The paper makes three key contributions. First, it introduces a new classification system for bike lanes using OpenStreetMap (OSM) data. Second, it proposes graph metrics (node strength and largest connected component) and investigates the correlation between these metrics and perceived safety and comfort, creating a model reflecting cyclists' perceptions. Finally, it presents a topology optimization algorithm to maximize perceived safety and comfort, applicable to any geographical area. This framework, tested in eleven French cities, effectively improves perceived safety and comfort while balancing precision and computational efficiency.

<figure><img src="image_1.png" /><figcaption>Fig. 1: Perceived cycling safety and comfort data in Grenoble, France (see Section II).</figcaption></figure>

<footnote n="1">¹Univ. Grenoble Alpes, Inria, 38334 Montbonnot Cedex - France
manuel.campero-jurado@inria.fr</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, remi.mourges@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>
<table><caption>TABLE I: Classification of Cycling Infrastructure based on degree of separation (DoS).</caption><thead><tr><td>Geovelo</td><td>DoS</td><td>Description</td></tr></thead><tbody><tr><td>7, 14</td><td>6</td><td>Cycleways exclusively reserved for bikes, physically separated from cars.</td></tr><tr><td>2, 10, 11, 15, 16, 17, 20</td><td>5</td><td>Cycleways separated from motor vehicles but shared with pedestrians.</td></tr><tr><td>18, 19</td><td>4</td><td>Bus lanes or central car lanes where cyclists have priority.</td></tr><tr><td>1, 3, 4, 6</td><td>3</td><td>Roads with painted bike lanes.</td></tr><tr><td>5, 8</td><td>2</td><td>Shared roads allow cycling alongside motor vehicles, sometimes with cyclist priority.</td></tr><tr><td>9, 12, 13, 21, 22</td><td>1</td><td>Roads where cycling is allowed, no designated lanes, shared with cars (speed limit: 30 km/h).</td></tr></tbody></table>

<figure><img src="image_2.png" /><figcaption>Fig. 2: Cycling network of Grenoble, France. The degree of separation (DoS) of the cycling infrastructure from motorized vehicles is indicated in ascending order from 1 to 6.</figcaption></figure>

## II. NETWORK DATA AND FEATURES

In this section, we introduce the main data sources and tools used in the following to analyze cyclability and topological characteristics of cycling networks. In particular, we present the reference safety and comfort data relative to cycling networks as obtained from field surveys. Then, we introduce our bike lane classification used to assign weights to each segment of the network, as well as the graph metrics that we will attempt to correlate with the reference safety and comfort data, via a prediction model.

### A. Perceived safety and comfort data

We gather perceived safety and comfort data from the Baromètre Vélo (Bicycle Barometer) project [8], which operates as a satisfaction questionnaire aimed at assessing and promoting bicycle usage in different cities and regions across France. This questionnaire collects users' perceptions regarding various aspects of their cycling environment every two years.

Designed to accommodate cyclists of varying skill levels, the survey comprises around thirty questions distributed across five categories: general impressions, safety, comfort, cycling significance, and parking. Integrating a cartographic tool enables the geo-referencing of responses, facilitating the identification of high-risk areas within surveyed municipalities.

Participants rate questions on a scale from worst to best, offering insights into cyclists' perceived feelings and infrastructure quality. Responses to the questionnaires are not restricted to residents of the municipality, as the survey is open to all individuals who frequently travel there. At the end, they generate global scores for the municipalities, and among these values are comfort and safety, which we define as perceived safety and comfort. In Fig. 1, we present an illustration of the Baromètre Vélo for the city of Grenoble. Global scores, obtained from 3009 respondents, are depicted on the left side, with red dots indicating priority sites for improvement, green dots signifying perceived improvements over the past two years, and blue dots indicating desired bike parking facilities. While this paper focuses solely on global scores, future work will explore the additional information provided by the survey.

### B. Bike lane classification

Our categorization of OSM road segments is inspired by Geovelo<fnref n="1" />, a platform for cyclist route planning, which offers a more detailed classification of twenty-two types of bike lanes. However, our method simplifies this into six categories by considering degree of separation (DoS) of the cycling infrastructure from the one used by motorized vehicles as the main classification criterion. This choice was driven by the intuition that roads with dedicated bicycle lanes are considered safer and more comfortable by cyclists than those shared with vehicles [9]. Our classification methodology is publicly available online<fnref n="2" /> for reference. In Table I, we offer a concise summary of the road types associated with each category and their alignment with the Geovelo classification. The numbers in the Geovelo classification are assigned based on alphabetical sorting. The illustration in Fig. 2 for Grenoble, France, exemplifies our categorization.

### C. Graph metrics

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 DoS 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 $\mathcal{H}$, we will explicitly write its sets of nodes, edges, and weights as $V(\mathcal{H})$, $E(\mathcal{H})$, and $W(\mathcal{H})$, respectively.

Evidently, the edge weights in terms of DoS give extremely local information and would hardly correlate with perceived safety or comfort at network-level. To address this limitation, we utilize graph theory metrics to assess safety and comfort on a broader network scale.

The graph theory metrics utilized in this study must exhibit a crucial property: monotonic behavior. Specifically,

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

<footnote n="2">²https://github.com/leunamCampero/ITSC2024</footnote>
if edges move from one DoS level to a higher one, we expect these metrics to show either increasing or non-decreasing trends. The choice of the two proposed metrics is supported by a previous Principal Component Analysis (PCA) study, where they demonstrated a positive correlation with perceived safety and comfort. This makes them suitable as foundational features for our safety-comfort prediction model, while fulfilling the monotonic property and offering intuitive interpretations within real networks. These metrics focus on node values and connected paths, respectively.

1) **Node strength:** In weighted graphs, the analogous concept to node degree is node strength, which quantifies the strength of connections a node possesses. In our context, since edge weights correspond to DoS, node strength provides a local measure where a high value indicates a safer and more comfortable intersection for cyclists. As already mentioned, the hypothesis is that the aggregate of node strengths across the entire graph (i.e. graph strength) may show high correlation with perceived safety and comfort at network level. Graph strength allows us to compute a global value derived from the local measures at individual nodes. Hereafter, the subscript FS denotes a metric definition equivalent to the original, but under the assumption of a hypothetical fully safe-comfortable (FS) network, where all edges have a DoS of 6. We employ this FS network as a reference to normalize the metrics.

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) **Largest connected component:** This metric operates on the assumption that individuals favor networks featuring extensive connected paths with high DoS values, as opposed to networks where roads with high DoS values are scattered among roads with low DoS values. Then, our metric is computed as the ratio of two quantities: 1) the cumulative geographical weight of edges within the largest CC, and 2) an equivalent definition in the FS graph.

Formally, let $CG$ be the set of CCs of $G$ sorted from the smallest CC to the largest one in non-decreasing order, and let $C_\gamma$ be the set of edges with DoS greater or equal to $\gamma$ with $\gamma \in \{2, \dots, 6\}$ of a connected component $C \in CG$. Let $H_\gamma$ be the largest connected graph induced by $C_\gamma$. Then we define:

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

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

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

where $\alpha_1 = \sum_{i_1=2}^6 \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 serve to assign greater significance to the larger CC.

### III. MODEL DESIGN

Let $\tilde{M} \in \mathbb{R}^{11 \times 2}$ be the metrics matrix formed by the columns $s_G, l_G$ of Table II. The vectors $y_s \in \mathbb{R}^{11}$ and $y_c \in \mathbb{R}^{11}$ gather the data from the perceived safety and comfort obtained from Baromètre Vélo on 11 cities. 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, \qquad (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}^{11}$ 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 this aim, we introduce the set of graphs isomorphic to $G$ but with edges having a DoS $\omega_{\tilde{G}}$ at least equal to that of the respective 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, l_G] \in \mathbb{R}^{1 \times 2}.$$

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}} \left\| f(\tilde{M}, \theta) - y \right\|^2 \qquad (2)$$

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

$$f_c(m_G, \theta_c) \le f_c(m_{\tilde{G}}, \theta_c). \qquad (4)$$

where Eq. (3)–(4) serve the purpose of ensuring the monotonous non-decreasing behavior of these models. Problem 1 is a functional optimization problem. Optimizing over a finite-dimensional function space (e.g., polynomials of degree up to a certain bound) may be simpler than optimizing over an infinite-dimensional function space (e.g., functions defined on an interval or functions that satisfy certain boundary conditions). For these reasons, we restrict our investigation to polynomials with degree one.
<table><caption>TABLE II: The values of $s_G$ and $l_G$ for eleven 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>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.4253</td><td>0.1054</td><td>0.42</td><td>0.484</td></tr><tr><td>2</td><td>Annecy</td><td>0.3348</td><td>0.0523</td><td>0.448</td><td>0.552</td></tr><tr><td>3</td><td>Bordeaux</td><td>0.4221</td><td>0.0661</td><td>0.44</td><td>0.458</td></tr><tr><td>4</td><td>Grenoble</td><td>0.3951</td><td>0.1420</td><td>0.608</td><td>0.674</td></tr><tr><td>5</td><td>Le Havre</td><td>0.5347</td><td>0.1083</td><td>0.458</td><td>0.444</td></tr><tr><td>6</td><td>Lyon</td><td>0.3297</td><td>0.1159</td><td>0.44</td><td>0.508</td></tr><tr><td>7</td><td>Nantes</td><td>0.3332</td><td>0.0508</td><td>0.47</td><td>0.522</td></tr><tr><td>8</td><td>Paris</td><td>0.3337</td><td>0.0342</td><td>0.412</td><td>0.462</td></tr><tr><td>9</td><td>Rennes</td><td>0.4322</td><td>0.0307</td><td>0.48</td><td>0.534</td></tr><tr><td>10</td><td>Strasbourg</td><td>0.5206</td><td>0.3636</td><td>0.622</td><td>0.654</td></tr><tr><td>11</td><td>Tours</td><td>0.3258</td><td>0.0685</td><td>0.43</td><td>0.468</td></tr></tbody></table>

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

### A. Linear regression model

We adopt the linear regression structure because of its simplicity. Then the proposed form for $f(\tilde{M}, \theta)$ is:

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

where $[\mathbf{1}|\tilde{M}] \in \mathbb{R}^{11 \times 3}$ 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}_{>0}^6$.

**Lemma 1.** Under the model structure Eq. (5), Problem 1 is equivalent to solve:

$$\theta^* = \underset{\theta \ge 0}{\operatorname{argmin}} \| M\hat{\theta} - y \|^2. \quad (6)$$

*Proof:* This equivalence can be easily demonstrated by observing that all selected metrics already have the non-decreasing monotonic behaviors with respect to their DoS components. Provided that all components of the $\theta$ parameter vector are positive semidefinite, then the linear regression structure inherits non-decreasing monotonic properties of the metrics. □

In current practices, the data are usually divided into training and validation sets using a ratio of 75% to 25%. By selecting 7 random samples each for safety and comfort training, the matrix $M \in \mathbb{R}^{14 \times 6}$, the vector $\theta \in \mathbb{R}_{>0}^6$ in Eq. (5), and the original data $y \in \mathbb{R}^6$ in Eq. (1) are redefined according to the 7 selected samples, with the remaining 4 samples used for validation. Problem in Eq. (6) can be treated with non-negative least squares (NNLS), which is well referenced in [10].

To enhance the conditioning of matrices for the 7-samples chosen for training by increasing the data size, we employ the Synthetic Data Vault (SDV) method for creating synthetic data [11]. The generation is based on the original data distribution, ensuring that the two datasets maintain similar statistical characteristics. Refer to the Fig. 3 for a breakdown of the complete process.

The coefficients derived from the NNLS method are

$$\theta^* = [0.41, 0.02, 0.52, 0.46, 0, 0.53]^T. \quad (7)$$

We find that the average error in predicting perceived safety is 2.13% and for comfort is 3.36%, indicating that NNLS is a simple but acceptable prediction model for our study.

## IV. NETWORK OPTIMAL DESIGN

In this section we use the previously identified linear regression model to formulate our network-upgrade optimization problem. We consider that each upgrade of the cycling infrastructure (i.e., increase in the DoS value of the considered road segment, or edge) incurs a cost per meter. Our goal is to optimize the selection of edges to be upgraded to maximize both the expected perceived safety and comfort of a specific cycling network $\mathcal{G}$ under a fixed budget $B$. Let us introduce the following notations:

* $\omega_0 = [\omega_1, \dots, \omega_e, \dots, \omega_{|E|}]$ are the original edge weights (DoS) 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 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 DoS weights,

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

with $\theta^*$ as defined in Eq. (7). $M_{\omega_0} \in \mathbb{R}^{2 \times 6}$, and $M_{\tilde{\omega}} \in \mathbb{R}^{2 \times 6}$ are matrices following similar structure as $M$. 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 3}$,

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

where $s_{\tilde{\omega}}$ and $l_{\tilde{\omega}}$ are computed in $\mathcal{G}$ with the DoS 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 (8) $$

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

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

Problem 2 is NP-hard where the objective function and constraints are non linear and finding the optimal solution has a computational complexity of $O(6^{|E|})$ because it is equivalent to the nonlinear 0-1 Knapsack problem. Hence in preliminary studies we tried some off-the-shelf solvers to solve it. However, we found that for large-scale networks they tend to be really slow and do not converge even slightly to the optimal. As a consequence, we chose to develop our own dedicated algorithm to approximate the solution that we named the MLCC (Maximize Largest CC) algorithm. We plan in future works to compare this solver to others in a more proper manner. The more complex operations for MLCC algorithm involve computing the largest CC and finding the shortest paths between them by using depth-first search algorithm (see Section IV-A), where in the worst scenario, each set of CCs contains $\frac{|V|}{2}$ elements and the process can occur at most $\frac{|E|}{2}$ times, then it has complexity of $O(|E||V|^4)$. Its solution will still be denoted as $\omega^*$ for the sake of simplicity.

### A. MLCC algorithm

The concept is to systematically update edges, prioritizing the expansion of sub-networks featuring the largest CC with the highest DoS. The rationality for this choice is due to the fact that $l_G$ is the metric that influences the most the first two principal components as can be seen in by the largest coefficients of $\theta^*$ in Eq. 7.

Hereafter, we call shortest DoS path the shortest path when the basis is the geographical inverted weights $d_e \cdot (7 - \omega_e)$. By using these geographical weight as the basis of the shortest weighted path search, this definition allows to interpret a shortest weighted path as a path where roads are related with high safety and comfort. At 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 DoS for each edge in E. The proposed algorithm is described below

For every connected component, do:

1) **Obtain a single CC with maximum DoS:** Identify the largest CC of edges with the highest DoS.

1.1) If DoS < 6, then upgrade it to DoS = 6;

1.2) Otherwise, if there are several CC of DoS = 6: start connecting them from largest to smallest by upgrading the connecting edges to the DoS = 6 level using shortest DoS path.

We obtain one single connected sub-network with DoS = 6 referred to as $C_6$.

<figure><img src="image_4.png" /><figcaption>Fig. 4: (a) Original configuration. Configuration for the optimal solution (b), and MLCC algorithm (c) for increasing the perceived safety and comfort when we have 50% of the budget need to upgrade the whole network, i.e., $\alpha = 0.5$.</figcaption></figure>

2) **Enlarge $C_6$ with lower DoS CCs:** Denote $C_{\tilde{\gamma}}$ the largest CC with highest DoS = $\tilde{\gamma} < 6$. Find the shortest DoS path between $C_6$ and $C_{\tilde{\gamma}}$, and upgrade the edges along this path. Then upgrade edges of $C_{\tilde{\gamma}}$ to the DoS = 6. This process progressively enlarges $C_6$ at each step. Iterate this step by considering the next largest CC $C_{\tilde{\gamma}}$ with the highest $\tilde{\gamma} < 6$. This iterative process continues until the budget is fully utilized or all edges are upgraded to their maximum DoS level.

## V. BENCHMARK EXAMPLE

Our objective now is to compare our MLCC algorithm, designed to tackle Problem 2, with a simple benchmark example where an optimal solution can be explicitly computed, in order to measure the distance to optimality of our MLCC algorithm.

Let $B = \alpha \cdot \tilde{B}$, be the available budget for optimization, with $\tilde{B}$ 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 an exponential growth.

In Fig. 4, our benchmark example comprising 10 nodes and 11 edges is displayed. We compare the configurations obtained by both the optimal solution and our MLCC algorithm under half of the budget ($\alpha = 0.5$). While our algorithm may not perfectly mirror the optimal one, notable similarities emerge, such as both solutions aiming to maximize the largest CC of DoS 6.

In Fig. 5, we present the improvements in normalized perceived safety and comfort for four values of $\alpha$. The optimal solution achieves approximately 70% improvement in perceived safety and comfort, while our algorithm attains around 60% improvement. Nevertheless, our algorithm still yields a relatively favorable outcome, with the added advantage of being significantly faster. This speed is particularly beneficial for its application to large-scale real cycling networks. Consequently, we choose to utilize it to approach the global optimum across 11 cities in France.

## VI. STUDY CASE: ELEVEN FRENCH MUNICIPALITIES

In Fig. 6, we showcase the outcomes of the MLCC algorithm. The results for safety and comfort exhibit a notable similarity among different cities, owing to the specific parameterization outlined in Eq. (7). Cities like Annecy, Le Havre, and Strasbourg demonstrate significant improvements
<figure><img src="image_5.png" /><figcaption>Fig. 5: Result of solving Problem 2 by the optimal and MLCC algorithm in the benchmark example. $\% = |\hat{y}_{\omega_0} - \hat{y}(\omega^*)| \times 100 / |\hat{y}_{FS} - \hat{y}_{\omega_0}|$.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 6: Results of the optimization problem (MLCC algorithm) for safety (top) and comfort (bottom). $\% = |\hat{y}_{\omega_0} - \hat{y}(\omega^*)| \times 100 / |\hat{y}_{FS} - \hat{y}_{\omega_0}|$.</figcaption></figure>

in safety and comfort, approaching nearly 100% enhancement for $\alpha = 0.75$. This trend is attributed to the presence of numerous disconnected components within their networks, which underscores the importance of upgrading the largest CC. In these cases, where the largest CC is fully upgraded, the observed improvements are particularly pronounced.

In contrast, cities such as Angers, Bordeaux, Nantes, Rennes and Tours show relatively minor improvements in the perception of safety and comfort. This can be attributed to the prevalence of CCs with high quality bicycle infrastructure related to a high DoS with a relatively small number of roads that are dispersed throughout their networks. Consequently, a substantial portion of the budget is spent trying to connect dispersed high DoS components within the larger CC. This phenomenon may reflect inadequate planning of cycling infrastructure in these cities, where high-DoS roads are scattered among unsafe and inconvenient routes.

Cities such as Grenoble, Lyon and Paris show considerable improvement, because the disconnected high-DoS components are considerably close to each other and large enough to have significant changes once they are connected to the largest connected high-DoS component, which may be reflected as good urban cycling planning by city authorities.

## VII. CONCLUSIONS

Given the complexity of this optimization problem, we developed a reduced-complexity MLCC algorithm for topology optimization. This methodology provides a quantitative framework for decision-making in urban planning and resource allocation, applied to 11 cities in France using real cyclist data. Results show significant improvements with minimal investments, especially in cities where high DoS network segments are well-connected.

Future research could enhance safety and comfort predictions by integrating weighted functions for DoS across different road categories and additional datasets such as motorized traffic flow, intersection traffic light data, and bike lane width. This aligns with studies on traffic stress levels [12]. Incorporating accident data, if available, could further refine predictive models. Additionally, exploring ways to correlate local graph theory metrics with spatial data from the Baromètre Vélo project is recommended Fig. 1.

## REFERENCES

[1] 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.

[2] M Lindman, S Jonsson, L Jakobsson, T Karlsson, D Gustafson, and A Fredriksson. Cyclists interacting with passenger cars; a study of real world crashes. In 2015 IRCOBI Conference Proceedings, pages 9–11, 2015.

[3] 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.

[4] 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.

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

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

[7] 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.

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

[9] 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.

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

[11] 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.

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