1 Search Results for "Costa, Elia"

Document
DOI: 10.4230/OASIcs.ATMOS.2021.5
On the Bike Spreading Problem

Authors: Elia Costa and Francesco Silvestri

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{costa_et_al:OASIcs.ATMOS.2021.5,
  author =	{Costa, Elia and Silvestri, Francesco},
  title =	{{On the Bike Spreading Problem}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{5:1--5:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.5},
  URN =		{urn:nbn:de:0030-drops-148746},
  doi =		{10.4230/OASIcs.ATMOS.2021.5},
  annote =	{Keywords: Mobility data, bike sharing, bike relocation, influence maximization, NP-completeness, approximation algorithm}
}
  • Refine by Author
  • 1 Costa, Elia
  • 1 Silvestri, Francesco

  • Refine by Classification
  • 1 Information systems → Data mining
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 Mobility data
  • 1 NP-completeness
  • 1 approximation algorithm
  • 1 bike relocation
  • 1 bike sharing
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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 Imprint Privacy Contact