A hybrid algorithm for the static bike-sharing re-positioning problem based on an effective clustering strategy. (October 2020)

• Record Type: Journal Article
• Authors: Lv, Chang; Zhang, Chaoyong; Lian, Kunlei; Ren, Yaping; Meng, Leilei
• Is Part Of: Transportation research. Volume 140(2020)
• Page Start: 1
• Page End: 21
• Publication Date: 2020-10
• Subjects: Bike-sharing systems -- Re-positioning -- Clustering strategy -- Destroy-and-repair algorithm -- Adaptive variable neighborhood search; Transportation -- Research -- Periodicals; Transportation -- Mathematical models -- Periodicals
• DOI: 10.1016/j.trb.2020.07.004
• Languages: English
• ISSNs: 0191-2615

Abstract

Highlights: formulate and study a new and practical variant of static bike-sharing re-positioning problem (BSRP) with multiple vehicle depots and comprehensive objective function of traveling cost minimization and inventory cost minimization. propose an effective clustering strategy that enables decomposition of the original problem into classical traveling salesman problem and multi-depot vehicle routing problem. design tailored destroy-and-repair algorithm to conduct clustering optimization, and adaptive variable neighborhood search for routing optimization. perform extensive computational studies to validate performance of the proposed algorithm, which demonstrates the algorithm's competitiveness in solving large-scale BSRPs when compared with CPLEX and state-of-the-art algorithms. Abstract: This paper studies the bike-sharing re-positioning problem (BSRP) frequently encountered in modern bike-sharing systems that are widely deployed around the world. To cope with customer demand fluctuations and improve service level, BSRP aims to identify the optimal vehicle routes to visit bike-sharing stations in order to balance their inventories, picking up excess bikes from surplus stations and adding needed bikes to insufficient stations, with the objective of minimizing total traveling cost and inventory cost. The mathematical model of the studied problem is first given, detailing the considerations of multiple depots available for re-positioning vehicles and the extra objective of inventory cost minimization. An effective clustering strategy is then proposed to put bike-sharing stations into self-sufficient groups, which is shown to be able to greatly decompose the problem complexity for large-scale instances. A destroy-and-repair algorithm is developed to improve the clusters, and an adaptive variable neighborhood search algorithm is designed to conduct intra-cluster and inter-cluster vehicle routing optimization. Performance of the hybrid algorithm is validated on three sets of benchmark instances, and compared with CPLEX as well as state-of-the-art algorithms from the literature, which demonstrates that the proposed algorithm is highly competitive in solving BSRPs.