Algorithms and Complexity Group
  • People
  • Research
  • Courses
  • Talks
  • Jobs
  • Contact

Balancing Bicycle Sharing Systems

BBSS

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.

Publications related to Balancing Bike Sharing Systems

7 results
2019
[7]Algorithmic Approaches for Optimization Problems in Bike Sharing and Security Control
Christian Kloimüllner
mar 2019, PhD thesis, Institute of Logic and Computation, TU Wien.
Note: supervised by Günther R. Raidl
[bibtex] [pdf]
2015
[6]PILOT, GRASP, and VNS Approaches for the Static Balancing of Bicycle Sharing Systems
Marian Rainer-Harbach, Petrina Papazek, Günther R. Raidl, Bin Hu, Christian Kloimüllner
Journal of Global Optimization, volume 63, number 3, pages 597-629, 2015, Springer.
[bibtex] [pdf] [doi]
2014
[5]Balancing Bicycle Sharing Systems: An Analysis of Path Relinking and Recombination within a GRASP Hybrid
Petrina Papazek, Christian Kloimüllner, Bin Hu, Günther R. Raidl
Parallel Problem Solving from Nature – PPSN XIII (Thomas Bartz-Beielstein, Jürgen Branke, Bogdan Filipic, Jim Smith, eds.), volume 8672 of LNCS, pages 792–801, 2014, Springer.
[bibtex] [pdf] [doi]
[4]Balancing Bicycle Sharing Systems: An Approach for the Dynamic Case
Christian Kloimüllner, Petrina Papazek, Bin Hu, Günther R. Raidl
Evolutionary Computation in Combinatorial Optimization – EvoCOP 2014 (Christian Blum, Gabriela Ochoa, eds.), volume 8600 of LNCS, pages 73–84, 2014, Springer.
[bibtex] [pdf] [doi]
2013
[3]Balancing Bicycle Sharing Systems: A Variable Neighborhood Search Approach
Marian Rainer-Harbach, Petrina Papazek, Bin Hu, Günther R. Raidl
Evolutionary Computation in Combinatorial Optimisation – 13th European Conference, EvoCOP 2013 (M. Middendorf, C. Blum, eds.), volume 7832 of LNCS, pages 121-132, 2013, Springer.
[bibtex] [pdf]
[2]Balancing Bicycle Sharing Systems: Improving a VNS by Efficiently Determining Optimal Loading Operations
Günther R. Raidl, Bin Hu, Marian Rainer-Harbach, Petrina Papazek
Hybrid Metaheuristics, 8th Int. Workshop, HM 2013 (M. J. Blesa, others, eds.), volume 7919 of LNCS, pages 130–143, 2013, Springer.
[bibtex] [pdf]
[1]A PILOT/VND/GRASP Hybrid for the Static Balancing of Public Bicycle Sharing Systems
Petrina Papazek, Günther R. Raidl, Marian Rainer-Harbach, Bin Hu
Computer Aided Systems Theory – EUROCAST 2013 (Roberto Moreno-Díaz, Franz Pichler, Alexis Quesada-Arencibia, eds.), volume 8111 of LNCS, pages 372–379, 2013, Springer.
[bibtex] [pdf]

News

  • Best Paper Award at SOFSEM 2025

    Best Paper Award at SOFSEM 2025

    2025-01-23
    Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, and Martin Nöllenburg received the Best Paper Award for their paper …Read More »
  • Markus Wallinger receives Award of Excellence for his PhD Thesis

    Markus Wallinger receives Award of Excellence for his PhD Thesis

    2024-12-05
    Our former group member Markus Wallinger won the Award of Excellence by the Federal Ministry for Education, Science and Research. …Read More »
  • Thomas Depian receives State Prize for his Master’s Thesis

    Thomas Depian receives State Prize for his Master’s Thesis

    2024-11-21
    Our group member Thomas Depian won the Appreciation Award given by the Federal Ministry for Education, Science and Research. This …Read More »
  • Best Paper Award at GECCO 2024 for M. Bresich, G. Raidl, and S. Limmer

    Best Paper Award at GECCO 2024 for M. Bresich, G. Raidl, and S. Limmer

    2024-07-24
    Maria Bresich, Günther Raidl, and Steffen Limmer received the best paper award at the 2024 Genetic and Evolutionary Computation Conference …Read More »
  • Welcome to our Feodor Lynen Fellow Dr. Frank Sommer

    Welcome to our Feodor Lynen Fellow Dr. Frank Sommer

    2024-06-14
    On June 1, 2024, Dr. Frank Sommer has joined the Algorithms and Complexity group with a prestigious Feodor Lynen postdoc …Read More »

News archive

All news for 2015, 2016, 2017, 2018, 2019, 2020, 2021, 2022, 2023 and 2024.
TU Wien Informatics
Offenlegung (§25 MedienG) Inhaber der Website ist das Institut für Logic and Computation an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. – Disclaimer – Datenschutzerklärung
Log in requires cookies.