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

Abstract

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.