Balancing Bicycle Sharing Systems
Kloimüllner, Papazek, Raidl, Hu
Public bicycle sharing systems are booming worldwide in many major
cities. Such systems augment public transport very well, are green
alternatives to motorized individual traffic, may decrease traffic jams
and parking problems in cities to a certain extent, and last but not
least are an incentive for sports and a significant contribution to
public health. Modern systems have automated rental stations
distributed over the (inner) districts of the city, and users can easily
rent bicycles and bring them back at any other stations.
For user acceptance it is essential to provide enough bicycles as well
as parking slots for returning them at any station at almost all time.
As the usage pattern typically is not symmetric, e.g., people tend to
rent bikes at topographically higher stations and return them to lower
stations, an active maintenance by regularly transporting bikes from
some stations to others is crucial.
Project partners:
- Austrian Institute of Technology
- Citybike Wien
- Energy and Environment Agency of Lower Austria
- Luca Di Gaspero, University of Udine, Italy
Contents
Problem Definition
The balancing bike sharing systems (BBSS) problem consists of finding an optimal rebalancing plan for the operator that consists of
- a route for each vehicle on duty and
- loading instructions for each station on the route
so that the system is in a balanced condition afterwards, i.e., no station is overly full or empty.
Two basic problem variants are considered:
- Static case: The rebalancing process is done when the system is not used (e.g., overnight). Initial and target station fill levels are given as constants.
- Dynamic case: The system is rebalanced while in use. Station fill levels are time-dependent and estimated by empirical data.
Approaches
Exact approaches based on mixed integer programming:
- Hop index model
- Time index model
Construction heuristics:
- Greedy heuristic
- PILOT heuristic
Metaheuristic approaches:
- Variable neighborhood search approach
- GRASP approach
- Hybrid of GRASP with Path Relinking
Problem Instances
Problem instances which we are using for our work can be found here.
