Effective heuristics for the facilities location problem

Over the past four decades, there has been an increasing interest in the problem of effective facility location which arises in the service and manufacturing industries. The fundamental questions that arise concern the number and location of facilities such as: schools; hospitals; ambulances; warehouses; factories; department stores; police stations; waste material dumps; fire stations; needed to achieve a prescribed level of service and or output. The main concern of many location problems is to place facilities to optimize some spatially dependent objectives such as: minimize average travel time or distance between demand points and servers; minimize a cost function of travel or response time. These optimization problems are complicated with the need to meet a number of specified constraints that relate to safety, demand, available resources, level of service and time. Indeed, the optimization problems that arise in practice are computationally difficult (NP hard) to solve by exact methods. An important problem is the pmedian problem which is to find the location of p-facilities so as to minimize the average weighted distance or time between demand points and service centres. Many heuristic algorithms have been proposed for this problem. In this paper we present a simple and effective heuristic that utilizes a reduction and an exchange procedure. Our methodology is tested on 400 randomly generated problems with 10 to 50 customer locations as well as 6 well known literature test problems. For the random problems the generated solutions were on average within 0.87% of the optimum. A similar result was achieved for the literature test problems. A comparative analysis with literature heuristics supports the superiority of our method. We also apply our heuristic to a case study involving the location of emergency vehicles (ambulances).