Balancing Bicycle Sharing Systems: An Analysis of Path Relinking and Recombination within a GRASP Hybrid^*

Petrina Papazek, Christian Kloimüllner, Bin Hu, and Günther R. Raidl

Abstract. In bike sharing systems, a vehicle fleet rebalances the system by continuously moving bikes among stations in order to avoid rental stations to run entirely empty or full. We address the static problem variant assuming initial fill levels for each station and seek vehicle tours with corresponding loading instructions to reach given target fill levels as far as possible. Our primary objective is to minimize the absolute deviation between target and final fill levels for all rental stations. Building upon a previously suggested GRASP hybrid, we investigate different approaches for hybridizing them with Path Relinking (PR) and simpler recombination operators. Computational tests on benchmark instances derived from a real world scenario in Vienna give insight on the impacts of the PR and recombination techniques and manifest that certain PR extension improve the results significantly. Ultimately, a hybrid exclusively searching a partial PR path in the neighborhood of the guiding solutions turns out to be most fruitful.

^*This work is supported by the Austrian Research Promotion Agency (FFG), contract 831740. The authors thank Citybike Wien, the Austrian Institute of Technology (AIT), and Energie und Umweltagentur Niederösterreich (eNu) for the collaboration in this project.

LNCS 8672, p. 792 ff.

Full article in PDF | BibTeX

lncs@springer.com
© Springer International Publishing Switzerland 2014