Evolutionary algorithm for vehicle routing for shared e-bicycle battery replacement and recycling
Yu‐Jun Zheng, Xin Chen, Hong-Fang Yan, Minxia Zhang
Abstract
Shared electric bicycles (e-bicycles) are becoming an increasingly popular model of sharing economy that provides the public with a convenient and labor-saving transport alternative. Efficient battery replacement is critical to maintain the operational capability of e-bicycles, but is quite difficult as there are often a large number of e-bicycles that are widely dispersed. In this paper, we study a problem of scheduling multiple vehicles to deliver fully-charged batteries to and take back low-power batteries from shared e-bicycles scattered in numerous parking spots, while the low-power batteries are recharged in battery depots for potential re-utilization. The aim of this problem is to minimize the completion time of all battery replacement tasks so as to keep a high operational efficiency of the system. The problem differs from existing vehicle routing problems in two main special features: (1) equivalent exchange of fully-charged batteries and low-power batteries; (2) recycling of batteries. To efficiently solve this special problem, we propose an evolutionary algorithm using variable local-search-based mutation to balance global exploration and local exploitation and employing enhanced local search around each newly found best known solution to improve accuracy. Experiments on test instances and real-world instances demonstrate the competitive performance of the proposed method.