Fifty years of metaheuristics Martí, Rafael; Sevaux, Marc; Sörensen, Kenneth
European journal of operational research,
4/2024
Journal Article
Peer reviewed
Open access
In this paper, we review the milestones in the development of heuristic methods for optimization over the last 50 years. We propose a critical analysis of the main findings and contributions, mainly ...from a European perspective. Starting with the roots of the area that can be traced back to the classical philosophers, we follow the historical path of heuristics and metaheuristics in the field of operations research and list the main milestones, up to the latest proposals to hybridize metaheuristics with machine learning. We pay special attention to the theories that changed our way of thinking about problem solving, and to the role played by the European Journal of Operational Research in the development of these theories. Our approach emphasizes methodologies and their connections with related areas, which permits to identify potential lines of future research.
•A review in the development of heuristic methods over the last 50 years.•The historical path of heuristics in Operations Research with the main milestones.•From heuristics to metaheuristics that changed our view on problem solving.•The role of EJOR in the metaheuristic literature.•The future of heuristic optimization.
In real-life applications problems can frequently change or require small adaptations. Manually creating and tuning algorithms for different problem domains or different versions of a problem can be ...cumbersome and time-consuming. In this paper we consider several important problems with high practical relevance, which are Rotating Workforce Scheduling, Minimum Shift Design, and Bus Driver Scheduling. Instead of designing very specific solution methods, we propose to use the more general approach based on hyper-heuristics which take a set of simpler low-level heuristics and combine them to automatically create a fitting heuristic for the problem at hand. This paper presents a major study on applying hyper-heuristics to these domains, which contributes in four different ways: First, it defines new low-level heuristics for these scheduling domains, allowing to apply hyper-heuristics to them for the first time. Second, it provides a comparison of several state-of-the-art hyper-heuristics on those domains. Third, new best solutions for several instances of the different problem domains are found. Finally, a detailed investigation of the use of low-level heuristics by the hyper-heuristics gives insights in the way hyper-heuristics apply to different domains and the importance of different low-level heuristics. The results show that hyper-heuristics are able to perform well even on very complex practical problem domains in the area of scheduling and, while being more general and requiring less problem-specific adaptation, can in several cases compete with specialized algorithms for the specific problems. Several hyper-heuristics with very good performance across different real-life domains are identified. They can efficiently select low-level heuristics to apply for each domain, but for repeated application they benefit from evaluating and selecting the most useful subset of these heuristics. These results help to improve industrial systems in use for solving different scheduling scenarios by allowing faster and easier adaptation to new problem variants.
•New low-level heuristics for several real-life scheduling domains.•Comparison of state-of-the-art hyper-heuristics on real-life domains.•New best solutions and solutions close to problem-specific methods.•Detailed analysis of the utility and usage of low-level heuristics.
•This paper surveys the recent attempts, both from the machine learning and operations research communities, at leveraging machine learning to solve combinatorial optimization problems.•Given the ...hard nature of these problems, state-of-the-art algorithms rely on handcrafted heuristics for making decisions which are otherwise too expensive to compute or mathematically not well-defined. Thus, machine learning looks like a natural candidate to make such decisions in a more principled and optimized way. We advocate for pushing further the integration of machine learning and combinatorial optimization and detail a methodology to do so. A main point of the paper is seeing generic optimization problems as data points and inquiring what is the relevant distribution of problems to use for learning on a given task.
This paper surveys the recent attempts, both from the machine learning and operations research communities, at leveraging machine learning to solve combinatorial optimization problems. Given the hard nature of these problems, state-of-the-art algorithms rely on handcrafted heuristics for making decisions that are otherwise too expensive to compute or mathematically not well defined. Thus, machine learning looks like a natural candidate to make such decisions in a more principled and optimized way. We advocate for pushing further the integration of machine learning and combinatorial optimization and detail a methodology to do so. A main point of the paper is seeing generic optimization problems as data points and inquiring what is the relevant distribution of problems to use for learning on a given task.
In concentrated solar power (CSP) plants based on parabolic trough collectors (PTC), the sun is tracked at discrete time intervals, with each interval representing a movement of the collector system. ...The act of moving heavy mechanical structures can lead to the development of cracks, bending, and/or displacement of components from their optimal optical positions. This, in turn, diminishes the overall energy capture performance of the entire system. In this context, we introduce two combinatorial optimization problems of great interest to PTC plants. The minimum tracking motion (MTM) problem is aimed at detecting the minimum number of movements needed while maintaining production within a given range. The maximal energy collection (MEC) problem seeks to achieve optimal energy production within a predetermined number of movements. Both problems are solved assuming scenarios where the energy collection function contains any number of local maximums/minimums due to optical errors of the elements in the PTC system. The MTM and MEC problems are solved in O(n) time and O(n2mω∗) time respectively, where n is the number of steps in the energy collection function, m the maximum number of movements of the solar structure, and ω∗ the maximal amplitude angle that the structure can cover. The advantages of the solutions are shown in realistic experiments. While these problems can be solved in polynomial time, we establish the NP-hardness of a slightly modified version of the MEC problem. The proposed algorithms are generic and can be adapted to schedule solar tracking in other CSP systems.
•New optimization problems are defined in the context of solar tracking.•Minimum Tracking Motion and Maximal Energy Collection are solved in polynomial time.•90% of the energy is captured with 75% of the movements of the solar collector.•A variant of the Maximal Energy Collection problem is NP-hard.
High-value payment systems (HVPSs) are typically liquidity intensive because payments are settled on a gross basis. State-of-the-art solutions to this problem include algorithms that seek netting ...sets and allow for ad hoc reordering of submitted payments. This paper introduces a new algorithm that explores the entire space of payments reordering to improve the liquidity efficiency of these systems without significantly increasing payment delays. Finding the optimal payment order among the entire space of reorderings is, however, an NP-hard combinatorial optimization problem. We solve this problem using a hybrid quantum annealing algorithm. Despite the limitations in size and speed of today’s quantum computers, our algorithm provides quantifiable liquidity savings when applied to the Canadian HVPS using a 30-day sample of transaction data. By reordering batches of 70 payments, we achieve an average of Canadian (C) $240 million in daily liquidity savings, with a settlement delay of approximately 90 seconds. For a few days in the sample, the liquidity savings exceed C$1 billion. Compared with classical computing and with current algorithms in HVPS, our quantum algorithm offers larger liquidity savings, and it offers more reliable and consistent solutions, particularly under time constraints. This paper was accepted by Chung Piaw Teo, optimization. Supplemental Material: The data files are available at https://doi.org/10.1287/mnsc.2023.00314 .
We present a unifying framework for Selective Routing Problems (SRPs) through a systematic analysis. The common goal in SRPs is to determine an optimal vehicle route to serve a subset of vertices ...while covering another subset. They arise in diverse fields such as logistics, public health, disaster response, and urban development. To establish a unifying framework for different but related problems, we associate the notion of service with coverage and argue that routing is a tool of service. We classify SRPs according to their selectiveness degree and emphasize the breadth and depth of this problem in terms of its characteristics. This SRP framework helps us identify research gaps as well as potential future research areas. We present a generic mathematical model, use it to describe the connections among these problems and identify some identical problems presented under different names.
•We present a unifying framework and a generic model for Selective Routing Problems.•Problems in logistics, public health, disaster response, and urban development.•We classify SRPs according to their selectiveness degree.•We identify some identical problems presented under different names.•We identify research gaps as well as potential future research areas.
The Ordered Median Tree Location Problem Pozo, Miguel A.; Puerto, Justo; Torrejón, Alberto
Computers & operations research,
September 2024, 2024-09-00, Volume:
169
Journal Article
Peer reviewed
Open access
In this paper, we propose the Ordered Median Tree Location Problem (OMT). The OMT is a single-allocation facility location problem where p facilities must be placed on a network connected by a ...non-directed tree. The objective is to minimize the sum of the ordered weighted averaged allocation costs plus the sum of the costs of connecting the facilities in the tree. We present different MILP formulations for the OMT based on properties of the minimum spanning tree problem and the ordered median optimization. Given that ordered median location problems are rather difficult to solve we have improved the OMT solution performance by introducing covering variables in a valid reformulation plus developing two pre-processing phases to reduce the size of this formulations. In addition, we propose a Benders decomposition algorithm to approach the OMT. We establish an empirical comparison between these new formulations and we also provide enhancements that together with a proper formulation allow to solve medium size instances on general random graphs.
•The Ordered Median Tree Location Problem (OMT) is a new problem in the literature.•Several MILP formulations based on properties of the Minimum Spanning Tree Problem and the Ordered Median Optimization are presented.•Polyhedral description and comparison of the two main formulations are detailed.•A Benders decomposition and alternative formulation for the resolution are included.•Extensive computational results are provided.
Many traditional algorithms for solving combinatorial optimization problems involve using hand-crafted heuristics that sequentially construct a solution. Such heuristics are designed by domain ...experts and may often be suboptimal due to the hard nature of the problems. Reinforcement learning (RL) proposes a good alternative to automate the search of these heuristics by training an agent in a supervised or self-supervised manner. In this survey, we explore the recent advancements of applying RL frameworks to hard combinatorial problems. Our survey provides the necessary background for operations research and machine learning communities and showcases the works that are moving the field forward. We juxtapose recently proposed RL methods, laying out the timeline of the improvements for each problem, as well as we make a comparison with traditional algorithms, indicating that RL models can become a promising direction for solving combinatorial problems.
•Survey explores synergy of combinatorial optimization and reinforcement learning.•It covers recent papers showing how RL can be applied to solve canonical CO problems.•Graph neural networks are used as a method for graph representation in RL for CO.•Policy-based and value-based RL methods are used to learn the solutions to CO tasks.•Most of the reported experiments do not overlap.•This makes it hard to fairly compare the surveyed methods.
PDF
