Setting second-level facilities in the multi-product maximal coveringlocation problem

Abstract

In hierarchical facility location problems, the goal is to locate a set of interacting facilities at different levels of a hierarchical framework. In thiscontext, we introduce a model which considers a first-level system of already established services (factories, product sources, etc.), a second-levelsystem of facilities (warehouses, shops, etc.) to determine their location and their supply of products, and a third-level system of clients demanding different products produced in the first-level and provided by the secondlevel facilities. Each client demands different products and has distinct preferences for the same product depending on the first-level facility producing that product. In this model, called multi-product maximal covering second-level facility location problem, there is a maximum number of different products that can be offered at each second-level facility and also a budget constraint for the total cost of the facility locations. The aim is to locate a set of second-level facilities and to decide the size of them (number of offered products), in such a way that the covered clients’ demand is maximized. Therefore, in order to satisfy a customer’sdemand there must be a double coverage, the customer must be covered by a second-level facility, and this, in turn, by a first-level facility. We propose a mixed integer linear program (MILP) for this problem which is reinforced by the use of valid inequalities. For cases where the number of valid inequalities is exponential, different separation procedures are developed. In addition, three variants of a heuristic algorithm are proposed. An extensive computational analysis is carried out. This illustrates the usefulness of the valid inequalities and the corresponding separationmethods, as well as, shows the good performance of the proposed heuristic algorithms.