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 loans . Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Buy Cialis is the one that definitely differs from all other products.