Selection of minimal set of locations in the public service system design

This paper deals with the problem of designing the optimal structure of a public service system. The public service system design problem are often related to the p-median location problem. Optimal solution of smaller instances of the problem can be obtained by universal IP solvers. The universal IP solvers are very time-consuming and often fail when a large instance is solved. Our approach to the problem is based on the Erlenkotter procedure for solving of the uncapacitated facility location problem. We generalized the Erlenkotter dual approach to lower bounding to be able to solve the associated location problem with restricted number of the located service centers. We designed the exact algorithm based on the branch and bound method. We try to obtain a minimal set of the locations with some heuristic. We design different variants of heuristic for obtaining the minimal set of locations. We verify the variants of heuristic on the benchmarks from the Slovak road network and select the best variant of heuristic by comparison of the individual variants of heuristic in the computational time and the quality of obtained solutions.