The static bike sharing rebalancing problem with forbidden temporary operations
Bruno P. Bruck (a), Fįbio Cruz (a), Manuel Iori (b), Anand Subramanian (a)
(a) Centro de Informįtica, Universidade Federal da Paraķba, Rua dos Escoteiros, Mangabeira, Joćo Pessoa -- PB, 58058-600, Brazil.
(b) DISMI, University of Modena and Reggio Emilia, Via Amendola 2, 42122 Reggio Emilia, Italy.
Abstract
This paper introduces and solves the static bike rebalancing problem with forbidden temporary operations. In this problem, one aims at finding a minimum cost route in which a vehicle performs a series of pickup and delivery operations, while satisfying demand and capacity constraints. In addition, a vehicle can visit stations multiple times but cannot use them to temporary store or provide bikes. Apart from bike rebalancing, the problem also models courier service transportation and repositioning of inventory between retail stores, where temporary operations are frequently disliked because they require additional manual work and service time. We present some theoretical results concerning problem complexity and worst case analysis, and then propose three exact algorithms based on different mathematical formulations. Extensive computational results on instances involving up to 80 stations show that an exact algorithm based on a minimal extended network produces the best average results.
Key words
Bike sharing; branch-and-cut; minimal extended network
To dowload the instances click here.