The Uncapacitated Facility Location Problem With Primary and Secondary Facility Requirements

Abstract

We consider the problem of locating uncapacitated facilities among a set of potential sites to minimize cost of serving a number of demand points each requiring service from two different facilities. This problem has many potential applications. One such application is location of emergency service facilities where it is desirable to have a primary and back-up service facility wthin a certain distance from every district An efficient solution procedure is developed. This procedure is tested on a number of problems and computational results are reported. It is compared to a state of the art commercial linear/integer programming package and found to be around two orders of magnitude faster than this package. It is also compared to a state of the art special purpose agorithm for the simple uncapacitated facility location problem to investigate the computational implications of introducing secondary service requirements. The model is used to illustrate the effect of considering secondary service on the spatial characteristics of the optimal set of locations. The model is further demonstrated on a “real life” example with 625 demand points and 30 potential facility locations.