A column generation heuristic for the dynamic bicycle rebalancing problem

Marte D. Gleditsch, Kristine Hagen, Henrik Andersson, Steffen J. Bakker and Kjetil Fagerholt

European Journal of Operational Research, 2024, vol. 317, issue 3, 762-775

Abstract: Public bicycle sharing systems are becoming an essential part of the future urban mobility system. Real-time monitoring of the system state through sensors on bicycles and/or stations gives possibilities for advanced coordination of the system. In this paper, we consider the dynamic bicycle rebalancing problem, where bicycles are re-positioned by service vehicles to prevent stations from becoming completely full or empty, and so satisfying the demand for bicycles or locks. We solve the problem in a rolling horizon fashion with dynamic deterministic bicycle rebalancing subproblems (DDBRS) at the decision epochs. To solve the DDBRS within a few seconds in real-time, we propose a novel column generation heuristic (CGH). The CGH is tested within a simulation framework based on real data from the bicycle sharing system in Oslo. We show that the CGH is able to solve large real-life instances with computational times that are suitable for actual operation and that it provides significantly improved solutions compared with current planning practice. We also perform a number of tests to analyze the effect of changing the number of bicycles and locks in the system, as well as adding extra service vehicles. The case company is now making preparations to implement an optimization-based decision support system based on the CGH proposed in this paper.

Keywords: Transportation; Bicycle sharing; Dynamic rebalancing; Column generation heuristic; Simulation (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722005574
Full text for ScienceDirect subscribers only

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:eee:ejores:v:317:y:2024:i:3:p:762-775

DOI: 10.1016/j.ejor.2022.07.004

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().