Friday, 15:45 - 16:10 h, Room: H 3010


Jannik Matuschke
Approximation algorithms for capacitated location routing

Coauthors: Tobias Harks, Felix G. K├Ânig


Location routing integrates the two classical optimization problems of facility location and vehicle routing, addressing both location decisions and tour planning in a single step. Given a graph whose vertex set consists of facilities and clients with given demands, the problem is to find a subset of facilities that have to be opened, and a set of tours originating from those facilities, serving all clients while at the same time respecting the (uniform) capacity limitation of the vehicles in use, and minimizing the incurred opening and connection costs.
We derive the first polynomial time constant factor approximation for capacitated location routing and some variants of the problem, including cross-docking, prize-collecting, and a group variant. Our results originate from combining algorithms and lower bounds for different relaxations of the original problem.
Finally, we present a computational study on popular benchmark instances from the literature and newly generated large-scale random instances. It turns out that, in practice, solutions of our algorithm are much closer to optimality than guaranteed by the theoretical approximation factor.


Talk 2 of the invited session Fri.3.H 3010
"Routing and shortest paths" [...]
Cluster 1
"Approximation & online algorithms" [...]


  Online lending company provides a wide range of ways to get money by means of Tennessee Payday Loans. Therefore, we can say that the active substances in its composition are more perfectly mixed. Vardenafil is not only present in the original Buy Levitra, but also as part of its analogs.