Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

6-2015

Abstract

Extensive usage of private vehicles has led to increased traffic congestion, carbon emissions, and usage of non-renewable resources. These concerns have led to the wide adoption of vehicle sharing (ex: bike sharing, car sharing) systems in many cities of the world. In vehicle-sharing systems, base stations (ex: docking stations for bikes) are strategically placed throughout a city and each of the base stations contain a pre-determined number of vehicles at the beginning of each day. Due to the stochastic and individualistic movement of customers,there is typically either congestion (more than required)or starvation (fewer than required) of vehicles at certain base stations. As demonstrated in our experimental results, this happens often and can cause a significant loss in demand. We propose to dynamically redeploy idle vehicles using carriers so as to minimize lost demand or alternatively maximize revenue for the vehicle sharing company. To that end, we contribute an optimization formulation to jointly address the redeployment (of vehicles) and routing (of carriers) problems and provide two approaches that rely on decomposability and abstraction of problem domains to reduce the computation time significantly. Finally, we demonstrate the utility of our approaches on two real world data sets of bike-sharing companies.

Keywords

Vehicle Sharing System, Dynamic Redeployment, Lagrangian Dual Decomposition, Abstraction

Discipline

Databases and Information Systems

Publication

Proceedings of the Twenty-Fifth International Conference on Automated Planning and Scheduling: Jerusalem, Israel, June 7-11, 2015

First Page

79

Last Page

87

ISBN

9781577357315

Publisher

AAAI Press

City or Country

Menlo Park, CA

Additional URL

http://www.aaai.org/ocs/index.php/ICAPS/ICAPS15/paper/view/10602

Download

Share

COinS