Group for Research in Decision Analysis


When closest is not always the best: The distributed p-median problem


The classical p-median problem assumes that service to customers is always provided by the closest facility, while in practice, customers often interact for a variety of reasons with several of the facilities (not just the closest). In this paper we introduce the concept of a distribution rule for modeling such flows, and use it to formulate a new class of median problems which we call the "distributed" p-median problem. Different types of distribution rule are investigated leading to some interesting properties. For example, if the weights are increasing (i.e., assigned flows are greater to facilities that are further away) the problem can be solved in polynomial time as a 1-median problem. For decreasing weights, of which the classical p-median is a special case, we obtain generalizations of the standard continuous and discrete models, which in turn lead to a broader interpretation of median points. Some small numerical examples are given to illustrate the concepts.

, 20 pages