Achieving location truthfulness in rebalancing supply-demand distribution for bike sharing

Hongtao Lv; Fan Wu; Tie Luo; Xiaofeng Gao; Guihai Chen

doi:10.1007/978-3-030-04618-7_21

Achieving location truthfulness in rebalancing supply-demand distribution for bike sharing

Hongtao Lv, Fan Wu, Tie Luo, Xiaofeng Gao, Guihai Chen

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Scopus citations

Abstract

Recently, station-free Bike sharing as an environment-friendly transportation alternative has received wide adoption in many cities due to its flexibility of allowing bike parking at anywhere. How to incentivize users to park bikes at desired locations that match bike demands - a problem which we refer to as a rebalancing problem - has emerged as a new and interesting challenge. In this paper, we propose a solution under a crowdsourcing framework where users report their original destinations and the bike sharing platform assigns proper relocation tasks to them. We first prove two impossibility results: (1) finding an optimal solution to the bike rebalancing problem is NP-hard, and (2) there is no approximate mechanism with bounded approximation ratio that is both truthful and budget-feasible. Therefore, we design a two-stage heuristic mechanism which selects an independent set of locations in the first stage and allocates tasks to users in the second stage. We show analytically that the mechanism satisfies location truthfulness, budget feasibility and individual rationality. In addition, extensive experiments are conducted to demonstrate the effectiveness of our mechanism. To the best of our knowledge, we are the first to address 2-D location truthfulness in the perspective of mechanism design.

Original language	English
Title of host publication	Algorithmic Aspects in Information and Management - 12th International Conference, AAIM 2018, Proceedings
Editors	Sergiy Butenko, Shaojie Tang, Ding-Zhu Du, David Woodruff
Pages	256-267
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-030-04618-7_21
State	Published - 2018
Event	12th International Conference on Algorithmic Aspects in Information and Management, AAIM 2018 - Dallas, United States Duration: Dec 3 2018 → Dec 4 2018

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11343 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	12th International Conference on Algorithmic Aspects in Information and Management, AAIM 2018
Country/Territory	United States
City	Dallas
Period	12/3/18 → 12/4/18

Bibliographical note

Publisher Copyright:
© Springer Nature Switzerland AG 2018.

Funding

This work was supported in part by the National Key R&D Program of China 2018YFB1004703, in part by China NSF grant 61672348, 61672353, and 61472252. The opinions, findings, conclusions, and recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the funding agencies or the government.

Funders	Funder number
NSF of China
National Key Basic Research Program of China	2018YFB1004703
U.S. Department of Energy Chinese Academy of Sciences Guangzhou Municipal Science and Technology Project Oak Ridge National Laboratory Extreme Science and Engineering Discovery Environment National Science Foundation National Energy Research Scientific Computing Center National Natural Science Foundation of China	61472252, 61672348, 61672353

Keywords

Bike sharing
Location truthfulness
Mechanism design

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

UN SDGs

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

Access to Document

10.1007/978-3-030-04618-7_21

Cite this

Lv, H., Wu, F., Luo, T., Gao, X., & Chen, G. (2018). Achieving location truthfulness in rebalancing supply-demand distribution for bike sharing. In S. Butenko, S. Tang, D.-Z. Du, & D. Woodruff (Eds.), Algorithmic Aspects in Information and Management - 12th International Conference, AAIM 2018, Proceedings (pp. 256-267). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11343 LNCS). https://doi.org/10.1007/978-3-030-04618-7_21

Lv, Hongtao ; Wu, Fan ; Luo, Tie et al. / Achieving location truthfulness in rebalancing supply-demand distribution for bike sharing. Algorithmic Aspects in Information and Management - 12th International Conference, AAIM 2018, Proceedings. editor / Sergiy Butenko ; Shaojie Tang ; Ding-Zhu Du ; David Woodruff. 2018. pp. 256-267 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b6ac25ac94c24d8cbf8403cdf4ceec65,

title = "Achieving location truthfulness in rebalancing supply-demand distribution for bike sharing",

abstract = "Recently, station-free Bike sharing as an environment-friendly transportation alternative has received wide adoption in many cities due to its flexibility of allowing bike parking at anywhere. How to incentivize users to park bikes at desired locations that match bike demands - a problem which we refer to as a rebalancing problem - has emerged as a new and interesting challenge. In this paper, we propose a solution under a crowdsourcing framework where users report their original destinations and the bike sharing platform assigns proper relocation tasks to them. We first prove two impossibility results: (1) finding an optimal solution to the bike rebalancing problem is NP-hard, and (2) there is no approximate mechanism with bounded approximation ratio that is both truthful and budget-feasible. Therefore, we design a two-stage heuristic mechanism which selects an independent set of locations in the first stage and allocates tasks to users in the second stage. We show analytically that the mechanism satisfies location truthfulness, budget feasibility and individual rationality. In addition, extensive experiments are conducted to demonstrate the effectiveness of our mechanism. To the best of our knowledge, we are the first to address 2-D location truthfulness in the perspective of mechanism design.",

keywords = "Bike sharing, Location truthfulness, Mechanism design",

author = "Hongtao Lv and Fan Wu and Tie Luo and Xiaofeng Gao and Guihai Chen",

note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2018.; 12th International Conference on Algorithmic Aspects in Information and Management, AAIM 2018 ; Conference date: 03-12-2018 Through 04-12-2018",

year = "2018",

doi = "10.1007/978-3-030-04618-7\_21",

language = "English",

isbn = "9783030046170",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "256--267",

editor = "Sergiy Butenko and Shaojie Tang and Ding-Zhu Du and David Woodruff",

booktitle = "Algorithmic Aspects in Information and Management - 12th International Conference, AAIM 2018, Proceedings",

}

Lv, H, Wu, F, Luo, T, Gao, X & Chen, G 2018, Achieving location truthfulness in rebalancing supply-demand distribution for bike sharing. in S Butenko, S Tang, D-Z Du & D Woodruff (eds), Algorithmic Aspects in Information and Management - 12th International Conference, AAIM 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11343 LNCS, pp. 256-267, 12th International Conference on Algorithmic Aspects in Information and Management, AAIM 2018, Dallas, United States, 12/3/18. https://doi.org/10.1007/978-3-030-04618-7_21

Achieving location truthfulness in rebalancing supply-demand distribution for bike sharing. / Lv, Hongtao; Wu, Fan; Luo, Tie et al.
Algorithmic Aspects in Information and Management - 12th International Conference, AAIM 2018, Proceedings. ed. / Sergiy Butenko; Shaojie Tang; Ding-Zhu Du; David Woodruff. 2018. p. 256-267 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11343 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Achieving location truthfulness in rebalancing supply-demand distribution for bike sharing

AU - Lv, Hongtao

AU - Wu, Fan

AU - Luo, Tie

AU - Gao, Xiaofeng

AU - Chen, Guihai

N1 - Publisher Copyright: © Springer Nature Switzerland AG 2018.

PY - 2018

Y1 - 2018

N2 - Recently, station-free Bike sharing as an environment-friendly transportation alternative has received wide adoption in many cities due to its flexibility of allowing bike parking at anywhere. How to incentivize users to park bikes at desired locations that match bike demands - a problem which we refer to as a rebalancing problem - has emerged as a new and interesting challenge. In this paper, we propose a solution under a crowdsourcing framework where users report their original destinations and the bike sharing platform assigns proper relocation tasks to them. We first prove two impossibility results: (1) finding an optimal solution to the bike rebalancing problem is NP-hard, and (2) there is no approximate mechanism with bounded approximation ratio that is both truthful and budget-feasible. Therefore, we design a two-stage heuristic mechanism which selects an independent set of locations in the first stage and allocates tasks to users in the second stage. We show analytically that the mechanism satisfies location truthfulness, budget feasibility and individual rationality. In addition, extensive experiments are conducted to demonstrate the effectiveness of our mechanism. To the best of our knowledge, we are the first to address 2-D location truthfulness in the perspective of mechanism design.

AB - Recently, station-free Bike sharing as an environment-friendly transportation alternative has received wide adoption in many cities due to its flexibility of allowing bike parking at anywhere. How to incentivize users to park bikes at desired locations that match bike demands - a problem which we refer to as a rebalancing problem - has emerged as a new and interesting challenge. In this paper, we propose a solution under a crowdsourcing framework where users report their original destinations and the bike sharing platform assigns proper relocation tasks to them. We first prove two impossibility results: (1) finding an optimal solution to the bike rebalancing problem is NP-hard, and (2) there is no approximate mechanism with bounded approximation ratio that is both truthful and budget-feasible. Therefore, we design a two-stage heuristic mechanism which selects an independent set of locations in the first stage and allocates tasks to users in the second stage. We show analytically that the mechanism satisfies location truthfulness, budget feasibility and individual rationality. In addition, extensive experiments are conducted to demonstrate the effectiveness of our mechanism. To the best of our knowledge, we are the first to address 2-D location truthfulness in the perspective of mechanism design.

KW - Bike sharing

KW - Location truthfulness

KW - Mechanism design

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

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

U2 - 10.1007/978-3-030-04618-7_21

DO - 10.1007/978-3-030-04618-7_21

M3 - Conference contribution

AN - SCOPUS:85058486410

SN - 9783030046170

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 256

EP - 267

BT - Algorithmic Aspects in Information and Management - 12th International Conference, AAIM 2018, Proceedings

A2 - Butenko, Sergiy

A2 - Tang, Shaojie

A2 - Du, Ding-Zhu

A2 - Woodruff, David

T2 - 12th International Conference on Algorithmic Aspects in Information and Management, AAIM 2018

Y2 - 3 December 2018 through 4 December 2018

ER -

Lv H, Wu F, Luo T, Gao X, Chen G. Achieving location truthfulness in rebalancing supply-demand distribution for bike sharing. In Butenko S, Tang S, Du DZ, Woodruff D, editors, Algorithmic Aspects in Information and Management - 12th International Conference, AAIM 2018, Proceedings. 2018. p. 256-267. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-04618-7_21

Achieving location truthfulness in rebalancing supply-demand distribution for bike sharing

Abstract

Publication series

Conference

Bibliographical note

Funding

Keywords

ASJC Scopus subject areas

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this