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

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
Mots-clés : 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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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. http://archive.numdam.org/articles/10.1051/ro/2011102/

[1] S. Anily and J. Bramel, Approximation algorithms for the capacitated traveling salesman problem with pickups and deliveries. Nav. Res. Logist. (1997). | MR | Zbl

[2] S. Anily and R. Hassin, The swapping problem. Networks 22 (1992) 419-433. | MR | Zbl

[3] P. Augerat, J.M. Belenguer, E. Benavent, A. Corberán and D. Naddef, Seprating capacity constraints in the CRVP using tabu search. Eur. J. Oper. Res. 106 (1998) 546-557. | Zbl

[4] P. Chalasani and R. Motwani, Approximating capacited routing and delivery problem. SIAM J. Comput. 28 (1999) 2133-2149. | MR | Zbl

[5] M. Charikar, S. Khuller and B. Raghavachari, Algorithms for capacitated vehicle routing. SIAM J. Comput. 31 (2001) 665-682. | MR | Zbl

[6] N. Christofides, Worst-case analysis for a new heuristic for the Traveling Salesman problem, in Symposium on New Directions and Recent Results in Algorithms and Complexity, edited by J.F. Traub, Academic Press (1976).

[7] M.R. Garey and D.S. Johnson, Computers and intractability: a guide to the theory of NP-completness. W.H. Freeman (1979). | MR | Zbl

[8] H. Hernández-Pérz and J.-J. Salazar-González, The one-commodity pickup-and-delivery travelling salesman problem, in Lect. Notes Comput. Sci. 2570 (2002) 89-104. | Zbl

[9] H. Hernández-Pérz and J.-J. Salazar-González, A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery. Discr. Appl. Math. 145 (2004) 126-139. | MR | Zbl

[10] J.A. Hoogeveen, Analysis of christofides'heuristic: some paths are more difficult than cycles. Oper. Res. Lett. 10 (1991) 291-295. | MR | Zbl

[11] D. König, Uber Graphen und ihre Anwendung auf Determinantentheorie une Mengenlehre. Math. Ann. 77 (1916) 453-465. | JFM | MR

[12] A. Lim, F. Wang and Z. Xu, The capacitated traveling salesman problem with pickups and deliveries on a tree, in Lect. Notes Comput. Sci. Algorithms and Computation. Springer Berlin/Heidelberg 3827 (2005) 1061-1070. | MR | Zbl

Cité par Sources :