2017/11/16 by Daniel Karapetyan, Karapetyan, Daniel, Boris Goldengorin +1
Engineering · #Advanced Manufacturing and Logistics Optimization #Artificial Intelligence (cs.AI) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Maritime Ports and Logistics #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.1711.06347
openalex publication_date 2017/11/16 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28
We address a family of hard benchmark instances for the Simple Plant Location Problem (also known as the Uncapacitated Facility Location Problem). The recent attempt by Fischetti et al. to tackle the Körkel-Ghosh instances resulted in seven new optimal solutions and 22 improved upper bounds. We use automated generation of heuristics to obtain a new algorithm for the Simple Plant Location Problem. In our experiments, our new algorithm matched all the previous best known and optimal solutions, and further improved 12 upper bounds, all within shorter time budgets compared to the previous efforts. Our algorithm design process is split into two phases: (i) development of algorithmic components such as local search procedures and mutation operators, and (ii) composition of a metaheuristic from the available components. Phase (i) requires human expertise and often can be completed by implementing several simple domain-specific routines known from the literature. Phase (ii) is entirely automated by employing the Conditional Markov Chain Search (CMCS) framework. In CMCS, a metaheuristic is flexibly defined by a set of parameters, called configuration. Then the process of composition of a metaheuristic from the algorithmic components is reduced to an optimisation problem seeking the best performing CMCS configuration. We discuss the problem of comparing configurations, and propose a new efficient technique to select the best performing configuration from a large set. To employ this method, we restrict the original CMCS to a simple deterministic case that leaves us with a finite and manageable number of meaningful configurations.