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

  • 1 Balancing Bicycle Sharing Systems
    • 1.1 Problem Definition
    • 1.2 Approaches
    • 1.3 Problem Instances
    • 1.4 Publications related to Balancing Bike Sharing Systems

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

  • New FWF ESPRIT Postdocs

    New FWF ESPRIT Postdocs

    2022-11-09
    Leroy Chew and Alexis de Colnet just joined the Algorithms and Complexity group as PIs of their own FWF ESPRIT …Read More »
  • Best student paper award at DIAGRAMS 2022

    Best student paper award at DIAGRAMS 2022

    2022-10-01
    Alexander Dobler received the Best Student Paper Award at the 13th International Conference on the Theory and Application of Diagrams …Read More »
  • Robert Ganian promoted to Associate Professor

    Robert Ganian promoted to Associate Professor

    2022-07-01
    Effective as of today, Robert Ganian is promoted to a tenured Associate Professor at the Algorithms and Complexity group. Congratulations, …Read More »
  • Best paper award at EvoCOP 2022

    Best paper award at EvoCOP 2022

    2022-05-24
    Jonas Mayerhofer, Markus Kirchweger, Marc Huber, and Günther Raidl received the best paper award for their work A Beam Search …Read More »
  • New PhD: Guangping Li

    New PhD: Guangping Li

    2022-05-13
    Guangping Li successfully defended her PhD thesis “An Algorithmic Study of Practical Map Labeling” on May 13, 2022. Congratulations, Dr. …Read More »

News archive

All news for 2015, 2016, 2017, 2018, 2019, 2020, 2021 and 2022.
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.