Geodesic
Balancing the stations of a self service “bike hire” system
RAIRO - Operations Research - Recherche Opérationnelle, Tome 45 (2011) no. 1, pp. 37-61

Voir la notice de l'article provenant de la source Numdam

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 ∑ v∈V x v =∑ v∈V y v 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.

DOI : 10.1051/ro/2011102
Classification : 90B06, 90C27
Keywords: approximation algorithm, routing problem, self service transport system 
@article{RO_2011__45_1_37_0,
     author = {Benchimol, Mike and Benchimol, Pascal and Chappert, Beno{\^\i}t and de la Taille, Arnaud and Laroche, Fabien and Meunier, Fr\'ed\'eric and Robinet, Ludovic},
     title = {Balancing the stations of a self service {\textquotedblleft}bike hire{\textquotedblright} system},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {37--61},
     publisher = {EDP-Sciences},
     volume = {45},
     number = {1},
     year = {2011},
     doi = {10.1051/ro/2011102},
     zbl = {1222.90073},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2011102/}
}
TY  - JOUR
AU  - Benchimol, Mike
AU  - Benchimol, Pascal
AU  - Chappert, Benoît
AU  - de la Taille, Arnaud
AU  - Laroche, Fabien
AU  - Meunier, Frédéric
AU  - Robinet, Ludovic
TI  - Balancing the stations of a self service “bike hire” system
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2011
SP  - 37
EP  - 61
VL  - 45
IS  - 1
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro/2011102/
DO  - 10.1051/ro/2011102
LA  - en
ID  - RO_2011__45_1_37_0
ER  - 
%0 Journal Article
%A Benchimol, Mike
%A Benchimol, Pascal
%A Chappert, Benoît
%A de la Taille, Arnaud
%A Laroche, Fabien
%A Meunier, Frédéric
%A Robinet, Ludovic
%T Balancing the stations of a self service “bike hire” system
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2011
%P 37-61
%V 45
%N 1
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro/2011102/
%R 10.1051/ro/2011102
%G en
%F RO_2011__45_1_37_0
Benchimol, Mike; Benchimol, Pascal; Chappert, Benoît; de la Taille, Arnaud; Laroche, Fabien; Meunier, Frédéric; Robinet, Ludovic. Balancing the stations of a self service “bike hire” system. RAIRO - Operations Research - Recherche Opérationnelle, Tome 45 (2011) no. 1, pp. 37-61. doi: 10.1051/ro/2011102

Cité par Sources :