Hybrid Heuristic for the Multi-Depot Static Bike Rebalancing and Collection Problem

Xue Bai, Ning Ma () and Kwai-Sang Chin
Additional contact information
Xue Bai: School of Economics and Management, Chang’an University, Xi’an 710064, China
Ning Ma: School of Public Policy and Administration, Xi’an Jiaotong University, Xi’an 710049, China
Kwai-Sang Chin: Department of System Engineering and Engineering Management, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong

Mathematics, 2022, vol. 10, issue 23, 1-28

Abstract: The bike rebalancing problem is one of the major operational challenges in the urban bike-sharing system, which involves the redistribution of bikes among stations to prevent stations from being empty or overloaded. This paper investigates a new bike rebalancing problem, which considers the collection of broken bikes in the multi-depot system. The proposed problem can be classified as a two-commodity vehicle routing problem with pick-up and delivery. An integer programming model is formulated to find the optimal vehicle assignment and visiting sequences with the minimum total working time and fixed cost of vehicles. A hybrid heuristic algorithm integrating variable neighborhood search and dynamic programming is proposed to solve the problem. The computational results show that the proposed method can find 26 best solutions out of 36 instances, while the CPLEX obtains 16 best solutions. Impact of broken bikes collection and distribution of depots is examined. Comparison of different practical strategies indicates that the number of vehicles can be significantly reduced by allowing multiple visits to depots. Allowing vehicles to return to different depots can help reduce the total working time.

Keywords: bike rebalancing problem; pick-up and delivery; variable neighborhood search; dynamic programming; broken bike collection (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/23/4583/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/23/4583/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:23:p:4583-:d:992453

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().