Free-floating bike sharing: Solving real-life large-scale static rebalancing problems

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 to serve the maximal demand as possible.Bicycle rebalancing refers to the reestablishment of the number of bikes at sites to desired quantities by using a fleet of vehicles transporting the bicycles. 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 Program for solving the Static Complete Rebalancing Problem. 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 complete rebalancing problems for large-scale bike sharing programs.Computational experiments were carried out on the 1 Commodity Pickup and Delivery Traveling Salesman Problem (1-PDTSP) instances used previously in the literature and on three new sets of instances, two (one real-life and one general) based on Share-A-Bull Bikes (SABB) FFBS program recently launched at the Tampa campus of University of South Florida and the other based on Divvy SBBS in Chicago. 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 and Divvy instances, demonstrate that the proposed algorithm is able to deal with the increase in scale of the static rebalancing problem pertaining to both FFBS and SBBS, while deriving high-quality solutions in a reasonable amount of CPU time.