An Indirect Method for the Generalized k-Median Problem Applied to Lock-Box Location

The problem of locating lock-boxes (post office boxes operated by banks for corporations) has been formulated as an uncapacitated plant location problem, for which there exist many efficient methods. However, corporations are often reluctant to establish as many lock-boxes as indicated by the optimal solution to this formulation. Hence, it is advisable to find the sequence of solutions containing 1, ..., m lock-boxes, where m denotes the optimal number for the uncapacitated problem. This can be done by imposing an additional constraint specifying that the number of lock-boxes to be established be equal to k, and solving the resulting generalized k-median problem parametrically for k = m, m - 1, ..., 1. It is very unlikely that an efficient direct algorithm exists for this problem, because it has been shown to be NP-complete. An indirect method is given in this paper, using an algorithm for the uncapacitated problem to solve the k-median problem. This method would be particularly valuable in situations where an uncapacitated algorithm is already in use; by adjusting the existing algorithm as indicated in the method, the time and cost required to implement a new algorithm can be avoided. The method has been successfully applied to some 1,000 real lock-box problems. It seems to be roughly as efficient as the underlying uncapacitated algorithm. The computational experience is discussed.