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

Lazaros P. Mavrides
Additional contact information
Lazaros P. Mavrides: Morgan Guaranty Trust Company

Management Science, 1979, vol. 25, issue 10, 990-996

Abstract: 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.

Keywords: location; k-median; lock-box (search for similar items in EconPapers)
Date: 1979
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.25.10.990 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:25:y:1979:i:10:p:990-996

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().