## 6.5.2 Median ProblemsLet us consider an undirected network G(N, A) with n nodes. Let k be some
positive integer (k = 1, 2, 3, . . .) and let us choose k distinct points
on the graph G to be indicated as the set X Now, if the k points in X We can now state a most important result, known as
The practical significance of this theorem is great. It states in effect that the search for the set of the k optimal locations for the k facilities can be limited to the node set of G (i.e., to a total of n points only) instead of the infinite number of points that lie on the links of G. The validity of the theorem is obvious for the trivial case when the required number of facilities k is greater than or equal to the number of nodes n. Then we only have to locate one facility on each node to reduce average travel distance to zero. We shall now prove the theorem for the special case of a single facility (k = 1). A line of approach similar to the one outlined below can be used to prove the more general case (k1) (see also Problem 6.9).
d(x, j) = Min (d(x, p) + d(p, j), d(x, q) + d(q,J)) (6.16) That is, any node j N will be reached from x (p, q) either through p or through q. Let now P be the set of nodes that point x reaches most efficiently through node p and Q the set of nodes reached more efficiently through q (ties can be broken arbitrarily). P and Q are thus mutually exclusive sets whose union is equal to N. Assume now without loss of generality that more users are reached through
p than through q, that is
From the definition of the distance d(p, j), we have
But the term d(x, p) · is, by assumption (6.17), greater than or equal to zero. Therefore, we conclude that J(x) J(p), which contradicts the assumption that the 1-median is located at an interior point of the link (p, q). Stated differently, we have proved that we can do "at least as well,, by moving the facility from x to the node p. This also completes our proof.
From the discussion above we immediately deduce an algorithm for finding the one-median of an undirected graph G(N, A).
Algorithm 6.10 can also be used, in principle, to obtain the k-medians for any value of k 1. Only Step 3 must be modified to provide for consideration of sets of k rows (rather than of single rows) in the manner indicated for the 2-median case in our example. Unfortunately, the combinations--and attendant required comparisons at
Step 3--become too many to handle even with a computer, as soon as the
number of nodes, n, and number of facility locations required, k, reach
moderate size. For instance, for n = 100 and k = 5 there exist some
75,000,000 possible combinations of 5-medians, with the computation of the
total distance for Several exact algorithms have been proposed for the k-median problem [REVE 70, GARF 74]. Basically, these algorithms attempt to solve efficiently integer programming formulations of the problem. Better known is a conceptually simple heuristic algorithm TEIT 68], which, however, does not always terminate with the optimum k-median solution. We describe below an improved version of that algorithm. It begins by finding the l-median of the network and then increases the number of medians in steps of one at a time, until they become equal to the required number, k (k > 1). Because of Hakimi's theorem we shall only be concerned with locations on nodes. We shall use S to indicate the set of nodes where medians have been (tentatively) located at any given stage in the execution of the algorithm and m to indicate the number of nodes in S. During the execution of the algorithm m will increase from 1 to k.
Algorithm 6.11 is typical of a number of heuristic network algorithms
that use the substitution method to improve initial solutions. For example,
one of the best-known algorithms for the traveling salesman problem
[LIN 73] begins with an initial tour and improves that tour by
substituting one link of the initial tour at a time with another link which
was not in the initial tour. The solutions obtained from such algorithms are
sometimes referred to as 1-optimal, because they cannot be improved by
replacing any single member (node, link, or whatever) of the final solution
set. Algorithm 6.11 could be easily modified to be 2-optimal (or 3-optimal,
etc.) by permitting the substitution in Step 3 of |