A two-phase heuristic approach to the bike repositioning problem.

• Bike repositioning problem with service requirements for rental and return requests was studied. • A mathematical model with the goal of minimizing the travel and unsatisfied costs was developed. • An efficient two-phase heuristic approach based on linear programming was proposed. • The proposed approach performs better than CPLEX optimizer and a genetic algorithm-based method. • The effects of various system parameters on the system were also investigated. An approach to overcome the bike imbalance problem is to transfer excess bikes to branches with bike shortages. This study develops a constrained mathematical model to deal with a multi-vehicle bike-repositioning problem, and aims to minimize the sum of transportation and unmet demand costs over a planning horizon through bike-transfer strategies under a minimum service requirement. A two-phase heuristic based on linear programming was proposed to solve the problem and produce compromising solutions. In the first phase, the paper developed a linear programming model to quickly develop decisions related to bike inventory, unloading, and loading for all stations for each time slot. In the second phase, this paper proposed an iterative approach through two parameter sensitive mathematical models to sequentially reduce the problem scale to develop decisions related to bike transfers. Computational results show that the proposed approach is superior to a CPLEX optimizer and a hybrid heuristic based on a genetic algorithm. The proposed approach was used to analyze the bicycle system in Taiwan. The impacts of various system parameters on the system were also investigated. [ABSTRACT FROM AUTHOR]