A two-echelon fuzzy clustering based heuristic for large-scale bike sharing repositioning problem. (June 2022)

• Record Type: Journal Article
• Authors: Lv, Chang; Zhang, Chaoyong; Lian, Kunlei; Ren, Yaping; Meng, Leilei
• Is Part Of: Transportation research. Volume 160(2022)
• Page Start: 54
• Page End: 75
• Publication Date: 2022-06
• Subjects: Routing -- Heuristics -- Bike sharing -- Redistribution -- Fuzzy clustering; Transportation -- Research -- Periodicals; Transportation -- Mathematical models -- Periodicals
• DOI: 10.1016/j.trb.2022.04.003
• Languages: English
• ISSNs: 0191-2615

Abstract

Abstract: 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. Highlights: The two-echelon structure from VRP literature is first adapted to solve BSRP. A fuzzy clustering strategy is designed considering both distance and inventory factors. Objective functions with traveling cost, inventory cost and service level are considered. A tailored fuzzy correlation based adaptive variable neighborhood search is provided.