A General Construct for the Zonally Constrained p-Median Problem

The well-known p -median location model is designed to site p facilities with respect to population centers such that the average travel distance of facility users is minimized. Many locational applications would benefit from a median problem that distributes, according to the discretion of the model user, some or all of the p facilities among defined zones. The notion of this ‘zonally constrained’ p -median can be defined as: locate p facilities to achieve the minimum average user distance while ensuring that (in those zones with such requirements) each zone receives at least its allotted minimum number of facilities and no more than its allotted maximum number of facilities. Authors of three recent articles have defined subsets of this problem but have not developed a completely general form. Previous work falls short in one or more of the following respects: (1) defining a minimum facility limit for zones other than one, (2) including any kind of maximum facility limit for zones, (3) allowing demand to be assigned across zonal boundaries, and (4) allowing zones to overlap such that an eligible site for a facility can be a member of more than one zone. In this paper we present an integer-linear programming formulation that generalizes the concept of the zonally constrained p-median problem by incorporating properties (1)-(4) above. We denote this formulation ZOMP (zonal constraints with overlap for the median problem). A solution approach based on Lagrangian relaxation is proposed along with computational results. In addition, comparative computational results using mixed integer programming are offered. Our results are mostly derived from a computationally challenging application, unique to ZOMP, in which we generate a complete rank-ordered list of close to optimal solutions to the p -median problem.