\input zb-basic
\input zb-ioport
\iteman{io-port 05920474}
\itemau{Benchimol, Mike; Benchimol, Pascal; Chappert, Beno{\^\i}t; de la Taille, Arnaud; Laroche, Fabien; Meunier, Fr\'ed\'eric; Robinet, Ludovic}
\itemti{Balancing the stations of a self service ``bike hire'' system.}
\itemso{RAIRO, Oper. Res. 45, No. 1, 37-61 (2011).}
\itemab
Summary: 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.
\itemrv{~}
\itemcc{}
\itemut{approximation algorithm; routing problem; self service transport system}
\itemli{doi:10.1051/ro/2011102}
\end