PILOT, GRASP, and VNS approaches for the static balancing of bicycle sharing systems

Marian Rainer-Harbach (), Petrina Papazek (), Günther Raidl (), Bin Hu () and Christian Kloimüllner ()

Journal of Global Optimization, 2015, vol. 63, issue 3, 597-629

Abstract: We consider a transportation problem arising in public bicycle sharing systems: To avoid rental stations to run entirely empty or full, a fleet of vehicles continuously performs tours moving bikes among stations. In the static problem variant considered in this paper, we are given initial and target fill levels for all stations, and the goal is primarily to find vehicle tours including corresponding loading instructions in order to minimize the deviations from the target fill levels. As secondary objectives we are further interested in minimizing the tours’ total duration and the overall number of loading actions. For this purpose we first propose a fast greedy construction heuristic and extend it to a PILOT method that evaluates each candidate station considered for addition to the current partial tour in a refined way by looking forward via a recursive call. Next we describe a Variable Neighborhood Descent (VND) that exploits a set of specifically designed neighborhood structures in a deterministic way to locally improve the solutions. While the VND is processing the search space of candidate routes to determine the stops for vehicles at unbalanced rental stations, the number of bikes to be loaded or unloaded at each stop is derived by an efficient method. Four alternatives are considered for this embedded procedure based on a greedy heuristic, two variants of maximum flow calculations, and linear programming. Last but not least, we investigate a general Variable Neighborhood Search (VNS) and variants of a Greedy Randomized Adaptive Search Procedure (GRASP) for further diversification and extended runs. Rigorous experiments using benchmark instances derived from a real-world scenario in Vienna with up to 700 stations document the performance of the suggested approaches and individual pros and cons. While the VNS yields the best results on instances of moderate size, a PILOT/GRASP hybrid turns out to be superior on very large instances. If solutions are required in short time, the construction heuristic or PILOT method optionally followed by VND still yield reasonable results. Copyright Springer Science+Business Media New York 2015

Keywords: Bicycle sharing systems; Vehicle routing; PILOT method; Variable Neighborhood Search; GRASP (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10898-014-0147-5 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:63:y:2015:i:3:p:597-629

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-014-0147-5

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().