Abstract
Public Bicycle Sharing Systems are booming all over the world as they provide a green way of commuting in cities. However, it is a challenging task to keep such systems in a balanced state, which means that people can rent and return bikes where and when they want. Usually, operators of these systems rebalance them actively by moving bikes using vehicles with trailers. They plan routes around the city so that technicians can move bikes from full stations to empty ones. In contrast to previous work we address this issue by a novel simplified problem definition in conjunction with a Cluster-First Route-Second approach. It is an exact algorithm utilizing logic-based Benders decomposition where we solve an Assignment Problem as master problem and Traveling Salesman Problems as subproblems. Results show that we are able to solve instances with up to 60 stations which was not possible with previous problem definitions.
This work is supported by the Austrian Research Promotion Agency (FFG), contract 831740. The authors thank Matthias Prandtstetter, Andrea Rendl and Markus Straub from the Austrian Institute of Technology (AIT) for the collaboration in this project.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Benchimol, M., Benchimol, P., Chappert, B., De la Taille, A., Laroche, F., Meunier, F., Robinet, L.: Balancing the stations of a self service bike hire system. RAIRO - Oper. Res. 45(1), 37–61 (2011)
Chemla, D., Meunier, F., Calvo, R.W.: Bike sharing systems: solving the static rebalancing problem. Discrete Optim. 10(2), 120–146 (2013)
Contardo, C., Morency, C., Rousseau, L.M.: Balancing a dynamic public bike-sharing system. Technical report. CIRRELT-2012-09, Montreal, Canada (2012)
Cook, W.: Concorde TSP Solver (2011). http://www.math.uwaterloo.ca/tsp/concorde/. Accessed 06 May 2015
DeMaio, P.: Bike-sharing: history, impacts, models of provision, and future. Public Transp. 12(4), 41–56 (2009)
Hooker, J.: Logic-based benders decomposition. Math. Program. 96, 33–60 (1995)
Jonker, R., Volgenant, T.: Transforming asymmetric into symmetric traveling salesman problems. Oper. Res. Lett. 2(4), 161–163 (1983)
Kloimüllner, C., Papazek, P., Hu, B., Raidl, G.R.: Balancing bicycle sharing systems: an approach for the dynamic case. In: Blum, C., Ochoa, G. (eds.) EvoCOP 2014. LNCS, vol. 8600, pp. 73–84. Springer, Heidelberg (2014)
Papazek, P., Kloimüllner, C., Hu, B., Raidl, G.R.: Balancing bicycle sharing systems: an analysis of path relinking and recombination within a GRASP hybrid. In: Bartz-Beielstein, T., Branke, J., Filipič, B., Smith, J. (eds.) PPSN 2014. LNCS, vol. 8672, pp. 792–801. Springer, Heidelberg (2014)
Papazek, P., Raidl, G.R., Rainer-Harbach, M., Hu, B.: A PILOT/VND/GRASP hybrid for the static balancing of public bicycle sharing systems. In: Moreno-Díaz, R., Pichler, F., Quesada-Arencibia, A. (eds.) EUROCAST. LNCS, vol. 8111, pp. 372–379. Springer, Heidelberg (2013)
Prins, C., Lacomme, P., Prodhon, C.: Order-first split-second methods for vehicle routing problems: a review. Transport. Res. C-Emer. 40, 179–200 (2014)
Raidl, G.R., Hu, B., Rainer-Harbach, M., Papazek, P.: Balancing bicycle sharing systems: improving a VNS by efficiently determining optimal loading operations. In: Blesa, M.J., Blum, C., Festa, P., Roli, A., Sampels, M. (eds.) HM 2013. LNCS, vol. 7919, pp. 130–143. Springer, Heidelberg (2013)
Rainer-Harbach, M., Papazek, P., Hu, B., Raidl, G.R.: 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 (2013)
Rainer-Harbach, M., Papazek, P., Hu, B., Raidl, G.R., Kloimüllner, C.: PILOT, GRASP, and VNS approaches for the static balancing of bicycle sharing systems. J. Glob. Optim. 63, 597–629 (2015)
Raviv, T., Tzur, M., Forma, I.A.: Static repositioning in a bike-sharing system: models and solution approaches. EURO J. Trans. Log. 2(3), 187–229 (2013)
Schuijbroek, J., Hampshire, R., van Hoeve, W.J.: Inventory rebalancing and vehicle routing in bike sharing systems. Technical report. 2013–E1, Tepper School of Business, Carnegie Mellon University (2013)
Thorsteinsson, E.S.: Branch-and-check: a hybrid framework integrating mixed integer programming and constraint logic programming. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 16–30. Springer, Heidelberg (2001)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Kloimüllner, C., Papazek, P., Hu, B., Raidl, G.R. (2015). A Cluster-First Route-Second Approach for Balancing Bicycle Sharing Systems. In: Moreno-Díaz, R., Pichler, F., Quesada-Arencibia, A. (eds) Computer Aided Systems Theory – EUROCAST 2015. EUROCAST 2015. Lecture Notes in Computer Science(), vol 9520. Springer, Cham. https://doi.org/10.1007/978-3-319-27340-2_55
Download citation
DOI: https://doi.org/10.1007/978-3-319-27340-2_55
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-27339-6
Online ISBN: 978-3-319-27340-2
eBook Packages: Computer ScienceComputer Science (R0)