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

Mike Benchimol; Pascal Benchimol; Benoît Chappert; Arnaud de la Taille; Fabien Laroche; Frédéric Meunier; Ludovic Robinet

RAIRO - Operations Research (2011)

- Volume: 45, Issue: 1, page 37-61
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topBenchimol, Mike, et al. "Balancing the stations of a self service “bike hire” system." RAIRO - Operations Research 45.1 (2011): 37-61. <http://eudml.org/doc/276363>.

@article{Benchimol2011,

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 xv of a commodity and wishes to have an amount equal to
yv (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 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.
},

author = {Benchimol, Mike, Benchimol, Pascal, Chappert, Benoît, de la Taille, Arnaud, Laroche, Fabien, Meunier, Frédéric, Robinet, Ludovic},

journal = {RAIRO - Operations Research},

keywords = {Approximation algorithm; routing problem; self service transport system; approximation algorithm},

language = {eng},

month = {5},

number = {1},

pages = {37-61},

publisher = {EDP Sciences},

title = {Balancing the stations of a self service “bike hire” system},

url = {http://eudml.org/doc/276363},

volume = {45},

year = {2011},

}

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

DA - 2011/5//

PB - EDP Sciences

VL - 45

IS - 1

SP - 37

EP - 61

AB -
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 $\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 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.

LA - eng

KW - Approximation algorithm; routing problem; self service transport system; approximation algorithm

UR - http://eudml.org/doc/276363

ER -

## References

top- S. Anily and J. Bramel, Approximation algorithms for the capacitated traveling salesman problem with pickups and deliveries. Nav. Res. Logist. (1997). Zbl0940.90051
- S. Anily and R. Hassin, The swapping problem. Networks22 (1992) 419–433. Zbl0763.90080
- 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. Zbl0991.90028
- P. Chalasani and R. Motwani, Approximating capacited routing and delivery problem. SIAM J. Comput.28 (1999) 2133–2149. Zbl0943.68076
- M. Charikar, S. Khuller and B. Raghavachari, Algorithms for capacitated vehicle routing. SIAM J. Comput.31 (2001) 665–682. Zbl1009.90095
- 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).
- M.R. Garey and D.S. Johnson, Computers and intractability: a guide to the theory of NP-completness. W.H. Freeman (1979). Zbl0411.68039
- 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. Zbl1024.90057
- 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. Zbl1058.90054
- J.A. Hoogeveen, Analysis of christofides'heuristic: some paths are more difficult than cycles. Oper. Res. Lett.10 (1991) 291–295. Zbl0748.90071
- D. König, Uber Graphen und ihre Anwendung auf Determinantentheorie une Mengenlehre. Math. Ann.77 (1916) 453–465. Zbl46.0146.03
- 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. Zbl1175.90334

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.