The Bike sharing Rebalancing Problem with Stochastic Demands

Mauro Dell’Amico(a), Manuel Iori(a), Stefano Novellani(a) and Anand Subramanian(b)

(a) DISMI, University of Modena and Reggio Emilia, Via Amendola 2, 42122 Reggio Emilia, Italy.
(b) Departamento de Sistemas de Computação, Centro de Informática, Universidade Federal da Paraíba, Rua dos Escoteiros, Mangabeira, João Pessoa -- PB, 58058-600, Brazil.

Abstract

In this paper we deal with the stochastic version of a problem arising in the context of self-service bike sharing systems, which aims at determining minimum cost routes for a fleet of homogeneous vehicles in order to redistribute bikes among stations. The Bike sharing Rebalancing Problem with Stochastic Demands is a variant of the one-commodity many-to-many pickup and delivery vehicle routing problem where demands at each station are represented by random variables, with associated probability distributions, that depend on stochastic scenarios. We develop stochastic programming models that are solved using different approaches, in particular, the L-Shaped and branch-and-cut. Moreover, we also propose heuristic algorithms based on an innovative use of positive and negative correlations between stations' stochastic demands, as well as an efficient strategy for checking feasibility. The proposed solution approaches are evaluated and compared by means of extensive computational experiments on newly real-world based benchmark instances.

Key words

Stochastic Programming, Vehicle Routing, Bike Sharing, Branch-and-cut, Correlations.

The instances could be found here.