Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 257, Issue 3, Pages 992-1004Publisher
ELSEVIER
DOI: 10.1016/j.ejor.2016.08.029
Keywords
Bike sharing; Routing; Inventory; Integer programming; Constraint programming; Markov processes
Funding
- National Science Foundation [1055832]
- Directorate For Engineering
- Div Of Civil, Mechanical, & Manufact Inn [1055832] Funding Source: National Science Foundation
Ask authors/readers for more resources
Bike sharing systems have been installed in many cities around the world and are increasing in popularity. A major operational cost driver in these systems is rebalancing the bikes over time such that the appropriate number of bikes and open docks are available to users. We combine two aspects that have previously been handled separately in the literature: determining service level requirements at each bike sharing station, and designing (near-)optimal vehicle routes to rebalance the inventory. Since finding provably optimal solutions is practically intractable, we propose a new cluster-first route-second heuristic, in which a polynomial-size Clustering Problem simultaneously considers the service level feasibility and approximate routing costs. Extensive computational results on real-world data from Hubway (Boston, MA) and Capital Bikeshare (Washington, DC) are provided, which show that our heuristic outperforms a pure mixed-integer programming formulation and a constraint programming approach. (C) 2016 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available