Formulations and heuristics for the problems leasing k-median and leasing k-center

• Jorge dos Santos PUC-GÓIAS
• Guilherme Londe PUC-GÓIAS
• Alexandre Ribeiro PUC-GÓIAS
• Welverton da Silva UNICAMP

DOI: https://doi.org/10.5753/etc.2019.6397

Abstract

In this paper, we consider the generalizations of the problems k-median and k-center, known, respectively, as leasing k-median (LKM) and leasing k-center (LKC). We present the formulations of integer linear programming and a heuristic based on the BRKGA meta-heuristic. We compare the solutions found by the heuristic to the solutions found by the solver GUROBI applied to the formulations of linear programming, setting a time limit of 10 minutes. For the tested small instances, the solutions costs found by the heuristic were close to the optimal cost (average GAP ≤ 8%). For the tested greater instances, the heuristic found better solutions than the solutions found by the solver, at least in half of the tests.

Keywords: Facility location problems, BRKGA, heuristics

References

Ahn, S., Cooper, C., Cornu´ejols, G., and Frieze, A. (1988). Probabilistic Analysis of a Relaxation for the k-Median Problem. Mathematics ofOperations Research.

Daskin, M. S. (1995). Network and Discrete Locations: Models, algorithms, and appli- cations. John Wiley & Sons.
Gonc¸alves, J. F. and Resende, M. G. C. (2010). Biased random-key genetic algorithms for combinatorial optimization. Journal ofHeuristics.

Kariv, O. and Hakimi, S. L. (1979a). An Algorithmic Approach to Network Location Problems. I: The p-Centers. SIAM Journal on Applied Mathematics.

Kariv, O. and Hakimi, S. L. (1979b). An Algorithmic Approach to Network Location Problems. II: The p-Medians. SIAM Journal on Applied Mathematics.

Lintzmayer, C. N. and Mota, G. O. (2017). Caderno de problemas. In 1o Workshop Paulista em Otimizac¸ ˜ao, Combinat´oria e Algoritmos.

Toso, R. and Resende, M. (2015). A C++ application programming interface for biased random-key genetic algorithms. Optimization Methods and Software.