TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)2010

COGA 5-Wheel

Page Content

to Navigation

Preprints 2010

Approximation Algorithms for Capacitated Location Routing
Citation key Report-010-2010
Author Harks, Tobias and König, Felix G. and Matuschke, Jannik
Year 2010
Number 010
Month april
Institution Technische Universität Berlin, Institut für Mathematik
Abstract An approximation algorithm for an optimization problem runs in polynomial time for all instances and is guaranteed to deliver solutions with bounded optimality gap. We derive such algorithms for different variants of capacitated location routing, an important generalization of vehicle routing where the cost of opening the depots from which vehicles operate is taken into account. Our results originate from combining algorithms and lower bounds for different relaxations of the original problem, and besides location routing we also obtain approximation algorithms for multi-depot capacitated vehicle routing by this framework. Moreover, we extend our results to further generalizations of both problems, including a prize-collecting variant, a group version, and a variant where cross-docking is allowed. We finally present a computational study of our approximation algorithm for capacitated location routing on benchmark instances and large-scale randomly generated instances. Our study reveals that the quality of the computed solutions is much closer to optimality than the provable approximation factor.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe