Balancing the stations of a self service “bike hire” system

¹ Université Paris Est, ENPC, 6-8 avenue Blaise Pascal, Cité Descartes Champs-sur-Marne, 77455 Marne-la-Vallée Cedex 2, France. mike.benchimol@eleves.enpc.fr; benoit.chappert@eleves.enpc.fr; de-la-ta@eleves.enpc.fr; frederic.meunier@enpc.fr; ludovic.robinet@eleves.enpc.fr
² École Polytechnique, 91128 Palaiseau Cedex, France. pascal.benchimol@polytechnique.edu; fabien.laroche@polytechnique.edu

Received: 23 December 2009
Accepted: 4 March 2011

Abstract

This paper is motivated by operating self service transport systems that flourish nowadays. In cities where such systems have been set up with bikes, trucks travel to maintain a suitable number of bikes per station. It is natural to study a version of the C-delivery TSP defined by Chalasani and Motwani in which, unlike their definition, C is part of the input: each vertex v of a graph G=(V,E) has a certain amount x_v of a commodity and wishes to have an amount equal to y_v (we assume that and all quantities are assumed to be integers); given a vehicle of capacity C, find a minimal route that balances all vertices, that is, that allows to have an amount y_v of the commodity on each vertex v. This paper presents among other things complexity results, lower bounds, approximation algorithms, and a polynomial algorithm when G is a tree.