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.
