An artificial bee colony algorithm for public bike repositioning problem

Abstract

Public bike repositioning is crucial in public bike sharing systems due to the imbalanced distribution of public bikes. This paper models the public bike repositioning problem (PBRP) involving two non-linear objectives, which are to minimize total service duration and the duration of the longest vehicle route. It includes practical constraints such as the tolerance of demand dissatisfaction and the limitation of duration on the longest route. These objective functions and constraints make the PBRP become NP-hard, so here introduces an artificial bee colony (ABC) algorithm to solve this PBRP. Three neighbourhood operators are introduced to improve the solution search. A modified ABC is proposed to further improve the solution quality. The performance of the modified heuristic was evaluated with the network of Vélib', and compared with the original heuristic and the Genetic Algorithm. These results may therefore prove that the modified heuristic can be an alternative to solve the PBRP. The numerical studies demonstrated that the two objective functions performed differently in which the increase in fleet size may not improve the objective value. This paper will therefore discuss on the practical implications of the trade-offs and provide suggestions about similar repositioning operations.