Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

6-2017

Abstract

Due to increased traffic congestion and carbon emissions, Bike Sharing Systems (BSSs) are adopted in various cities for short distance travels, specifically for last mile transportation. The success of a bike sharing system depends on its ability to have bikes available at the "right" base stations at the "right" times. Typically, carrier vehicles are used to perform repositioning of bikes between stations so as to satisfy customer requests. Owing to the uncertainty in customer demand and day-long repositioning, the problem of having bikes available at the right base stations at the right times is a challenging one. In this paper, we propose a multi-stage stochastic formulation, to consider expected future demand over a set of scenarios to find an efficient repositioning strategy for bike sharing systems. Furthermore, we provide a Lagrangian decomposition approach (that decouples the global problem into routing and repositioning slaves and employs a novel DP approach to efficiently solve routing slave) and a greedy online anticipatory heuristic to solve large scale problems effectively and efficiently. Finally, in our experimental results, we demonstrate significant reduction in lost demand provided by our techniques on real world datasets from two bike sharing companies in comparison to existing benchmark approaches.

Discipline

Artificial Intelligence and Robotics | Computer Sciences | Transportation

Research Areas

Intelligent Systems and Optimization

Publication

Proceedings of the 27th International Conference on Automated Planning and Scheduling 27th ICAPS 2017, Pittsburgh, PA, June 18-23

First Page

200

Last Page

208

Publisher

AAAI

City or Country

Palo Alto, CA

Additional URL

https://aaai.org/ocs/index.php/ICAPS/ICAPS17/paper/view/15743

Download

Share

COinS