The DOI matches its Crossref record.
Tabu Search—Part I
Abstract
This paper presents the fundamental principles underlying tabu search as a strategy for combinatorial optimization problems. Tabu search has achieved impressive practical successes in applications ranging from scheduling and computer channel balancing to cluster analysis and space planning, and more recently has demonstrated its value in treating classical problems such as the traveling salesman and graph coloring problems. Nevertheless, the approach is still in its infancy, and a good deal remains to be discovered about its most effective forms of implementation and about the range of problems for which it is best suited. This paper undertakes to present the major ideas and findings to date, and to indicate challenges for future research. Part I of this study indicates the basic principles, ranging from the short-term memory process at the core of the search to the intermediate and long term memory processes for intensifying and diversifying the search. Included are illustrative data structures for implementing the tabu conditions (and associated aspiration criteria) that underlie these processes. Part I concludes with a discussion of probabilistic tabu search and a summary of computational experience for a variety of applications. Part II of this study (to appear in a subsequent issue) examines more advanced considerations, applying the basic ideas to special settings and outlining a dynamic move structure to insure finiteness. Part II also describes tabu search methods for solving mixed integer programming problems and gives a brief summary of additional practical experience, including the use of tabu search to guide other types of processes, such as those of neural networks. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cited by
The Whale Optimization Algorithm
Mirjalili, S., & Lewis, A. (2016) · Advances in Engineering Software · doi:10.1016/j.advengsoft.2016.01.008 · Cited by 14,581
No free lunch theorems for optimization
Wolpert, D. H., & Macready, W. G. (1997) · IEEE Transactions on Evolutionary Computation · doi:10.1109/4235.585893 · Cited by 14,237
Ant system: optimization by a colony of cooperating agents
Dorigo, M., Maniezzo, V., & Colorni, A. (1996) · IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) · doi:10.1109/3477.484436 · Cited by 12,067
Harris hawks optimization: Algorithm and applications
Heidari, A. A., Mirjalili, S., Faris, H., Aljarah, I., Mafarja, M., & Chen, H. (2019) · Future Generation Computer Systems · doi:10.1016/j.future.2019.02.028 · Cited by 6,324
Survey of Clustering Algorithms
Xu, R., & WunschII, D. (2005) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2005.845141 · Cited by 6,197
Salp Swarm Algorithm: A bio-inspired optimizer for engineering design problems
Mirjalili, S., Gandomi, A. H., Mirjalili, S. Z., Saremi, S., Faris, H., & Mirjalili, S. M. (2017) · Advances in Engineering Software · doi:10.1016/j.advengsoft.2017.07.002 · Cited by 5,082
Moth-flame optimization algorithm: A novel nature-inspired heuristic paradigm
Mirjalili, S. (2015) · Knowledge-Based Systems · doi:10.1016/j.knosys.2015.07.006 · Cited by 4,626
Mladenović, N., & Hansen, P. (1997) · Computers & Operations Research · doi:10.1016/s0305-0548(97)00031-2 · Cited by 4,254
Ant Algorithms for Discrete Optimization
Dorigo, M., Caro, G. D., & Gambardella, L. M. (1999) · Artificial Life · doi:10.1162/106454699568728 · Cited by 2,808
Greedy Randomized Adaptive Search Procedures
Feo, T. A., & Resende, M. G. C. (1995) · Journal of Global Optimization · doi:10.1007/bf01096763 · Cited by 2,778
Grasshopper Optimisation Algorithm: Theory and application
Saremi, S., Mirjalili, S., & Lewis, A. (2017) · Advances in Engineering Software · doi:10.1016/j.advengsoft.2017.01.004 · Cited by 2,727
Dowsland, K. A., & Thompson, J. M. (2012) · Handbook of Natural Computing · doi:10.1007/978-3-540-92910-9_49 · Cited by 2,432
Metaheuristics in Combinatorial Optimization
Gendreau, M., & Potvin, J.-Y. (2005) · Annals of Operations Research · doi:10.1007/s10479-005-3971-7 · Cited by 2,338
Ant colony optimization theory: A survey
Dorigo, M., & Blum, C. (2005) · Theoretical Computer Science · doi:10.1016/j.tcs.2005.05.020 · Cited by 2,295
Svergun, D. I. (1999) · Biophysical Journal · doi:10.1016/s0006-3495(99)77443-6 · Cited by 2,221
Models of core/periphery structures
Borgatti, S. P., & Everett, M. G. (2000) · Social Networks · doi:10.1016/s0378-8733(99)00019-2 · Cited by 2,219
Variable neighborhood search: Principles and applications
Hansen, P., & Mladenović, N. (2001) · European Journal of Operational Research · doi:10.1016/s0377-2217(00)00100-4 · Cited by 1,902
A new optimization method: Big Bang–Big Crunch
Erol, O. K., & Eksin, I. (2006) · Advances in Engineering Software · doi:10.1016/j.advengsoft.2005.04.005 · Cited by 1,612
Routing and scheduling in a flexible job shop by tabu search
Brandimarte, P. (1993) · Annals of Operations Research · doi:10.1007/bf02023073 · Cited by 1,322
Lourenço, H. R., Martin, O. C., & Stützle, T. (2006) · International Series in Operations Research & Management Science · doi:10.1007/0-306-48056-5_11 · Cited by 1,164
An improved grey wolf optimizer for solving engineering problems
Nadimi-Shahraki, M. H., Taghian, S., & Mirjalili, S. (2021) · Expert Systems with Applications · doi:10.1016/j.eswa.2020.113917 · Cited by 1,153
Bomze, I. M., Budinich, M., Pardalos, P. M., & Pelillo, M. (1999) · Handbook of Combinatorial Optimization · doi:10.1007/978-1-4757-3023-4_1 · Cited by 1,148
Network analysis of 2-mode data
Borgatti, S. P., & Everett, M. G. (1997) · Social Networks · doi:10.1016/s0378-8733(96)00301-2 · Cited by 1,128
Snake Optimizer: A novel meta-heuristic optimization algorithm
Hashim, F. A., & Hussien, A. G. (2022) · Knowledge-Based Systems · doi:10.1016/j.knosys.2022.108320 · Cited by 1,106
Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem
Osman, I. H. (1993) · Annals of Operations Research · doi:10.1007/bf02023004 · Cited by 1,046
Dhiman, G., & Kumar, V. (2017) · Advances in Engineering Software · doi:10.1016/j.advengsoft.2017.05.014 · Cited by 1,042
The traveling salesman problem: An overview of exact and approximate algorithms
Laporte, G. (1992) · European Journal of Operational Research · doi:10.1016/0377-2217(92)90138-y · Cited by 971
On the design of early generation variety trials with correlated data
Cullis, B. R., Smith, A. B., & Coombes, N. E. (2006) · Journal of Agricultural, Biological, and Environmental Statistics · doi:10.1198/108571106x154443 · Cited by 926
Abandoning Objectives: Evolution Through the Search for Novelty Alone
Lehman, J., & Stanley, K. O. (2011) · Evolutionary Computation · doi:10.1162/evco_a_00025 · Cited by 917
Glover, F., Taillard, E., & Taillard, E. (1993) · Annals of Operations Research · doi:10.1007/bf02078647 · Cited by 902
Self-citationMetaheuristic research: a comprehensive survey
Hussain, K., Mohd Salleh, M. N., Cheng, S., & Shi, Y. (2019) · Artificial Intelligence Review · doi:10.1007/s10462-017-9605-z · Cited by 864
Vehicle Routing Problem with Time Windows, Part II: Metaheuristics
Bräysy, O., & Gendreau, M. (2005) · Transportation Science · doi:10.1287/trsc.1030.0057 · Cited by 844
Boros, E., & Hammer, P. L. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(01)00341-9 · Cited by 827
INFO: An efficient optimization algorithm based on weighted mean of vectors
Ahmadianfar, I., Heidari, A. A., Noshadian, S., Chen, H., & Gandomi, A. H. (2022) · Expert Systems with Applications · doi:10.1016/j.eswa.2022.116516 · Cited by 822
Deterministic job-shop scheduling: Past, present and future
Jain, A. S., & Meeran, S. (1999) · European Journal of Operational Research · doi:10.1016/s0377-2217(98)00113-1 · Cited by 782
Inuiguchi, M., & Ramı́k, J. (2000) · Fuzzy Sets and Systems · doi:10.1016/s0165-0114(98)00449-7 · Cited by 769
A survey for the quadratic assignment problem
Loiola, E. M., de Abreu, N. M. M., Boaventura-Netto, P. O., Hahn, P., & Querido, T. (2007) · European Journal of Operational Research · doi:10.1016/j.ejor.2005.09.032 · Cited by 741
Mixed-integer nonlinear optimization
Belotti, P., Kirches, C., Leyffer, S., Linderoth, J., Luedtke, J., & Mahajan, A. (2013) · Acta Numerica · doi:10.1017/s0962492913000032 · Cited by 712
Ultra-Low Latency (ULL) Networks: The IEEE TSN and IETF DetNet Standards and Related 5G ULL Research
Nasrallah, A., Thyagaturu, A. S., Alharbi, Z., Wang, C., Shao, X., Reisslein, M., & ElBakoury, H. (2019) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2018.2869350 · Cited by 695
Rajwar, K., Deep, K., & Das, S. (2023) · Artificial Intelligence Review · doi:10.1007/s10462-023-10470-y · Cited by 687
Metaheuristics: A bibliography
Osman, I. H., & Laporte, G. (1996) · Annals of Operations Research · doi:10.1007/bf02125421 · Cited by 672
A Survey of Automated Timetabling
Schaerf, A. (1999) · Artificial Intelligence Review · doi:10.1023/a:1006576209967 · Cited by 654
Supervised, Unsupervised, and Semi-Supervised Feature Selection: A Review on Gene Selection
Ang, J. C., Mirzal, A., Haron, H., & Hamed, H. N. A. (2016) · IEEE/ACM Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbb.2015.2478454 · Cited by 641
Shadravan, S., Naji, H. R., & Bardsiri, V. K. (2019) · Engineering Applications of Artificial Intelligence · doi:10.1016/j.engappai.2019.01.001 · Cited by 634
Protein-to-protein interactions: Technologies, databases, and algorithms
Cannataro, M., Guzzi, P. H., & Veltri, P. (2010) · ACM Computing Surveys · doi:10.1145/1824795.1824796 · Cited by 620
Graph mining: Laws, generators, and algorithms
Chakrabarti, D., & Faloutsos, C. (2006) · ACM Computing Surveys · doi:10.1145/1132952.1132954 · Cited by 609
Metaheuristic design of feedforward neural networks: A review of two decades of research
Ojha, V. K., Abraham, A., & Snášel, V. (2017) · Engineering Applications of Artificial Intelligence · doi:10.1016/j.engappai.2017.01.013 · Cited by 606
A novel metaheuristic optimizer inspired by behavior of jellyfish in ocean
Chou, J.-S., & Truong, D.-N. (2021) · Applied Mathematics and Computation · doi:10.1016/j.amc.2020.125535 · Cited by 606
Planning models for freight transportation
Crainic, T. G., & Laporte, G. (1997) · European Journal of Operational Research · doi:10.1016/s0377-2217(96)00298-6 · Cited by 592
Local elevation: A method for improving the searching properties of molecular dynamics simulation
Huber, T., Torda, A. E., & van Gunsteren, W. F. (1994) · Journal of Computer-Aided Molecular Design · doi:10.1007/bf00124016 · Cited by 575
Iterated Local Search: Framework and Applications
Lourenço, H. R., Martin, O. C., & Stützle, T. (2010) · International Series in Operations Research & Management Science · doi:10.1007/978-1-4419-1665-5_12 · Cited by 571
A review of optimization techniques in metal cutting processes
Mukherjee, I., & Ray, P. K. (2006) · Computers & Industrial Engineering · doi:10.1016/j.cie.2005.10.001 · Cited by 549
The job shop scheduling problem: Conventional and new solution techniques
Błażewicz, J., Domschke, W., & Pesch, E. (1996) · European Journal of Operational Research · doi:10.1016/0377-2217(95)00362-2 · Cited by 536
The Theory and Practice of Simulated Annealing
Henderson, D., Jacobson, S. H., & Johnson, A. W. (2006) · International Series in Operations Research & Management Science · doi:10.1007/0-306-48056-5_10 · Cited by 514
Abdmouleh, Z., Gastli, A., Ben-Brahim, L., Haouari, M., & Al-Emadi, N. A. (2017) · Renewable Energy · doi:10.1016/j.renene.2017.05.087 · Cited by 508
A novel algorithm for global optimization: Rat Swarm Optimizer
Dhiman, G., Garg, M., Nagar, A., Kumar, V., & Dehghani, M. (2021) · Journal of Ambient Intelligence and Humanized Computing · doi:10.1007/s12652-020-02580-0 · Cited by 507
Recent Advances in Graph Partitioning
Buluç, A., Meyerhenke, H., Safro, I., Sanders, P., & Schulz, C. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-49487-6_4 · Cited by 482
Golden eagle optimizer: A nature-inspired metaheuristic algorithm
Mohammadi-Balani, A., Dehghan Nayeri, M., Azar, A., & Taghizadeh-Yazdi, M. (2021) · Computers & Industrial Engineering · doi:10.1016/j.cie.2020.107050 · Cited by 480
Generating software test data by evolution
Michael, C. C., McGraw, G., & Schatz, M. A. (2001) · IEEE Transactions on Software Engineering · doi:10.1109/32.988709 · Cited by 478
Jaszkiewicz, A. (2002) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2002.802873 · Cited by 474
Devika, K., Jafarian, A., & Nourbakhsh, V. (2014) · European Journal of Operational Research · doi:10.1016/j.ejor.2013.12.032 · Cited by 455
Designing and reporting on computational experiments with heuristic methods
Barr, R. S., Golden, B. L., Kelly, J. P., Resende, M. G. C., & Stewart, W. R. (1995) · Journal of Heuristics · doi:10.1007/bf02430363 · Cited by 448
A comprehensive review: Krill Herd algorithm (KH) and its applications
Bolaji, A. L., Al-Betar, M. A., Awadallah, M. A., Khader, A. T., & Abualigah, L. M. (2016) · Applied Soft Computing · doi:10.1016/j.asoc.2016.08.041 · Cited by 443
The p-median problem: A survey of metaheuristic approaches
Mladenović, N., Brimberg, J., Hansen, P., & Moreno-Pérez, J. A. (2007) · European Journal of Operational Research · doi:10.1016/j.ejor.2005.05.034 · Cited by 433
Heuristics for multi-attribute vehicle routing problems: A survey and synthesis
Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2013) · European Journal of Operational Research · doi:10.1016/j.ejor.2013.02.053 · Cited by 430
Glover, F., & Laguna, M. (1998) · Handbook of Combinatorial Optimization · doi:10.1007/978-1-4613-0303-9_33 · Cited by 428
Self-citationSalp swarm algorithm: a comprehensive survey
Abualigah, L., Shehab, M., Alshinwan, M., & Alabool, H. (2020) · Neural Computing and Applications · doi:10.1007/s00521-019-04629-4 · Cited by 427
A new optimization method based on COOT bird natural life model
Naruei, I., & Keynia, F. (2021) · Expert Systems with Applications · doi:10.1016/j.eswa.2021.115352 · Cited by 427
Taboo Search: An Approach to the Multiple Minima Problem
Cvijović, D., & Klinowski, J. (1995) · Science · doi:10.1126/science.267.5198.664 · Cited by 416
Optimal Power Flow Using Tabu Search Algorithm
Abido, M. A. (2002) · Electric Power Components and Systems · doi:10.1080/15325000252888425 · Cited by 414
Guided local search and its application to the traveling salesman problem
Voudouris, C., & Tsang, E. (1999) · European Journal of Operational Research · doi:10.1016/s0377-2217(98)00099-x · Cited by 409
Evaluating evolutionary algorithms
Whitley, D., Rana, S., Dzubera, J., & Mathias, K. E. (1996) · Artificial Intelligence · doi:10.1016/0004-3702(95)00124-7 · Cited by 406
Enhanced sampling in molecular dynamics
Yang, Y. I., Shao, Q., Zhang, J., Yang, L., & Gao, Y. Q. (2019) · The Journal of Chemical Physics · doi:10.1063/1.5109531 · Cited by 398
MiarNaeimi, F., Azizyan, G., & Rashki, M. (2021) · Knowledge-Based Systems · doi:10.1016/j.knosys.2020.106711 · Cited by 398
Power load forecasting using support vector machine and ant colony optimization
Niu, D., Wang, Y., & Wu, D. D. (2010) · Expert Systems with Applications · doi:10.1016/j.eswa.2009.08.019 · Cited by 391
An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem
Gambardella, L. M., & Dorigo, M. (2000) · INFORMS Journal on Computing · doi:10.1287/ijoc.12.3.237.12636 · Cited by 373
A Graph-based Ant System and its convergence
Gutjahr, W. J. (2000) · Future Generation Computer Systems · doi:10.1016/s0167-739x(00)00044-3 · Cited by 368
A review of planning and scheduling systems and methods for integrated steel production
Tang, L., Liu, J., Rong, A., & Yang, Z. (2001) · European Journal of Operational Research · doi:10.1016/s0377-2217(00)00240-x · Cited by 362
Local search in combinatorial optimization
Crama, Y., Kolen, A. W. J., & Pesch, E. J. (1995) · Lecture Notes in Computer Science · doi:10.1007/bfb0027029 · Cited by 361
Algorithms for the maximum satisfiability problem
Hansen, P., & Jaumard, B. (1990) · Computing · doi:10.1007/bf02241270 · Cited by 360
Identification of Outliers in Multivariate Data
Rocke, D. M., & Woodruff, D. L. (1996) · Journal of the American Statistical Association · doi:10.1080/01621459.1996.10476975 · Cited by 360
A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows
Bent, R., & Van Hentenryck, P. (2004) · Transportation Science · doi:10.1287/trsc.1030.0049 · Cited by 355
Houssein, E. H., Gad, A. G., Wazery, Y. M., & Suganthan, P. N. (2021) · Swarm and Evolutionary Computation · doi:10.1016/j.swevo.2021.100841 · Cited by 355
Simulated annealing metaheuristics for the vehicle routing problem with time windows
Chiang, W.-C., & Russell, R. A. (1996) · Annals of Operations Research · doi:10.1007/bf02601637 · Cited by 354
An Introduction to Variable Neighborhood Search
Hansen, P., & Mladenović, N. (1999) · Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization · doi:10.1007/978-1-4615-5775-3_30 · Cited by 340
Analysis of Travel Times and CO 2 Emissions in Time‐Dependent Vehicle Routing
Jabali, O., VanWoensel, T., & de Kok, A. G. (2012) · Production and Operations Management · doi:10.1111/j.1937-5956.2012.01338.x · Cited by 332
Massive Quasi-Clique Detection
Abello, J., Resende, M. G. C., & Sudarsky, S. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45995-2_51 · Cited by 331
Optimal sensor placement for fault detection
Worden, K., & Burrows, A. P. (2001) · Engineering Structures · doi:10.1016/s0141-0296(00)00118-8 · Cited by 331
Sea-horse optimizer: a novel nature-inspired meta-heuristic for global optimization problems
Zhao, S., Zhang, T., Ma, S., & Wang, M. (2023) · Applied Intelligence · doi:10.1007/s10489-022-03994-3 · Cited by 328
Scheduling flow shops using differential evolution algorithm
Onwubolu, G., & Davendra, D. (2006) · European Journal of Operational Research · doi:10.1016/j.ejor.2004.08.043 · Cited by 328
Supervised Regionalization Methods: A Survey
Duque, J. C., Ramos, R., & Suriñach, J. (2007) · International Regional Science Review · doi:10.1177/0160017607301605 · Cited by 318
An improved discrete bat algorithm for symmetric and asymmetric Traveling Salesman Problems
Osaba, E., Yang, X.-S., Diaz, F., Lopez-Garcia, P., & Carballedo, R. (2016) · Engineering Applications of Artificial Intelligence · doi:10.1016/j.engappai.2015.10.006 · Cited by 312
Bagnall, A. J., Rayward-Smith, V. J., & Whittley, I. M. (2001) · Information and Software Technology · doi:10.1016/s0950-5849(01)00194-x · Cited by 311
Das, B., Mukherjee, V., & Das, D. (2020) · Advances in Engineering Software · doi:10.1016/j.advengsoft.2020.102804 · Cited by 305
Thermodynamics and Kinetics of Drug-Target Binding by Molecular Simulation
Decherchi, S., & Cavalli, A. (2020) · Chemical Reviews · doi:10.1021/acs.chemrev.0c00534 · Cited by 301
Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches
Jans, R., & Degraeve, Z. (2007) · European Journal of Operational Research · doi:10.1016/j.ejor.2005.12.008 · Cited by 297
Variable Neighborhood Decomposition Search
Hansen, P., Mladenović, N., & Perez-Britos, D. (2001) · Journal of Heuristics · doi:10.1023/a:1011336210885 · Cited by 296
Bison: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem
Scholl, A., Klein, R., & Jürgens, C. (1997) · Computers & Operations Research · doi:10.1016/s0305-0548(96)00082-2 · Cited by 295
Optimal power flow: a bibliographic survey II: Non-deterministic and hybrid methods
Frank, S., Steponavice, I., & Rebennack, S. (2012) · Energy Systems · doi:10.1007/s12667-012-0057-x · Cited by 294
Heuristics from nature for hard combinatorial optimization problems
Colorni, A. (1996) · International Transactions in Operational Research · doi:10.1016/0969-6016(96)00004-4 · Cited by 288
Metadata
- Authors
- Glover, F.
- Venue
- ORSA Journal on Computing
- Published
- 1989-08
- Volume
- 1
- Issue
- 3
- Pages
- 190-206
- ISSN
- 0899-1499 (ISSN-L)
- 2326-3245
- OpenAlex
- W4246598646
- Cited by
- 5,106
- References
- 0
- FWCI
- 14.58
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.