2018/01/10 by David Chalupa, Peter Nielsen, Chalupa, David +1
Business, Management and Accounting · Computer Science · Engineering · #Computational Engineering #FOS: Computer and information sciences #Facility Location and Emergency Management #Finance #Optimization and Search Problems #Vehicle Routing Optimization Methods #and Science (cs.CE)
paper · pdf · doi:10.48550/arxiv.1801.03419
openalex publication_date 2018/01/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Metaheuristics are known to be strong in solving large-scale instances of\ncomputationally hard problems. However, their efficiency still needs\nexploration in the context of instance structure, scale and numerical\nproperties for many of these problems. In this paper, we present an in-depth\ncomputational study of two local search metaheuristics for the classical\nuncapacitated facility location problem. We investigate four problem instance\nmodels, studied for the same problem size, for which the two metaheuristics\nexhibit intriguing and contrasting behaviours. The metaheuristics explored\ninclude a local search (LS) algorithm that chooses the best moves in the\ncurrent neighbourhood, while a randomised local search (RLS) algorithm chooses\nthe first move that does not lead to a worsening. The experimental results\nindicate that the right choice between these two algorithms depends heavily on\nthe distribution of coefficients within the problem instance. This is also put\nfurther into context by finding optimal or near-optimal solutions using a\nmixed-integer linear programming problem solver. Since the facility location\nproblem is a relatively simple example of a choice-and-assignment problem,\nsimilar phenomena are likely to be discovered in a number of other, possibly\nmore complex computational problems in science and engineering.\n