E cient and clean urban mobility is a key factor in quality of life and sustainability of towns and cities. Traditionally, cities have focused on cars and other fuel-based vehicles as transport means. However, several problems are directly linked to massive car use, particularly in terms of air pollution and tra c congestion. Several works reckon that vehicle emissions produce over 90% of air pollution. One way to reduce the use of fuel-based vehicles (and thus the emission of pollutants) is to create e cient, easily accessible and secure bike lane networks which, as many studies show, promote cycling as a major mean of conveyance. In this regard, this paper presents an approach to design and calculate bike lane networks based on the use of open data about the historical use of a urban bike rental services. Concretely, we model this task as a network design problem (NDP) and we study four di erent optimisation strategies to solve it. We test these methods using data of the city of Valencia (Spain). Our experiments conclude that an optimisation approach based on genetic programming obtains the best performance. The proposed method can be easily used to improve or extend bike lane networks based on historic bike use data in other cities.
Cycling has long been a part of everyday sustainable urban mobility in many
countries. This trend being accentuated by the demographic changes of the
second half of the 20th century: majority of citizens living in urban areas.
Furthermore, over the last decade there has been a substantial growth in bike
commuting thanks to, among other reasons, the bicycling infrastructures developed and
the onset of bike sharing systems which have been implemented in more than
a thousand cities in the world [
The advantages of cycling are undeniable: reducing car use and increasing
cycling results in health bene ts for commuters (and citizens in general) due to
the increase of physical activity and the reduction of air pollution (particularly,
green house gas emissions). To put this into gures, in [
In metropolitan areas, cycling infrastructure is generally required for
commuting to work, school, or shopping. In this sense, bicycle lanes are necessary
and they should be thought as e cient connections between popular origins and
destinations for the commuters [
Access to public data can only be possible with the collaboration of many
contributors and data providers: the public, private and non-pro t sectors, as
well as citizens. Furthermore, researchers, policy makers, institutions and
companies are beginning to realise how important the massive amount of (open) data
produced and collected is for smart cities. All this data can be converted into
useful information for the common bene t: identify social needs, provide new
services, predict and prevent disasters, etc [
With all of this in mind, in this paper we present (and compare) several approaches for computing comprehensive and e cient bike lanes networks at the city level. The nal goal is thus improving the cycling infrastructure and aid decision-making for regional governments when planning new bicycle lanes. Through the use of open data we also aim to support cities in making the transition to \smart cities". As starting point, and in order to illustrate how our approach works, we have focused on the city of Valencia, Spain (although our approach could by applied to potentially any city with bicycling infrastructures). Valencia is the perfect example of an environmental-friendly place which is making a concerted e ort to improve its bicycling: the Valencia City Council is currently studying how to improve the bike-lane network (currently having more than 180 kilometres of bike paths) with the aim of improving not only the circulation for cyclists, also their safety, while reducing tra c and the pollution levels4. Additionally, their citizens are showing an increasing interest in the use of the bike city: in 2014 there were 75,407 daily trips made by bicycle, 17% more than in 20095. The launch of a bike sharing service (valenbisi 6) provided by JCDecaux in 2010 has been also a turning point in the use of the bike in the city of Valencia with an average of 19,773 daily trips made by public bikes.
This document is organised as following. Section 2 summarises how we collected data used for the methods. Section 3 presents our approach, the optimisation techniques used and some experiments performed. Section 4 brie y reviews the related work. Finally, some conclusions are listed in Section 5 2
In this section we will focus on the data acquisition, transformation an cleaning processes. Two main sources of data have been used: bike sharing demand and descriptive data about bike stations and current bike lane network. In the following we will describe them in detail. 2.1
We have collected bike rental data from the 276 bike stations of the city of Valencia (Spain) provided by JCDecaux open data service for bike rental information7. Data collection started on September, 2014 and has been running continuously since then. However, the data used in our approach covers the period from January 2015 to December 2015. Bike rental data is downloaded once every minute (the average interval between two updates is 7 minutes) from all bike stations provided by the JCDecaux open data serviced. This service delivers the following data for each station: 4 In https://goo.gl/Y2SOts we can nd some of the government future plans concerning the improvement of the cycling network in Valencia (information in Spanish). 5 See http://www.valencia.es/ayuntamiento/estadistica.nsf for the most recent complete statistics (in spanish) 6 http://www.valenbisi.com/ 7 http://developer.jcdecaux.com { Facts of stations (static data): station number, name, address, geographical location (latitude, longitude), number of docks (stands), availability of the station, banking facilities (pay with credit card). All these properties for one station do not change over time, although the latter three attributes can change very seldom. { Temporal information (dynamic data): time of last update, the number of available bikes at that time, the number of available empty docks at that time.
Static data can be downloaded manually in text le format or accessed through the given API. Dynamic data are refreshed every minute and can be accessed only through the API by means of a personal and free API key provided by the service. Request to the dynamic data uses a GET call where one of the parameters is your API key and the user gets data in JSON format. Data are provided under an Open Data license (ODC-BY, CC-BY 2.0). There are some missing values due to denials of service from the open data server. In total, there are less than 0.7% of missing bike data. The data used is publicly available8.
The data collected does not explicitly provide the demand of bikes (number of rented bikes per time interval) but we can estimate this number from the updates to the number of bikes in the stations: if the number of bikes in the station has decreased by k, then we know that at least k bikes have been rented in that time interval. However, this is a lower estimation of demand since it is also possible that n bikes have been returned and n + k have been rented out. Another factor which a ects demand estimation is the \balancing" activities carried out by the bike rental company (moving some of the bikes from one station to another). However both factors have an relative small e ect in the demand (71% of times, the number of bikes decreases by exactly 1).
As we will see in the following sections, since we are interested on using
demand information to weight the di erent bike rental stations (the bigger the
bike demand is, the more important a bike rental station could be considered),
and knowing that bike rental data have a strong weekly periodic component [
The city of Valencia has a network of interconnected cycle routes of more than 180 kilometres (this value increases every year), distributed between bike lanes, the so-called cycle-streets, and some \shared" areas with pedestrians. We have 8 See http://www.dsic.upv.es/~flip/BikeSharingDemand/.
96 Week hour 120 144 168 collected location data for all the bike lanes placed in the city of Valencia. This data is easily accessible and freely available in the Transparency and Open Data portal9 which provides public access to the data catalogue and information of the Valencia City Council. In particular, the data downloaded is in KML10 format which contains information about the location of each bike lane as a vector of coordinates (latitude and longitude) that characterises the complete route. Figure 2 includes the current map of bike-lanes of the city, obtained from the aforementioned downloaded information.
10 Keyhole Markup Language (KML) is a tag-based le format with nested elements and attributes (similar to the XML standard), and it is used to display geographic data in an Earth browser such as Google Earth.
As commented in the introduction, the principal aim of this work is to analyse and estimate optimal bike lane networks based on the use of open data about the historical use of a urban bike rental services. Furthermore, we want to compare the computed network solutions with the current bike lane system in order to aid the decision-making process of constructing new bike lanes. Those connections (edges in a network) returned by our approach, and not re ected in the current map of bike routes in Valencia, could be considered for construction in accordance with the stated economic and relevance criteria. For this goal, in this section we will de ne this task as a network design and optimisation problem and we will show some empirical experiments performed to test and compare the di erent strategies implemented. 3.1
Given a set V of bike stations fviji 2 [1; N ]g where N is the number of stations
(N = 276 valenbisi stations). We de ne DR as distance matrix of size N N
that contains distances in kilometres between all the stations in V . This matrix
is computed using the geographical location of the bike stations and applying
the Haversine formula [
We de ne a solution S as a Boolean matrix of size N N . A true value in the matrix position i; j indicates that the solution includes a direct bike path connection between stations i and j. Note that, to avoid duplicated connections, we only consider solutions where Si;j = f alse if j i. Given V and S, we generate an undirected graph G(V; S) where there is an edge between stations i and j if Si;j = true (for practical purpouses true 1 and f alse 0) . Given a solution S, we de ne the length of a solution such as L(S) = PiN=1 PjN=1(Si;j DR(i;j)), namely, the total length (in kilometres) of the proposed bike lane network. We also de ne the constant value Lmax as the maximum permitted length (also in kilometres) of a solution network.
Regarding the number of possible valid solutions (matrices S 2 S), there are 2N(N 1)=2 di erent matrices. However, not all of these solutions are useful. In order for a solution S to be valid, the following constraints have to be met: 1. All the stations must be connected, i.e., there is only one fully connected network component in G(V; S). 2. The length of the solution networks must not be grater than Lmax, i.e.
L(s) Lmax.
Furthermore, not all the solutions are equally interesting. Although we could use the length of the solution as a measure of performance (the shorter the network is, the better the solution is), we are more interested in increasing the probabilities of connecting (directly) those more relevant (most used) stations. For that reason we de ne w as an array of size N , where fwiji 2 [1; N ]g represents the importance (or weight) of station i (values between [0; 1]). These weights are computed taking into account the historical demand or use of each station in the network V . Additionally, we de ne W as a matrix of size N N such that Wi;j = wi wj . This matrix represents the importance of every pair of possible stations. Additionally, we de ne DG(S) as distance matrix of size N N that contains distances in kilometres between all the stations in V . In other words, DG(S) contains the length in kilometres for each pair of stations using the shortest path in the graph G(V; S) between them. By de nition, DG(S)i;j = 0 if j i. We use Dijkstra's algorithm to compute the distance (shortest path) between stations. Finally, as a measure of optimality, we de ne the cost C of 11 The alternative would be to use real distances computed considering the path in the streets of the city between stations. a solution S as C(S) = PiN=1 PjN=1(Wi;j DG(i;j)(S)). In this way, we use as cost of a solution the sum of the distances of travelling for each pair of stations using G(V; S) weighted by the importance of the stations. Therefore, we want to nd solutions that minimise bike path distances between stations in V giving more relevance to the most used stations. Summing up, given a set of stations V , a matrix of distance DR between the stations in V and an array of stations weights w de ning their relevance, the goal of our approach is to nd a valid solution S with the minimum C(S).
Last but not least, we need to de ne the weights that characterise each bike station (wi). These weights seek to re ect not only historical demand (number of rented bikes) of the bike stations (average usage during 2015), also their size in terms of number of docks (stands) (the more docks they have, the more relevant they can be considered). As we have seen in the previous section, bike rental data have a strong weekly periodic component, so we have considered weekly demand pro les for each station. Furthermore, it is easy to see (Figure 1) that the demand per station usually follow a di erent pattern (regularity) during working days and during weekend days respectively, i.e., each station have thus two clear distinct patterns. Therefore, as a very simple approach, we characterise the average demand for each station as the weighted sum of (a) the average working days demand plus (b) the average weekend days demand of its weekly pro le. Furthermore, we take into account the importance of the stations in terms of their size (the number of docks varies from 10 to 40), so we nally characterise an station as the weighted sum of both previous terms (all values are normalised between 0 and 1). Figure 3 illustrates the weight associated to each valenbisi bike station in the city of Valencia. 3.2
In this part we include the results of the experiments performed. We test several
optimisation strategies aiming at nding a suboptimal solution to the network
con guration problem de ned in the previous section. In particular, as a
preliminary approach for exploring the solution space we use four common and
well-known randomised search methods. These optimisation methods introduce
randomness into the search-process to accelerate progress and thus it is possible
to escape a local optimum and eventually to approach a global optimum [
{ HillClimb: The hill climbing optimisation technique is an iterative algorithm that, for a given problem, starts with the selection of an arbitrary solution and then attempts to nd a better solution by exploring the neighbouring solutions (incrementally changing a single element of the former considered solution). In our case, we start from a valid solution and then we create k neighbouring solutions. Each new solution is created by randomly adding a new connection (a T rue value in S) for each of the N rows in S. If the change produces a better solution (solution with a lower cost), an incremental change is made to the new solution, repeating until no further improvements can be found.This process can be seen as going down a hill. { Simulated Annealing: This technique is inspired by physics processes. Annealing is a softening process in which metals are heated and then allowed to cool slowly. The atoms are rst highly excited and then gradually settle into a low energy state. In this way the atoms are able to nd a stable con guration. In the same way as the previous techniques, our simulated annealing algorithm starts with a random solution. In each iteration, we slightly modify the current solution by randomly adding or removing a connection between stations. The key di erence with the above methods is that it uses a parameter called temperature used for calculating the acceptance probability of inferior neighbouring solutions (candidate solutions with higher cost). This parameter usually starts at 1:0 and is decreased at the end of each iteration by multiplying it by a cooling rate constant. The process works this way: if the cost of a candidate solution is lower than the cost of current solution, it is accepted as the new solution. If the cost is higher, the candidate can still be accepted according to a given probability: the higher the temperature value is, the higher the odds are for the solution to be accepted. The algorithm stops when the temperature parameter reaches a bottom limit. { Genetic Algorithm: This family of techniques are based on adaptive heuristic search based on the evolutionary ideas and processes of natural selection and genetics. Genetic algorithms repeatedly modify a population of individual solutions by using di erent techniques of natural evolution: inheritance, mutation, selection and crossover. In our implementation, at each step, the genetic algorithm selects individuals (\elite" set formed by the ten best solutions) from the current population (starting with 100 valid solutions) to be parents and uses them to produce the children for the next generation. Over successive generations, the population evolves toward an optimal solution. We perform 300 iterations in order to obtain the optimal solution.
All these previous optimisation techniques have been implemented in R12. We use package igraph13 which provides functions for generating, visualising and handling large scale networks and graphs. The source code and data used for the experiments can be found in GitHub14
20 30 40 50
Method Cost Length Time Cost Length Time Cost Length Time Cost Length Time Montecarlo 287 1927 694 287 1927 707 287 1927 613 287 1927 634 HillClimb 32 5919 85 40 3946 41 47 2959 22 54 2367 13 Anneal 30 5920 330 34 3947 273 40 2960 236 46 2368 223 Genetic 25 5916 544 29 3941 370 34 2956 313 39 2362 280
In Table 1 we include the results of the experiments using the data from the city of Valencia (described in Section 2) and the four optimisation techniques previously introduced. In this table we show the results for each method tested under four di erent scenarios. In each scenario we consider a di erent upper limit length (in kilometres) for the bike lane network to be estimated. We de ne the Ltotal constant as the total length of this network, on the assumption that all valenbisi stations are directly connected (118,411Km for the current network). 12 See http://caret.r-forge.r-project.org. 13 See https://cran.r-project.org/web/packages/igraph/index.html 14 For reproducibility, all the experiments and the source code can be found inhttps: //github.com/ceferra/ValenbisiNetwork
We already de ned Lmax as the length maximum of a solution in the network of bike lanes. Then, we explore four di erent Lmax values (for illustrative purposes), Lmax = Ltotal= where = [20; 30; 40; 50], namely, the greater the value is, the smaller the Lmax value is. The table contains the average results (10 repetitions) for each approach and scenario. We show three results for each method. The cost of the solution (C(S)), the average time in seconds required to compute the solution, and the size in kilometres of the proposed solution. The cost is computed as de ned previously.
From the table we see that, when we increase the value of the factor , we (obviously) limit the size of the valid solutions. However, this reduction in the size of the estimated network is re ected in higher costs since we are removing direct connections (edges) between stations. If we compare the four optimisation techniques (attending to the cost of the solution), the same results are obtained for all the scenarios studied: the best results are obtained by the the geneticbased technique, followed by simulated annealing and in third position comes Hillclimb. As expected, Montecarlo gets always the worst performance due to its random nature. It is noticeable that, since Montecarlo selects costly solutions but small networks at the same time, we obtain the same results for the di erent values of alpha. Regarding the time values, we see that Hillclimb obtains the best performance due to its greedy behaviour. Figure 4 shows an illustrative example of an estimated network solution by using the genetic approach and the biggest value (for visualisation reasons we use just the 25 most relevant bike stations).
Considering the limited scope of the open data employed in the optimisation
methods, we need to remark that results in Table 1 are just a simple approach to
the the network design problem (NDP) [
Considering the best cost-e ective solution (genetic approach) and analysing the current bike lane network in the city of Valencia, we are able to propose the construction of some new bike lanes aiming at improving the current network (and purely for illustrative purposes). We show the estimated solution in the left part of Figure 5. This map shows the current network of bike lanes in solid blue lines and the new proposed ones are drawn as dashed black lines. Recently, the city of Valencia announced an extension of the bike lane network. In the right section of Figure 5 we can see the proposed extension. New bike lanes are shown as dashed red lines. As we can see, there are relevant coincidences between both proposals (highlighted in yellow). These coincidences show that our proposal provide a useful aid for extending bike lane networks (it is possible to provide a greater number of connections changing the maximum length requirements).
Finally, we have created a public website15 with the objective of providing information about the estimated bike lane networks (graphs and features about valenbisi stations). Written in PHP and jQuery, and using javascript libraries 15 http://users.dsic.upv.es/~flip/RutasBici/ such as leaflet16 as well as plugins and services of Mapbox platform17, the website uses OpenStreetMap maps with di erent interactive layers showing di erent data: (1) the geographical location of all valenbisi stations, (2) the geographical location of all the bike lanes in the city of Valencia, and (3) the optimal solution (using the genetic approach) for connecting the 276 Valenbisi stations. 4
The stated problem of building new bike lane connections in an existent bike lane
network is closely related to the network design problem (NDP) [
In particular, our approach was initially inspired by the ideas from [
Explicitly focusing on the problem of improving the cycling network in a city,
most of the literature concentrates on the estimation of the potential demand
to the services [
However, there are much less approaches related to the decision-making
process for constructing bike lanes. Some examples include [
Sustainable urban mobility requires a gradual increase in the use of bikes as a major mean of conveyance. An e cient and well-designed bike lane network is a relevant factor for promoting an everyday use of the bike for a variety of reasons. For instance, safety is signi cantly increased since the existence of a bike lane network helps to reduce the rate of cyclist accidents. Furthermore, some studies have shown that the bike lines stimulate the local economy as they facilitate commuting. Finally, bike lines have a real impact on the environment since cycling reduces ones carbon footprint by not burning fossil fuels, thus avoiding the emission associated pollutants.
In this paper we have presented an approach for computing and analysing bike lane networks from open data of bike sharing systems. Speci cally, we use bike station locations and their historical use (demand) in order to characterise each station independently. With all this information, we address the task as a network design problem (NDP) where stations are seen as nodes and bike lanes are considered as edges of the network. Four di erent optimisation strategies have been studied and analysed: Montecarlo, HillClimb, simulated annealing and genetic algorithm. The experiments using open data from the city of Valencia (Spain) show that the technique based on the genetic algorithm obtains the best performance. We have compared the obtained solution with the current bike lane network in the city of Valencia, obtaining several new bike lanes which could be useful to extend the existing network. It is worth highlighting that some of these new lines correspond with some of the new bike lanes that the city of Valencia has already scheduled to be assembled.
We may emphasise once again the preliminary character of our approach. Therefore, based on our own experimentation and the related bibliography, we plan to explore and analyse new optimisation strategies and techniques (such as SAT based solvers for optimization problems), including a further improvement of the current methods.