Minimizing Multimodular Functions and Allocating Capacity in Bike-Sharing Systems

References

• Altman E, Gaujal B, Hordijk A (2000) Multimodularity, convexity, and optimization properties. Math. Oper. Res. 25(2):324–347.Link, Google Scholar
• Alvarez-Valdes R, Belenguer JM, Benavent E, Bermudez JD, Muñoz F, Vercher E, Verdejo F (2016) Optimizing the level of service quality of a bike-sharing system. Omega 62:163–175.Crossref, Google Scholar
• Brinkmann J, Ulmer MW, Mattfeld DC (2019) Dynamic lookahead policies for stochastic-dynamic inventory routing in bike sharing systems. Comput. Oper. Res. 106:260–279.Crossref, Google Scholar
• Bruck BP, Cruz F, Iori M, Subramanian A (2019) The static bike sharing rebalancing problem with forbidden temporary operations. Transportation Sci. 53(3):882–896.Link, Google Scholar
• Capital Bikeshare (2014) Capital Bikeshare member survey report. https://d21xlh2maitm24.cloudfront.net/wdc/cabi-2014surveyreport.pdf?mtime=20161206135936.Google Scholar
• Chemla D, Meunier F, Calvo RW (2013) Bike sharing systems: Solving the static rebalancing problem. Discrete Optim. 10(2):120–146.Crossref, Google Scholar
• Chen L, Zhang D, Wang L, Yang D, Ma X, Li S, Wu Z, et al.. (2016) Dynamic cluster-based over-demand prediction in bike sharing systems. Proc. ACM Internat. Joint Conf. on Pervasive and Ubiquitous Comput. (ACM, New York), 841–852.Google Scholar
• Chen X, Li M (2021) Discrete convex analysis and its applications in operations: A survey. Production Oper. Management 30(6):1904–1926.Crossref, Google Scholar
• Chung H, Freund D, Shmoys DB (2018) Bike angels: An analysis of citi bike’s incentive program. Proc. 1st ACM SIGCAS Conf. on Comput. and Sustainable Societies (ACM, New York).Google Scholar
• Cinlar E (1972) Superposition of point processes. Lewis PAW, ed. Stochastic Point Processes: Statistical Analysis, Theory, and Applications (Wiley Interscience, New York), 549–606.Google Scholar
• Datner S, Raviv T, Tzur M, Chemla D (2019) Setting inventory levels in a bike sharing network. Transportation Sci. 53(1):62–76.Link, Google Scholar
• de Chardon CM, Caruso G, Thomas I (2016) Bike-share rebalancing strategies, patterns, and purpose. J. Transportation Geography 55:22–39.Crossref, Google Scholar
• Dell’Amico M, Hadjicostantinou E, Iori M, Novellani S (2014) The bike sharing rebalancing problem: Mathematical formulations and benchmark instances. Omega 45:7–19.Crossref, Google Scholar
• Di Gaspero L, Rendl A, Urli T (2013) A hybrid ACO+CP for balancing bicycle sharing systems. Proc. Internat. Workshop on Hybrid Metaheuristics (Springer, Berlin), 198–212.Google Scholar
• Erdoğan G, Battarra M, Calvo RW (2015) An exact algorithm for the static rebalancing problem arising in bicycle sharing systems. Eur. J. Oper. Res. 245(3):667–679.Crossref, Google Scholar
• Erdoğan G, Laporte G, Calvo RW (2014) The static bicycle relocation problem with demand intervals. Eur. J. Oper. Res. 238(2):451–457.Crossref, Google Scholar
• Forma IA, Raviv T, Tzur M (2015) A 3-step math heuristic for the static repositioning problem in bike-sharing systems. Transportation Res. Part B: Methodological 71:230–247.Crossref, Google Scholar
• Freund D, Henderson SG, Shmoys DB (2016) Minimizing multimodular functions and allocating capacity in bike-sharing systems. Preprint, submitted November 28, https://arxiv.org/abs/1611.09304.Google Scholar
• Freund D, Henderson SG, Shmoys DB (2017) Minimizing multimodular functions and allocating capacity in bike-sharing systems. Proc. Internat. Conf. on Integer Programming and Combinatorial Optimization (Springer, Berlin), 186–198.Google Scholar
• Freund D, Henderson SG, Shmoys DB (2019) Bike sharing. Sharing Economy (Springer, Berlin), 435–459.Crossref, Google Scholar
• Freund D, Norouzi-Fard A, Paul A, Henderson SG, Shmoys DB (2020) Data-driven rebalancing methods for bike-share systems. Analytics for the Sharing Economy: Mathematics, Engineering and Business Perspectives (Springer, Cham), 255–278.Google Scholar
• Fujishige S, Murota K (2000) Notes on l-/m-convex functions and the separation theorems. Math. Programming 88(1):129–146.Crossref, Google Scholar
• Ghosh S, Trick M, Varakantham P (2016) Robust repositioning to counter unpredictable demand in bike sharing systems. Proc. 25th Internat. Joint Conf. on Artificial Intelligence (AAAI Press, Palo Alto, CA), 3096–3102.Google Scholar
• Hajek B (1985) Extremal splittings of point processes. Math. Oper. Res. 10(4):543–556.Link, Google Scholar
• Hernández-Pérez H, Salazar-González J-J (2004) A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery. Discrete Appl. Math. 145(1):126–139.Crossref, Google Scholar
• Ho SC, Szeto W (2014) Solving a static repositioning problem in bike-sharing systems using iterated tabu search. Transportation Res., Part E Logist. Transportation Rev. 69:180–198.Crossref, Google Scholar
• Hochbaum DS (1994) Lower and upper bounds for the allocation problem and other nonlinear optimization problems. Math. Oper. Res. 19(2):390–409.Link, Google Scholar
• Jian N, Henderson SG (2015) An introduction to simulation optimization. Proc. Winter Simulation Conf. (IEEE, New York), 1780–1794.Google Scholar
• Jian N, Freund D, Wiberg HM, Henderson SG (2016) Simulation optimization for a large-scale bike-sharing system. Proc. Winter Simulation Conf. (IEEE, New York), 602–613.Google Scholar
• Kabra A, Belavina E, Girotra K (2020) Bike-share systems: Accessibility and availability. Management Sci. 66(9):3803–3824.Google Scholar
• Karlin S, Taylor HM (1975) A First Course in Stochastic Processes, 2nd ed. (Academic Press, Boston).Google Scholar
• Kaspi M, Raviv T, Tzur M (2017) Bike-sharing systems: User dissatisfaction in the presence of unusable bicycles. IISE Transactions. 49(2):144–158.Crossref, Google Scholar
• Kloimüllner C, Papazek P, Hu B, Raidl GR (2014) Balancing bicycle sharing systems: An approach for the dynamic case. Proc. Eur. Conf. on Evolutionary Comput. in Combinatorial Optim. (Springer, Berlin), 73–84.Google Scholar
• Laporte G, Meunier F, Calvo RW (2018) Shared mobility systems: An updated survey. Ann. Oper. Res. 271(1):105–126.Crossref, Google Scholar
• Li J, Qin H, Baldacci R, Zhu W (2020) Branch-and-price-and-cut for the synchronized vehicle routing problem with split delivery, proportional service time and multiple time windows. Transportation Res., Part E Logist. Transportation Rev. 140:101955.Crossref, Google Scholar
• Li Q, Yu P (2014) Multimodularity and its applications in three stochastic dynamic inventory problems. Manufacturing Service Oper. Management 16(3):455–463.Link, Google Scholar
• Li Y, Zheng Y, Zhang H, Chen L (2015) Traffic prediction in a bike-sharing system. Proc. 23rd SIGSPATIAL Internat. Conf. on Advances in Geographic Inform. Systems (ACM, New York), 33.Google Scholar
• Liu J, Sun L, Chen W, Xiong H (2016) Rebalancing bike sharing systems: A multi-source data smart optimization. Proc. 22nd ACM SIGKDD Internat. Conf. on Knowledge Discovery and Data Mining (ACM, New York), 1005–1014.Google Scholar
• Lu Y, Song J-S (2005) Order-based cost optimization in assemble-to-order systems. Oper. Res. 53(1):151–169.Link, Google Scholar
• Moriguchi S, Murota K, Tamura A, Tardella F (2020). Discrete midpoint convexity. Math. Oper. Res. 45(1):99–128.Google Scholar
• Murota K (1996) Convexity and Steinitz’s exchange property. Adv. Math. 124(2):272–310.Crossref, Google Scholar
• Murota K (1998) Discrete convex analysis. Math. Programming 83(1):313–371.Crossref, Google Scholar
• Murota K (2003) Discrete Convex Analysis (SIAM, Philadelphia).Crossref, Google Scholar
• Murota K (2018) Main features of discrete convex analysis. Accessed February 21, 2019, http://www.comp.tmu.ac.jp/kzmurota/paper/rimsCOSS2018/COSS2018chap1.pdf.Google Scholar
• Murota K, Shioura A (1999) M-convex function on generalized polymatroid. Math. Oper. Res. 24(1):95–105.Link, Google Scholar
• Nair R, Miller-Hooks E, Hampshire RC, Bušić A (2013) Large-scale vehicle sharing systems: Analysis of vélib’. Internat. J. Sustainable Transportation 7(1):85–106.Crossref, Google Scholar
• Nelson BL (2013) Foundations and Methods of Stochastic Simulation, vol. 187 of International Series in Operations Research & Management Science (Springer, New York).Crossref, Google Scholar
• NYCBS (2016) June 2016 monthly report.Google Scholar
• O’Mahony E (2015) Smarter tools for (Citi) bike sharing. PhD thesis, Cornell University, Ithaca, NY.Google Scholar
• O’Mahony E, Henderson SG, Shmoys DB (2016) (Citi)Bike sharing. Working paper, Cornell University, Ithaca, NY.Google Scholar
• O’Mahony E, Shmoys DB (2015) Data analysis and optimization for (Citi) bike sharing. Proc. 29th AAAI Conf. on Artificial Intelligence (AAAI, Palo Alto, CA), 687–694.Google Scholar
• Parikh P, Ukkusuri S (2015) Estimation of optimal inventory levels at stations of a bicycle sharing system. In Transportation Research Board 94th Annual Meeting Compendium of Papers. Transportation Research Board, 1–14.Google Scholar
• Raidl GR, Hu B, Rainer-Harbach M, Papazek P (2013) Balancing bicycle sharing systems: Improving a VNS by efficiently determining optimal loading operations. Proc. Internat. Workshop on Hybrid Metaheuristics (Springer, Berlin), 130–143.Google Scholar
• Rainer-Harbach M, Papazek P, Hu B, Raidl GR (2013) Balancing bicycle sharing systems: A variable neighborhood search approach. Proc. Eur. Conf. on Evolutionary Comput. in Combinatorial Optim. (Springer, Berlin), 121–132.Google Scholar
• Raviv T, Kolka O (2013) Optimal inventory management of a bike-sharing station. IIE Trans. 45(10):1077–1093.Crossref, Google Scholar
• Raviv T, Tzur M, Forma IA (2013) Static repositioning in a bike-sharing system: Models and solution approaches. EURO J. Transportation Logist. 2(3):187–229.Crossref, Google Scholar
• Schuijbroek J, Hampshire R, van Hoeve W-J (2017) Inventory rebalancing and vehicle routing in bike sharing systems. Eur. J. Oper. Res. 257(3):992–1004.Crossref, Google Scholar
• Shioura A (2021) M-convex function minimization under l1-distance constraint and its application to dock reallocation in bike-sharing system. Math. Oper. Res. 47(2):1566–1611.Google Scholar
• 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.Link, Google Scholar
• Shui C, Szeto W (2020) A review of bicycle-sharing service planning problems. Transportation Res., Part C Emerging Tech. 117:102648.Crossref, Google Scholar
• 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. Proc. AAAI Workshop: Computat. Sustainability. https://dblp.org/rec/conf/aaai/SinghviSFHOSW15.html?view=bibtex.Google Scholar
• Wang J, Tsai C-H, Lin P-C (2016) Applying spatial-temporal analysis and retail location theory to public bikes site selection in Taipei. Transportation Res. Part A Policy Practice 94:45–61.Crossref, Google Scholar
• Zhang J, Pan X, Li M, Yu PS (2016) Bicycle-sharing system analysis and trip prediction. Preprint, submitted April 3, https://arxiv.org/abs/1604.00664.Google Scholar
• Zipkin P (2008) On the structure of lost-sales inventory models. Oper. Res. 56(4):937–944.Link, Google Scholar