IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v53y2019i3p882-896.html
   My bibliography  Save this article

The Static Bike Sharing Rebalancing Problem with Forbidden Temporary Operations

Author

Listed:
  • Bruno P. Bruck

    (Department of Sciences and Methods for Engineering, University of Modena and Reggio Emilia, 42122 Reggio Emilia, Italy; Centro de Informática, Universidade Federal da Paraíba, João Pessoa, 58056-010, Brazil)

  • Fábio Cruz

    (Centro de Informática, Universidade Federal da Paraíba, João Pessoa, 58056-010, Brazil)

  • Manuel Iori

    (Department of Sciences and Methods for Engineering, University of Modena and Reggio Emilia, 42122 Reggio Emilia, Italy)

  • Anand Subramanian

    (Centro de Informática, Universidade Federal da Paraíba, João Pessoa, 58056-010, Brazil)

Abstract

This paper introduces and solves the static bike rebalancing problem with forbidden temporary operations. In this problem, one aims at finding a minimum cost route in which a vehicle performs a series of pickup and delivery operations while satisfying demand and capacity constraints. In addition, a vehicle can visit stations multiple times but cannot use them to temporarily store or provide bikes. Apart from bike rebalancing, the problem also models courier service transportation and repositioning of inventory between retail stores, where temporary operations are frequently disliked because they require additional manual work and service time. We present some theoretical results concerning problem complexity and worst-case analysis, and then propose three exact algorithms based on different mathematical formulations. Extensive computational results on instances involving up to 80 stations show that an exact algorithm based on a minimal extended network produces the best average results. The online appendix is available at https://doi.org/10.1287/trsc.2018.0859 .

Suggested Citation

  • Bruno P. Bruck & Fábio Cruz & Manuel Iori & Anand Subramanian, 2019. "The Static Bike Sharing Rebalancing Problem with Forbidden Temporary Operations," Transportation Science, INFORMS, vol. 53(3), pages 882-896, May.
    • Handle: RePEc:inm:ortrsc:v:53:y:2019:i:3:p:882-896
    DOI: 10.1287/trsc.2018.0859
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/trsc.2018.0859
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.2018.0859?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Gerardo Berbeglia & Jean-François Cordeau & Irina Gribkovskaia & Gilbert Laporte, 2007. "Rejoinder on: Static pickup and delivery problems: a classification scheme and survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 15(1), pages 45-47, July.
    2. Bruno P. Bruck & Manuel Iori, 2017. "Non-Elementary Formulations for Single Vehicle Routing Problems with Pickups and Deliveries," Operations Research, INFORMS, vol. 65(6), pages 1597-1614, December.
    3. Gianni Codato & Matteo Fischetti, 2006. "Combinatorial Benders' Cuts for Mixed-Integer Linear Programming," Operations Research, INFORMS, vol. 54(4), pages 756-766, August.
    4. Maciek Nowak & Özlem Ergun & Chelsea C. White, 2008. "Pickup and Delivery with Split Loads," Transportation Science, INFORMS, vol. 42(1), pages 32-43, February.
    5. VANDERBECK, François & WOLSEY, Laurence A., 2010. "Reformulation and decomposition of integer programs," LIDAM Reprints CORE 2188, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    6. Mladenović, Nenad & Urošević, Dragan & Hanafi, Saı¨d & Ilić, Aleksandar, 2012. "A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem," European Journal of Operational Research, Elsevier, vol. 220(1), pages 270-285.
    7. Gerardo Berbeglia & Jean-François Cordeau & Irina Gribkovskaia & Gilbert Laporte, 2007. "Static pickup and delivery problems: a classification scheme and survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 15(1), pages 1-31, July.
    8. Erdoğan, Güneş & Laporte, Gilbert & Wolfler Calvo, Roberto, 2014. "The static bicycle relocation problem with demand intervals," European Journal of Operational Research, Elsevier, vol. 238(2), pages 451-457.
    9. Dell'Amico, Mauro & Hadjicostantinou, Eleni & Iori, Manuel & Novellani, Stefano, 2014. "The bike sharing rebalancing problem: Mathematical formulations and benchmark instances," Omega, Elsevier, vol. 45(C), pages 7-19.
    10. Schuijbroek, J. & Hampshire, R.C. & van Hoeve, W.-J., 2017. "Inventory rebalancing and vehicle routing in bike sharing systems," European Journal of Operational Research, Elsevier, vol. 257(3), pages 992-1004.
    11. Erdoğan, Güneş & Battarra, Maria & Wolfler Calvo, Roberto, 2015. "An exact algorithm for the static rebalancing problem arising in bicycle sharing systems," European Journal of Operational Research, Elsevier, vol. 245(3), pages 667-679.
    12. Claudia Archetti & Martin W. P. Savelsbergh & M. Grazia Speranza, 2006. "Worst-Case Analysis for Split Delivery Vehicle Routing Problems," Transportation Science, INFORMS, vol. 40(2), pages 226-234, May.
    13. Matteo Fischetti & Michele Monaci, 2014. "Exploiting Erraticism in Search," Operations Research, INFORMS, vol. 62(1), pages 114-122, February.
    14. Forma, Iris A. & Raviv, Tal & Tzur, Michal, 2015. "A 3-step math heuristic for the static repositioning problem in bike-sharing systems," Transportation Research Part B: Methodological, Elsevier, vol. 71(C), pages 230-247.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Wang, Xu & Sun, Huijun & Zhang, Si & Lv, Ying & Li, Tongfei, 2022. "Bike sharing rebalancing problem with variable demand," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 591(C).
    2. Huang, Sen & Liu, Kanglin & Zhang, Zhi-Hai, 2023. "Column-and-constraint-generation-based approach to a robust reverse logistic network design for bike sharing," Transportation Research Part B: Methodological, Elsevier, vol. 173(C), pages 90-118.
    3. Lv, Chang & Zhang, Chaoyong & Lian, Kunlei & Ren, Yaping & Meng, Leilei, 2020. "A hybrid algorithm for the static bike-sharing re-positioning problem based on an effective clustering strategy," Transportation Research Part B: Methodological, Elsevier, vol. 140(C), pages 1-21.
    4. Wu, Weitiao & Li, Yu, 2024. "Pareto truck fleet sizing for bike relocation with stochastic demand: Risk-averse multi-stage approximate stochastic programming," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 183(C).
    5. Albert Einstein Fernandes Muritiba & Tibérius O. Bonates & Stênio Oliveira Da Silva & Manuel Iori, 2021. "Branch-and-Cut and Iterated Local Search for the Weighted k -Traveling Repairman Problem: An Application to the Maintenance of Speed Cameras," Transportation Science, INFORMS, vol. 55(1), pages 139-159, 1-2.
    6. Jiaqing Sun & Yulin He & Jiantong Zhang, 2023. "A Cluster-Then-Route Framework for Bike Rebalancing in Free-Floating Bike-Sharing Systems," Sustainability, MDPI, vol. 15(22), pages 1-33, November.
    7. Du, Mingyang & Cheng, Lin & Li, Xuefeng & Tang, Fang, 2020. "Static rebalancing optimization with considering the collection of malfunctioning bikes in free-floating bike sharing system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 141(C).
    8. Hua, Mingzhuang & Chen, Xuewu & Chen, Jingxu & Huang, Di & Cheng, Long, 2022. "Large-scale dockless bike sharing repositioning considering future usage and workload balance," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 605(C).
    9. Cheng, Yao & Wang, Junwei & Wang, Yan, 2021. "A user-based bike rebalancing strategy for free-floating bike sharing systems: A bidding model," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 154(C).
    10. Zhou, Yaoming & Lin, Zeyu & Guan, Rui & Sheu, Jiuh-Biing, 2023. "Dynamic battery swapping and rebalancing strategies for e-bike sharing systems," Transportation Research Part B: Methodological, Elsevier, vol. 177(C).
    11. van der Laan, Niels & Teunter, Ruud H. & Romeijnders, Ward & Kilic, Onur A., 2022. "The data-driven newsvendor problem: Achieving on-target service-levels using distributionally robust chance-constrained optimization," International Journal of Production Economics, Elsevier, vol. 249(C).
    12. Li, Jiliu & Qin, Hu & Baldacci, Roberto & Zhu, Wenbin, 2020. "Branch-and-price-and-cut for the synchronized vehicle routing problem with split delivery, proportional service time and multiple time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 140(C).
    13. Gu, Wei & Yu, Xiaoru & Zhang, Shichen & Yan, Xiangbin & Wang, Chen, 2023. "To outsource or not: Bike-share rebalancing strategies under the service quality deviation of a third party," European Journal of Operational Research, Elsevier, vol. 310(2), pages 847-859.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Dell’Amico, Mauro & Iori, Manuel & Novellani, Stefano & Subramanian, Anand, 2018. "The Bike sharing Rebalancing Problem with Stochastic Demands," Transportation Research Part B: Methodological, Elsevier, vol. 118(C), pages 362-380.
    2. Alain Quilliot & Antoine Sarbinowski & Hélène Toussaint, 2021. "Vehicle driven approaches for non preemptive vehicle relocation with integrated quality criterion in a vehicle sharing system," Annals of Operations Research, Springer, vol. 298(1), pages 445-468, March.
    3. Lei, Chao & Ouyang, Yanfeng, 2018. "Continuous approximation for demand balancing in solving large-scale one-commodity pickup and delivery problems," Transportation Research Part B: Methodological, Elsevier, vol. 109(C), pages 90-109.
    4. Jiliu Li & Zhixing Luo & Roberto Baldacci & Hu Qin & Zhou Xu, 2023. "A New Exact Algorithm for Single-Commodity Vehicle Routing with Split Pickups and Deliveries," INFORMS Journal on Computing, INFORMS, vol. 35(1), pages 31-49, January.
    5. Du, Mingyang & Cheng, Lin & Li, Xuefeng & Tang, Fang, 2020. "Static rebalancing optimization with considering the collection of malfunctioning bikes in free-floating bike sharing system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 141(C).
    6. Bolor Jargalsaikhan & Ward Romeijnders & Kees Jan Roodbergen, 2021. "A Compact Arc-Based ILP Formulation for the Pickup and Delivery Problem with Divisible Pickups and Deliveries," Transportation Science, INFORMS, vol. 55(2), pages 336-352, March.
    7. Ye Ding & Jiantong Zhang & Jiaqing Sun, 2022. "Branch-and-Price-and-Cut for the Heterogeneous Fleet and Multi-Depot Static Bike Rebalancing Problem with Split Load," Sustainability, MDPI, vol. 14(17), pages 1-24, August.
    8. Gilbert Laporte & Frédéric Meunier & Roberto Wolfler Calvo, 2018. "Shared mobility systems: an updated survey," Annals of Operations Research, Springer, vol. 271(1), pages 105-126, December.
    9. Xue Bai & Ning Ma & Kwai-Sang Chin, 2022. "Hybrid Heuristic for the Multi-Depot Static Bike Rebalancing and Collection Problem," Mathematics, MDPI, vol. 10(23), pages 1-28, December.
    10. Salazar-González, Juan-José & Santos-Hernández, Beatriz, 2015. "The split-demand one-commodity pickup-and-delivery travelling salesman problem," Transportation Research Part B: Methodological, Elsevier, vol. 75(C), pages 58-73.
    11. Bruno Albert Neumann-Saavedra & Teodor Gabriel Crainic & Bernard Gendron & Dirk Christian Mattfeld & Michael Römer, 2020. "Integrating Resource Management in Service Network Design for Bike-Sharing Systems," Transportation Science, INFORMS, vol. 54(5), pages 1251-1271, September.
    12. Yiwei Fan & Gang Wang & Xiaoling Lu & Gaobin Wang, 2019. "Distributed forecasting and ant colony optimization for the bike-sharing rebalancing problem with unserved demands," PLOS ONE, Public Library of Science, vol. 14(12), pages 1-26, December.
    13. Bahman Lahoorpoor & Hamed Faroqi & Abolghasem Sadeghi-Niaraki & Soo-Mi Choi, 2019. "Spatial Cluster-Based Model for Static Rebalancing Bike Sharing Problem," Sustainability, MDPI, vol. 11(11), pages 1-21, June.
    14. Carlos M. Vallez & Mario Castro & David Contreras, 2021. "Challenges and Opportunities in Dock-Based Bike-Sharing Rebalancing: A Systematic Review," Sustainability, MDPI, vol. 13(4), pages 1-26, February.
    15. Szeto, W.Y. & Shui, C.S., 2018. "Exact loading and unloading strategies for the static multi-vehicle bike repositioning problem," Transportation Research Part B: Methodological, Elsevier, vol. 109(C), pages 176-211.
    16. Li, Yanfeng & Liu, Yang, 2021. "The static bike rebalancing problem with optimal user incentives," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 146(C).
    17. Osorio, Jesus & Lei, Chao & Ouyang, Yanfeng, 2021. "Optimal rebalancing and on-board charging of shared electric scooters," Transportation Research Part B: Methodological, Elsevier, vol. 147(C), pages 197-219.
    18. Liang Gao & Wei Xu & Yifeng Duan, 2019. "Dynamic Scheduling Based on Predicted Inventory Variation Rate for Public Bicycle System," Sustainability, MDPI, vol. 11(7), pages 1-11, March.
    19. Brandstätter, Georg & Kahr, Michael & Leitner, Markus, 2017. "Determining optimal locations for charging stations of electric car-sharing systems under stochastic demand," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 17-35.
    20. Gábor Nagy & Niaz A. Wassan & M. Grazia Speranza & Claudia Archetti, 2015. "The Vehicle Routing Problem with Divisible Deliveries and Pickups," Transportation Science, INFORMS, vol. 49(2), pages 271-294, May.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ortrsc:v:53:y:2019:i:3:p:882-896. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.