Optimization in static repositioning activities of bike-sharing systems

• Main Author: Zhu, Tiantian
• Other Authors: Chen Chun-Hsien
• Format: Theses and Dissertations
• Language: English
• Published: 2018
• Subjects: DRNTU::Engineering::Industrial engineering::Operations research
• Online Access: http://hdl.handle.net/10356/75811
• Institution: Nanyang Technological University

Bike-sharing systems have become increasingly popular in cities all over the world. Satisfying the fluctuating and asymmetric demand is a crucial problem for bike-sharing systems. In order to ensure a good quality of user service, repositioning activities are conducted by a fleet of vehicles. This study focuses on the static repositioning problem, which usually happens at night and assumes no demand occurs during the period of repositioning operatIons. The goal is to determine the routes and loading instructions of vehicles with the minimal total time cost. In this thesis, first, new constraints are developed to speed up the Integer Programming (IP) model of the static repositioning problem. Tests on the IP model and the IP model with new constraints have been done to show the performance improvement by adding these new constraints. Then, a novel IP model with two commodities is formulated, which considers transferring both bikes and docking lockers, since movable docking stations are in a developing trend. After conducting a numerical experiment with small-sized simulated data, some patterns of computation time are pointed out and discussed. As the static repositioning problem is NP-hard, in the following study, two novel heuristics are put forward to handle larger-sized instances. One is called IP model based heuristic, which includes forming an undirected graph with less costly arcs and running IP model by setting the upper bound of decision variables based on the graph. The testing results of this IP model based heuristic show that this method can efficiently handle medium-sized instances with 40-90 stations. The other is called Set-Partitioning (SP) based heuristic, which includes generating a pool of feasible routes, selecting the best combination of feasible routes by SP model, modifying the solution of SP model, and rerunning the SP model after adding new modified feasible routes back to the pool of feasible routes. The process of solution modification and SP model rerun keeps repeating until the stopping criterion is reached. To our best knowledge, it is the first time that the SP model is implemented in the repositioning problem of bike-sharing systems. It is worth noting that the number of vehicles becomes an output instead of input in this SP model based heuristic. As a result, the computation time will not be affected by the increase of fleet size. In the numerical experiment, the maximum size of tested instances is 500 stations with 10 vehicles needed. The computational results show that all of the instances from 50 stations up to 200 stations can be solved in 7 minutes with a gap less than 7%. For the instances with 300-500 stations, the maximum computation time is up to 20 minutes.