Adaptive memory programming: A unified view of metaheuristics
European Journal of Operational ResearchPublished 1 November 2001
Éric D. Taillard, Mirko Nava, Michel Gendreau, Jean‐Yves Potvin
Citations210
SJR quartileQ1
SJR score2.24
SNIP2.62
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
The paper analyses recent developments of a number of memory-based metaheuristics such as taboo search, scatter search, genetic algorithms and ant colonies and proposes Adaptive Memory Programming (AMP), a unified presentation of methods recently developed for quadratic assignment, vehicle routing and graph colouring problems.
Abstract
The paper analyses recent developments of a number of memory-based metaheuristics such as taboo search (TS), scatter search (SS), genetic algorithms (GA) and ant colonies. It shows that the implementations of these general solving methods are increasingly similar. So, a unified presentation is proposed under the name of adaptive memory programming (AMP). A number of methods recently developed for the quadratic assignment, vehicle routing and graph colouring problems are reviewed and presented under the AMP point of view. AMP presents a number of interesting aspects such as a high parallelization potential and the ability of dealing with real and dynamic applications.
Keywords
Computer Science
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
IEEE Transactions on Evolutionary ComputationAnt colony system: a cooperative learning approach to the traveling salesman problem
7,994 Citations1997Marco Dorigo, Luca Maria Gambardella
The results show that the ACS outperforms other nature-inspired algorithms such as simulated annealing and evolutionary computation, and it is concluded comparing ACS-3-opt, a version of the ACS augmented with a local search procedure, to some of the best performing algorithms for symmetric and asymmetric TSPs.
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.
Computers & Operations ResearchFuture paths for integer programming and links to artificial intelligence
4,050 Citations1986Fred Glover
Four key areas of Integer programming are examined from a framework that links the perspectives of artificial intelligence and operations research, and each has characteristics that appear usefully relevant to developments on the horizon.
Journal of Global OptimizationGreedy Randomized Adaptive Search Procedures
2,709 Citations1995Thomas A. Feo, Maurício G. C. Resende
This paper defines the various components comprising a GRASP and demonstrates, step by step, how to develop such heuristics for combinatorial optimization problems.
Decision SciencesHEURISTICS FOR INTEGER PROGRAMMING USING SURROGATE CONSTRAINTS
1,352 Citations1977Fred Glover
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.
PolyPublie (École Polytechnique de Montréal)A Tabu Search Heuristic for the Vehicle Routing Problem
1,231 Citations1994Michel Gendreau, Alain Hertz +1 more
Annals of Operations ResearchMetastrategy simulated annealing and tabu search algorithms for the vehicle routing problem
1,022 Citations1993Ibrahim H. Osman
Approximate methods based on descent, hybrid simulated annealing/tabu search, and tabu search algorithms are developed and different search strategies are investigated and an estimate for the tabu list size is statistically derived.
Transportation ScienceA Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows
930 Citations1997Éric D. Taillard, Philippe Badeau +3 more
A tabu search heuristic for the vehicle routing problem with soft time windows, where lateness at customer locations is allowed although a penalty is incurred and added to the objective value.
Journal of HeuristicsProbabilistic diversification and intensification in local search for vehicle routing
893 Citations1995Yves Rochat, Éric D. Taillard
A probabilistic technique to diversify, intensify, and parallelize a local search adapted for solving vehicle routing problems and local searches is presented.
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.
Journal of the Operational Research SocietyAnt colonies for the quadratic assignment problem
676 Citations1999L. M. Gambardella, Éeric D. Taillard +1 more
Experimental results show that HAS-QAP and the hybrid genetic algorithm perform best on real world, irregular and structured problems due to their ability to find the structure of good solutions, while HAS–QAP performance is less competitive on random, regular and unstructured problems.
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.
NetworksParallel iterative search methods for vehicle routing problems
593 Citations1993Éric D. Taillard
Two partition methods that speed up iterative search methods applied to vehicle routing problems including a large number of vehicles, based on the arborescence built from the shortest paths from any city to the depot are presented.
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.
Transportation ScienceParallel Tabu Search for Real-Time Vehicle Routing and Dispatching
448 Citations1999Michel Gendreau, François Guertin +2 more
A tabu search heuristic, initially designed for the static version of the problem, has been adapted to the dynamic case and implemented on a parallel platform to increase the computational effort.
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.
INFORMS journal on computingThe Vehicle Routing Problem with Time Windows Part II: Genetic Search
403 Citations1996Jean‐Yves Potvin, Samy Bengio
This paper is the second part of a work on the application of new search techniques for the vehicle routing problem with time windows and describes GENEROUS, the GENEtic ROUting System, which is based on the natural evolution paradigm.
Parallel ComputingEvolution algorithms in combinatorial optimization
397 Citations1988Heinz Mühlenbein, M. Gorges-Schleuter +1 more
A new genetic algorithm which relies on intelligent evolution of individuals is presented, which is inherently parallel and shows a superlinear speedup in multiprocessor systems.
RAIRO - Operations ResearchA heuristic column generation method for the heterogeneous fleet VRP
371 Citations1999Éric D. Taillard
The heuristic column generation method may also solve the fleet size and composition vehicle routing problem and new best known solutions are reported for a set of classical problems.
INFORMS Journal on ComputingParallel Taboo Search Techniques for the Job Shop Scheduling Problem
355 Citations1994Éric D. Taillard
A fast parallel algorithm is given that provides good solutions to very large problems in a very short computation time and identifies a type of problem for which taboo search provides an optimal solution in a polynomial mean time in practice.
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.
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.
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.
Annals of Operations ResearchGenetic and hybrid algorithms for graph coloring
307 Citations1996Charles Fleurent, Jacques A. Ferland
It is illustrated that genetic operators can fulfill long-term strategic functions for a tabu search implementation that is chiefly founded on short-term memory strategies.
Journal of the Operational Research SocietyVehicle Routeing with Multiple Use of Vehicles
222 Citations1996Éric D. Taillard, Gilbert Laporte +1 more
A tabu search heuristic is developed for the vehicle routeing problem with multiple use of vehicles and is shown to produce high quality solutions on a series of test problems.
INFORMS journal on computingThe Vehicle Routing Problem with Time Windows Part I: Tabu Search
219 Citations1996Jean‐Yves Potvin, Tanguy Kervahut +2 more
A tabu search heuristic for the vehicle routing problem with time windows is described, based on specialized local search heuristics that maintain the feasibility of the solution at all time.
INFORMS journal on computingA Reactive Tabu Search Metaheuristic for the Vehicle Routing Problem with Time Windows
203 Citations1997Wen‐Chyuan Chiang, Robert A. Russell
A reactive tabu search metaheuristic for the vehicle routing and scheduling problem with time window constraints is developed and achieves solutions that compare favorably with previously reported results.
Transportation Research Part C Emerging TechnologiesA parallel tabu search heuristic for the vehicle routing problem with time windows
196 Citations1997Philippe Badeau, François Guertin +3 more
In this paper, a parallel tabu search heuristic for solving the vehicle routing problem with time windows is developed and implemented on a network of workstations, and it is shown that parallelization of the original sequential algorithm does not reduce solution quality.
Vehicle Routing with Time Windows using Genetic Algorithms
182 Citations1995Sam R. Thangiah
GIDEON, a genetic algorithm heuristic for solving vehicle routing problems with time windows, consists of a global customer clustering method and a local post-optimization method that obtained 41 new best known solutions.
Transportation ScienceA Network Flow-Based Tabu Search Heuristic for the Vehicle Routing Problem
163 Citations1996Jiefeng Xu, James P. Kelly
A new local search approach based on a network flow model that is used to simultaneously evaluate several customer ejection and insertion moves is developed and incorporated into the procedure to overcome local optimality.
GIDEON: a genetic algorithm system for vehicle routing with time windows
133 Citations2002Sam R. Thangiah, Kendall E. Nygard +1 more
GIDEON, a genetic algorithm system to heuristically solve the vehicle routing problem with time windows, consists of two distinct modules: a global clustering module that assigns customers to vehicles by a process called genetic sectoring and a local route optimization module (SWITCH-OPT).
Transportation ScienceA Tabu Search Heuristic for the Vehicle Routing Problem with Backhauls and Time Windows
117 Citations1997Christophe Duhamel, Jean‐Yves Potvin +1 more
A tabu search heuristic is described for the vehicle routing problem with backhauls and time windows where linehauls must precede bachhauls on each route and the time of beginning of service at each customer location must occur within a particular time interval.
Management ScienceThe Facilities Layout Problem in Perspective
108 Citations1966Thomas E. Vollmann, Elwood S. Buffa
Each layout problem is made unique by its particular assumptions, constraints, limitations, and the intrinsic activity of the components; a guide to establishing this uniqueness and to selecting appropriate tool3 for analysis is presented.
Computers & Operations ResearchAn adaptive memory heuristic for a class of vehicle routing problems with minmax objective
102 Citations1997Bruce Golden, Gilbert Laporte +1 more
A tabu search based adaptive memory procedure of instances indicate that the method produces very good solutions within reasonable computing times.
A scatter search based approach for the quadratic assignment problem
96 Citations2002Van‐Dat Cung, Thierry Mautor +2 more
The authors propose a scatter search approach to the QAP problem and the basic method is extended with intensification and diversification stages and they present a procedure to generate good scattered initial solutions.
Journal of HeuristicsEmbedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs
91 Citations1995Daniel Costa, Alain Hertz +1 more
An evolutionary procedure for solving general optimization problems that combines efficiently the mechanism of a simple descent method and of genetic algorithms is presented.
INFORMS Journal on ComputingSome Convergence Results for Probabilistic Tabu Search
86 Citations1992Ulrich Faigle, Walter Kern
It turns out that several Tabu Search ideas can be subjected to mathematical analyses similar to those applied to Simulated Annealing, making it possible to establish corresponding convergence properties based on a broader foundation.
American Journal of Mathematical and Management SciencesAlgorithms for the Vehicle Routing Problems with Time Deadlines
78 Citations1993Sam R. Thangiah, Ibrahim H. Osman +2 more
Three heuristics to solve the VRPTD: deadline sweep, push-forward insertion and genetic sectoring are developed and improved using a local post-optimization procedure.
Annals of Operations ResearchDiversification strategies in tabu search algorithms for the maximum clique problem
56 Citations1996Patrick Soriano, Michel Gendreau
The implementation of various diversification strategies in several tabu search heuristics developed for the maximum clique problem are discussed and computers are compared to assess the impact of these techniques on solution quality and running time.
Journal of HeuristicsA Memory Adaptive Reasoning Technique for Solving the Capacitated Minimum Spanning Tree Problem
49 Citations1999Raymond A. Patterson, Hasan Pirkul +1 more
This paper augments the problem formulation with additional non-redundant constraints via use of adaptive memory, to improve upon the performance of an elementary heuristic (the Esau-Williams heuristic), and concludes that the generalized procedure performs on par with the best of these approaches in terms of solution quality.
Discrete Applied MathematicsOn the quality of local search for the quadratic assignment problem
37 Citations1998Éric Angel, Vassilis Zissimopoulos
An upper bound for the quality of solutions obtained with deepest local search is given for the Quadratic Assignment Problem, and other recently established results on the traveling salesman problem, the graph bipartitioning problem and the maximum independent set problem can be deduced as particular cases.