Branch and bound algorithm for a facility location problem with concave site dependent costs

The purpose of facility location models is to select a set of facilities (warehouses, plants, public facilities, antennas, etc.) to be implanted over a given area in order to satisfy the needs of all or part of the customers within this area. In this paper, the objective is to minimize the sum of the costs of investment, production and distribution while satisfying all customers' demands. We introduce a new type of facility location model, in which the global cost incurred for each established facility is a concave function of the quantity q delivered by this facility. We introduce some properties of an optimal solution and derive heuristic algorithms and a branch and bound method from these properties. Numerical examples illustrate this approach.