Column-generation-based heuristics for integrating static rebalancing and faulty bike collection in bike-sharing systems

Bruno A. Neumann-Saavedra () and Rossana Cavagnini ()
Additional contact information
Bruno A. Neumann-Saavedra: Technische Universität Braunschweig
Rossana Cavagnini: RWTH Aachen University

OR Spectrum: Quantitative Approaches in Management, 2025, vol. 47, issue 2, No 2, 375-409

Abstract: Abstract This paper studies the static rebalancing problem in bike-sharing systems with faulty bike collection and multiple depots. The decisions of this problem involve the routes to be executed by rebalancing vehicles, the number of usable bikes to load and unload across stations, and the number of faulty bikes to collect from each station. The goal is to minimize rebalancing costs and penalty costs due to users’ dissatisfaction. We propose the first cycle formulation for this problem to model decisions regarding the execution of vehicle routes explicitly. To solve this problem, we implement a column-generation-based heuristic and a matheuristic that relies on a neighborhood-search scheme. We also propose a restrictive optimization model that can be solved after executing the matheuristic to further improve the quality of the solution. Our computational results on a set of small instances show that our matheuristic returns solutions equal to the optimal ones. Our solution methods can also solve bigger instances based on a variety of real-world bike-sharing systems. For these instances, the results provide evidence of the effectiveness of our solution methods, and they considerably improve the service level offered to the users of bike-sharing systems. Finally, we assess the effect of the availability of multiple vehicles and depots on the quality of the solutions. Both of them are beneficial, but the advantage of having multiple depots is bigger than the advantage of having multiple vehicles.

Keywords: Bike-sharing systems; Static rebalancing; Faulty bike collection; Column-generation-based heuristics (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00291-024-00789-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:orspec:v:47:y:2025:i:2:d:10.1007_s00291-024-00789-5

Ordering information: This journal article can be ordered from
http://www.springer. ... research/journal/291

DOI: 10.1007/s00291-024-00789-5

Access Statistics for this article

OR Spectrum: Quantitative Approaches in Management is currently edited by Rainer Kolisch

More articles in OR Spectrum: Quantitative Approaches in Management from Springer, Gesellschaft für Operations Research e.V.
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().