The Median Problem for Networks

The median problem is a model for finding the optimal location for a distribution center given the location of the warehouses that have to be served. In its simplest form the model reads as:

Let N = (V, A) be a network, and let W Í V be the location of the warehouses in the network. Then a vertex x that minimizes the sum of the distances to all vertices in W is a median vertex of W. The median set M(W) of W consists of all median vertices of W. It is the set of optimal locations for a distribution center with respect to W.

In the case that N is a tree, the set M(W) has a simple structure (either a unique point or a path) and it is easily found by various simple algorithms.

From the mathematical point of view it is interesting to see what happens when restrictions are imposed on the structure of the network N or on the structure or size of the median sets M(W).

In this talk this line of research is pursued. It turns out that structures arise that have found applications in diverse areas as: location theory, chemistry, biology, literary history, mathematics, informatics.

The purpose of this talk is to present ideas, results and techniques in these areas to people working in operations research to elicit comments and to bring about an exchange of ideas that could incite problems and questions for future research.

Information: Robin Nicolai, rnicolai@few.eur.nl , Wilco van den Heuvel, wvandenheuvel@few.eur.nl