An exact algorithm for the static rebalancing problem arising in bicycle sharing systems

G Erdogan, Maria Battarra, Roberto Wolfler Calvo

Research output: Contribution to journalArticle

61 Citations (Scopus)
140 Downloads (Pure)

Abstract

Bicycle sharing systems can significantly reduce traffic, pollution, and the need for parking spaces in city centers. One of the keys to success for a bicycle sharing system is the efficiency of rebalancing operations, where the number of bicycles in each station has to be restored to its target value by a truck through pickup and delivery operations. The Static Bicycle Rebalancing Problem aims to determine a minimum cost sequence of stations to be visited by a single vehicle as well as the amount of bicycles to be collected or delivered at each station. Multiple visits to a station are allowed, as well as using stations as temporary storage. This paper presents an exact algorithm for the problem and results of computational tests on benchmark instances from the literature. The computational experiments show that instances with up to 60 stations can be solved to optimality within 2 hours of computing time.
Original languageEnglish
Pages (from-to)667-679
Number of pages13
JournalEuropean Journal of Operational Research
Volume245
Issue number3
Early online date6 Apr 2015
DOIs
Publication statusPublished - 16 Sep 2015

Fingerprint

Bicycles
Exact Algorithms
Sharing
Pickup and Delivery
Pollution
Computational Experiments
Optimality
Traffic
Benchmark
Target
Computing
Costs
Pickups
Parking
Trucks
Rebalancing
Experiments
Experiment
Pickup and delivery

Keywords

  • bicycle sharing systems
  • pickup and delivery
  • multiple visits
  • branch-and-cut

Cite this

An exact algorithm for the static rebalancing problem arising in bicycle sharing systems. / Erdogan, G; Battarra, Maria; Wolfler Calvo, Roberto.

In: European Journal of Operational Research, Vol. 245, No. 3, 16.09.2015, p. 667-679.

Research output: Contribution to journalArticle

@article{7b73779f200447649a04e2ea4e101e45,
title = "An exact algorithm for the static rebalancing problem arising in bicycle sharing systems",
abstract = "Bicycle sharing systems can significantly reduce traffic, pollution, and the need for parking spaces in city centers. One of the keys to success for a bicycle sharing system is the efficiency of rebalancing operations, where the number of bicycles in each station has to be restored to its target value by a truck through pickup and delivery operations. The Static Bicycle Rebalancing Problem aims to determine a minimum cost sequence of stations to be visited by a single vehicle as well as the amount of bicycles to be collected or delivered at each station. Multiple visits to a station are allowed, as well as using stations as temporary storage. This paper presents an exact algorithm for the problem and results of computational tests on benchmark instances from the literature. The computational experiments show that instances with up to 60 stations can be solved to optimality within 2 hours of computing time.",
keywords = "bicycle sharing systems, pickup and delivery, multiple visits, branch-and-cut",
author = "G Erdogan and Maria Battarra and {Wolfler Calvo}, Roberto",
year = "2015",
month = "9",
day = "16",
doi = "10.1016/j.ejor.2015.03.043",
language = "English",
volume = "245",
pages = "667--679",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "3",

}

TY - JOUR

T1 - An exact algorithm for the static rebalancing problem arising in bicycle sharing systems

AU - Erdogan, G

AU - Battarra, Maria

AU - Wolfler Calvo, Roberto

PY - 2015/9/16

Y1 - 2015/9/16

N2 - Bicycle sharing systems can significantly reduce traffic, pollution, and the need for parking spaces in city centers. One of the keys to success for a bicycle sharing system is the efficiency of rebalancing operations, where the number of bicycles in each station has to be restored to its target value by a truck through pickup and delivery operations. The Static Bicycle Rebalancing Problem aims to determine a minimum cost sequence of stations to be visited by a single vehicle as well as the amount of bicycles to be collected or delivered at each station. Multiple visits to a station are allowed, as well as using stations as temporary storage. This paper presents an exact algorithm for the problem and results of computational tests on benchmark instances from the literature. The computational experiments show that instances with up to 60 stations can be solved to optimality within 2 hours of computing time.

AB - Bicycle sharing systems can significantly reduce traffic, pollution, and the need for parking spaces in city centers. One of the keys to success for a bicycle sharing system is the efficiency of rebalancing operations, where the number of bicycles in each station has to be restored to its target value by a truck through pickup and delivery operations. The Static Bicycle Rebalancing Problem aims to determine a minimum cost sequence of stations to be visited by a single vehicle as well as the amount of bicycles to be collected or delivered at each station. Multiple visits to a station are allowed, as well as using stations as temporary storage. This paper presents an exact algorithm for the problem and results of computational tests on benchmark instances from the literature. The computational experiments show that instances with up to 60 stations can be solved to optimality within 2 hours of computing time.

KW - bicycle sharing systems

KW - pickup and delivery

KW - multiple visits

KW - branch-and-cut

U2 - 10.1016/j.ejor.2015.03.043

DO - 10.1016/j.ejor.2015.03.043

M3 - Article

VL - 245

SP - 667

EP - 679

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 3

ER -