Some new algorithms for location problems on networks

In this paper we present new algorithms for the one centre, the one median and the one absolute centre problem. Since Hakimi proved that there is always an optimal solution for the one median problem that is also an optimal solution for the one absolute median problem, the new algorithm for the one median problem can also be used for solving the one absolute median problem. Moreover, we define eight new location problems for most of which we also propose algorithms: The lower-k l-centre, the upper-k l-centre, the lower-k absolute l-centre, the upper-k absolute l-centre, the lower-k l-median, the upper-k l-median, the lower-k absolute 1-median and the upper-k absolute 1-median problem. While most existing algorithms for solving discrete location problems assume the knowledge of the distance matrix of the network, our algorithms do not start from this assumption. By taking advantage of the properties of a modified some-to-all shortest path algorithm, we can solve the location problems during the calculation, and before the total generation, of the distance matrix. All the proposed algorithms have a time complexity of O(nd log n + de), where n denotes the number of vertices, d the number of destinations and e the number of arcs in the network. Computational results are given, showing the average superiority of the proposed approach with respect to the standard procedures.