Near Real-Time Routing of Redistributing Vehicles in Bike-Sharing Rebalancing

Felix Gotzler (), Gori Camps Tomàs (), Damir Safin (), Hajime Sekiya (), Manuel Wackerle García () and Rainer Callies ()
Additional contact information
Felix Gotzler: School of Engineering & Design, Institute of Automotive Technology, Technical University of Munich
Gori Camps Tomàs: School of Computation, Information and Technology, Technical University of Munich
Damir Safin: School of Computation, Information and Technology, Technical University of Munich
Hajime Sekiya: School of Computation, Information and Technology, Technical University of Munich
Manuel Wackerle García: School of Computation, Information and Technology, Technical University of Munich
Rainer Callies: School of Computation, Information and Technology, Technical University of Munich

Chapter Chapter 31 in Operations Research Proceedings 2023, 2025, pp 241-248 from Springer

Abstract: Abstract Lowering overhead costs and environmental impact in bike-sharing requires the efficient realization and optimization of a vehicle-based rebalancing strategy. The goal is to solve the total problem for a large city within one minute. For that, carefully chosen metaheuristics together with efficient numerical implementations have been developed. Initial solutions, stochastically produced by a Greedy method, are improved by an advanced Variable Neighborhood Search (VNS) algorithm together with a Large Neighborhood Search (LNS) metaheuristic. VNS is the efficient local search strategy, LNS better explores global solution space but is slower. For VNS, different neighborhood operators and operator change strategies are experimentally analyzed for real and large data sets of cities like Munich. Loading instructions obtained from exact maximum flow computations are derived for every set of intermediate candidate routes and are used as feasibility checks. Our two approaches (VNS+LNS and Parallel Variable Neighborhood Search (pVNS)) are benchmarked against (exact) Branch-and-Cut (B&C) methods and provide near-optimal solutions while vastly outperforming the exact method in terms of computational time, especially for large cities. Extensions to hybrid systems and a new windowing strategy modeling behavior of human experts are presented. They significantly improve real-world applicability and ease the work of bike-sharing systems (BS) operators.

Keywords: Bike-sharing; Routing; Combinatorial optimization (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:lnopch:978-3-031-58405-3_31

Ordering information: This item can be ordered from
http://www.springer.com/9783031584053

DOI: 10.1007/978-3-031-58405-3_31

Access Statistics for this chapter

More chapters in Lecture Notes in Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().