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. 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.
    2. 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.
    3. 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.
    4. 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).
    5. 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.
    6. 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.
    7. 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.
    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. 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.
    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. 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.
    7. 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).
    8. 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.
    9. 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.
    10. 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.
    11. 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).
    12. 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.
    13. 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.
    14. 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.
    15. 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.
    16. 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.
    17. Yuanyuan Zhang & Yuming Zhang, 2018. "Associations between Public Transit Usage and Bikesharing Behaviors in The United States," Sustainability, MDPI, vol. 10(6), pages 1-20, June.
    18. Yang, Yu & Ridouane, Yassine & Boland, Natashia & Erera, Alan & Savelsbergh, Martin, 2022. "Substitution-based equipment balancing in service networks with multiple equipment types," European Journal of Operational Research, Elsevier, vol. 300(3), pages 966-978.
    19. 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).
    20. 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.

    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.