Towards optimal free-of-charge trip planning in bike-sharing systems

Jian Xu, Jianliang XU, Guanjie Cao, Haitao Xu, Ming Xu, Ning Zheng

Research output: Chapter in book/report/conference proceedingConference contributionpeer-review

1 Citation (Scopus)

Abstract

Most bike-sharing service providers offer a free ride for a short time period. In this paper, we study how to find the optimal route that is free of rental cost and minimizes the trip distance from one location to another within a bike-sharing system, in which the utilization of bike stations dynamically changes over time. We use a time-dependent dynamic graph to model the network of bike stations. In the graph, each vertex represents a bike station and is associated with a vertex-usage function. The difficulty of this problem is mainly attributed to the fluctuation of the usage function because a fully utilized station cannot accept returned bikes. Efficiency is another challenge, as we must explore all possible paths between the source and the destination. To address these challenges, we propose techniques to find a solution optimized for efficiency. First, to reduce the search space, we construct a station network graph on top of a road network. Next, we employ a pathstree to identify all the paths with lengths less than the userpreferred maximum detour distance and we select an optimal path toward the destination. We present the design details of our algorithms and we analyze the algorithms' correctness and complexity. To demonstrate the feasibility of our methods, we also report the results from the extensive experiments we conducted.

Original languageEnglish
Title of host publicationProceedings - 18th IEEE International Conference on Mobile Data Management, MDM 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages92-101
Number of pages10
ISBN (Electronic)9781538639320
DOIs
Publication statusPublished - 29 Jun 2017
Event18th IEEE International Conference on Mobile Data Management, MDM 2017 - Daejeon, Korea, Republic of
Duration: 29 May 20171 Jun 2017

Publication series

NameProceedings - 18th IEEE International Conference on Mobile Data Management, MDM 2017

Conference

Conference18th IEEE International Conference on Mobile Data Management, MDM 2017
Country/TerritoryKorea, Republic of
CityDaejeon
Period29/05/171/06/17

Scopus Subject Areas

  • Hardware and Architecture
  • Computer Networks and Communications
  • Information Systems and Management

User-Defined Keywords

  • Bike-sharing
  • Trip planning

Fingerprint

Dive into the research topics of 'Towards optimal free-of-charge trip planning in bike-sharing systems'. Together they form a unique fingerprint.

Cite this