Code and data for the paper 'On the Bike Spreading Problem'

Authors: Elia Costa and Francesco Silvestri, University of Padova

Contact email: silvestri@dei.unipd.it

A free-floating bike-sharing system (FFBSS) is a dockless rental system where an individual can borrow a bike and returns it anywhere, within the service area. To improve the rental service, available bikes should be distributed over the entire service area: a customer leaving from any position is then more likely to find a near bike and then to use the service. Moreover, spreading bikes among the entire service area increases urban spatial equity since the benefits of FFBSS are not a prerogative of just a few zones. For guaranteeing such distribution, the FFBSS operator can use vans to manually relocate bikes, but it incurs high economic and environmental costs. We propose a novel approach that exploits the existing bike flows generated by customers to distribute bikes. More specifically, by envisioning the problem as an Influence Maximization problem, we show that it is possible to position batches of bikes on a small number of zones, and then the daily use of FFBSS will efficiently spread these bikes on a large area. We show that detecting these zones is NP-complete, but there exists a simple and efficient 1-1/e approximation algorithm; our approach is then evaluated on a dataset of rides from the free-floating bike-sharing system of the city of Padova.

For more details see the paper in Arxiv. This repository contains the code and datasets used in the paper.

Datasets

The available graphs represent bike flows in the city of Padova subdivided by grids of 100 meters x 100 meters and 500 meters x 500 meters: each node is a grid cell; an edge (a,b) with weight p indicates that a bike in cell a has probability p to be moved in cell c by an user. The graphs contans no information on single rides or users. The graphs area available in the directory resources/graphs, while grid details in resources/grid.

Code

The repository contains the code for solving the bike problem with two different approches: a simple and fast greedy algorithm which finds a sub-optimal solution in polynomial time, and a brute-force algorithm that finds one optimal solution in exponential time. Both algorithms work with two different diffusion models: the u-model in which the objective is to uniformely distributing bikes across the graph, and the t-model which maximizes the nodes with more than a given threshold of bikes. (Note that the code refers to u-model with the older term s-model.)

The input parameters for the scripts must be passed through the file resources/input.csv

• graph_name: the graph filename (i.e. G_500_0.0_E.csv)
• algorithm: the algorithm to be used (greedy/brute)
• model: the model to be used (s/t)
• seed_size: the desired size of the initial seed (i.e. 5)
• tau: the number of daily rides for each bikes (i.e. 2)
• n_bikes: the total number of bikes (i.e. 100)
• t_model_threshold: the threshold used for t-model (i.e. 1)

The output can be found in the output folder and consists of two files:

• results.csv:

  • Algorithm: algorithm used
  • Model: model used
  • Seed: initial seed-set returned by the algorithm
  • Sigma: value of the objective function (number of nodes with more than the given threshold of bikes for t-model and sum of square root of bikes in each node for u-model)
  • Threshold(t-model): the threshold in the case of t-model
  • time [ms]: the computing time for the algorithm to return a solution

• final_distribution.geojson:

  • for each cell of the greed contains a flag seed = 1 if the node belongs to the initial seed set and the field bikes that contains number of bikes ending in that node