Abstract

We study of a class of discrete facility location problems, called multi-level facility location problems, that has received major attention in the last decade. These problems arise in several applications such as in production-distribution systems, telecommunication networks, freight transportation, and health care, among others. Moreover, they generalize well-known facility location problems which have been shown to lie at the heart of operations research due to their applicability and mathematical structure. We first present a comprehensive review of multi-level facility location problems where we formally define and categorize them based on the types of decisions involved. We also point out some gaps in the literature and present overviews of related applications, models and algorithms. We then concentrate our efforts on the development of solution methods for a general multi-level uncapacitated facility location problem. In particular, based on an alternative combinatorial representation of the problem whose objective function satisfies the submodularity property, we propose a mixed integer linear programming formulation. Using that same representation, we present approximation algorithms with constant performance guarantees for the problem and analyze some special cases where these worst-case bounds are sharper. Finally, we develop an exact algorithm based on Benders decomposition for a slightly more general problem where the activation of links between level of facilities is also considered part of the decision process. Extensive computational experiments are presented to assess the performance of the various models and algorithms studied. We show that the multi-level extension of some fundamental problems in operations research maintain certain structure that allows us to develop more efficient algorithms in practice.