Variable neighborhood search
Computers & Operations ResearchPublished 1 November 1997
Nenad Mladenović, Pierre Hansen
Citations4,147
SJR quartileQ1
SJR score1.60
SNIP2.02
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
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.
Abstract
Systematic change of neighborhood within a local search algorithm yields a simple and effective metaheuristic for combinatorial optimization. We present a basic scheme for this purpose which can be implemented easily using any local search algorithm as a subroutine. Its effectiveness is illustrated by improvements in the GENIUS algorithm for the traveling salesman problem [1], without and with backhauls [2].
Keywords
Computer ScienceEngineering
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.
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Some methods for classification and analysis of multivariate observations
22,787 Citations1967James B. MacQueen
Annals of EugenicsTHE USE OF MULTIPLE MEASUREMENTS IN TAXONOMIC PROBLEMS
14,727 Citations1936Ronald Aylmer Fisher
Medical Entomology and ZoologyGenetic Programming: On the Programming of Computers by Means of Natural Selection
13,257 Citations1992John R. Koza
This book discusses the evolution of architecture, primitive functions, terminals, sufficiency, and closure, and the role of representation and the lens effect in genetic programming.
Journal of CyberneticsA Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters
6,548 Citations1973J. C. Dunn
Two fuzzy versions of the k-means optimal, least squared error partitioning problem are formulated for finite subsets X of a general inner product space; in both cases, the extremizing solutions are shown to be fixed points of a certain operator T on the class of fuzzy, k-partitions of X, and simple iteration of T provides an algorithm which has the descent property relative to the least squarederror criterion function.
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.
The Computer JournalA Rapidly Convergent Descent Method for Minimization
4,571 Citations1963R. Fletcher, M. J. D. Powell
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.
Journal of the American Chemical SocietyCharacterization of molecular branching
3,547 Citations1975Milan Randić
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.
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.
Kluwer Academic Publishers eBooksGreedy Randomized Adaptive Search Procedures
2,325 Citations2006Maurício G. C. Resende, Celso C. Ribeiro
Princeton University Press eBooksLocal Search in Combinatorial Optimization
2,059 Citations2003Emile Aarts, Jan Karel Lenstra
Journal of the Operational Research SocietyOR-Library: Distributing Test Problems by Electronic Mail
1,862 Citations1990J. E. Beasley
A system (OR-Library) that distributes test problems by electronic mail (e-mail) that has available test problems drawn from a number of different areas of operational research.
European Journal of Operational ResearchResource-constrained project scheduling: Notation, classification, models, and methods
1,482 Citations1999Peter Brucker, Andreas Drexl +3 more
A classification scheme is provided, i.e. a description of the resource environment, the activity characteristics, and the objective function, respectively, which is compatible with machine scheduling and which allows to classify the most important models dealt with so far, and a unifying notation is proposed.
Journal of Computer and System SciencesNP-complete scheduling problems
1,429 Citations1975Jeffrey D. Ullman
It is shown that the problem of finding an optimal schedule for a set of jobs is NP-complete even in the following two restricted cases, tantamount to showing that the scheduling problems mentioned are intractable.
Lecture notes in computer scienceUsing Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems
1,274 Citations1998Paul Shaw
This work uses a local search method that is analogous to the shuffling technique of job-shop scheduling, and so meshes well with constraint programming technology, to solve vehicle routing problems.
Operations ResearchA Dual-Based Procedure for Uncapacitated Facility Location
910 Citations1978Donald Erlenkotter
This approach has obtained and verified optimal solutions to all the Kuehn-Hamburger location problems in well under 0.1 seconds each on an IBM 360/91 computer, with no branching required.
The Steiner Tree Problem
860 Citations1992Frank K. Hwang, Dana Richards +1 more
Operations ResearchHeuristic Methods for Estimating the Generalized Vertex Median of a Weighted Graph
795 Citations1968Michael B. Teitz, Polly Bart
This paper investigates alternatives of choice of location of p sources of unconstrained capacity from among n destinations having fixed demands and located at nodes of a network and proposes a method that seems to perform well in comparison with others found in the literature.
Mathematical ProgrammingSolving mixed integer nonlinear programs by outer approximation
668 Citations1994R. Fletcher, Sven Leyffer
An alternative approach is considered to the difficulties caused by infeasibility in outer approximation, in which exact penalty functions are used to solve the NLP subproblems.
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.
IEEE Transactions on Pattern Analysis and Machine IntelligenceEfficient Implementation of the Fuzzy c-Means Clustering Algorithms
622 Citations1986Robert Cannon, Jitendra V. Dave +1 more
An approximate fuzzy c-means (AFCM) implementation based upon replacing the necessary ``exact'' variates in the FCM equation with integer-valued or real-valued estimates enables AFCM to exploit a lookup table approach for computing Euclidean distances and for exponentiation.
Mathematical ProgrammingCluster analysis and mathematical programming
617 Citations1997Pierre Hansen, Brigitte Jaumard
Algorithms for hierarchical, partitioning, sequential, and additive clustering are studied, and emphasis is on solution methods, i.e., dynamic programming, graph theoretical algorithms, branch-and-bound, cutting planes, column generation and heuristics.
International series in management science/operations research/International series in operations research & management scienceHeuristic Algorithms for the Resource-Constrained Project Scheduling Problem: Classification and Computational Analysis
507 Citations1999Rainer Kolisch, Sönke Hartmann
The objective of the RCPSP is to find precedence and resource feasible completion times for all activities such that the makespan of the project is minimized.
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.
Management ScienceCapacitated Lot Sizing with Setup Times
456 Citations1989William W. Trigeiro, L. Joseph Thomas +1 more
Location ScienceVariable neighborhood search for the p-median
388 Citations1997Pierre Hansen, Nenad Mladenović
Lecture notes in computer scienceLocal search in combinatorial optimization
359 Citations1995Yves Crama, Antoon Kolen +1 more
Computational bounds for local search in combinatorial local search algorithms for Combinatorial problems local searchgorithms for solving the combinatoric a dual local search framework for combinatorials the max-min ant system and local search for combinatorsial a framework for local combinatoria optimization problems localSearch in combinatorship optimization radarx heuristics and localsearch paginas.
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.
ComputingAlgorithms for the maximum satisfiability problem
339 Citations1990Pierre Hansen, Brigitte Jaumard
Two recent local search algorithmic schemes are considered, the Simulated Annealing method of Kirkpatrick, Gelatt and Vecchi and the Steepest Ascent Mildest Descent method, and adapt them to the Maximum Satisfiability problem and are shown empirically to be more efficient than the heuristics previously proposed in the literature.
Management ScienceA Nonlinear Programming Technique for the Optimization of Continuous Processing Systems
333 Citations1961R. E. Griffith, Richard A. D. Stewart
A numerical example, a model construction example, and a description of a particular existing computer system are included in order to clarify the mode of operation of the method.
Discrete MathematicsOn conjectures of Graffiti
290 Citations1988Siemion Fajtlowicz
CNCL deletes those conjectures of the second and third type in which one of the invariants on the left is always smaller than an invariant on the right that may undoubtedly remove a number of interesting conjectures.
SIAM Journal on OptimizationNumerical Experience with Lower Bounds for MIQP Branch-And-Bound
211 Citations1998R. Fletcher, Sven Leyffer
It is shown how lower bounds can be computed efficiently during the branch-and-bound process to reduce the number of quadratic programming (QP) problems that have to be solved.
Australian Journal of BotanyMultidimensional group analysis
191 Citations1966RC Jancey
A quantitative taxonomic method is described, based on the calculation of distance functions in multidimensional space, and provides objective discrimination and characterization of taxa.
INFOR Information Systems and Operational ResearchA Fast Algorithm For The Greedy Interchange For Large-Scale Clustering And Median Location Problems
185 Citations1983R.A. Whitaker
A fast algorithm is described for implementing the greedy interchange heuristic for lise in solving large scale clustering and uncapacitated median location problems and an additional heuristic is proposed for solving these set partitioning problems based on an efficient procedure for achieving the interchange.
European Journal of Operational ResearchCrew pairing at Air France
180 Citations1997Guy Desaulniers, Jacques Desrosiers +5 more
This work presents the application and implementation of an optimal approach for a large airline carrier using a branch-and-bound algorithm based on an extension of the Dantzig-Wolfe decomposition principle and chooses a subproblem network representation where the duties rather than the legs are on the arcs.
Lecture notes in computer scienceA Hybrid Tabu Search Algorithm for the Nurse Rostering Problem
172 Citations1999Edmund Burke, Patrick De Causmaecker +1 more
The algorithms presented in this paper are a commercial nurse rostering product developed for the Belgian hospital market, entitled Plane, which combines constraint programming and linear programming techniques to deal with the over constrained schedules.
Journal of Parallel and Distributed ComputingEfficient Scheduling of Arbitrary Task Graphs to Multiprocessors Using a Parallel Genetic Algorithm
161 Citations1997Yu‐Kwong Kwok, Ishfaq Ahmad
This paper proposes a novel GA-based algorithm with an objective to simultaneously meet the goals of high performance, scalability, and fast running time and outperforms both heuristics while taking considerably less running time.
Computers & Operations ResearchIntensification and diversification with elite tabu search solutions for the linear ordering problem
159 Citations1999Manuel Laguna, Rafael Martı́ +1 more
The goal of this paper is to develop an efficient heuristic procedure for the linear ordering problem (LOP), and to experiment with the use of specialized strategies for search intensification and diversification, within the context of the search methodology that is chosen to apply.
European Journal of Operational ResearchA note on solving large p-median problems
155 Citations1985J. E. Beasley
It is shown that it is possible to enhance a tree search algorithm for the p -median problem to solve (optimally) problems having up to 900 vertices using the Cray-1S computer.
NetworksWeighted <i>k</i>‐cardinality trees: Complexity and polyhedral structure
113 Citations1994Matteo Fischetti, Horst W. Hamacher +2 more
An integer programming formulation of k-CARD TREE and an efficient exact separation routine for a set of generalized subtour elimination constraints are given and the polyhedral structure of the convex hull of the integer solutions is studied.
Lecture notes in computer scienceA view of local search in constraint programming
92 Citations1996Gilles Pesant, Michel Gendreau
A novel way of looking at local search algorithms for combinatorial optimization problems which better suits constraint programming by performing branch- and-bound search at their core is proposed and a framework described yields a more efficient local search and opens the door to more elaborate neighborhoods.
European Journal of Operational ResearchCapacitated lot-sizing and scheduling by Lagrangean relaxation
85 Citations1992Moustapha Diaby, Harish C. Bahl +2 more
SUPSI ARISAdaptive memories for the Quadratic Assignment Problems
85 Citations1997Éric D. Taillard, Luca Maria Gambardella
The paper proposes, compares and analyses different memory- based meta-heuristics for the quadratic assignment problem (QAP), including FANT and GDH, which are new while two others are among the best for structured QAP instances.
DIMACS series in discrete mathematics and theoretical computer scienceApproximate solution of weighted MAX-SAT problems using GRASP
81 Citations1997Maurício G. C. Resende, Leonidas Pitsoulis +1 more
A greedy randomized adaptive search procedure (GRASP) for computing approximate solutions of weighted MAX-SAT problems and computational experience indicates the suitability of GRASP for this class of problems.
Les Cahiers du GERADImprovements and Comparison of Heuristics for solving the Multisource Weber Problem
64 Citations1997Jack Brimberg, Pierre Hansen +2 more
Parallel ComputingMultiprocessor scheduling in a genetic paradigm
64 Citations1996Imtiaz Ahmad, M.K. Dhodhi
A technique based on the problem-space genetic algorithm (PSGA) for the static scheduling of directed acyclic graphs onto homogeneous multiprocessor systems to reduce the response-time is presented.
Annals of Operations ResearchDynamic tabu search strategies for the traveling purchaser problem
60 Citations1996Stefan Voß
Two dynamic strategies, the reverse elimination method and the cancellation sequence method are investigated, which incorporate the incorporation of strategic oscillation as well as a combination of these methods with respect to the traveling purchaser problem.
IEEE Journal on Selected Areas in CommunicationsA method of a spread-spectrum radar polyphase code design
57 Citations1990M.L. Dukić, Z. Dobrosavljevic
The main features of the synthesized code are the absence of sidelobes in the compressed pulse and its tolerance of precompression bandlimiting limitations.
Handbooks in operations research and management scienceChapter 7 Location on networks
49 Citations1995Martine Labbé, Dominique Peeters +1 more
Lecture notes in computer scienceOptimal cutwidths and bisection widths of 2- and 3-dimensional meshes
36 Citations1995Andrea Roli, Ondřej Sýkora +1 more
The exact cyclic cutwidth of 2-dimensional toroidal meshes is shown, and upper bounds for cutwidths and bisection widths of many dimensional meshes are given.
Heuristics for the K-Cardinality Tree and Subgraph Problems
30 Citations1996Matthias Ehrgott, Horst W. Hamacher +2 more
This paper considers the problem of finding in a given graph a minimal weight subtree of connected subgraph, which has a given number of edges, and presents different heuristic approaches based on spanning tree and shortest path methods and on an exact algorithm solving the problem in polynomial time if the underlying graph is a tree.
Journal of Chemical Information and Computer SciencesSome Bounds for the Connectivity Index of a Chemical Graph
27 Citations1998Oswaldo Araujo, José Antonio de la Peña
Some graph theoretic constructions are used to find bounds for 1χ(G) which depend only on the number of vertices, the ramification index, and the cyclomatic number of the graph G.