Upgrading Location Problems: An Approach using Integer Programming

Abstract

Our study on the upgrading version of the maximal covering location problem with edge length modifications in networks. Given a fixed coverage radius, we say that a node is covered by a facility if the distance between them is lower than or equal to this radius. Therefore, the upgrading maximal covering location problem with edge length modifications aims at locating p facilities on the nodes of the network to maximize coverage, considering that the length of the edges can be reduced within a budget. Note that for each edge an upper limit on the maximum reduction ofits length and the cost per unit of reduction is given. Hence, we seek both solutions: the optimal location of p facilities and the optimal edgelength reductions. This problem is NP-hard on general graphs. In this talk, we propose three different mixed-integer formulations to solve the problem on general graphs. Moreover, we provide a preprocessing phase for fixing several variables and removing some constraints. Furthermore, we develop several sets of valid inequalities to enhance the formulations. Finally, we present computational experiments in which we analyze the performance of the three formulations. First, we test the usefulness of the preprocessing phase, showing the great improvement in computational times that this produces. Then, we compare the proposed formulations by testing their performance on a set of networks, outlining the strengths and weaknesses of each formulation. We also test the efficiency of the developed valid inequalities.