Achieving Location Truthfulness in Rebalancing Supply-Demand Distribution for Bike Sharing

Achieving Location Truthfulness in Rebalancing Supply-Demand Distribution for Bike Sharing
Title:
Achieving Location Truthfulness in Rebalancing Supply-Demand Distribution for Bike Sharing
Other Titles:
12th International Conference on Algorithmic Aspects of Information and Management (AAIM 2018)
DOI:
Publication URL:
Publication Date:
01 December 2018
Citation:
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 rst prove two impossibility results: (1) nding 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 rst stage and allocates tasks to users in the second stage. We show analytically that the mechanism satisfi es 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 rst to address 2-D location truthfulness in the perspective of mechanism design.
License type:
PublisherCopyrights
Funding Info:
Description:
ISBN:

Files uploaded:

File Size Format Action
aaim2018-camera-ready.pdf 412.90 KB PDF Open