IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v10y2022i22p4175-d966407.html
   My bibliography  Save this article

A VNS-Based Matheuristic to Solve the Districting Problem in Bicycle-Sharing Systems

Author

Listed:
  • Guillermo Cabrera-Guerrero

    (Escuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362807, Chile)

  • Aníbal Álvarez

    (Escuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362807, Chile)

  • Joaquín Vásquez

    (Escuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362807, Chile)

  • Pablo A. Maya Duque

    (Research Group of Analytics for Decision Making (ALIADO), Industrial Engineering Department, Universidad de Antioquia, Calle 67 No. 53-108, Medellín 050010, Colombia)

  • Lucas Villavicencio

    (Escuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362807, Chile)

Abstract

A matheuristic approach that combines a reduced variable neighbourhood search (rVNS) algorithm and a mathematical programming (MP) solver to solve a novel model for the districting problem in a public bicycle-sharing system is presented. The problem is modelled as an integer programming problem. While the rVNS algorithm aims to find a high-quality set of centres for the repositioning zones, the MP solver computes the optimal allocation network of the stations to the centres of the repositioning zones. We use a predefined grid to reduce the search space the rVNS needs to explore. The proposed approach obtains promising results for small and medium-sized instances, and is also able to handle large-sized models.

Suggested Citation

  • Guillermo Cabrera-Guerrero & Aníbal Álvarez & Joaquín Vásquez & Pablo A. Maya Duque & Lucas Villavicencio, 2022. "A VNS-Based Matheuristic to Solve the Districting Problem in Bicycle-Sharing Systems," Mathematics, MDPI, vol. 10(22), pages 1-15, November.
    • Handle: RePEc:gam:jmathe:v:10:y:2022:i:22:p:4175-:d:966407
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/10/22/4175/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/10/22/4175/
    Download Restriction: no
    ---><---

    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. Médard de Chardon, Cyrille & Caruso, Geoffrey & Thomas, Isabelle, 2016. "Bike-share rebalancing strategies, patterns, and purpose," Journal of Transport Geography, Elsevier, vol. 55(C), pages 22-39.
    3. S. W. Hess & J. B. Weaver & H. J. Siegfeldt & J. N. Whelan & P. A. Zitlau, 1965. "Nonpartisan Political Redistricting by Computer," Operations Research, INFORMS, vol. 13(6), pages 998-1006, December.
    4. Nicolas Dupin & El-Ghazali Talbi, 2021. "Matheuristics to optimize refueling and maintenance planning of nuclear power plants," Journal of Heuristics, Springer, vol. 27(1), pages 63-105, April.
    5. Guillermo Cabrera-Guerrero & Andrew J. Mason & Andrea Raith & Matthias Ehrgott, 2018. "Pareto local search algorithms for the multi-objective beam angle optimisation problem," Journal of Heuristics, Springer, vol. 24(2), pages 205-238, April.
    6. 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.
    7. Shang, Wen-Long & Chen, Jinyu & Bi, Huibo & Sui, Yi & Chen, Yanyan & Yu, Haitao, 2021. "Impacts of COVID-19 pandemic on user behaviors and environmental benefits of bike sharing: A big-data analysis," Applied Energy, Elsevier, vol. 285(C).
    Full references (including those not matched with items on IDEAS)

    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. Yixiao Liu & Wenshan Liu & Rui Zhao & Lixin Tian, 2023. "Can Docked Bike-Sharing Systems Reach Their Dual Sustainability in Terms of Environmental Benefits and Financial Operations? A Comparative Study from Nanjing, 2017 and 2023," Sustainability, MDPI, vol. 15(24), pages 1-39, December.
    2. Yu, Qing & Xie, Yingkun & Li, Weifeng & Zhang, Haoran & Liu, Xiaolei & Shang, Wen-Long & Chen, Jinyu & Yang, Dongyuan & Yan, Jinyue, 2022. "GPS data in urban bicycle-sharing: Dynamic electric fence planning with assessment of resource-saving and potential energy consumption increasement," Applied Energy, Elsevier, vol. 322(C).
    3. 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.
    4. 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.
    5. Jialing Zhao & Hongwei Wang & Yuxin Huang & Yuan Meng, 2020. "Does Massive Placement of Bicycles Win the Market for the Bicycle-Sharing Company in China?," Sustainability, MDPI, vol. 12(13), pages 1-14, June.
    6. 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.
    7. Bruno A. Neumann-Saavedra & Rossana Cavagnini, 2025. "Column-generation-based heuristics for integrating static rebalancing and faulty bike collection in bike-sharing systems," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 47(2), pages 375-409, June.
    8. Shi, Ziyi & Xu, Meng & Song, Yancun & Zhu, Zheng, 2024. "Multi-Platform dynamic game and operation of hybrid Bike-Sharing systems based on reinforcement learning," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 181(C).
    9. Zhang, J. & Meng, M. & Wang, David, Z.W., 2019. "A dynamic pricing scheme with negative prices in dockless bike sharing systems," Transportation Research Part B: Methodological, Elsevier, vol. 127(C), pages 201-224.
    10. Jiang, Zhoutong & Lei, Chao & Ouyang, Yanfeng, 2020. "Optimal investment and management of shared bikes in a competitive market," Transportation Research Part B: Methodological, Elsevier, vol. 135(C), pages 143-155.
    11. Mohammed Elhenawy & Hesham A. Rakha & Youssef Bichiou & Mahmoud Masoud & Sebastien Glaser & Jack Pinnow & Ahmed Stohy, 2021. "A Feasible Solution for Rebalancing Large-Scale Bike Sharing Systems," Sustainability, MDPI, vol. 13(23), pages 1-19, December.
    12. 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.
    13. 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).
    14. Daniel Freund & Shane G. Henderson & Eoin O’Mahony & David B. Shmoys, 2019. "Analytics and Bikes: Riding Tandem with Motivate to Improve Mobility," Interfaces, INFORMS, vol. 49(5), pages 310-323, September.
    15. 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).
    16. Liu, Yixiao & Tian, Zihao & Pan, Baoran & Zhang, Wenbin & Liu, Yunqi & Tian, Lixin, 2022. "A hybrid big-data-based and tolerance-based method to estimate environmental benefits of electric bike sharing," Applied Energy, Elsevier, vol. 315(C).
    17. 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.
    18. Bruck, Bruno P. & Coutinho, Walton P. & Munari, Pedro, 2025. "The Robust Bike sharing Rebalancing Problem: Formulations and a branch-and-cut algorithm," European Journal of Operational Research, Elsevier, vol. 325(1), pages 67-80.
    19. Muhammad Usama & Yongjun Shen & Onaira Zahoor, 2019. "Towards an Energy Efficient Solution for Bike-Sharing Rebalancing Problems: A Battery Electric Vehicle Scenario," Energies, MDPI, vol. 12(13), pages 1-21, June.
    20. 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.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:gam:jmathe:v:10:y:2022:i:22:p:4175-:d:966407. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    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.