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) frequentlyencountered in modern bike sharing systems. To cope with customer demand fluctuations, BSRPaims to identify the optimal routes traveled by homogeneous vehicles to fulfill the inventoryneeds at each bike-sharing station in order to minimize the total cost. It is computationallyintractable 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, anovel fuzzy clustering strategy quantitatively considering the correlation between stations isdesigned to construct the clusters with satellites and their corresponding customers to form thetwo-echelon structure. Then, a tailored fuzzy correlation based adaptive variable neighborhoodsearch (FC-AVNS) with newly designed neighborhood structures and several feasibility andsatisfaction check mechanisms is proposed to construct the routes within and between theclusters. Performance of the proposed method is compared with that of a exact model solvedby CPLEX and other three state-of-the-art methods. Also, comparisons are made between thepresented fuzzy clustering strategy and the other two classical clustering methods taken fromthe literature. Computational experiments based on medium- and large-scale instances involving100 to 519 stations are performed and the results validate the superior performance of theproposed method with respect to solution efficiency and stability

Automated summary

This paper addresses the large-scale bike sharing repositioning problem and proposes a two-echelon BSRP model using a fuzzy clustering strategy. The proposed method demonstrates superior performance in terms of solution efficiency and stability.