## Locating Depots for Capacitated Vehicle Routing

Publication: Research - peer-review › Article in proceedings – Annual report year: 2011

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].

Original language | English |
---|---|

Title of host publication | Approximation, Randomization, and Combinatorial Optimization : 14th InternationalWorkshop, APPROX 2011 and 15th InternationalWorkshop, RANDOM 2011 Princeton, NJ, USA, August 17-19, 2011 Proceedings |

Volume | 6845 |

Publisher | Springer |

Publication date | 2011 |

Pages | 230-241 |

ISBN (print) | 978-3-642-22934-3 |

ISBN (electronic) | 978-3-642-22935-0 |

DOIs | |

State | Published - 2011 |

Event | International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, and the International Workshop on Randomization and Computation - Princeton, New Jersey, USA |

### Conference

Conference | International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, and the International Workshop on Randomization and Computation |
---|---|

Number | 14 & 15 |

City | Princeton, New Jersey, USA |

Period | 01/01/2011 → … |

Name | Lecture Notes in Computer Science |
---|---|

ISSN (Print) | 0302-9743 |

Citations | Web of Science® Times Cited: No match on DOI |
---|

Download as:

Loading map data...

ID: 6243784