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 ${\sum}_{v\in V}{x}_{v}={\sum}_{v\in 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 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.

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://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, Volume 45 (2011) no. 1, pp. 37-61. doi : 10.1051/ro/2011102. http://archive.numdam.org/articles/10.1051/ro/2011102/

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

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

and ,[3] Seprating capacity constraints in the CRVP using tabu search. Eur. J. Oper. Res. 106 (1998) 546-557. | Zbl

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

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

, and ,[6] 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] Computers and intractability: a guide to the theory of NP-completness. W.H. Freeman (1979). | MR | Zbl

and ,[8] The one-commodity pickup-and-delivery travelling salesman problem, in Lect. Notes Comput. Sci. 2570 (2002) 89-104. | Zbl

and ,[9] A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery. Discr. Appl. Math. 145 (2004) 126-139. | MR | Zbl

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

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

,[12] 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

, and ,*Cited by Sources: *