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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. Matteo Fischetti & Michele Monaci, 2014. "Exploiting Erraticism in Search," Operations Research, INFORMS, vol. 62(1), pages 114-122, February.
    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. 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.
    8. 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.
    9. 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.
    10. 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).
    11. Gianni Codato & Matteo Fischetti, 2006. "Combinatorial Benders' Cuts for Mixed-Integer Linear Programming," Operations Research, INFORMS, vol. 54(4), pages 756-766, August.
    12. Maciek Nowak & Özlem Ergun & Chelsea C. White, 2008. "Pickup and Delivery with Split Loads," Transportation Science, INFORMS, vol. 42(1), pages 32-43, February.
    13. 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.
    14. 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.
    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. 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).
    2. 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).
    3. 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).
    4. 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).
    5. 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).
    6. 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.
    7. 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.
    8. 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.
    9. 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).
    10. 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).
    11. 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).
    12. 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.
    13. 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.

    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. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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).
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. 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.
    13. 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.
    14. 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.
    15. 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).
    16. 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.
    17. Bulhões, Teobaldo & Subramanian, Anand & Erdoğan, Güneş & Laporte, Gilbert, 2018. "The static bike relocation problem with multiple vehicles and visits," European Journal of Operational Research, Elsevier, vol. 264(2), pages 508-523.
    18. Alvarez-Valdes, Ramon & Belenguer, Jose M. & Benavent, Enrique & Bermudez, Jose D. & Muñoz, Facundo & Vercher, Enriqueta & Verdejo, Francisco, 2016. "Optimizing the level of service quality of a bike-sharing system," Omega, Elsevier, vol. 62(C), pages 163-175.
    19. Maggioni, Francesca & Cagnolari, Matteo & Bertazzi, Luca & Wallace, Stein W., 2019. "Stochastic optimization models for a bike-sharing problem with transshipment," European Journal of Operational Research, Elsevier, vol. 276(1), pages 272-283.
    20. Huang, Di & Chen, Xinyuan & Liu, Zhiyuan & Lyu, Cheng & Wang, Shuaian & Chen, Xuewu, 2020. "A static bike repositioning model in a hub-and-spoke network framework," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 141(C).

    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.