Autosoft Journal

Online Manuscript Access

A Clustering-based Approach for Balancing and Scheduling Bicycle-sharing Systems



This paper addresses an inventory regulation problem in bicycle sharing-systems. The problem is to balance a network consisting of a set of stations by using a single vehicle, with the aim of minimizing the weighted sum of the waiting times during which some stations remain imbalanced. Motivated by the complexity of this problem, we propose a two-stage procedure based on decomposition. First, the network is divided into multiple zones by using two different clustering strategies. Then, the balancing problem is solved in each zone. Finally, the order in which the zones must be visited is defined. To solve these problems, different algorithms based on approximate, greedy and exact methods are developed. The numerical results show the effectiveness of the proposed regulation methodology.



Total Pages: 10
Pages: 421-430


Manuscript ViewPdf Subscription required to access this document

Obtain access this manuscript in one of the following ways

Already subscribed?

Need information on obtaining a subscription? Personal and institutional subscriptions are available.

Already an author? Have access via email address?


Volume: 24
Issue: 2
Year: 2018

Cite this document


G. Bendall and F. Margot. (2006). Greedy Type Resistance of Combinatorial Problems. Discrete Optimization 3, 288-298.

Benchimol, Mike et al. "Balancing the Stations of a Self Service ‘bike Hire” System." RAIRO - Operations Research 45.1 (2011): 37-61. Crossref. Web.

E. Call. (2009). Director of Operation in Vlib. April 2009, Personal communication.

D. Chemla, F. Meunier, and R. Wolfer-Calvo. (2013). Bike sharing systems: solving the static rebalancing problem. Discrete Optimization. 10(2), 120-146.

L. Di Gaspero, A. Rendl, and T. Urli. (2016). Balancing bike sharing systems with constraint programming. Constraints, 21(2), 318-348.

L. Di Gasperro, A. Rendl, and T. Urli. (2013). A hybrid ACO+CP for balancing bicycle sharing systems. In: Blesa, M.J., Blum, C., Festa, P., Roli, A., Sampels, M. (eds.) HM 2013. LNCS, vol. 7919, pp. 198-212. Springer, Heidelberg.

C. Ding, Ye Cheng, and M. He. (2007). Two-Level Genetic Algorithm for Clustered Travelling Salesman Problem with Application in Large-Scale TSPs. Tsinghua Science and Technology, 12(4), 459-465.

K. Helsgaun. (2014). Solving the Clisteres Traveling Salesman Problem Using the Lin-Kernighan-Helsgaun Algorithm. in Copmut. Sci. Rep, Roskilde University. ISSN 01099779.

I. Kacem. (2013). Genetic Algorithms for Solving Flexible Job Shop Scheduling Problems. In book: Metaheuristics for Production Scheduling, pp. 19-44.

I. Kacem, A.A. Kadri, and P. Laroche. (2016). A 2-Steps Procedure for Solving the Inventory Balancing Problem with Time Constraints. 46rd International Conference on Computer and Industrial Engineering (CIE46). October 29-31 2016, Tianjin (China). ISSN 2164-8689.

A.A. Kadri, I. Kacem, and K. Labadi. (2016). A branch-and-bound algorithm for solving the static rebalancing problem in bicycle sharing systems. Computers & Industrial Engineering journal (Elsevier). 95, 41-52.

A.A. Kadri, I. Kacem, and K. Labadi. (2016). A Memetic Algorithm for Solving the Multiple Vehicles Routing Problem in Bicycle-Sharing Systems. The 12th FLINS International Conference. August 24-26 2016, Roubaix (France). ISBN 978-981-3146-96-9.

D. Karapetyan and G. Gutin. (2011). Lin-Kernighan Heuristic Adaptations for the Generalized Traveling Salesman Problem. European Journal of Operational Re- search. 208(3), pp. 221-232.

Kloimüllner, Christian et al. "A Cluster-First Route-Second Approach for Balancing Bicycle Sharing Systems." Lecture Notes in Computer Science (2015): 439-446. Crossref. Web.

P. Papazek, G.R. Raidl, M. Rainer-Harbach, and B. Hu. (2013). A PILOT/VND/GRASP hybrid for the static balancing of public bicycle sharing sys- tems. In: Moreno-Diaz, R., Pichler, F., Quesada-Arencibia, A. (eds.) EUROCAST. LNCS, vol. 8111, pp. 372-379. Springer, Heidelberg.

M. Rainer-Harbach, P. Papazek, B. Hu, and G. R., Raidl. (2013). Balancing bicycle sharing systems: A variable neighborhood search approach. In: Middendorf, M., Blum, C. (eds.) EvoCOP 2013. LNCS, vol. 7832, pp. 121-132. Springer, Heidelberg.

Raviv, Tal, Michal Tzur, and Iris A. Forma. "Static Repositioning in a Bike-Sharing System: Models and Solution Approaches." EURO Journal on Transportation and Logistics 2.3 (2013): 187-229. Crossref. Web.


ISSN PRINT: 1079-8587
ISSN ONLINE: 2326-005X
DOI PREFIX: 10.31209
10.1080/10798587 with T&F
IMPACT FACTOR: 0.652 (2017/2018)
Journal: 1995-Present


TSI Press
18015 Bullis Hill
San Antonio, TX 78258 USA
PH: 210 479 1022
FAX: 210 479 1048