Book chapter · Conference paper
Locating Depots for Capacitated Vehicle Routing
We study a location-routing problem in the context of capacitated vehicle routing. The input to k-LocVRP is a set of demand locations in a metric space and a fleet of k vehicles each of capacity Q. The objective is to locate k depots, one for each vehicle, and compute routes for the vehicles so that all demands are satisfied and the total cost is minimized.
Our main result is a constant-factor approximation algorithm for k-LocVRP. To achieve this result, we reduce k-LocVRP to the following generalization of k median, which might be of independent interest. Given a metric (V, d), bound k and parameter ρ ∈ R+, the goal in the k median forest problem is to find S ⊆ V with |S| = k minimizing: E u∈V d(u, S) + ρ · d(MST(V/S) ), where d(u, S) = minw∈S d(u,w) and MST(V/S) is a minimum spanning tree in the graph obtained by contracting S to a single vertex.
We give a (3+E)-approximation algorithm for k median forest, which leads to a (12+E)-approximation algorithm for k-LocVRP, for any constant E > 0. The algorithm for k median forest is t-swap local search, and we prove that it has locality gap 3 + 2 t ; this generalizes the corresponding result for k median [3].
Finally we consider the k median forest problem when there is a different (unrelated) cost function c for the MST part, i.e. the objective is Eu∈V d(u, S) + c(MST(V/S) ). We show that the locality gap for this problem is unbounded even under multi-swaps, which contrasts with the c = d case. Nevertheless, we obtain a constant-factor approximation algorithm, using an LP based approach along the lines of [12].
Language: | English |
---|---|
Publisher: | Springer |
Year: | 2011 |
Pages: | 230-241 |
Proceedings: | International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, and the International Workshop on Randomization and Computation |
Series: | Lecture Notes in Computer Science |
Journal subtitle: | 14th Internationalworkshop, Approx 2011 and 15th Internationalworkshop, Random 2011 Princeton, Nj, Usa, August 17-19, 2011 Proceedings |
ISBN: | 3642229344 , 3642229352 , 9783642229343 and 9783642229350 |
ISSN: | 16113349 and 03029743 |
Types: | Book chapter and Conference paper |
DOI: | 10.1007/978-3-642-22935-0_20 |
ORCIDs: | Gørtz, Inge Li |