Heurísticas para o problema leasing k-median

Abstract

In this term paper a generalization of the k-median problem, known as leasing k-median problem, was studied. For this generalization are given a set of time instants, sets of customers that need to be served at each time instant, a set of points where facilities can be opened to serve customers, the possible durations for a facility opening and a constant value k. The objective of the problem is to determine which, when and for how long the facilities should be opened to minimize the costs of serving the customers, while respecting a rescriction that at most k facilities may be open at the same time. Throughout the work, an integer linear programming formulation and two heuristics based on the BRKGA and VNS metaheuristics were proposed. The linear programming formulation was used with a commercial solver as a benchmark for the computational experiments. The experiments were performed by running each approach for 10 minutes and considering the best solution obtained within that timeframe for a set of random instances. The solver was very useful in resolving small instances, finding, during the test phase, an optimal solution for all instances of this type in less than 30 seconds. The BRKGA presented an average optimality gap of 7.08% between a lower bound of the optimal value and the value of the incumbent solution found by the heuristic. Among the three approaches, the VNS was the best option for medium and large-sized instances, obtaining, on average, optimal gaps, respectively, of 2.08% and 5.70% between the value of the incumbent solution and a lower bound of the optimal value.