Chemical reaction optimization for solving a static bike repositioning problem

Abstract

Bike sharing is very popular worldwide nowadays. One common phenomenon is that the bikes are imbalanced distributed over stations and vehicles are deployed to redistribute these bikes. This operational problem is called a bike repositioning problem. The static repositioning refers to the operation which is performed in the night time. The demand and inventory at the stations are known before repositioning takes place. In this paper, a static bike repositioning problem is formulated as a mixed-integer problem (MIP) with the objective function considering the customers’ dissatisfaction and vehicle’s operational time. A new metaheuristic called chemical reaction optimization (CRO) is introduced to solve this problem. An enhanced version of CRO is proposed by adding new operators and neighbor solution search methods to the original CRO. A concept of neighbor-node set is proposed to narrow the solution search space. The computational results indicate that the enhanced CRO could provide solutions of high quality using short computing time and it outperforms the original CRO and CPLEX in the aspect of solution quality and speed.