Free-floating bike sharing (FFBS) is an innovative bike sharing model. FFBS saves on start-up cost, in comparison to station-based bike sharing (SBBS), by avoiding construction of expensive docking stations and kiosk machines. FFBS prevents bike theft and offers significant opportunities for smart management by tracking bikes in real-time with built-in GPS. However, like SBBS, the success of FFBS depends on the efficiency of its rebalancing operations. Rebalancing refers to the reestablishment of the number of bikes at sites to desired quantities. Static rebalancing for SBBS is a challenging combinatorial optimization problem. FFBS takes it a step further, with an increase in the scale of the problem. This article is the first effort in a series of studies of FFBS planning and management, tackling static rebalancing with single and multiple vehicles. We present a Novel Mixed Integer Linear Programming formulation for solving the Static Rebalancing Problem in FFBS. The proposed formulation, can not only handle single as well as multiple vehicles, but also allows for multiple visits to a node by the same vehicle. We present a hybrid nested large neighborhood search with variable neighborhood descent algorithm, which is both effective and efficient in solving static rebalancing problems for both FFBS and SBBS. Computational experiments were carried out on the 1-PDTSP instances used previously in the literature and on a new set of instances based on the Share-A-Bull FFBS (SABB) program recently launched at University of South Florida on its Tampa campus. Computational experiments on the 1-PDTSP instances demonstrate that the proposed algorithm outperforms a tabu search algorithm and is highly competitive with exact algorithms previously reported in the literature for solving static rebalancing problems in SBSS. Computational experiments on the SABB instances, consisting of up to 400 nodes, 300 bikes and 3 vehicles, demonstrate that the proposed algorithm is able to deal with the increase of scale of the static rebalancing problem pertaining to FFBS while deriving high-quality solutions in a reasonable amount of CPU time.
Citation
DOI: 10.13140/RG.2.1.1727.1766
Article
View Free-Floating Bike Sharing: Solving Real-life Large-scale Static Rebalancing Problems