An enhanced artificial bee colony algorithm for the static public bike repositioning problem

Abstract

A bike repositioning problem (BRP) that simultaneously considers total demand dissatisfaction and service time is investigated. Given the conditions of each bike station before the repositioning, the problem aims to determine the routes of the repositioning vehicles that minimize the service time while the total demand dissatisfaction should be kept below an overall tolerable limit. This paper proposes two service times to be minimized: the total service time of the fleet and the maximum route duration. To reduce the computation time to solve the loading and unloading sub-problem of the BRP, this paper proposes and examines a novel set of loading and unloading strategies and further proves them to be optimal strategies for a given route. This set of strategies is then embedded into an enhanced artificial bee colony (ABC) algorithm to solve the BRP. To improve the effectiveness of the solution process, an enhanced version is proposed to improve the solution quality of the original version. The performance of the modified heuristic was evaluated and compared with the original heuristic and the Genetic Algorithm (GA). The computational results show that the enhanced heuristic outperforms both the original ABC algorithm and the GA with similar computation time. These results, therefore, demonstrate that the modified heuristic can be an alternative to solve the BRP. The numerical studies demonstrate that an increase in fleet size may not lead to a lower service time. The studies also illustrate the trade-offs between each objective with the tolerance of total demand dissatisfaction, the trade-off between the two service time objectives, and the effect of fleet size. This paper, therefore, discusses the practical implications of the trade-offs and provide suggestions about similar repositioning operations.