Communications - Scientific Letters of the University of Zilina 2015, 17(2):4-10 | DOI: 10.26552/com.C.2015.2.4-10

Re-Aggregation Heuristics for the Large Location Problems with Lexicographic Minimax Objective

Matej Cebecauer¹, Lubos Buzna¹

¹ Department of Mathematical Methods and Operations Research, Faculty of Management Science and Informatics, University of Zilina, Slovakia

We propose a new heuristic algorithm that provides solutions to the discrete lexicographic minimax location problem. The algorithm is applicable to large instances of the problem. The lexicographic minimax location problem is known to be NP-hard. Therefore, the large instances of the problem are not computable in reasonable time. An aggregation is a valuable tool that allows to adjust the size of the problem and approximate the problem by another one that can be solved. An inevitable consequence of aggregation is the loss of the precision. Typically, an aggregation method is used only once, in the initial phase of the solving process. Here, we propose iterative re-aggregating approach which adapts aggregated problem to achieve more precise location of facilities. To test the efficiency of the proposed method, we compute large location problems reaching 67 000 aggregated customers. The proposed approach is versatile and can be used for large range of location problems.

Keywords: location problem; heuristics; aggregation; lexicographic minimax

Published: May 31, 2015  Show citation