Effective method for locating facilities

There has been an increasing interest in the problem of effective facility location over the past five decades. The location of these important facilities 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 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 p-median 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 centers. Many heuristic algorithms have been proposed for this problem due to the difficulty in obtaining solutions by the exact methods. We discussed below a reduction concept applied to p-median problem as follows. Consider a weighted p-median problem with a distance matrix given as D = (d_ij). Note that each row (column) of D is associated with a demand (facility) location. We say that column k dominates column l if d_ik ≤ d_il for all i ≠ k . We use the term strongly dominates in the case of strict inequalities. Observe that locating a facility at a dominated location l would provide no advantage to locating a facility at k except possibly in serving the demands of customers in location l. Further, strongly dominated columns would only be used for ‘self-serve’. Consequently, dominated column can be dropped to generate a feasible solution and the location can later be considered as a possible ‘self-service’ facility. We extend the concept of dominance somewhat further as follows. We say columns k and l dominate column j if d_ij ≤min{d_ik, d_il} for all i ≠ j . In this case there is no advantage in using location j (except for serving customers in location j) when locations k and l are used. So again we can drop the dominated column j if columns k and l are used. The term strongly is used as before. We further extend this concept of dominance as follows. We say that column k partially dominates column l if d_ik ≤ d_il for at least half or more of the entries for which i ≠ k . Similarly, we say columns k and l partially dominate column j if d_ij ≥ min{d_ik, d_il} for at least half or more of the entries for which i ≠ j. Partially dominated columns correspond to nodes which may be assigned ‘self-serve’ facilities in the original and the reduced matrix. In this paper, we developed a new greedy algorithm based on a concept known as dominance to obtain solutions for the p-median problem. This concept reduces the number of columns of a distance matrix by considering potential facilities that are near and those that are far from the population or demand. We illustrate our ideas and the algorithm with an example. We further applied the new algorithm to effectively locate additional ambulance stations in the Central and South East metropolitan areas of Perth to complement the existing ones. We also compare the performance of our new Greedy Reduction Algorithm (GRA) with the existing greedy algorithm of the p-median problem