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

Chang Lv, Chaoyong Zhang, Kunlei Lian, Yaping Ren and Leilei Meng

Transportation Research Part B: Methodological, 2022, vol. 160, issue C, 54-75

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.

Keywords: Routing; Heuristics; Bike sharing; Redistribution; Fuzzy clustering (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261522000662
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:160:y:2022:i:c:p:54-75

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2022.04.003

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().