Home  << 1 >> 
Averbakh, I., & Pereira, J. (2021). Tree optimization based heuristics and metaheuristics in network construction problems. Comput. Oper. Res., 128, 105190.
Abstract: We consider a recently introduced class of network construction problems where edges of a transportation network need to be constructed by a server (construction crew). The server has a constant construction speed which is much lower than its travel speed, so relocation times are negligible with respect to construction times. It is required to find a construction schedule that minimizes a nondecreasing function of the times when various connections of interest become operational. Most problems of this class are strongly NPhard on general networks, but are often treeefficient, that is, polynomially solvable on trees. We develop a generic local search heuristic approach and two metaheuristics (Iterated Local Search and Tabu Search) for solving treeefficient network construction problems on general networks, and explore them computationally. Results of computational experiments indicate that the methods have excellent performance.
Keywords: Network design; Scheduling; Network construction; Heuristics; Metaheuristics; Local search

Lagos, F., & Pereira, J. (2023). Multiarme d banditbase d hyperheuristics for combinatorial optimization problems. Eur. J. Oper. Res., 312(1), 70–91.
Abstract: There are significant research opportunities in the integration of Machine Learning (ML) methods and Combinatorial Optimization Problems (COPs). In this work, we focus on metaheuristics to solve COPs that have an important learning component. These algorithms must explore a solution space and learn from the information they obtain in order to find highquality solutions. Among the metaheuristics, we study HyperHeuristics (HHs), algorithms that, given a number of lowlevel heuristics, iteratively select and apply heuristics to a solution. The HH we consider has a Markov model to produce sequences of lowlevel heuristics, which we combine with a MultiArmed Bandit Problem (MAB)based method to learn its parameters. This work proposes several improvements to the HH metaheuristic that yields a better learning for solving problem instances. Specifically, this is the first work in HHs to present Exponential Weights for Exploration and Exploitation (EXP3) as a learning method, an algorithm that is able to deal with adversarial settings. We also present a case study for the Vehicle Routing Problem with Time Windows (VRPTW), for which we include a list of lowlevel heuristics that have been proposed in the literature. We show that our algorithms can handle a large and diverse list of heuristics, illustrating that they can be easily configured to solve COPs of different nature. The computational results indicate that our algorithms are competitive methods for the VRPTW (2.16% gap on average with respect to the best known solutions), demonstrating the potential of these algorithms to solve COPs. Finally, we show how algorithms can even detect lowlevel heuristics that do not contribute to finding better solutions to the problem.& COPY
