Local Search Algorithms for Combinatorial Problems - Analysis, Improvements and New Applications
Dépôt institutionnel de l'Université libre de Bruxelles (Université Libre de Bruxelles)Published 1 September 1999
Thomas Stützle
Citations166
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
info:eu-repo/semantics/published
Keywords
Computer Science
Choice Reviews OnlineGenetic algorithms in search, optimization, and machine learning
49,278 Citations1989
This book brings together the computer techniques, mathematical tools, and research results that will enable both students and practitioners to apply genetic algorithms to problems in many fields.
ScienceOptimization by Simulated Annealing
44,600 Citations1983Scott Kirkpatrick, C. D. Gelatt +1 more
A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems.
The MIT Press eBooksAdaptation in Natural and Artificial Systems
35,568 Citations1992John H. Holland
Initially applying his concepts to simply defined artificial systems with limited numbers of parameters, Holland goes on to explore their use in the study of a wide range of complex, naturally occuring processes, concentrating on systems having multiple factors that interact in nonlinear ways.
IEEE Transactions on Pattern Analysis and Machine IntelligenceStochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
17,980 Citations1984Stuart Geman, Donald Geman
The analogy between images and statistical mechanics systems is made and the analogous operation under the posterior distribution yields the maximum a posteriori (MAP) estimate of the image given the degraded observations, creating a highly parallel ``relaxation'' algorithm for MAP estimation.
IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics)Ant system: optimization by a colony of cooperating agents
11,908 Citations1996Marco Dorigo, Vittorio Maniezzo +1 more
Artificial intelligenceGenetic Algorithms + Data Structures = Evolution Programs
11,598 Citations1992Zbigniew Michalewicz
Journal of Artificial Intelligence ResearchReinforcement Learning: A Survey
8,831 Citations1996Leslie Pack Kaelbling, Michael L. Littman +1 more
Central issues of reinforcement learning are discussed, including trading off exploration and exploitation, establishing the foundations of the field via Markov decision theory, learning from delayed reinforcement, constructing empirical models to accelerate learning, making use of generalization and hierarchy, and coping with hidden state.
International Journal of BiochemistryThe origins of order; self organization and selection in evolution
6,753 Citations1994
Thank you very much for downloading the origins of order self organization and selection in evolution, which many people have look hundreds of times for their favorite readings like this, but end up in infectious downloads.
Biological Cybernetics“Neural” computation of decisions in optimization problems
6,040 Citations1985J. J. Hopfield, David W. Tank
Results of computer simulations of a network designed to solve a difficult but well-defined optimization problem-the Traveling-Salesman Problem-are presented and used to illustrate the computational power of the networks.
Tabu Search
5,702 Citations1997Fred Glover, Manuel Laguna
INFORMS Journal on ComputingTabu Search—Part II
5,643 Citations1990Fred Glover
The elements of staged search and structured move sets are characterized, which bear on the issue of finiteness, and new dynamic strategies for managing tabu lists are introduced, allowing fuller exploitation of underlying evaluation functions.
Journal of the Operational Research SocietyInteger and Combinatorial Optimization
5,548 Citations1990H. P. Williams, George L. Nemhauser +1 more
Bell System Technical JournalAn Efficient Heuristic Procedure for Partitioning Graphs
5,218 Citations1970Brian W. Kernighan, Shang Min Lin
A heuristic method for partitioning arbitrary graphs which is both effective in finding optimal partitions, and fast enough to be practical in solving large problems is presented.
Computers & Operations ResearchVariable neighborhood search
4,147 Citations1997Nenad Mladenović, Pierre Hansen
This chapter presents the basic schemes of VNS and some of its extensions, and presents five families of applications in which VNS has proven to be very successful.
Operations ResearchAn Effective Heuristic Algorithm for the Traveling-Salesman Problem
3,797 Citations1973Simon Lin, Brian W. Kernighan
This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric traveling-salesman problem based on a general approach to heuristics that is believed to have wide applicability in combinatorial optimization problems.
TechnometricsStatistical Theory of Reliability and Life Testing-Probability Models
3,710 Citations1977Donald R. Smith, Richard E. Barlow +1 more
Journal of Optimization Theory and ApplicationsThermodynamical approach to the traveling salesman problem: An efficient simulation algorithm
3,357 Citations1985V. Černý
It is conjecture that the analogy with thermodynamics can offer a new insight into optimization problems and can suggest efficient algorithms for solving them.
Communications of the ACMA machine program for theorem-proving
3,191 Citations1962Martin Davis, George Logemann +1 more
The programming of a proof procedure is discussed in connection with trial runs and possible improvements.
Modern heuristic techniques for combinatorial problems
2,623 Citations1993Colin R. Reeves
This chapter discusses combinatorial problems local and global optima heuristics, the tabu framework, and Evaluation of heuristic performance: analytical methods empirical testing statistical inference conclusions.
Distributed Optimization by Ant Colonies
2,580 Citations1992Alberto Colorni, Marco Dorigo +3 more
A distributed problem solving environment is introduced and its use to search for a solution to the travelling salesman problem is proposed.
INFORMS Journal on ComputingTSPLIB—A Traveling Salesman Problem Library
2,570 Citations1991Gerhard Reinelt
This paper contains the description of a traveling salesman problem library (TSPLIB) which is meant to provide researchers with a broad set of test problems from various sources and with various properties.
Optimization—Theory and Applications
2,564 Citations1983Lamberto Cesari
Theoretical Equivalence of Mayer, Lagrange, and Bolza Problems of Optimal Control, and the Necessary Conditions and Sufficient Conditions Convexity and Lower Semicontinuity.
OmegaA heuristic algorithm for the m-machine, n-job flow-shop sequencing problem
2,493 Citations1983Muhammad Nawaz, E. Emory Enscore +1 more
A simple algorithm is presented in this paper, which produces very good sequences in comparison with existing heuristics, and performs especially well on large flow-shop problems in both the static and dynamic sequencing environments.
European Journal of Operational ResearchBenchmarks for basic scheduling problems
2,403 Citations1993Éric D. Taillard
This paper proposes 260 randomly generated scheduling problems whose size is greater than that of the rare examples published, and the objective is the minimization of the makespan.
Kluwer Academic Publishers eBooksGreedy Randomized Adaptive Search Procedures
2,325 Citations2006Maurício G. C. Resende, Celso C. Ribeiro
New Ideas In Optimization
2,135 Citations1999David Corne, Marco Dorigo +5 more
The techniques treated in this text represent research as elucidated by the leaders in the field and are applied to real problems, such as hilllclimbing, simulated annealing, and tabu search.
Princeton University Press eBooksLocal Search in Combinatorial Optimization
2,059 Citations2003Emile Aarts, Jan Karel Lenstra
Operations ResearchBranch-and-Bound Methods: A Survey
1,982 Citations1966Eugene L. Lawler, Derek Wood
The essential features of the branch-and-bound approach to constrained optimization are described, and several specific applications are reviewed, including integer linear programming Land-Doig and Balas methods, nonlinear programming minimization of nonconvex objective functions, and the quadratic assignment problem Gilmore and Lawler methods.
Artificial IntelligenceTemporal constraint networks
1,800 Citations1991Rina Dechter, Itay Meiri +1 more
It is shown that the STP, which subsumes the major part of Vilain and Kautz's point algebra, can be solved in polynomial time and the applicability of path consistency algorithms as preprocessing of temporal problems is studied, to demonstrate their termination and bound their complexities.
Journal of the ACMP-Complete Approximation Problems
1,715 Citations1976Sartaj Sahni, Teofilo F. Gonzalez
For P- complete problems such as traveling salesperson, cycle covers, 0-1 integer programming, multicommodity network flows, quadratic assignment, etc., it is shown that the approximation problem is also P-complete.
Elsevier eBooksFoundations of Constraint Satisfaction
1,616 Citations1993
Introduction to the C SP CSP solving - an overview chapter fundamental concepts of the CSP chapter problem reduction chapter basic search strategies for solving CSPs search orders in searching in C SPs exploitation of problem specific features stochastic search methods.
Communications of the ACMNew methods to color the vertices of a graph
1,564 Citations1979Daniel Brélaz
An exact method is given which performs better than the Randall-Brown algorithm and is able to color larger graphs and the new heuristic methods, the classical methods, and the exact method are compared.
Operations ResearchA Method for Solving Traveling-Salesman Problems
1,532 Citations1958G. A. Croes
A method of solution for the traveling-salesman problem that is applicable to both symmetric and asymmetric problems with random elements, and does not use subjective decisions, so that it can be completely mechanized.
Medical Entomology and ZoologyOn Evolution, Search, Optimization, Genetic Algorithms and Martial Arts : Towards Memetic Algorithms
1,514 Citations1989Pablo Moscato
Discrete Applied MathematicsSimulated annealing and boltzmann machines: A stochastic approach to combinatorial optimization and neural computing
1,454 Citations1990
Mathematics of Operations ResearchCooling Schedules for Optimal Annealing
1,232 Citations1988Bruce Hajek
A Monte Carlo optimization technique called “simulated annealing” is a descent algorithm modified by random ascent moves in order to escape local minima which are not global minima.
A new method for solving hard satisfiability problems
1,183 Citations1992Bart Selman, Hector J. Levesque +1 more
A greedy local search procedure called GSAT is introduced for solving propositional satisfiability problems and its good performance suggests that it may be advantageous to reformulate reasoning tasks that have traditionally been viewed as theorem-proving problems as model-finding tasks.
Operations Research ForumWorst-Case Analysis of a New Heuristic for the Travelling Salesman Problem
1,142 Citations2022Nicos Christofides
An O(n3) heuristic algorithm is described for solving d-city travelling salesman problems (TSP) whose cost matrix satisfies the triangularity condition and a worst-case analysis of this heuristic shows that the ratio of the answer obtained to the optimum TSP solution is strictly less than 3/2.
Telematics and InformaticsHeuristics: Intelligent Search Strategies for Computer Problem Solving
1,083 Citations1986
SIAM ReviewA Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
1,061 Citations1991Manfred Padberg, Giovanni Rinaldi
An algorithm is described for solving large-scale instances of the Symmetric Traveling Salesman Problem (STSP) to optimality using a “polyhedral” cutting-plane procedure that exploits a subset of the system of linear inequalities defining the convex hull of the incidence vectors of the hamiltonian cycles of a complete graph.
A Survey of Parallel Genetic Algorithms
900 Citations2000Erick Cantú‐Paz
This survey attempts to collect, organize, and present in a unified way some of the most representative publications on parallel genetic algorithms.
AI MagazineAlgorithms for constraint-satisfaction problems: a survey
886 Citations1992Vipin Kumar
A large number of problems in AI and other areas of computer science can be viewed as special cases of the constraint-satisfaction problem, and a number of different approaches have been developed for solving them.
Computers & Operations ResearchA genetic algorithm for flowshop sequencing
870 Citations1995Colin R. Reeves
A Genetic Algorithm is developed for finding (approximately) the minimum makespan of the n-job, m-machine permutation flowshop sequencing problem and the performance of the algorithm is compared with that of a naive Neighbourhood Search technique and with a proven Simulated Annealing algorithm.
European Journal of Operational ResearchSome efficient heuristic methods for the flow shop sequencing problem
855 Citations1990Éric D. Taillard
The best heuristic methods known up to now are compared to solve the flow shop sequencing problem and the complexity of the best one is improved and a parallel taboo search algorithm is presented and experimental results show that this heuristic allows very good speed-up.
Pushing the envelope: planning, propositional logic, and stochastic search
845 Citations1996Henry Kautz, Bart Selman
Stochastic methods are shown to be very effective on a wide range of scheduling problems, but this is the first demonstration of its power on truly challenging classical planning instances.
Artificial IntelligenceMinimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems
830 Citations1992Steven Minton, Mark Johnston +2 more
A theoretical analysis is presented both to explain why this heuristic approach to solving large-scale constraint satisfaction and scheduling problems works well on certain types of problems and to predict when it is likely to be most effective.
Parallel ComputingRobust taboo search for the quadratic assignment problem
827 Citations1991Éric D. Taillard
An adaptation of taboo search to the quadratic assignment problem is discussed in this paper, which is efficient and robust, requiring less complexity and fewer parameters than earlier adaptations.
INFORMS Journal on ComputingThe Reactive Tabu Search
806 Citations1994Roberto Battiti, Giampietro Tecchiolli
An algorithm for combinatorial optimization where an explicit check for the repetition of configurations is added to the basic scheme of Tabu search, and it is shown that the Hashing or Digital Tree techniques can be used in order to search for repetitions in a time that is approximately constant.
ePubWU Institutional Repository (Wirtschaftsuniversität Wien)A new rank based version of the Ant System. A computational study.
802 Citations1997B. Bullnheimer, Richard F. Hartl +1 more
It turns out that the new rank based ant system can compete with the other methods in terms of average behavior, and shows even better worst case behavior.
Noise strategies for improving local search
761 Citations1994Bart Selman, Henry Kautz +1 more
It is shown that mixed random walk is the superior strategy for solving MAX-SAT problems, and results demonstrating the effectiveness of local search with walk for solving circuit synthesis and circuit diagnosis problems are presented.
IEEE Transactions on Knowledge and Data EngineeringThe ant system applied to the quadratic assignment problem
745 Citations1999Vittorio Maniezzo, A. Colorni
A distributed heuristic algorithm that was inspired by the observation of the behavior of ant colonies is described and its use for the quadratic assignment problem is proposed.
Mathematical ProgrammingConvergence of an annealing algorithm
696 Citations1986Margaret E. Lundy, A.I. Mees
This paper presents a model of the annealing algorithm and proves that the algorithm converges with probability arbitrarily close to 1, and shows that there are cases where convergence takes exponentially long—that is, it is no better than a deterministic method.
ComputingUsing tabu search techniques for graph coloring
660 Citations1987Alain Hertz, D. de Werra
It is shown that tabu search techniques provide almost optimal colorings of graphs having up to 1000 nodes and their efficiency is shown to be significantly superior to the famous simulated annealing.
Journal of Global OptimizationQAPLIB – A Quadratic Assignment Problem Library
655 Citations1997Rainer E. Burkard, Stefan E. Karisch +1 more
A collection of electronically available data instances for the Quadratic Assignment Problem are described, indicating whether or not the problem is solved to optimality and the best known bounds for the problem are supplied.
Annals of Operations ResearchMetaheuristics: A bibliography
643 Citations1996Ibrahim H. Osman, Gilbert Laporte
This bibliography provides a classification of a comprehensive list of 1380 references on the theory and application of metaheuristics that have had widespread successes in attacking a variety of difficult combinatorial optimization problems that arise in many practical areas.
Dépôt institutionnel de l'Université libre de Bruxelles (Université Libre de Bruxelles)Ant system for Job-shop scheduling
618 Citations1994Alberto Colorni, Marco Dorigo +2 more
This paper shows how a new heuristic called ant system, in which the search task is distributed over many simple, loosely interacting agents, can be successfully applied to find good solutions of job-shop scheduling problems.
Artificial IntelligencePartial constraint satisfaction
609 Citations1992Eugene C. Freuder, Richard J. Wallace
A general model of partial constraint satisfaction is proposed and standard backtracking and local consistency techniques for solving constraint satisfaction problems can be adapted to cope with, and take advantage of, the differences between partial and complete constraint satisfaction.
Elsevier eBooksAnt-Q: A Reinforcement Learning approach to the traveling salesman problem
601 Citations1995Luca Maria Gambardella, Marco Dorigo
Ant-Q algorithms were inspired by work on the ant system (AS), a distributed algorithm for combinatorial optimization based on the metaphor of ant colonies and are applied to the solution of symmetric and asymmetric instances of the traveling salesman problem.
ScienceCritical Behavior in the Satisfiability of Random Boolean Expressions
598 Citations1994Scott Kirkpatrick, Bart Selman
Finite-size scaling, a method from statistical physics, can be used to characterize size-dependent effects near the threshold and a relationship can be drawn between thresholds and computational complexity.
Biological CyberneticsCorrelated and uncorrelated fitness landscapes and how to tell the difference
547 Citations1990Ed Weinberger
A framework for the mathematical treatment of multi-peaked “fitness landscapes”, including an explicit mathematical model, is suggested, which might be useful in the “tuning” of combinatorial optimization algorithms, and in modelling in the experimental sciences.
Operations research, computer science. Interface seriesTabu Search and Adaptive Memory Programming — Advances, Applications and Challenges
524 Citations1997Fred Glover
Basic concepts and principles of tabu search are examined, emphasizing those that have sometimes led to applying the label “adaptive memory programming” to this class of methods.
Solving symmetric and asymmetric TSPs by ant colonies
502 Citations2002Luca Maria Gambardella, Marco Dorigo
ACS is presented, a distributed algorithm for the solution of combinatorial optimization problems which was inspired by the observation of real colonies of ants and is able to find good solutions to these problems.
Management ScienceAn Evaluation of Flow Shop Sequencing Heuristics
499 Citations1977David G. Dannenbring
Three previously unreported heuristics are included in the study, one of which turns out to be superior to the other ten heuristic tested and is presented in this paper.
INFORMS Journal on ComputingFast Algorithms for Geometric Traveling Salesman Problems
469 Citations1992Jon Jouis Bentley
Efficient algorithms for computing approximate traveling salesman tours in multidimensional point sets and three local optimizations are described, which are able to solve uniform planar million-city traveling salesman problems to within a few percent of optimal in several midicomputer CPU hours.
INFORMS Journal on ComputingTabu Search Applied to the Quadratic Assignment Problem
461 Citations1990Jadranka Skorin‐Kapov
This paper describes an adaptation of Tabu Search, a recent technique to overcome local optimality, to the Quadratic Assignment Problem (QAP), and suggests that good tabu list sizes increase with dimension of the problem.
Modern Heuristic Search Methods
461 Citations1996V. J. Rayward‐Smith, Ibrahim H. Osman +2 more
This chapter discusses local search strategies for the Vehicle Fleet Mix Problem, the Evolution of Solid Object Designs Using Genetic Algorithms, and more.
European Journal of Operational ResearchA fast tabu search algorithm for the permutation flow-shop problem
440 Citations1996Eugeniusz Nowicki, Czesław Smutnicki
Journal of HeuristicsTesting heuristics: We have it all wrong
426 Citations1995John Hooker
This article argues that a more scientific approach of controlled experimentation, similar to that used in other empirical sciences, avoids or alleviates problems of competitive testing in algorithmic experimentation.
Applying the ANT System to the Vehicle Routing Problem
412 Citations1999B. Bullnheimer, Richard F. Hartl +1 more
A recently proposed metaheuristic, the Ant System, is used to solve the Vehicle Routing Problem in its basic form, i.e., with capacity and distance restrictions, one central depot and identical vehicles.
European Journal of Operational ResearchAn improved annealing scheme for the QAP
406 Citations1990David T. Connolly
The result is a much-improved annealing scheme for this problem which performs well on a range of examples, finding improved solutions for several of the largest problems available in the literature and requiring only modest amounts of computational effort.
Evidence for invariants in local search
368 Citations1997David McAllester, Bart Selman +1 more
This work presents two statistical measures of the local search process that allow one to quickly find the optimal noise settings, and applies these principles to the problem of evaluating new search heuristics, and discovered two promising new strategies.
Optimal speedup of Las Vegas algorithms
360 Citations2002Michael Luby, Alistair Sinclair +1 more
The authors describe a simple universal strategy S/sup univ/, with the property that, for any algorithm A, T(A,S/Sup univ/)=O (l/sub A/log(l/ sub A/)), which is the best performance that can be achieved, up to a constant factor, by any universal strategy.
European Journal of Operational ResearchA new heuristic method for the flow shop sequencing problem
353 Citations1989Marino Widmer, Alain Hertz
Operations Research LettersA new adaptive multi-start technique for combinatorial global optimizations
351 Citations1994Kenneth D. Boese, Andrew B. Kahng +1 more
This work motivates a new adaptive multi-start paradigm for heuristic global optimization, wherein starting points for greedy descent are adaptively derived from the best previously found local minima.
European Journal of Operational ResearchA thermodynamically motivated simulation procedure for combinatorial optimization problems
346 Citations1984Rainer E. Burkard, Franz Rendl
Suboptimal solutions differing 1–2% from the best known solutions are obtained by a simple program in short time by starting this program several times with different starting values all known minimal objective function values were reached.
An Introduction to Variable Neighborhood Search
342 Citations1999Pierre Hansen, Nenad Mladenović
A relatively unexplored approach to the design of heuristics, the guided change of neighborhood in the search process, is examined, which leads to a new metaheuristic, which is widely applicable.
INFORMS journal on computingExact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem
340 Citations1999Vittorio Maniezzo
Two new techniques for solving the Quadratic Assignment Problem are introduced, one of which is a heuristic technique, defined in accordance with the Ant System metaphor, and includes as a distinctive feature the use of a new lower bound at each constructive step.
Computers & Operations ResearchA genetic approach to the quadratic assignment problem
330 Citations1995David M. Tate, Alice E. Smith
This paper presents computational results which show that this genetic algorithm approach to QAP finds solutions competitive with those of the best previously-known heuristics, and argues that genetic algorithms provide a particularly robust method for QAP and its more complex extensions.
Foundations of genetic algorithmsEvolution in Time and Space – The Parallel Genetic Algorithm
326 Citations1991Heinz Mühlenbein
This work investigates the PGA with deceptive problems and the traveling salesman problem, a parallel search with information exchange between the individuals, and shows the correlation for thetraveling salesman problem by a configuration space analysis.
Location ScienceComparison of iterative searches for the quadratic assignment problem
323 Citations1995Éric D. Taillard
This paper compares some of the most efficient heuristic methods for the quadratic assignment problem and shows that no one method is better than all the others.
Large-step Markov chains for the Traveling Salesman Problem
322 Citations2018Olivier Martin
A new class of Markov chain Monte Carlo search procedures are introduced, leading to more powerful optimizat~on methods than simulated annealing, and a new best heuristic is introduced.
National Conference on Artificial IntelligenceThe breakout method for escaping from local minima
322 Citations1993Paul Morris
This paper describes an iterative improvement algorithm, called Breakout, that can escape from local minima, and proves that an idealized (but less efficient) version of the algorithm is complete.
Computers & Operations ResearchThe application of the simulated annealing algorithm to the solution of the n/m/Cmax flowshop problem
311 Citations1990F.A. Ogbu, D.K. Smith
It is found that the proposed simulated annealing algorithm provides better solutions than repeated iterative improvement algorithm, for a fixed total computational time.
Domain-independent extensions to GSAT: solving large structured satisfiability problems
296 Citations1993Bart Selman, Henry Kautz
This work presents three strategies that dramatically improve GSAT's performance on formulas with a high degree of asymmetry, thereby significantly extending the applicability of the GSAT algorithm.
Artificial IntelligenceMacro-operators: A weak method for learning
295 Citations1985Richard E. Korf
The macro technique is a new kind of weak method, a method for learning as opposed to problem solving, and introduces a new type of problem structure called operator decomposability.
Artificial IntelligenceExperimental results on the crossover point in random 3-SAT
292 Citations1996James M. Crawford, Larry D. Auton
This paper reports on the most extensive set of experiments to date on the location and nature of the crossover point in satisfiability problems, finding no evidence of any hard problems in the under-constrained region.
Journal of the Operational Research SocietyHospital Layout as a Quadratic Assignment Problem
276 Citations1977Alwalid N. Elshafei
This paper presents a heuristic procedure to solve the problem of locating hospital departments so as to minimize the total distance travelled by patients, and comments on the computational experience with the heuristic.
Artificial Neural Nets and Genetic AlgorithmsImprovements on the Ant-System: Introducing the MAX-MIN Ant System
259 Citations1998Thomas Stützle, Holger H. Hoos
This paper describes in detail the improvements on Ant system, discusses the addition of local search to MMAS, and reports on the computational results, showing that the system also improves over other variations of Ant system.
Genetic local search for the TSP: new results
237 Citations2002P. Merz, Bernd Freisleben
The previously proposed genetic local search algorithms for the symmetric and asymmetric traveling salesman problem are revisited and potential improvements are identified.
Data Archiving and Networked Services (DANS)Job shop scheduling by local search
232 Citations1992Aarts, E.H.L., Lenstra, J.K. +2 more
DIMACS series in discrete mathematics and theoretical computer scienceGenetic hybrids for the quadratic assignment problem
231 Citations1994Charles Fleurent, Jacques A. Ferland
A new hybrid procedure that combines genetic operators to existing heuristics is proposed to solve the Quadratic Assignment Problem (QAP).
Operations ResearchThe Lessons of Flowshop Scheduling Research
220 Citations1992Richard A. Dudek, S. S. Panwalkar +1 more
The paper comments on NP-completeness, the selection of criteria for optimization, and the lack of applications of this work in industry, and draws some conclusions about the possible future of sequencing research and the lessons that this area's work has to teach the rest of operations research.
Lecture notes in computer scienceGenetic local search algorithms for the traveling salesman problem
220 Citations1991Nico L. J. Ulder, Emile Aarts +3 more
Experimental approaches to Genetic Local Search with 2-Opt neighbourhoods and Lin-Kernighan neighbourhoods are compared with the corresponding classical multi-start Local Search algorithms, as well as with Simulated Annealing and Threshold Accepting.
Annals of Operations ResearchCombining simulated annealing with local search heuristics
217 Citations1996Olivier Martin, Steve W. Otto
A meta-heuristic to embed deterministic local search techniques into simulated annealing so that the chain explores only local optima makes large, global changes, even at low temperatures, thus overcoming large barriers in configuration space.
Operations ResearchNeeded: An Empirical Science of Algorithms
210 Citations1994John Hooker
It is argued that an empirical science of algorithms is a viable alternative to deductive algorithmic science, and some examples of recent work that partially achieves this aim are given.
Parallel Genetic Algorithms
208 Citations1993Ron Shonkwiler
A universal method for parallelizing a Genetic Algorithm referred to as IIP parallel, independent and identical processing, theoretical analysis shows that the technique achieves a speedup using m processors given bymsm−1 where the acceleration factor s is a parameter depending on the details of the GA.
…