Data-driven rebalancing methods for bike-share systems. (English) Zbl 1471.91199
Crisostomi, Emanuele (ed.) et al., Analytics for the sharing economy: mathematics, engineering and business perspectives. Cham: Springer. 255-278 (2020).
Summary: As bike-share systems expand in urban areas, the wealth of publicly available data has drawn researchers to address the novel operational challenges these systems face. One key challenge is to meet user demand for available bikes and docks by rebalancing the system. This chapter reports on a collaborative effort with Citi Bike to develop and implement real data-driven optimization to guide their rebalancing efforts. In particular, we provide new models to guide truck routing for overnight rebalancing and new optimization problems for other non-motorized rebalancing efforts during the day. Finally, we evaluate how our practical methods have impacted rebalancing in New York City.
For the entire collection see [Zbl 1470.91006].
For the entire collection see [Zbl 1470.91006].
MSC:
| 91B32 | Resource and cost allocation (including fair division, apportionment, etc.) |
| 90C10 | Integer programming |
References:
| [1] | Zheng F, He P, Belavina E, Girotra K (2018) Customer preference and station network in the london bike share system |
| [2] | Zhang J, Pan X, Li M, Philip SY (2016) Bicycle-sharing system analysis and trip prediction. In: Mobile data management (MDM), 2016 17th IEEE international conference on, vol 1. IEEE, pp 174-179 |
| [3] | Vogel P, Saavedra BA, Mattfeld DC (2014) A hybrid metaheuristic to solve the resource allocation problem in bike sharing systems. International workshop on hybrid metaheuristics. pp 16-29 |
| [4] | Szeto W, Liu Y, Ho SC (2016) Chemical reaction optimization for solving a static bike repositioning problem. Transp Res Part D: Transp Environ 47:104-135 · doi:10.1016/j.trd.2016.05.005 |
| [5] | Singla A, Santoni M, Bartók G, Mukerji P, Meenen M, Krause A (2015) Incentivizing users for balancing bike sharing systems. In: AAAI. pp 723-729 |
| [6] | Singhvi D, Singhvi S, Frazier PI, Henderson SG, O’Mahony E, Shmoys DB, Woodard DB (2015) Predicting Bike usage for New York city’s bike sharing system. Computational Sustainability. In: AAAI Workshop |
| [7] | Shu J, Chou MC, Liu Q, Teo C-P, Wang I-L (2013) Models for effective deployment and redistribution of bicycles within public bicycle-sharing systems. Oper Res 61(6):1346-1359 · Zbl 1291.90039 · doi:10.1287/opre.2013.1215 |
| [8] | Schuijbroek J, Hampshire R, van Hoeve WJ Inventory rebalancing and vehicle routing in bike sharing systems. Euorpean J Oper Res to appear · Zbl 1394.90046 |
| [9] | Saltzman RM, Bradford RM (2016) Simulating a more efficient bike sharing system. J Supply Chain Oper Manag 14(2):36 |
| [10] | Salaken SM, Hosen MA, Khosravi A, Nahavandi S (2015) Forecasting bike sharing demand using fuzzy inference mechanism. In: ICONIP 2015: Proceedings of the 22nd international conference on neural information processing. Springer, pp 567-574 |
| [11] | Rudloff C, Lackner B (2014) Modeling demand for bikesharing systems: neighboring stations as source for demand and reason for structural breaks. Transp Res Rec: J Transp Res Board 1-11 |
| [12] | Riquelme C, Johari R, Zhang B (2017) Online active linear regression via thresholding. In: AAAI pp 2506-2512 |
| [13] | Regional Plan Association (1997) Building transit-friendly communities a design and development strategy for the tri-state metropolitan region |
| [14] | Raviv T, Tzur M, Forma IA (2013) Static repositioning in a bike-sharing system: models and solution approaches. EURO J Transp Logist 2(3):187-229 · doi:10.1007/s13676-012-0017-6 |
| [15] | Raviv T, Kolka O (2013) Optimal inventory management of a bike-sharing station. IIE Trans 45(10):1077-1093 · doi:10.1080/0740817X.2013.770186 |
| [16] | Rainer-Harbach M, Papazek P, Hu B, Raidl GR (2013) Balancing bicycle sharing systems: a variable neighborhood search approach. In: European conference on evolutionary computation in combinatorial optimization. Springer pp 121-132 |
| [17] | Paul A, Freund D, Ferber A, Shmoys DB, Williamson DP (2017) Prize-collecting tsp with a budget constraint. In: LIPIcs-Leibniz international proceedings in informatics, vol 87. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik · Zbl 1442.90170 |
| [18] | Parikh P, Ukkusuri SV (2014) Estimation of optimal inventory levels at stations of a bicycle sharing system |
| [19] | Papazek P, Kloimüllner C, Hu B, Raidl GR (2014) Balancing bicycle sharing systems: an analysis of path relinking and recombination within a grasp hybrid. In: International conference on parallel problem solving from nature. Springer, pp 792-801 |
| [20] | O’Mahony E, Shmoys DB (2015) Data analysis and optimization for (citi) bike sharing. In: Twenty-Ninth AAAI conference on artificial intelligence |
| [21] | O’Mahony E (2015) Smarter tools For (Citi) bike sharing. PhD thesis, Cornell University |
| [22] | Lowalekar M, Varakantham P, Ghosh S, Jena SD, Jaillet P (2017) Online repositioning in bike sharing systems. In: Proceedings of the international conference on automated planning and scheduling (ICAPS) |
| [23] | Liu J, Sun L, Chen W, Xiong H (2016) Rebalancing bike sharing systems: a multi-source data smart optimization. In: Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 1005-1014 |
| [24] | Li Y, Zheng Y, Zhang H, Chen L (2015) Traffic prediction in a bike-sharing system. In: Proceedings of the 23rd SIGSPATIAL international conference on advances in geographic information systems. ACM, p 33 |
| [25] | Kloimullner C, Papazek P, Hu B, Raidl GR (2014) Balancing bicycle sharing systems: an approach for the dynamic case. European conference on evolutionary computation in combinatorial optimization. pp 73-64 |
| [26] | Kaspi M, Raviv T, Tzur M (2016) Detection of unusable bicycles in bike-sharing systems. Omega 65:10-16 · doi:10.1016/j.omega.2015.12.003 |
| [27] | Kabra A, Belavina E, Girotra K (2016) Bike-share systems: accessibility and availability |
| [28] | Jian N, Henderson SG (2015) An introduction to simulation optimization. In: Proceedings of the 2015 winter simulation conference. IEEE Press, pp 1780-1794 |
| [29] | Jian N, Freund D, Wiberg HM, Henderson SG (2016) Simulation optimization for a large-scale bike-sharing system. In: Proceedings of the 2016 winter simulation conference. IEEE Press, pp 602-613 |
| [30] | Hsu YT, Kang L, Wu YH (2016) User behavior of bikesharing systems under demand-supply imbalance. Transp Res Rec: J Transp Res Board 117-124 |
| [31] | Ho SC, Szeto W (2014) Solving a static repositioning problem in bike-sharing systems using iterated tabu search. Transp Res Part E: Logist Transp Rev 69:180-198 · doi:10.1016/j.tre.2014.05.017 |
| [32] | Henderson SG, O’Mahony E, Shmoys DB (2016) (citi)bike sharing. Submitted |
| [33] | Ghosh S, Varakantham P, Adulyasak Y, Jaillet P (2017) Dynamic repositioning to reduce lost demand in bike sharing systems. J Artif Intell Res 58:387-430 · doi:10.1613/jair.5308 |
| [34] | Ghosh S, Trick M, Varakantham P (2016) Robust repositioning to counter unpredictable demand in bike sharing systems. In: Proceedings of the twenty-fifth international joint conference on artificial intelligence. AAAI Press, pp 3096-3102 |
| [35] | Freund D, Henderson SG, Shmoys DB (2017) Minimizing multimodular functions and allocating capacity in bike-sharing systems. In: International conference on integer programming and combinatorial optimization. Springer, pp 186-198 · Zbl 1418.90164 |
| [36] | Forma IA, Raviv T, Tzur M (2015) A 3-step math heuristic for the static repositioning problem in bike-sharing systems. Transp Res Part B: Methodol 71:230-247 · doi:10.1016/j.trb.2014.10.003 |
| [37] | Erdoğan G, Laporte G, Calvo R (2014) The static bicycle relocation problem with demand intervals. Eur J Oper Res 238:451-457 · Zbl 1338.90264 · doi:10.1016/j.ejor.2014.04.013 |
| [38] | Erdoğan G, Battara M, Calvo R (2015) An exact algorithm for the static rebalancing problem arising in bicycle sharing systems. Eur J Oper Res 245:667-679 · Zbl 1346.90104 · doi:10.1016/j.ejor.2015.03.043 |
| [39] | Di Gaspero L, Rendl A, Urli T (2013) Constraint-based approaches for balancing bike sharing systems. In: International conference on principles and practice of constraint programming. Springer, pp 758-773 · Zbl 1334.90078 |
| [40] | de Chardon CM, Caruso G, Thomas I (2016) Bike-share rebalancing strategies, patterns, and purpose. J Transp Geogr 55:22-39 · doi:10.1016/j.jtrangeo.2016.07.003 |
| [41] | Contardo C, Morency C, Rousseau LM (2012) Balancing a dynamic public bike-sharing system, vol 4. Cirrelt, Montreal |
| [42] | Chung H, Freund D, Shmoys DB (2018) Bike angels: an analysis of citi bike’s incentive program. In: Proceedings of the 1st ACM SIGCAS conference on computing and sustainable societies. ACM, p 5 |
| [43] | Casazza M, Ceselli A, Calvo RW (2017) Inventory rebalancing in bike-sharing systems. In: 15th cologne-twente workshop on graphs and combinatorial optimization. p 35 |
| [44] | Bikeshare C (2014) capital bikeshare member survey report |
| [45] | Bulhoes T, Subramanian A, Erdoğan G, Laporte G (2018) The static bike relocation problem with multiple vehicles and visits. Eur J Oper Res 264:508-523 · Zbl 1375.90034 · doi:10.1016/j.ejor.2017.06.028 |
| [46] | Benchimol M, Benchimol P, Chappert B, De La Taille A, Laroche F, Meunier F, Robinet L (2011) Balancing the stations of a self service bike hire system. RAIRO-Oper Res 45(1):37-61 · Zbl 1222.90073 · doi:10.1051/ro/2011102 |
| [47] | Datner S, Raviv T, Tzur M, Chemla D (2017) Setting inventory levels in a bike sharing network. Transp Sci 0 (0):null https://doi.org/10.1287/trsc.2017.0790 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
