Abstract
Bike sharing systems have recently enabled sustainable means of shared mobility through automated rental stations. Spatio-temporal variation of bike rentals, however, leads to imbalances in the distribution of bikes causing full or empty stations.
The resource allocation problem tackles imbalances at a tactical planning level by means of bike allocation and relocation. We propose a MIP formulation of an extended dynamic service network design model. The objective is to determine optimal fill levels at stations while minimizing the expected costs of relocation for the typical bike demand. The MIP formulation is hard to solve due to a large number of binary variables for relocations (stations times stations times periods).
Thus, we present a hybrid metaheuristic integrating a large neighborhood search with exact solution methods provided by a solver. The large neighborhood search iteratively improves the solution with the help of limiting and controlling possible relocation regimes by a fix-and-optimize strategy, i.e. a small subset of “free” binary relocation variables. The majority of remaining binary variables are tentatively fixed to zero leading to a fast solvable truncated MIP of the resource allocation problem. Therefore, a commercial solver can provide a local optimal value based on the defined neighborhood, in a reasonable time. Results obtained indicate that the hybrid metaheuristic outperforms CPLEX for data from Vienna’s bike sharing system “Citybike Wien”.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Büttner, J., Petersen, T.: Optimising Bike Sharing in European Cities - A Handbook (2011)
Midgley, P.: Bicycle-sharing schemes: enhancing sustainable mobility in urban areas (2011)
Zahory, M.N.: Request for Proposals for the operation of the Arlington Bike-sharing Program, http://www.metrobike.net/index.php?s=file_download&id=18
DeMaio, P.: Bike-sharing: History, impacts, models of provision, and future. Journal of Public Transportation 12, 41–56 (2009)
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-Operations Research 45, 37–61 (2011)
Raviv, T., Tzur, M., Forma, I.A.: Static repositioning in a bike-sharing system: models and solution approaches. EURO Journal on Transportation and Logistics, 1–43 (2012)
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)
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)
Di Gaspero, L., Rendl, A., Urli, T.: 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 (2013)
Di Gaspero, L., Rendl, A., Urli, T.: Constraint-based approaches for balancing bike sharing systems. In: Schulte, C. (ed.) CP 2013. LNCS, vol. 8124, pp. 758–773. Springer, Heidelberg (2013)
Ricker, V., Meisel, S., Mattfeld, D.C.: Optimierung von stationsbasierten Bike-Sharing-Systemen. In: Proceedings of MKWI 2012, pp. 215–226 (2012)
Contardo, C., Morency, C., Rousseau, L.M.: Balancing a dynamic public bike-sharing system (2012)
Caggiani, L., Ottomanelli, M.: A modular soft computing based method for vehicles repositioning in bike-sharing systems. Procedia-Social and Behavioral Sciences 54, 675–684 (2012)
Dell’Amico, M., Hadjicostantinou, E., Iori, M., Novellani, S.: The bike sharing rebalancing problem: Mathematical formulations and benchmark instances. Omega (2013)
George, D.K., Xia, C.H.: Fleet-sizing and service availability for a vehicle rental system via closed queueing networks. European Journal of Operational Research 211, 198–207 (2011)
Raviv, T., Kolka, O.: Optimal inventory management of a bike-sharing station. IIE Transactions (2013)
Correia, G.H.A., Antunes, A.P.: Optimization approach to depot location and trip selection in one-way carsharing systems. Transportation Research Part E: Logistics and Transportation Review 48, 233–247 (2012)
Jorge, D., Correia, G.: Carsharing systems demand estimation and defined operations: a literature review. EJTIR 13, 201–220 (2013)
Sayarshad, H., Tavassoli, S., Zhao, F.: A multi-periodic optimization formulation for bike planning and bike utilization. Applied Mathematical Modelling 36, 4944–4951 (2012)
Cepolina, E.M., Farina, A.: A new shared vehicle system for urban areas. Transportation Research Part C: Emerging Technologies 21, 230–243 (2012)
Schuijbroek, J., Hampshire, R., van Hoeve, W.-J.: Inventory Rebalancing and Vehicle Routing in Bike Sharing Systems (2013)
Crainic, T.G.: Service network design in freight transportation. European Journal of Operational Research 122, 272–288 (2000)
Vogel, P., Ehmke, J.F., Mattfeld, D.C.: Decision support for tactical resource allocation in bike sharing systems (under review, 2014)
Blum, C., Roli, A.: Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys (CSUR) 35, 268–308 (2003)
Blum, C., Roli, A.: Hybrid metaheuristics: an introduction. In: Hybrid Metaheuristics. pp. 1–30. Springer (2008)
Blum, C., Puchinger, J., Raidl, G.R., Roli, A.: Hybrid metaheuristics in combinatorial optimization: A survey. Applied Soft Computing 11, 4135–4151 (2011)
Shaw, P.: Using constraint programming and local search methods to solve vehicle routing problems. In: Maher, M.J., Puget, J.-F. (eds.) CP 1998. LNCS, vol. 1520, pp. 417–431. Springer, Heidelberg (1998)
Pesant, G., Gendreau, M.: A view of local search in constraint programming. In: Freuder, E.C. (ed.) CP 1996. LNCS, vol. 1118, pp. 353–366. Springer, Heidelberg (1996)
Pisinger, D., Ropke, S.: A general heuristic for vehicle routing problems. Computers & Operations Research 34, 2403–2435 (2007)
Ahuja, R.K., Ergun, Ö., Orlin, J.B., Punnen, A.P.: A survey of very large-scale neighborhood search techniques. Discrete Applied Mathematics 123, 75–102 (2002)
Pisinger, D., Ropke, S.: Large neighborhood search. In: Handbook of Metaheuristics, pp. 399–419. Springer (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Vogel, P., Neumann Saavedra, B.A., Mattfeld, D.C. (2014). A Hybrid Metaheuristic to Solve the Resource Allocation Problem in Bike Sharing Systems. In: Blesa, M.J., Blum, C., Voß, S. (eds) Hybrid Metaheuristics. HM 2014. Lecture Notes in Computer Science, vol 8457. Springer, Cham. https://doi.org/10.1007/978-3-319-07644-7_2
Download citation
DOI: https://doi.org/10.1007/978-3-319-07644-7_2
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-07643-0
Online ISBN: 978-3-319-07644-7
eBook Packages: Computer ScienceComputer Science (R0)