A two-echelon fuzzy clustering based heuristic for large-scale bike sharing repositioning problem

This paper considers the large-scale bike sharing repositioning problem (BSRP) frequently encountered in modern bike sharing systems. To cope with customer demand fluctuations, BSRP aims to identify the optimal routes traveled by homogeneous vehicles to fulfill the inventory needs at each bike-sharing station in order to minimize the total cost. It is computationally intractable to obtain promising solutions, especially for large-scale instances, given its NP-hardness. This paper adapts the two-echelon structure from the vehicle routing problem (VRP) to BSRP, proposes the two-echelon BSRP model and demonstrates its competitiveness. First, a novel fuzzy clustering strategy quantitatively considering the correlation between stations is designed to construct the clusters with satellites and their corresponding customers to form the two-echelon structure. Then, a tailored fuzzy correlation based adaptive variable neighborhood search (FC-AVNS) with newly designed neighborhood structures and several feasibility and satisfaction check mechanisms is proposed to construct the routes within and between the clusters. Performance of the proposed method is compared with that of a exact model solved by CPLEX and other three state-of-the-art methods. Also, comparisons are made between the presented fuzzy clustering strategy and the other two classical clustering methods taken from the literature. Computational experiments based on medium- and large-scale instances involving 100 to 519 stations are performed and the results validate the superior performance of the proposed method with respect to solution efficiency and stability.