  The growing popularity of bike-sharing systems around the world has motivated
recent attention to models and algorithms for their effective operation. Most
of this literature focuses on their daily operation for managing asymmetric
demand. In this work, we consider the more strategic question of how to
(re-)allocate dock-capacity in such systems. We develop mathematical
formulations for variations of this problem (either for service performance
over the course of one day or for a long-run-average) and exhibit discrete
convex properties in associated optimization problems. This allows us to design
a practically fast polynomial-time allocation algorithm to compute an optimal
solution for this problem, which can also handle practically motivated
constraints, such as a limit on the number of docks moved in the system.
  We apply our algorithm to data sets from Boston, New York City, and Chicago
to investigate how different dock allocations can yield better service in these
systems. Recommendations based on our analysis have led to changes in the
system design in Chicago and New York City. Beyond optimizing for improved
quality of service through better allocations, our results also provide a
metric to compare the impact of strategically reallocating docks and the
rebalancing of bikes.
