Fast local search and guided local search and their application to British Telecom's workforce scheduling problem
Operations Research LettersPublished 1 March 1997
Edward Tsang, Chris Voudouris
Citations137
SJR quartileQ2
SJR score0.44
SNIP0.68
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.
TL;DR
A fast local search (FLS) algorithm which helps to improve the efficiency of hill climbing and a guided local search algorithm which was developed to help local search to escape local optima and distribute search effort are reported.
Abstract
This paper reports a fast local search (FLS) algorithm which helps to improve the efficiency of hill climbing and a guided local search (GLS) algorithm which was developed to help local search to escape local optima and distribute search effort. To illustrate how these algorithms work, this paper describes their application to British Telecom's workforce scheduling problem, which is a hard real life problem. The effectiveness of FLS and GLS are demonstrated by the fact that they both outperform all the methods applied to this problem so far, which include simulated annealing, genetic algorithms and constraint logic programming.
Keywords
Computer ScienceDecision SciencesEngineering
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.
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.
Genetic Algorithms in Search, Optimization and Machine Learning
17,773 Citations1988David E. Goldberg, David Robson
Handbook of Genetic Algorithms
7,308 Citations1991Lawrence Davis
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.
INFORMS Journal on ComputingTabu Search—Part I
4,974 Citations1989Fred Glover
The fundamental principles underlying tabu search as a strategy for combinatorial optimization problems are presented and more advanced considerations are examined, applying the basic ideas to special settings and outlining a dynamic move structure to insure finiteness.
ComputerArtificial neural networks: a tutorial
4,881 Citations1996Abhishek Jain, Jianchang Mao +1 more
The article discusses the motivations behind the development of ANNs and describes the basic biological neuron and the artificial computational model, and outlines network architectures and learning processes, and presents some of the most commonly used ANN models.
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.
Series on software engineering and knowledge engineeringData Structures and Algorithms
2,131 Citations2003
The basis of this book is the material contained in the first six chapters of the earlier work, The Design and Analysis of Computer Algorithms, and has added material on algorithms for external storage and memory management.
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.
Discrete Applied MathematicsSimulated annealing and boltzmann machines: A stochastic approach to combinatorial optimization and neural computing
1,454 Citations1990
Constraint satisfaction in logic programming
1,222 Citations1989Pascal Van Hentenryck
The ideas introduced in "Constraint Satisfaction in Logic Programming " have been used successfully to solve more than a dozen practical problems in operations research and circuit design, including disjunctive scheduling, warehouse location, cutting stock car sequencing, and microcode labeling problems.
Annals of Operations ResearchA user's guide to tabu search
910 Citations1993Fred Glover, Éric D. Taillard +1 more
This presentation demonstrates that a well-tuned implementation of tabu search makes it possible to obtain solutions of high quality for difficult problems, yielding outcomes in some settings that have not been matched by other known techniques.
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.
Kluwer international series in engineering and computer scienceThe Annealing Algorithm
406 Citations1989Ria Otten, L. P. P. P. van Ginneken
The Annealing Algorithm: A Preview is presented, with a focus on the implementation of the selection function, which addresses the challenge of determining the minimum number of iterations for a discrete-time algorithm.
Operations ResearchThe Theory of Search
262 Citations1957B. O. Koopman
This is Part III, concluding the series of three papers on The Theory of Search, where the material was first presented by the author at the fall meeting of the Operations Research Society of America in 1953, where it was treated as a natural extension of his paper, The Optimum distribution of effort.
Medical Entomology and ZoologyMathematical programming: State of the art 1994
148 Citations1994John R. Birge, Katta G. Murty
This book presents sixteen of the tutorial lectures given at the 15th International Symposium on Mathematical Programming, which provide an assessment of the remarkable progress of research in the subject, and indicate some of the problems that will be the focus of future research as the authors approach the beginning of the next century.
OpenGrey (Institut de l'Information Scientifique et Technique)GENET: a connectionist architecture for solving constraint satisfaction problems by iterative improvement
119 Citations1994Andrew Davenport, Edward Tsang +2 more
Although GENET has been designed to be implemented on VLSI hardware, empirical evidence is presented to show that even when simulated on a single processor GENET can outperform existing iterative improvement techniques on hard instances of certain constraint satisfaction problems.
Partial Constraint Satisfaction Problems and Guided Local Search
87 Citations1996Chris Voudouris
The stochastic search method of Guided Local Search (GLS) is examined and the effectiveness of the method is demonstrated on instances of the Radio Link Frequency Assignment Problem (RLFAP), which is a real-world Partial CSP.
Solving constraint satisfaction problems using genetic algorithms
80 Citations2002Á. E. Eiben, Paul-Erik Raué +1 more
The requirements and possibilities of defining so-called heuristic GAs (HGAs), which can be expected to be effective and efficient methods to solve CSPs since they adopt heuristics used in classical CSP solving search techniques are discussed.
Solving constraint satisfaction problems using neural networks
45 Citations1991C. J. Wang, Edward Tsang
Evolutionary ComputationTackling Car Sequencing Problems Using a Generic Genetic Algorithm
44 Citations1995Terry Warwick, Edward Tsang
Promising results are reported in applying a generic genetic algorithm, which is called GAcSP, to tackle both solvable and unsolvable CarSPs, which are a version of the job-shop scheduling problem.
Constraint logic programming for scheduling and planning
36 Citations1995Jonathan M. Lever, Mark Wallace +1 more
Operations ResearchFeature Article—The Process of Search Planning: Current Approaches and Continuing Problems
31 Citations1983Lawrence D. Stone
The purpose of this article is to present an approach to search planning that encompasses both objective and subjective methods and provides for compromises between theoretically optimal plans and operationally feasible ones.
International Joint Conference on Artificial IntelligenceBranch-and-bound and beyond
22 Citations1971Patrick A. V. Hall
The branch-and-bound algorithm is stated in generality, and illustrated by two applications, unidirectional graph search, and reducing a sparse matrix to its minimal band form, which is generalised to multiple partitions, applied to bidirectionalgraph searching for both heuristic and non-heuristic searches, and further extended to graph searches and problem solving with subgoals.
Using a genetic algorithm to tackle the processors configuration problem
16 Citations1994Terry Warwick, Edward Tsang
Preliminary results suggest that the proposed GA provides a useful heuristic strategy to tackling the PCP, the optimisation of irregular multiprocessor network configurations.
Molecular and Cellular ProbesFunction Optimization using Guided Local Search
10 Citations2007Chris Voudouris, Edward Tsang
The potential use of Guided Local Search (GLS) for function optimization is examined, in which the function to be minimized is augmented with a set of penalty terms that enable local search to escape from local minima.