A general model for the uncapacitated facility and depot location problem

This paper considers the problem of locating pairs of facilities and depots in order to maximize the sum of the profits for serving each client by exactly one facility and one depot, taking into account the fixed costs of opening those new entities and also the fixed costs of having facilities and depots operating together. It proposes three formulations for the problem and studies different Lagrangean relaxations in order to derive upper bounds for these formulations. It also presents a branch and bound scheme to solve the problem which uses bounds given by a greedy heuristic and a Lagrangean relaxation. Finally, the model is compared with three models previously presented in the literature, and computational results are reported.