Volume 45, Number 1, January-March 2011
|Page(s)||37 - 61|
|Published online||10 May 2011|
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. firstname.lastname@example.org; email@example.com; firstname.lastname@example.org; email@example.com; firstname.lastname@example.org
2 École Polytechnique, 91128 Palaiseau Cedex, France. email@example.com; firstname.lastname@example.org
Accepted: 4 March 2011
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 xv of a commodity and wishes to have an amount equal to yv (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 yv 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.
Mathematics Subject Classification: 90B06 / 90C27
Key words: Approximation algorithm / routing problem / self service transport system
© EDP Sciences, ROADEF, SMAI, 2011
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.