Rebalancing Bike Sharing Systems: A Multi-source Data Smart Optimization

Junming Liu; Leilei Sun; Weiwei Chen; Hui Xiong

doi:10.1145/2939672.2939776

Rebalancing Bike Sharing Systems: A Multi-source Data Smart Optimization

Junming Liu, Leilei Sun, Weiwei Chen, Hui Xiong^*

^*Corresponding author for this work

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

196 Citations (Scopus)

Abstract

Bike sharing systems, aiming at providing the missing links in public transportation systems, are becoming popular in urban cities. A key to success for a bike sharing systems is the effectiveness of rebalancing operations, that is, the efforts of restoring the number of bikes in each station to its target value by routing vehicles through pick-up and drop-off operations. There are two major issues for this bike rebalancing problem: the determination of station inventory target level and the large scale multiple capacitated vehicle routing optimization with outlier stations. The key challenges include demand prediction accuracy for inventory target level determination, and an effective optimizer for vehicle routing with hundreds of stations. To this end, in this paper, we develop a Meteorology Similarity Weighted K-Nearest-Neighbor (MSWK) regressor to predict the station pick-up demand based on large-scale historic trip records. Based on further analysis on the station network constructed by station-station connections and the trip duration, we propose an inter station bike transition (ISBT) model to predict the station drop-off demand. Then, we provide a mixed integer nonlinear programming (MINLP) formulation of multiple capacitated bike routing problem with the objective of minimizing total travel distance. To solve it, we propose an Adaptive Capacity Constrained K-centers Clustering (AdaCCKC) algorithm to separate outlier stations (the demands of these stations are very large and make the optimization infeasible) and group the rest stations into clusters within which one vehicle is scheduled to redistribute bikes between stations. In this way, the large scale multiple vehicle routing problem is reduced to inner cluster one vehicle routing problem with guaranteed feasible solutions. Finally, the extensive experimental results on the NYC Citi Bike system show the advantages of our approach for bike demand prediction and large-scale bike rebalancing optimization.

Original language	English
Title of host publication	KDD 2016 - Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Publisher	Association for Computing Machinery
Pages	1005-1014
Number of pages	10
ISBN (Electronic)	9781450342322
DOIs	https://doi.org/10.1145/2939672.2939776
Publication status	Published - 13 Aug 2016
Externally published	Yes
Event	22nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2016) - San Francisco, United States Duration: 13 Aug 2016 → 17 Aug 2016 https://www.kdd.org/kdd2016/

Publication series

Name	Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Volume	13-17-August-2016

Conference

Conference	22nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2016)
Abbreviated title	KDD 2016
Place	United States
City	San Francisco
Period	13/08/16 → 17/08/16
Internet address	https://www.kdd.org/kdd2016/

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 9 Industry, Innovation, and Infrastructure
SDG 11 Sustainable Cities and Communities

Research Keywords

Bike sharing system
Clustering
Optimization

Access Output

10.1145/2939672.2939776

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Liu, J., Sun, L., Chen, W., & Xiong, H. (2016). Rebalancing Bike Sharing Systems: A Multi-source Data Smart Optimization. In KDD 2016 - Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 1005-1014). (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; Vol. 13-17-August-2016). Association for Computing Machinery. https://doi.org/10.1145/2939672.2939776

Liu, Junming ; Sun, Leilei ; Chen, Weiwei et al. / Rebalancing Bike Sharing Systems : A Multi-source Data Smart Optimization. KDD 2016 - Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery, 2016. pp. 1005-1014 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining).

@inproceedings{9ec074d303a540bb83d49afe382dcb8b,

title = "Rebalancing Bike Sharing Systems: A Multi-source Data Smart Optimization",

abstract = "Bike sharing systems, aiming at providing the missing links in public transportation systems, are becoming popular in urban cities. A key to success for a bike sharing systems is the effectiveness of rebalancing operations, that is, the efforts of restoring the number of bikes in each station to its target value by routing vehicles through pick-up and drop-off operations. There are two major issues for this bike rebalancing problem: the determination of station inventory target level and the large scale multiple capacitated vehicle routing optimization with outlier stations. The key challenges include demand prediction accuracy for inventory target level determination, and an effective optimizer for vehicle routing with hundreds of stations. To this end, in this paper, we develop a Meteorology Similarity Weighted K-Nearest-Neighbor (MSWK) regressor to predict the station pick-up demand based on large-scale historic trip records. Based on further analysis on the station network constructed by station-station connections and the trip duration, we propose an inter station bike transition (ISBT) model to predict the station drop-off demand. Then, we provide a mixed integer nonlinear programming (MINLP) formulation of multiple capacitated bike routing problem with the objective of minimizing total travel distance. To solve it, we propose an Adaptive Capacity Constrained K-centers Clustering (AdaCCKC) algorithm to separate outlier stations (the demands of these stations are very large and make the optimization infeasible) and group the rest stations into clusters within which one vehicle is scheduled to redistribute bikes between stations. In this way, the large scale multiple vehicle routing problem is reduced to inner cluster one vehicle routing problem with guaranteed feasible solutions. Finally, the extensive experimental results on the NYC Citi Bike system show the advantages of our approach for bike demand prediction and large-scale bike rebalancing optimization.",

keywords = "Bike sharing system, Clustering, Optimization",

author = "Junming Liu and Leilei Sun and Weiwei Chen and Hui Xiong",

year = "2016",

month = aug,

day = "13",

doi = "10.1145/2939672.2939776",

language = "English",

series = "Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

publisher = "Association for Computing Machinery",

pages = "1005--1014",

booktitle = "KDD 2016 - Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

address = "United States",

note = "22nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2016), KDD 2016 ; Conference date: 13-08-2016 Through 17-08-2016",

url = "https://www.kdd.org/kdd2016/",

}

Liu, J, Sun, L, Chen, W & Xiong, H 2016, Rebalancing Bike Sharing Systems: A Multi-source Data Smart Optimization. in KDD 2016 - Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, vol. 13-17-August-2016, Association for Computing Machinery, pp. 1005-1014, 22nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2016), San Francisco, United States, 13/08/16. https://doi.org/10.1145/2939672.2939776

Rebalancing Bike Sharing Systems: A Multi-source Data Smart Optimization. / Liu, Junming; Sun, Leilei; Chen, Weiwei et al.
KDD 2016 - Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery, 2016. p. 1005-1014 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; Vol. 13-17-August-2016).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Rebalancing Bike Sharing Systems

T2 - 22nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2016)

AU - Liu, Junming

AU - Sun, Leilei

AU - Chen, Weiwei

AU - Xiong, Hui

PY - 2016/8/13

Y1 - 2016/8/13

N2 - Bike sharing systems, aiming at providing the missing links in public transportation systems, are becoming popular in urban cities. A key to success for a bike sharing systems is the effectiveness of rebalancing operations, that is, the efforts of restoring the number of bikes in each station to its target value by routing vehicles through pick-up and drop-off operations. There are two major issues for this bike rebalancing problem: the determination of station inventory target level and the large scale multiple capacitated vehicle routing optimization with outlier stations. The key challenges include demand prediction accuracy for inventory target level determination, and an effective optimizer for vehicle routing with hundreds of stations. To this end, in this paper, we develop a Meteorology Similarity Weighted K-Nearest-Neighbor (MSWK) regressor to predict the station pick-up demand based on large-scale historic trip records. Based on further analysis on the station network constructed by station-station connections and the trip duration, we propose an inter station bike transition (ISBT) model to predict the station drop-off demand. Then, we provide a mixed integer nonlinear programming (MINLP) formulation of multiple capacitated bike routing problem with the objective of minimizing total travel distance. To solve it, we propose an Adaptive Capacity Constrained K-centers Clustering (AdaCCKC) algorithm to separate outlier stations (the demands of these stations are very large and make the optimization infeasible) and group the rest stations into clusters within which one vehicle is scheduled to redistribute bikes between stations. In this way, the large scale multiple vehicle routing problem is reduced to inner cluster one vehicle routing problem with guaranteed feasible solutions. Finally, the extensive experimental results on the NYC Citi Bike system show the advantages of our approach for bike demand prediction and large-scale bike rebalancing optimization.

AB - Bike sharing systems, aiming at providing the missing links in public transportation systems, are becoming popular in urban cities. A key to success for a bike sharing systems is the effectiveness of rebalancing operations, that is, the efforts of restoring the number of bikes in each station to its target value by routing vehicles through pick-up and drop-off operations. There are two major issues for this bike rebalancing problem: the determination of station inventory target level and the large scale multiple capacitated vehicle routing optimization with outlier stations. The key challenges include demand prediction accuracy for inventory target level determination, and an effective optimizer for vehicle routing with hundreds of stations. To this end, in this paper, we develop a Meteorology Similarity Weighted K-Nearest-Neighbor (MSWK) regressor to predict the station pick-up demand based on large-scale historic trip records. Based on further analysis on the station network constructed by station-station connections and the trip duration, we propose an inter station bike transition (ISBT) model to predict the station drop-off demand. Then, we provide a mixed integer nonlinear programming (MINLP) formulation of multiple capacitated bike routing problem with the objective of minimizing total travel distance. To solve it, we propose an Adaptive Capacity Constrained K-centers Clustering (AdaCCKC) algorithm to separate outlier stations (the demands of these stations are very large and make the optimization infeasible) and group the rest stations into clusters within which one vehicle is scheduled to redistribute bikes between stations. In this way, the large scale multiple vehicle routing problem is reduced to inner cluster one vehicle routing problem with guaranteed feasible solutions. Finally, the extensive experimental results on the NYC Citi Bike system show the advantages of our approach for bike demand prediction and large-scale bike rebalancing optimization.

KW - Bike sharing system

KW - Clustering

KW - Optimization

UR - http://www.scopus.com/inward/record.url?scp=84985038239&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84985038239&origin=recordpage

U2 - 10.1145/2939672.2939776

DO - 10.1145/2939672.2939776

M3 - RGC 32 - Refereed conference paper (with host publication)

AN - SCOPUS:84985038239

T3 - Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

SP - 1005

EP - 1014

BT - KDD 2016 - Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

PB - Association for Computing Machinery

Y2 - 13 August 2016 through 17 August 2016

ER -

Liu J, Sun L, Chen W, Xiong H. Rebalancing Bike Sharing Systems: A Multi-source Data Smart Optimization. In KDD 2016 - Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery. 2016. p. 1005-1014. (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining). doi: 10.1145/2939672.2939776

Rebalancing Bike Sharing Systems: A Multi-source Data Smart Optimization

Abstract

Publication series

Conference

UN SDGs

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this