Source-linked AI summary
Research trends in combinatorial optimisation
Jann Michael Weinand, Kenneth Sörensen, Pablo San Segundo, Max Kleinebrahm, Russell McKenna
TL;DR
Practical CO problems can outgrow simple enumeration, while existing reviews cover selected aspects of the field. This paper uses bibliometric analysis to examine global CO research trends, reporting strong emphasis on metaheuristics and increasing attention to applications in energy, production, and data management.
Problem
Practical CO problems can outgrow simple enumeration, while existing reviews cover only selected aspects of the field.
Source: §1 · p. 2Method
The paper uses bibliometric analysis to demonstrate global research trends in combinatorial optimisation.
Source: §5 · p. 22Results
Publications focus on developing, extending, and applying metaheuristics, especially genetic algorithms, while increasingly problem-oriented studies address energy, production, and data management.
Source: §5 · pp. 21–22Takeaways & Limitations
The analysis offers an insight into current CO research trends, rather than a 100% comprehensive picture of the field.
Source: §4.3 · p. 20, §5 · p. 22The analysis depends on the search and literature database; studies not indexed in Web of Science are excluded, so the picture is not 100% comprehensive.
Source: §4.3 · p. 20
Abstract
from arXiv · showhide
Real-world problems are becoming highly complex and, therefore, have to be solved with combinatorial optimisation (CO) techniques. Motivated by the strong increase of publications on CO, 8,393 articles from this research field are subjected to a bibliometric analysis. The corpus of literature is examined using mathematical methods and a novel algorithm for keyword analysis. In addition to the most relevant countries, organisations and authors as well as their collaborations, the most relevant CO problems, solution methods and application areas are presented. Publications on CO focus mainly on the development or enhancement of metaheuristics like genetic algorithms. The increasingly problem-oriented studies deal particularly with real-world applications within the energy sector, production sector or data management, which are of increasing relevance due to various global developments. The demonstration of global research trends in CO can support researchers in identifying the relevant issues regarding this expanding and transforming research area.
1. Introduction
As combinatorial optimisation problems become difficult to solve by enumeration and new challenges emerge, the paper argues for a broad review of a growing literature whose existing reviews cover selected aspects. It uses bibliometric analysis to map research trends and identify prominent contributors, themes, and challenges, while framing its results as an insight into current focus rather than an exhaustive account.
1. Introduction
- Enumeration becomes impractical as candidate solutions grow with input size, while uncertainty, combined hard problems, and real-time requirements create further challenges.The paper notes that actual difficulty can motivate solution approaches beyond what worst-case complexity alone reflects.Source: §1 · p. 2
- Existing reviews address selected CO problems, metaheuristics, algorithms, or applications, leaving a broad review of the growing literature useful for understanding overall trends.The paper notes more than 150 reviews on CO, but says they cover only certain aspects.Source: §1 · p. 2
- The bibliometric review aims to infer trends, show researched themes and disciplinary shifts, identify prolific authors, organisations, and countries, and overview existing research.The authors describe the approach as a structured analysis of extensive information on CO.Source: §1 · pp. 2–3
- The paper presents its analysis as an insight into current research focus and important challenges, not a complete and exhaustive list of CO contributions.The authors explicitly note that the bibliometric study has limitations.Source: §1 · pp. 2–3
2. Methodology
The study examines the CO literature through bibliometric and statistical methods, with Web of Science and bibliometrix supporting its analyses. It also defines measures of influence and publication trends, and develops a string-matching algorithm to analyse keywords and author collaboration.
2. Methodology
- The methodology examines the structure and patterns of a document system using mathematical and statistical methods, with Web of Science and bibliometrix used to investigate CO literature.The study also describes an adjusted Web of Science search query and several analysis components, including indicators, trend measurement, and a keyword and author algorithm.Source: §2 · p. 3
2.1. R-tool bibliometrix
- Bibliometrix is an open-source tool for comprehensive scientific mapping analyses, implemented in R and flexible for integration with statistical or graphical packages.The study applies it alongside Web of Science analysis and a newly developed algorithm.Source: §2.1 · p. 3
2.2. Measures of influence: h-index, m-index and g-index
- The h-index counts papers with at least h citations, the m-index divides h by years of scientific activity, and the g-index captures citation totals among the top g articles.The g-index is the largest number of top-cited articles that together receive at least g² citations.Source: §2.2 · p. 4
- Because CO publications are only a subset of each author's output, the study uses these indices for comparisons rather than evaluating an individual's overall scientific activity.For this subset, every author's m-index is below one, although it may be above one across all their publications.Source: §2.2 · p. 4
2.3. Measuring trends
- Publication-growth trends are estimated from annual percentage increases over 2015–2019, averaged and divided into five ranges for arrow-icon display.Table 2 illustrates the arrows using a maximum average annual increase of 100%.Source: §2.3 · p. 4, Table 2 · p. 4
2.4. Keyword and author analysis
- A MATLAB algorithm groups similar keyword strings using Levenshtein distance, with thresholds of one for strings of at least five characters and two for strings of at least nine.The latter threshold is intended to group variants such as a word's plural and hyphenated form.Source: §2.4 · pp. 4–5
- The algorithm also calculates keyword occurrence counts, mean publication year and citations, and co-occurrence in articles to examine keyword links and author collaboration.The distance between two strings is represented as the shortest path between their endpoints in a grid graph.Source: §2.4 · pp. 4–5
3. Results
The results map patterns in combinatorial optimisation research, covering its growth and concentration, influential work, frequently addressed problems and methods, and application areas. They also highlight newer keyword activity and recent problem-oriented topics.
3.1. Development of the research field
- CO publications rose from 13 in 1990 to 533 in 2019, while their share of optimisation articles increased from 0.5% to 0.8%.Source: §3.1 · p. 6
3.2. Publication distribution and collaboration of countries, organisations and authors
- The top 20 countries contributed 7,157 articles (85% of CO publications); the USA led overall with 23%, followed by China with 14%.Source: §3.2 · p. 6
- Since 2014, most annual CO articles were written by Chinese authors, and the top 20 organisations produced 1,696 publications (20%).The most frequent organisational collaboration was between the University of Montreal and Polytechnique Montreal (41 publications).Source: §3.2 · pp. 6–8
3.3. Most relevant sources and articles
- The top 20 sources published 35% of CO articles, with the European Journal of Operational Research accounting for 7% of all publications.Source: §3.3 · p. 9
- LNCS publication counts rose exponentially from 2001 to 2005, but Web of Science lists none from 2007 onward, when it stopped covering LNCS articles.Source: Figure 2 · p. 8, §3.3 · p. 9
- The most-cited study was Dorigo et al. (1996) on ant colony optimisation (5,646 citations), while other top-20 papers developed or enhanced metaheuristics.Source: §3.3 · p. 11
- New metaheuristics are mostly benchmarked on TSP; ant colony optimization appears in four of the 20 most-cited articles, while application-focused articles have few local citations.The application examples include vision and image processing, quantum computers, and atomic decomposition.Source: §3.3 · p. 11
- 108 citations make Deng et al. (2019) the highest annually cited post-2010 article; it develops a particle swarm optimization method, while Wen and Yin (2013) introduce a search algorithm.Other highly cited recent studies address applications including phosphorus systems for white-light LEDs, biological transport networks, and fatty-acid production.Source: §3.3 · p. 12
3.4.2. Combinatorial optimisation problems and solution methods
- The top five relevant keywords are genetic algorithm (521 occurrences), metaheuristic (435), heuristic (419), simulated annealing (310), and optimization (272).Annual occurrences fluctuate but generally increase, except for simulated annealing, whose mean publication year is 2005.7.Source: §3.4.2 · p. 14
- TSP and integer programming each appear 225 times, followed by scheduling at 219; TSP links most often with ant colony optimization (20), genetic algorithms (18), and local search (16).Scheduling is associated with tabu search (13) and simulated annealing (10).Source: §3.4.2 · p. 14
- Robust optimization (mean publication year 2014.0) and multi-objective optimization (2011.4) are the most recent specific problem topics identified.Their publication shares have increased annually since 2015.Source: §3.4.2 · p. 14
- Metaheuristics (435 appearances), heuristics (419), optimization (272), and approximation algorithms (258) are the leading general solution-method keywords, alongside many specific metaheuristics.The three most frequently employed metaheuristics in the corpus are genetic algorithms, simulated annealing, and tabu search.Source: §3.3 · pp. 12–13, §3.4.2 · p. 15
- Genetic algorithms appeared 521 times, simulated annealing 310 times and tabu search 257 times; the latter two are local search, while genetic algorithms use population search.These three metaheuristics were often studied jointly, with at least 34 shared occurrences.Source: §3.4.2 · p. 15
- Ant colony optimisation appeared 175 times and its articles averaged 55 citations, compared with 52 for particle swarm optimisation and 50 for quadratic assignment problems.Source: §3.4.2 · p. 16
3.4.3. Application areas for combinatorial optimisation
- Twelve application areas were identified; production, data, power and management each appeared in 2% of the 8,393 articles.Source: §3.4.3 · p. 16
- Production’s mean publication year was 2011.1, while data-related work focused mainly on data mining and information-related work on information theory.Source: §3.4.3 · p. 17
- Power and energy were the most frequently represented application subjects, and energy had the most recent mean publication year among the twelve areas, at 2011.7.Source: §3.4.3 · p. 17
- Management and decision were the other major application fields covered in more than 100 CO articles each.Source: §3.4.3 · p. 17
- Genetic algorithms were mainly used across application areas, and robust optimisation was a prominent topic, with robust and uncertainty mean publication years of 2013.8 and 2013.3.Source: §3.4.3 · p. 17
4. Discussion
The discussion examines dominant patterns in (meta)heuristic research and prospects for heuristic and exact CO methods, while outlining limitations of the bibliometric analysis and cautions for interpreting its keyword findings.
4.1. Challenges and prospects of (meta)heuristics
- Most CO papers follow a problem-algorithm-results pattern, often offering only anecdotal knowledge while consuming substantial research time on performance-focused development.In this pattern, algorithms are developed for specific problems and compared with other algorithms for the same problem.Source: §4.1 · p. 18
- Competitive-testing publication favors positive findings, while few shared testing protocols and often absent statistical tests make claimed performance improvements difficult to assess.Negative findings are also described as rare.Source: §4.1 · p. 18
- The authors describe a widening divide between metaphor-based and traditional metaheuristics, with novelty of metaphor shaping perceived value and especially low standards in the metaphor-based subfield.The passage notes that traditional metaheuristics also have issues.Source: §4.1 · pp. 18–19
- Research increasingly targets rich, real-life problems as practitioners adopt heuristics and researchers combine them with exact methods and constraint programming.Heuristic-exact combinations, often called matheuristics, have developed into a field of their own.Source: §4.1 · p. 19
4.2. Challenges and prospects of exact algorithms
- Branch-and-bound and integer programming are the main exact-CO keywords, and publications on exact algorithms are considerably fewer than those on approximation algorithms.Source: §4.2 · p. 19
- Kernelization and branch-and-reduce exploit problem structure to speed exact algorithms and have helped solve some large-scale hard instances to proven optimality.Kernelization is applied in preprocessing; branch-and-reduce applies reductions at each branching-tree node.Source: §4.2 · p. 20
4.3. Limitations of this study
- The search query may omit CO studies that do not identify combinatorial optimization in searchable text or Web of Science KeywordPlus, so the analysis is not fully comprehensive.The stated objective is to analyze studies that explicitly treat CO as a methodology.Source: §4.3 · pp. 20–21
- The corpus is assumed representative, but keyword-analysis findings are only indications of research trends.The authors state that the analysis cannot group all relevant keywords.Source: §4.3 · p. 21
- Arbitrary parameter settings, including trend-analysis years and Levenshtein-distance thresholds, can affect results.The authors note that different parameter choices may yield different results.Source: §4.3 · p. 21
- Distance-based keyword grouping requires interpretation and can miss relevant terms or fail to group concepts expressed with different names.For example, large neighborhood search is also called destroy-and-repair or ruin-and-recreate, unlike simulated annealing, which is consistently known by that name.Source: §4.3 · p. 21
- 225 occurrences of “traveling salesman problem” versus 384 of “traveling” and 349 of “salesman” suggest the problem appears in more than 225 articles.Figure 5 reports 225 uses of the combined keyword, while the higher counts for its component words suggest broader coverage.Source: §4.3 · p. 21
5. Summary and conclusions
Across 8,393 records, the analysis finds an expanding field shifting from metaheuristic development toward problem-oriented work on real-world applications. Robust optimisation and the growing relevance of energy, production and data management define key current themes.
5. Summary and conclusions
- Publications on CO increased exponentially from 1990 to 2019, reaching 8,393 articles; the study uses bibliometric analysis and a novel keyword algorithm.The analysis draws on Web of Science and the R-tool bibliometrix.Source: §5 · p. 21
- Among 85 countries, the USA leads with 1,918 articles and h-index 104, China has 1,197 articles and the highest annual output since 2014, and France has 676 articles.Cross-country collaboration is low; the most collaborations are between the USA and China (146).Source: §5 · p. 21
- The French National Centre for Scientific Research leads organisations with 235 articles; the University of California System has 162 and h-index 37, and the Chinese Academy of Sciences has 118.The University of Montreal and Polytechnique Montreal record the most institute collaborations (42); core sources include European Journal of Operational Research, Lecture Notes in Computer Science and Computers & Operations Research.Source: §5 · p. 21
- Metaheuristic development and application dominate; genetic algorithms account for 6% of publications and are often tested on the Traveling Salesman problem as research shifts toward problem-oriented work.The analysis also identifies ant colony optimisation among globally cited publications.Source: §5 · pp. 21–22
- The research focus has partly shifted from algorithm-oriented metaheuristics toward problem-oriented studies, alongside a widening divide between metaphor-based and traditional approaches.Earlier metaheuristic development could be justified by introducing a new metaphor.Source: §5 · p. 22
- CO problems are particularly relevant in energy, production and data management, amid challenges including production networks, greenhouse-gas reduction and big-data processing.The paper links energy applications to the energy-system transition and production applications to global production networks.Source: §5 · p. 22
- Uncertainty and robust optimisation are increasingly relevant in the application areas, while many articles retain a “problem-algorithm-results” format requiring substantial development time.The passage identifies development activities as requiring large amounts of research time to achieve top-notch performance.Source: §5 · p. 22
- The bibliometric analysis demonstrates global CO research trends and can support researchers and policymakers in identifying relevant issues in this expanding, transforming field and its real-world applications.Source: §5 · p. 22