The Crisp P-median Problem

The crisp p-median problem consists in locating p facilities on a network to cover certain given demands in such a way that total transport costs are minimized. It is assumed that these costs are directly proportional to the distances to be covered and to the quantities of product to be transported. And it is shown that in an optimal solution of the p-medianproblem, all the facilities are located at p vertices of the network and that the demand of each vertex will be covered by its nearest facility.

This model was introduced in the mid-60's by Hakimi, who proposed a well-known explicit enumeration algorithm. Later, ReVelle and Swain formulated the model as the following mixed integer 0-1 problem.

where

x_ij is the demand of vertex v_j  covered by the facility at vertex v_i (if any)

y_i  is 1 if there is a facility at vertex v_i  and 0 otherwise

w_i  is the demand at vertex v_i 

d_ij  is the distance from v_i to v_j.

Constraints (1) ensure that all the demand is covered at each vertex v_j, constraints (2) guarantee that only vertices with a facility will serve the product, and   constraint (3) establishes that exactly p facilities will be located.

There are several programs that can be shown to be equivalent to (CP). On the other hand, this basic model of location on networks has given rise to many other models adapted to more complex situations: the capacited p-median problem, the hub p-median problem, ... It is also closely related with other basic location models on a network and on a plane, such as the p-center problem, covering problems, the simple plant location problem, etc.

The p-median problem includes as a hypothesis that all the demand must be covered. However, it is important to remember that the objective of the public sector is usually the maximizing of social benefits, while the objective of the private sector is generally the maximizing of profits. For that reason, a private firm can prefer to leave a part of the demand uncovered if it provides significantly lower costs. This is the reason why most applications of the pmedian problem are related with the public sector: the location of hospitals, schools, etc.