Document Open Access Logo

On the Bike Spreading Problem

Authors Elia Costa, Francesco Silvestri

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2021.5.pdf
  • Filesize: 4.14 MB
  • 16 pages

Document Identifiers

Author Details

Elia Costa
  • Dept. of Information Engineering, University of Padova, Italy
Francesco Silvestri
  • Dept. of Information Engineering, University of Padova, Italy

Funding

The paper was partially supported by UniPD SID18 grant, PRIN17 20174LF3T8, MIUR "Departments of Excellence".

Acknowledgements

The authors would like to thank the Municipality of Padova for providing us the dataset with rides of the free-floating service in Padova. We are also grateful to Pietro Rampazzo for providing us the grids of the city of Padova and useful suggestions on plotting maps.

Cite As Get BibTex

Elia Costa and Francesco Silvestri. On the Bike Spreading Problem. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/OASIcs.ATMOS.2021.5

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Approximation algorithms analysis
  • Information systems → Data mining
Keywords
  • Mobility data
  • bike sharing
  • bike relocation
  • influence maximization
  • NP-completeness
  • approximation algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Paola Alimonti and Viggo Kann. Some APX-completeness results for cubic graphs. Theor. Comput. Sci., 237(1-2):123-134, 2000. Google Scholar
  2. Valentin Bouquet, François Delbot, Christophe Picouleau, and Stéphane Rovedakis. On minimum dominating sets in cubic and (claw, H)-free graphs. CoRR, abs/2002.12232, 2020. URL: http://arxiv.org/abs/2002.12232.
  3. Leonardo Caggiani, Rosalia Camporeale, Michele Ottomanelli, and Wai Yuen Szeto. A modeling framework for the dynamic management of free-floating bike-sharing systems. Transportation Research Part C: Emerging Technologies, 87:159-182, 2018. Google Scholar
  4. Wei Chen, Alex Collins, Rachel Cummings, Te Ke, Zhenming Liu, David Rincón, Xiaorui Sun, Yajun Wang, Wei Wei, and Yifei Yuan. Influence maximization in social networks when negative opinions may emerge and propagate. In Proc. of the 11th SIAM Int. Conf. on Data Mining (SDM), pages 379-390, 2011. Google Scholar
  5. Iris A. Forma, Tal Raviv, and Michal Tzur. A 3-step math heuristic for the static repositioning problem in bike-sharing systems. Transportation Research Part B: Methodological, 71:230-247, 2015. Google Scholar
  6. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  7. Ashish Kabra, Elena Belavina, and Karan Girotra. Bike-share systems: Accessibility and availability. Management Science, 66(9), 2019. Google Scholar
  8. David Kempe, Jon M. Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In Proc. 9th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (KDD), pages 137-146, 2003. Google Scholar
  9. William Ogilvy Kermack, A. G. McKendrick, and Gilbert Thomas Walker. A contribution to the mathematical theory of epidemics. Proc. Royal Society of London, series A, 115(772):700-721, 1927. Google Scholar
  10. Yuchen Li, Ju Fan, Yanhao Wang, and Kian-Lee Tan. Influence maximization on social graphs: A survey. IEEE Trans. Knowl. Data Eng., 30(10):1852-1872, 2018. Google Scholar
  11. Zhi Li, Jianhui Zhang, Jiayu Gan, Pengqian Lu, and Fei Lin. Large-scale trip planning for bike-sharing systems. In Proc. 14th IEEE Int. Conf. on Mobile Ad Hoc and Sensor Systems (MASS), pages 328-332, 2017. Google Scholar
  12. Lei Lin, Zhengbing He, and Srinivas Peeta. Predicting station-level hourly demand in a large-scale bike-sharing network: A graph convolutional neural network approach. Transportation Research Part C: Emerging Technologies, 97:258-276, 2018. Google Scholar
  13. Russell Meddin, Paul DeMaio, Oliver O’Brien, Renata Rabello, Chumin Yu, Rahil Gupta, and Jess Seamon. The Meddin bike-sharing world map. Accessed August 17th, 2021. URL: http://bikesharingworldmap.com/.
  14. Stephen J. Mooney, Kate Hosford, Bill Howe, An Yan, Meghan Winters, Alon Bassok, and Jana A. Hirsch. Freedom from the station: Spatial equity in access to dockless bike share. Journal of Transport Geography, 74:91-96, 2019. Google Scholar
  15. George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. An analysis of approximations for maximizing submodular set functions - I. Math. Program., 14(1):265-294, 1978. Google Scholar
  16. Aritra Pal and Yu Zhang. Free-floating bike sharing: Solving real-life large-scale static rebalancing problems. Transportation Research Part C: Emerging Technologies, 80:92-116, 2017. Google Scholar
  17. Svenja Reiss and Klaus Bogenberger. Validation of a relocation strategy for Munich’s bike sharing system. Transportation Research Procedia, 19:341-349, 2016. Google Scholar
  18. Muhammad Usama, Yongjun Shen, and Onaira Zahoor. A free-floating bike repositioning problem with faulty bikes. Procedia Computer Science, 151:155-162, 2019. Google Scholar
  19. Yue Wang and W.Y. Szeto. Static green repositioning in bike sharing systems with broken bikes. Transportation Research Part D: Transport and Environment, 65:438-457, 2018. Google Scholar
  20. Yongping Zhang and Zhifu Mi. Environmental benefits of bike sharing: A big data-based analysis. Applied Energy, 220:296-301, 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact