Inspired by an algorithm due to Minieka, we develop a simple and yet very efficient exact algorithm for the problem of locating p facilities and assigning clients to them in order to minimize the maximum distance between a client and the facility it is assigned to. After a lower bounding phase, the algorithm iteratively sets a maximum distance value within which it tries to assign all clients, and thus solves integer feasibility subproblems. Excellent computational results are reported on a set of 84 test problems derived from OR-Lib and TSP-Lib problem instances with up to 900 vertices, solved to optimality for the first time.
Citation
Bilkent University Technical Report, Department of Industrial Engineering 06533 Ankara Turkey