Bike sharing systems: Solving the static rebalancing problem

By D. Chemla, Frédéric Meunier, R. W. Calvo. Discrete Optimization, 2013

487 citations recorded by the source corpus.

Abstract This paper deals with a new problem that is a generalization of the many to many pickup and delivery problem and which is motivated by operating self-service bike sharing systems. There is only one commodity, initially distributed among the vertices of a graph, and a capacitated single vehicle aims to redistribute the commodity in order to reach a target distribution. Each vertex can be visited several times and also can be used as a buffer in which the commodity is stored for a later visit. This problem is NP-hard, since it contains several NP-hard problems as special cases (the TSP being maybe the most obvious one). Even finding a tractable exact formulation remains problematic. This paper presents efficient algorithms for solving instances of reasonable size, and contains several theoretical results related to these algorithms. A branch-and-cut algorithm is proposed for solving a relaxation of the problem. An upper bound of the optimal solution of the problem is obtained by a tabu search, which is based on some theoretical properties of the solution, once fixed the sequence of the visited vertices. The possibility of using the information provided by the relaxation receives a special attention, both from a theoretical and a practical point of view. It is proven that to build a feasible solution of the problem by using the one obtained by the relaxation is an NP-hard problem. Nevertheless, a tabu search initialized with the optimal solution of the relaxation often shows that it is the optimal one. The algorithms have been tested on a set of instances coming from the literature, proving their effectiveness.

Subfields: Automotive Engineering, Building and Construction, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/6575c4ed89490f43b4210eaacd2bfd1c2c6a38b5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Automotive Engineering

1. Konstantinos G. Zografos
2. Nikolaos Geroliminis
3. Burak Boyaci
4. E. Fishman

In Building and Construction

1. Konstantinos G. Zografos
2. Nikolaos Geroliminis
3. Burak Boyaci
4. Jack Haddad
5. W. Jin

In Industrial and Manufacturing Engineering

1. Konstantinos G. Zografos
2. Nikolaos Geroliminis
3. Burak Boyaci

Citations in the corpus

• An optimization framework for the development of efficient one-way car-sharing systems (2015, methodology): “The static balancing problem has been modeled as a single vehicle one-commodity capacitated pickup and delivery problem (SVOCPDP) and was solved with an exact algorithm based on column-generation [20].”
• Incentives and redistribution in homogeneous bike-sharing systems with stations of finite capacity (2012, background): “[2] develop an algorithm that minimizes the distance traveled by trucks to achieve a given bike positions, assuming that bikes do not move (e.”