Robust design of bicycle infrastructure networks

Table of Contents

Copenhagen cycle superhighway model

Network For the numerical implementation, we represent the street, bike path, and cycle superhighway network as a directed graph $G = (V,E)$. The vertices represent intersections as well as intermediate points along single streets, bike paths, or cycle superhighways. The edges E represent the directed connections along the streets, bike paths, or cycle superhighways. Each directed edge $e \in E$ is assigned a physical length $l_e$ and one of three infrastructure categories (street, bike path, cycle superhighway), determining the travel speed of cyclists on the edge (see below).

We distinguish between the base network $G_\textrm{base} = (V_\textrm{base}, E_\textrm{base})$ without any of the proposed cycle superhighway upgrades (Fig. 2a) and the planned upgrades $G_\textrm{build}$ (Fig. 2b). Their combination constitutes the fully upgraded network, $G_\textrm{full} = G_\textrm{base} \cup G_\textrm{build}$. Over the course of the optimization, we add a total of $S = 202$ cycle superhighway segments $E_s$, $s \in \{1,2,\ldots ,S\}$, each consisting of multiple individual edges, $E_s = \{e_1(s), e_2(s), \ldots \}$. These edges may represent upgrades to existing edges in the network $G_\textrm{base}$ or entirely new connections. When a cycle superhighway segment is added to the graph G, we add its edges and vertices to the network (if the edges did not exist in the network yet) or update the infrastructure types of the edges included in the segment to cycle superhighway (if the edges were already part of the network as streets or normal bike path).

The full network $G_\textrm{full}$ (compare Fig. 2a,b) has $|V|= 191\,448$ vertices and $|E|= 453\,433$ directed edges with a total length of approximately 33678 km, double-counting directed edges in both directions along the same path. A large part of the network is already covered by the normal bike path network, accounting for 9894 km (29.4%) of the length of the network. The existing cycle superhighway network makes up 460 km (1.4%) with the proposed upgrades adding 1876 km (5.6%). Of the proposed segments, 1666 km are upgrades based on existing links within the base network and 210 km are completely new infrastructure.

The construction cost⁵⁴of the proposed cycle superhighway segments range between 5468.73 €/km and 1245096.76 €/km, with an average of 138978.02 €/km (median 96972.49 €/km). Their annual maintenance cost⁵⁴ range between 636.41 €/km and 98621.53 €/km, with an average of 11484.49 €/km (median 7441.89 €/km).

Demand The demand model consists of $52\,808$ origin-destination pairs between 258 starting and end points (compare Fig. 2c), representing the annual number of cyclists³⁶. The demand for each origin-destination pair is further split into 9 different cyclist types, reflecting the fitness or general speed of the cyclists (slow, medium, fast) and the type of bicycle (regular bicycle, e-bike and speed pedelec)³⁶. Normal bikes make up 95% of the trips, e-bikes 4.5%, and speed pedelecs account for the remaining 0.5%. We assume that 50% of cyclists belong to the medium speed type and 25% to the slow and fast type, respectively. Each cyclist type is assigned a velocity v for each of the three infrastructure categories of edges in the network (street, bike path, cycle superhighway), see Tab. 3, summarizing the actual travel time as well as perceived comfort and safety of travel along the edge.

We model induced demand as a function of the travel time $\tau (\omega ,G)$ of cyclists for a trip-cyclist-type combination $\omega$ in the network $G$ with a logit model⁵⁵. The travel demand $n(\omega , G)$ changes as

$$\begin{aligned} n(\omega ,G) = n(\omega ) \, P(\omega , G) = n(\omega ) \, \frac{e^{-\beta \,\tau (\omega ,G)}}{e^{-\beta \,\tau (\omega ,G)} + e^{-\beta \,\tau _\textrm{other}(\omega )}} \end{aligned}$$

(6)

where $n(\omega )$ denotes the total travel demand for the trip $\omega$ and $\tau _\textrm{other}(\omega )$ the constant travel time for the trip $\omega$ with other modes of transport. The parameter $\beta \approx {-0.0518}\,\textrm{h}^{-1}$ is the parameter that describes the demand sensitivity. This parameter is calibrated to render elasticities similar to the ones used by Hallberg et al.³⁶and Paulsen & Rich⁸.

For the evaluation of the net present value, we include population growth. The trip demand in a network G at time t is given by

$$\begin{aligned} n(\omega ,G,t) = \gamma (t) \, n(\omega ,G) = \gamma (t) \, \frac{n(\omega ,G_\textrm{base})}{P(\omega ,G_\textrm{base})}\, \frac{e^{-\beta \,\tau (\omega ,G)}}{e^{-\beta \,\tau (\omega ,G)} + e^{-\beta \,\tau _\textrm{other}(\omega )}} \end{aligned}$$

(7)

with the prefactor $\gamma (t)$ capturing overall population growth, with $\gamma (0) = 1$ and increasing by approximately ${0.2}\%$ per year for a total increase of ${7}\%$ by the end of the 50-year planning period⁵⁶. Here we write the total demand $n(\omega ) = \frac{n(\omega ,G_\textrm{base})}{P(\omega ,G_\textrm{base})}$ as a function of the demand $n(\omega ,G_\textrm{base})$ and the fraction $P(\omega ,G_\textrm{base})$ of cyclists in the base network.

Route choice model Modelling cyclist route choices in a changing network environment is in itself a complex problem⁵⁷. Cyclist routing is largely unaffected by congestion, as low space requirements and cyclist volumes keep travel times stable, with uncertainties mainly from intersection delays⁵⁸. We, therefore, consider each trip individually and adopt a simplified shortest-path choice model. This has the added benefit of avoiding complications and bias introduced by the explicit generation of choice sets as the network changes over time. Hence, cyclists travel through the network following the shortest path with respect to their travel time, determined by their bike type and speed on the different types of network edges as explained above (Tab. 3, derived from empirical speed measurement from cyclists in Denmark on different infrastructure types³⁶). In addition to the travel time along the network edges, we add time penalties for complex intersections. These penalties are the same for all cyclist types, adding 30 s for large traffic light-controlled intersections, 5 s for roundabouts, and 0 s for the remaining ones (including, for example, intermediate vertices along paths, intersections between small residential streets, and on- and off-ramps of the cycle superhighway network)³⁶.

Table 3 Travel speeds in km/h of cyclist types based on Hallberg et al.³⁶.

Net present value of the cycle superhighway network

We measure the societal benefits of the cycle superhighway network extensions in terms of the net present value [NPV, Eq. (1)] of the network G^7,8. The net present value includes five components:

(i) The annual travel time benefits (TB),

$$\begin{aligned} {\textrm{TB}}(G,t) = \sum _\omega \zeta (\omega )\,\frac{n(\omega ,G_\textrm{base}) + n(\omega ,G,t)}{2} \, \left[ \tau (\omega ,G_\textrm{base}) – \tau (\omega ,G)\right] \,, \end{aligned}$$

(8)

in year t measures the travel time savings $\tau (\omega , G_\textrm{base}) – \tau (\omega ,G)$ of cyclists across all trip-cyclist-type combinations $\omega$ compared to the base network $G_\textrm{base}$, employing the rule-of-half approximation to account for induced demand⁵⁹. Here, $\tau (\omega , G)$ and $\tau (\omega , G_\textrm{base})$ denote the travel time of cyclists and $n(\omega ,G,t)$ and $n(\omega , G_\textrm{base})$ denote the cycling demand in the current and base network, respectively. The factor $\zeta$ represents the value of time, converting the travel time savings into a monetary value.

(ii) The annual health benefits (HB),

$$\begin{aligned} \textrm{HB}(G, t)&= \sum _\omega \xi (\omega ) \left[ n(\omega , G, t) \, \ell (\omega , G) – n(\omega , G_\textrm{base}) \, \ell (\omega , G_\textrm{base}) \right] \,, \end{aligned}$$

(9)

in year t capture the value of increased distance cycled over all trip-cyclist-type combinations $\omega$, mainly due to induced demand. Here, $\ell (\omega , G)$ and $\ell (\omega , G_\textrm{base})$ denote the physical trip distances in the current and base network, respectively. The factor $\xi$ again represents the conversion factor of the health benefits to monetary value.

(iii) The total construction costs (CC),

$$\begin{aligned} \textrm{CC}(G)&= \sum _{s \in S_{G}} \textrm{cc}(s) \,, \end{aligned}$$

(10)

denote the total financial investment in the cycle superhighway extensions for all built segments $S_{G}$ in the graph G, where $\textrm{cc}(s)$ are the construction cost for the individual segment s.

(iv) The annual maintenance costs (MC),

$$\begin{aligned} \textrm{MC}(G)&= \sum _{s \in S_{G}} \textrm{mc}(s) \,, \end{aligned}$$

(11)

denote the required financial investment for maintaining the current cycle superhighway extensions for all built segments $S_{G}$ in the graph G, where $\textrm{mc}(s)$ are the annual maintenance cost for the individual segment s.

(v) Finally, the total scrap value (SV),

$$\begin{aligned} \textrm{SV}(t, G)&= \kappa (t) \sum _{s \in S_{G}} \,\textrm{cc}(s) \,, \end{aligned}$$

(12)

denotes the remaining value of the construction costs of the cycle superhighway extensions at time t. The factor $\kappa (t)$ captures the devaluation as a function of time.

The net present value of a sequence of networks $\{G(t)\}$ up to year t of the planning stage (including the newly built cycle superhighway extensions) is then given by the sum of the annual components up to year t plus the one-time contributions of construction cost and scrap value. Importantly, the net present value contribution of each year is weighted with the devaluation factor $\kappa (t)$. In total, we have

$$\begin{aligned}&\phantom {=} \textrm{NPV}(t, \{G(t)\}) \nonumber \\&= \left[ \sum _{t’ = 2}^{t} \kappa (t’) \, {\textrm{TB}}(G(t’), t’) \right] \nonumber \\&+ \left[ \sum _{t’ = 2}^{t} \kappa (t’) \, \textrm{HB}(G(t’), t’) \right] – \Bigg [ \textrm{CC}(G(t)) \Bigg ] – \left[ \sum _{t’ = 2}^{t} \kappa (t’) \, \textrm{MC}(G(t’-1)) \right] + \Bigg [ \textrm{SV}(t, G(t)) \Bigg ] \nonumber \\&= \left[ \sum _{t’ = 2}^{t} \kappa (t’) \, \sum _\omega \zeta (\omega )\,\frac{n(\omega , G_\textrm{base}) + n(\omega , G(t’), t’)}{2} \, \Big (\tau (\omega , G_\textrm{base}) – \tau (\omega , G(t’))\Big ) \right] \nonumber \\&\phantom {=} + \left[ \sum _{t’ = 2}^{t} \kappa (t’) \sum _\omega \xi (\omega ) \Big (n(\omega , G(t’), t’) \, \ell (\omega , G(t’)) – n_\omega (G_\textrm{base}) \, \ell (\omega , G_\textrm{base}) \Big ) \right] \nonumber \\&\phantom {=} – \left[ \sum _{s \in S_{G(t)}} \textrm{cc}(s) \right] – \left[ \sum _{t’ = 2}^{t} \kappa (t) \sum _{s \in S_{G(t’-1)}} \textrm{mc}(s) \right] + \left[ \kappa (T) \sum _{s \in S_{G(t)}} \textrm{cc}(s) \right] \,, \end{aligned}$$

(13)

where the summation starts in the second year, after the first planned extensions have been constructed in year $t=1$, where only construction and scrap value contribute to the net present value.

Direct optimization of the cycle superhighway network

Batched optimization The direct optimization model from Paulsen & Rich (2024)⁸ iteratively finds the best cycle superhighway segments to be built by maximizing the predicted net present value at the end of the 50-year planning period. The model incorporates expected changes in travel time and health benefits, including those driven by increased demand, to identify the optimal combination of segments to be constructed each year. The objective function $\Delta \,\widetilde{\textrm{NPV}}$ approximating the gain in net present value, defined for all segments not yet included in the graph G at a given period t, is expressed as

$$\begin{aligned} \Delta \,\widetilde{\textrm{NPV}}(s,G,t)&= \left[ \sum _{t’ = t+1}^{T} \kappa (t’) \right] \, \Delta {\widetilde{\textrm{TB}}}(s,G,t)\, + \left[ \sum _{t’ = t+1}^{T} \kappa (t’) \right] \Delta \widetilde{\textrm{HB}}(s,G,t) – \kappa (t) \,\textrm{cc}(s) – \left[ \sum _{t’ = t+1}^{T} \kappa (t’)\right] \, \textrm{mc}(s) \,. \end{aligned}$$

(14)

Here, $\widetilde{\textrm{TB}}$ represents the linearized estimates of raw travel time benefits, approximated using the travel times of the network G before the current decision step and the fully expanded network, $G_\textrm{full}$:

$$\begin{aligned} \Delta {\widetilde{\textrm{TB}}}(s,G,t) = \sum _\omega \zeta (\omega )\,\frac{n(\omega ,G_\textrm{base}) + \tilde{n}(\omega ,s,G,t)}{2} \, \left[ \tau (\omega ,G) – \tilde{\tau }(\omega ,s,G) \right] \,, \end{aligned}$$

(15)

with $\tilde{\tau }(\omega ,s,G)$ defined as

$$\begin{aligned} \tilde{\tau }(\omega ,s,G)&= \tau (\omega ,G) – \Big (\tau (\omega ,G) – \tau (\omega ,G_\textrm{full})\Big ) \frac{d\left( \omega ,s,G_\textrm{full}\right) }{\sum _{s’ \notin G}d\left( \omega ,s’,G_\textrm{full}\right) } \,, \end{aligned}$$

(16)

and $\tilde{n}(\omega ,s,G,t)$ as

$$\begin{aligned} \tilde{n}(\omega ,s,G,t)&= \gamma (t)\,n(\omega ,\tilde{\tau }(\omega , s,G))\,. \end{aligned}$$

(17)

The linearized estimations of health benefits $\Delta \widetilde{\textrm{HB}}$ are similarly defined as

$$\begin{aligned} \Delta \widetilde{\textrm{HB}}(\omega ,s,G)&= \sum _\omega \xi (\omega ) \left[ \tilde{n}(\omega ,s, G, t) \, \tilde{\ell }(\omega ,s,G) – n(\omega , G_\textrm{base}) \, \ell (\omega , G_\textrm{base}) \right] \,, \end{aligned}$$

(18)

with

$$\begin{aligned} \tilde{\ell }(\omega ,s,G)&= \ell (\omega ,G) – \left( \ell (\omega , G) – \ell (\omega , G_\textrm{full})\right) \frac{d\left( \omega ,s,G_\textrm{full}\right) }{\sum _{s’\notin G}d\left( \omega ,s’,G_\textrm{full}\right) }\,. \end{aligned}$$

(19)

The concept behind the linearization⁷ is that, for each $\omega$, the changes in travel times and distances resulting from upgrading the entire network can be attributed to the segments utilized in the full network, $G_\textrm{full}$. The individual weighting of each segments s (as represented by the fractions in Eq. (16), Eq. (17), and Eq. (19)) is proportional to the distance traveled on s in the full network $G_\textrm{full}$. If the denominator is zero, the numerator will also be zero. In this case, the fraction should be treated as a zero and thus does not influence $\tilde{\tau }$, $\tilde{n}$ or $\tilde{\ell }$.

Based on the predicted change $\Delta \,\widetilde{\textrm{NPV}}(s,G,t)$ in the net present value for each segment s, we formulate a binary integer program over the set of non-selected segments. The problem is solved using a standard solver⁶⁰ to find the optimal set $S_t = \left\{ s^*_{t,1}, s^*_{t,2}, \ldots \right\}$ to be built in year t. This set of segments maximizes the expected change in net present value subject to the budget constraint in the current year t,

$$\begin{aligned} \sum _{s \,\in \, S(t)} \textrm{cc}(s) \le \sum _{t’ = 1}^{t} b(t’) \;- \sum _{s \,\in \, S_{< t}} \textrm{cc}(s) – \sum _{t’=2}^t \, \sum _{s \,\in \, S_{< t’}} \textrm{mc}(s) , \end{aligned}$$

(20)

where b denotes the (constant) annual budget and $S_{< t} = \bigcup _{t’ = 1}^{t-1} S_{t’}$ denotes the set of cycle superhighway segments constructed up to but not including year t. The second sum on the right-hand-side thus describes the total construction cost of all segments built until and including year $t-1$, the third sum describes the cumulative maintenance cost for all constructed segments, e.g. in year t we pay the maintenance cost for all cycle superhighway segments constructed in year $t-1$ and before.

After each year t, we add the set $S_t$ to G and recompute the estimated net present value changes for each remaining segment, update the budget constraints and select the next set of segments to be constructed until the expected change in net present value is negative for all remaining segments. The update from year to year requires recomputing the routes for each $\omega$ in order to update the actual and estimated travel times and distances of the shortest paths for each $\omega$.

Greedy optimization We also analyze a simpler version of the optimization algorithm from Paulsen & Rich (2023)⁷. This version differs from the more advanced approach⁸ described above by selecting segments greedily based on an estimated net present value rate per construction cost $\Delta \tilde{R}$ under the assumption of constant demand (comparable to the advanced evaluation functions for the backward percolation approach, see below),

$$\begin{aligned} \Delta \,\tilde{\textrm{R}}(s,t)&= \frac{ \left[ \sum _{t’ = t+1}^{T} \kappa (t’) \right] \, \Delta \widetilde{\textrm{TB}}(s,G_\textrm{base},0)\, – \kappa (t) \,\textrm{cc}(s) – \left[ \sum _{t’ = t+1}^{T} \kappa (t’)\right] \, \textrm{mc}(s) }{ \kappa (t)\,\textrm{cc}(s)}\,. \end{aligned}$$

(21)

This greedy approach does not consider optimal bundling of segments within a period and entirely excludes health benefits, as they are considered negligible under the assumption of constant demand.

As before, construction costs contribute immediately, while travel time benefits and maintenance costs contribute only in the years following construction ($t’ \ge t+1$). It is assumed that the contribution from each segment s can be isolated, independent of other segments. In contrast to the batched optimization approach introduced above, the simplified travel time benefit estimates are computed based only on the initial and final network state $G_\textrm{base}$ and $G_\textrm{full}$ without recomputing the routes or travel times of cyclists. The approximated travel time benefits associated with segment s is thus a simplified case of Eq. (15),

$$\begin{aligned} \Delta {\widetilde{\textrm{TB}}}(s,G_\textrm{base},0) = \sum _\omega n(\omega ,G_\textrm{base}) \, \left[ \tau (\omega ,G_\textrm{base}) – \tilde{\tau }(\omega ,s,G_\textrm{base}) \right] \,. \end{aligned}$$

(22)

Using the predicted change $\Delta R(s,t)$ in net present value per construction cost for each segment s, we greedily select the set $S_t = \left\{ s^*_{t,1}, s^*_{t,2}, \ldots \right\}$ of segments to be constructed in year t. This set maximizes the expected change in net present value, satisfying $\Delta \widetilde{\textrm{NPV}}(s^*_{t,1}) \ge \Delta \widetilde{\textrm{NPV}}(s^*_{t,2}) \ge \ldots$, while adhering to the same budget constraint as specified in the advanced model (Eq. (20)). After each year, we recompute the estimates of the net present value rates and select the next set of segments to be built until all cycle superhighway segments have been added to the network (after 47 years). The update from year to year is much faster compared to the advanced method, as only the discount factors $\kappa$ depend on t. However, evaluation of the network quality requires additional post-processing and computation of the routes and travel times of all cyclists.

Dynamic backward percolation approach

The backward percolation algorithm starts from the full network and iteratively removes the least important cycle superhighway segment from the network. The general procedure is as follows:

Algorithm

1.

Set up initial network state $G \leftarrow G_\textrm{full}$
1. 1.a
  
  Read in base network $G_\textrm{base}$
2. 1.b
  
  Add all buildable cycle superhighway segments $s \in S$
3. 1.c
  
  Calculate the routes of all trips
2.

Main loop, iterate until all buildable cycle superhighway segments have been removed and $G = G_\textrm{base}$.
1. 2.a
  
  Calculate the evaluation function Q(s) for each remaining segment $s \subset G$.
2. 2.b
  
  Select the least important remaining segment $s^*$ with $Q(s^*) \le Q(s)$ for all $s \subset G$.
3. 2.c
  
  Remove the segment from the network, $G \leftarrow G \setminus s^*$.
4. 2.d
  
  Recalculate the routes for all affected trips
3.

Algorithm finished.

Evaluation criteria We use three different evaluation criteria Q to determine the least important cycle superhighway segment to be removed in each step of the algorithm:

(i)

The normalized travel time penalty $Q_\text {pen}$introduced in the original backward percolation model³²,

$$\begin{aligned} Q_\textrm{pen}(s, G)&= \frac{\sum _\omega \sum _{e \in s} n_e(\omega , G) \, l_e \, c_e(\omega )}{\sum _{e \in s} l_e} \,. \end{aligned}$$

(23)

The penalty $c_e(\omega ) = \frac{v_\textrm{csh}(\omega )}{v_e(\omega )}> 1$ describes the relative change in travel time for cyclists when the cycle superhighway is removed, assuming cyclists do not change their routes. Here $v_\textrm{csh}(\omega )$ denotes the speed of cyclists traveling in the cycle superhighway network, while $v_e(\omega )$ denotes the speed of cyclists traveling in the original base network (compare Tab. 3). This measure is proportional to the total travel time for all cyclists $n_e(\omega , G)$ using edges e of the segment s. For newly built edges, we take the penalty c as the penalty of a street edge to avoid infinite importance of segments.
(ii)

The relative change $Q_\textrm{stat}$,

$$\begin{aligned} Q_\textrm{stat}(s, G)&= \frac{\sum _\omega \sum _{e \in s} \zeta (\omega ) \frac{n(\omega , G_\textrm{base}) + n(\omega , G)}{2} \Delta \tau _e(\omega )}{\textrm{CC}(s)} \nonumber \\&\approx \frac{\Delta {\textrm{TB}}(s,G)}{\textrm{CC}(s)} \,, \end{aligned}$$

(24)

represent the relative change in net present value, attributable to travel time reduction, relative to the required investment cost-under the assumption that demand and route choices remain unchanged when the segment is removed. Here, $\Delta \tau _e(\omega )> 0$ describes the change in travel time when the cycle superhighway segment is removed.
(iii)

The relative change $Q_\textrm{dyn}$ in travel time benefits and health benefits,

$$\begin{aligned} Q_\textrm{dyn}(s, G)&= \frac{1}{CC(s)} \, \sum _\omega \sum _{e \in s} \left[ \zeta (\omega ) \, \left( \beta \, n(\omega ,G)(P(\omega , G)-1) \, \frac{\tau (\omega , G_\textrm{base})-\tau (\omega , G)}{2} + \frac{n(\omega , G_\textrm{base})+n(\omega , G)}{2}\right) \right. \nonumber \\&\quad \quad \quad \quad \quad \quad \quad + \; \xi (\omega ) \, \beta \, n(\omega ,G) \, (P(\omega , G)-1) \, \ell (\omega , G) \bigg ] \, \Delta \tau _e(\omega ) \nonumber \\&\approx \frac{\Delta {\textrm{TB}}(s, G) + \Delta \textrm{HB}(s, G)}{\textrm{CC}(s)} \,, \end{aligned}$$

(25)

reflects the relative change in net present value, driven by travel time reductions and induced demand, in proportion to the required investment costs, under the assumption of fixed route choices.

Here, we evaluate the demand $n(\omega , G)$ at time $t=0$ without population growth and neglect future maintenance costs, since the exact time of construction of the segment is unknown during the planning stage for the backward algorithm. Including population growth would only add a multiplicative factor to the importance of all segments without changing the relative ordering.

Details on the extension of the original evaluation function for individual edges to the segment-evaluation $Q_\textrm{pen}$ are given in Supplementary Note 1. Derivations of the evaluation criteria $Q_\textrm{stat}$ and $Q_\textrm{dyn}$ from the net present value are given in Supplementary Note 3.

link