×

Balancing the stations of a self service “bike hire” system. (English) Zbl 1222.90073

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.

MSC:

90C35 Programming involving graphs or networks
90B06 Transportation, logistics and supply chain management
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] S. Anily and J. Bramel, Approximation algorithms for the capacitated traveling salesman problem with pickups and deliveries. Nav. Res. Logist. (1997). · Zbl 0940.90051
[2] S. Anily and R. Hassin, The swapping problem. Networks22 (1992) 419-433. · Zbl 0763.90080
[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 0991.90028
[4] P. Chalasani and R. Motwani, Approximating capacited routing and delivery problem. SIAM J. Comput.28 (1999) 2133-2149. · Zbl 0943.68076
[5] M. Charikar, S. Khuller and B. Raghavachari, Algorithms for capacitated vehicle routing. SIAM J. Comput.31 (2001) 665-682. · Zbl 1009.90095
[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). · Zbl 0411.68039
[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. Zbl1024.90057 · Zbl 1024.90057
[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. Zbl1058.90054 · Zbl 1058.90054
[10] J.A. Hoogeveen, Analysis of christofides’heuristic: some paths are more difficult than cycles. Oper. Res. Lett.10 (1991) 291-295. Zbl0748.90071 · Zbl 0748.90071
[11] D. König, Uber Graphen und ihre Anwendung auf Determinantentheorie une Mengenlehre. Math. Ann.77 (1916) 453-465. · JFM 46.0146.03
[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. Zbl1175.90334 · Zbl 1175.90334
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.