A large-scale application of the partial coverage uncapacitated facility location problem

The traditional, uncapacitated facility location problem (UFLP) seeks to determine a set of warehouses to open such that all retail stores are serviced by a warehouse and the sum of the fixed costs of opening and operating the warehouses and the variable costs of supplying the retail stores from the opened warehouses is minimized. In this paper, we discuss the partial coverage uncapacitated facility location problem (PCUFLP) as a generalization of the uncapacitated facility location problem in which not all the retail stores must be satisfied by a warehouse. Erlenkotter's dual-ascent algorithm, DUALOC, will be used to solve optimally large (1600 stores and 13 000 candidate warehouses) real-world implemented PCUFLP applications in less than two minutes on a 500 MHz PC. Furthermore, a simple analysis of the problem input data will indicate why and when efficient solutions to large PCUFLPs can be expected.