2020/04/02 by Luc Libralesso, Libralesso, Luc, Florian Fontan +1
Computer Science · Engineering · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Metaheuristic Optimization Algorithms Research #Optimization and Packing Problems #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2004.00963
openalex publication_date 2020/04/02 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
In this article, we present the anytime tree search algorithm we designed for\nthe 2018 ROADEF/EURO challenge glass cutting problem proposed by the French\ncompany Saint-Gobain. The resulting program was ranked first among 64\nparticipants. Its key components are: a new search algorithm called Memory\nBounded A* (MBA*) with guide functions, a symmetry breaking strategy, and a\npseudo-dominance rule. We perform a comprehensive study of these components\nshowing that each of them contributes to the algorithm global performances. In\naddition, we designed a second tree search algorithm fully based on the\npseudo-dominance rule and dedicated to some of the challenge instances with\nstrong precedence constraints. On these instances, it finds the best-known\nsolutions very quickly.\n