The planar collection depots location problem

In this thesis we examine the collection depots location problem, which is an extension of the classical facility center location problem. Besides n customers, a set of p collection depots are given, and the service of a customer consists of the travel of a server to the customer and return back to the center via a collection depot. We show that the problem can be transformed to 0(p2n2) number of different classical facility location problems by using Voronoi diagrams. This is the first such non-trivial bound for this problem. We present fast 2-approximation algorithms for both the 1-median and 1-center versions of the the problem. We also show how some of the techniques developed in this thesis can be applied to facility location problems involving line barriers.