The p-median problem is useful to model many real world situations such as the location of public or industrial facilities, warehouses [1, 2] and others [3]. The p-median problem differs from the UFLP in two respects — there are no costs for opening facilities and there is an upper bound on the number of facilities that should be opened. It models the problem of finding a minimum cost clustering and belongs to the class of  NP hard problems in strong sense [4].

Let us consider a set I={1,..., n} of potential locations for p facilities, a set J={1,..., m}of customers, and  n m matrix (g_ij) of transportations costs for satisfying the demands of the customers from the facilities.  The p-median problem is to locate the p facilities at locations of I in order to minimize the total transportation cost for satisfying the demand of the customers. Each customer is supplied from the closest open facility. The following is integer program for the problem: 

REFERENCES

1. Cristofides, N. Graph Theory. An Algorithm Approach. New York: Academic Press. 1975.

2. Hansen, P. and Jaumard, B. Cluster Analysis and Mathematical Programming. Mathematical Programming 79 (1997), p. 191-215.

3. Krarup, J. and Pruzan, P. The simple plant location problem: survey and synthesis. European J. Oper. Res. 12 (1983), N 1, p.36-81.

4. Mirchandani, P. and Francis, R. (eds.) Discrete Location Theory. Wiley-Intersience. 1990.

Home