Meta-Heuristics

We present two tabu search algorithms for the resource-constrained project scheduling problem. Given are n activities which have to be processed without preemptions. During the processing period of an activity constant amounts of renewable resources are needed where the available capacity of each resource type is limited. Furthermore, finish-start precedence relations between the activities are given. The objective is to determine a schedule with minimal makespan. The first tabu search approach relies on elimination of critical arcs and list-scheduling techniques. The second neighborhood is based on schedule schemes, where neighbors are generated by placing activities in parallel or deleting a parallelity relation. Furthermore, a column-generation approach for a linear programming-based lower bound is presented and computational results are reported.

The objective of this paper is to describe a tabu search metaheuristic for the vehicle routing problem with time windows, and to compare it with some of the best known algorithms for the same problem developed by other authors. From this comparison it can be concluded that the present algorithm performs rather well, outperforming the latter algorithms in several test problems. Another aim of this paper is to show the enormous influence on the results of the type of objective function used, in spite of the travelling time between customers being numerically equal to the distance.

In this paper we describe the implementation of two Tabu search based algorithms for the Crew Scheduling Problem (CSP). The problem is a standard CSP, for an urban transport problem, formulated as the minimal number of duties necessary to cover a predefined timetable under contractual rules which excludes the possibility of resorting to extra-time. The initial solution is obtained with a run-cutting algorithm. Two algorithms are proposed to improve that initial solution. In the first algorithm the run-cutting procedure is applied again to a subset of the problem in a Tabu search framework guided by a strategic oscillation procedure. The second algorithm uses block partition and matching algorithms embedded in a Tabu subgraph ejection chain to explore the neighborhood. Computational results are presented showing the superior performance of the latter algorithm for the case study.

An algorithm called Enhanced Continuous Tabu Search ECTS is proposed for the global optimization of multiminima functions. It results from an adaptation of combinatorial Tabu Search which aims to follow, as close as possible, Glover’s basic approach. In order to cover a wide domain of possible solutions, our algorithm first performs diversification: it locates the most promising areas, by fitting the size of the neighborhood structure to the objective function and its definition domain. When the most promising areas are located, the algorithm continues the search by intensification within one promising area of the solution space. The efficiency of ECTS is thoroughly tested by using a set of benchmark multimodal functions, of which global and local minima are known. ECTS is compared to other published versions of continuous Tabu Search and to some alternative algorithms like Simulated Annealing.

Constraint Programming has proved to be useful for solving many combinatorial problems. In particular, it provides a language allowing to easily model complex problems, and to describe a way to solve them. However, it has seldom been used to solve Vehicle Routing Problems (VRP). Indeed, traditional Constraint Programming systems explore the search space in a depth-first fashion. On the other hand, local search methods have proved to be efficient for solving VRP. In this article, a constraint programming model for the VRP is described, along with a method allowing to perform local non-monotonic search within a Constraint Programming framework. This framework has been used to implement Tabu Search meta-heuristics. The implementation choices are described, as well as the results of experiments performed on problems from the literature.

In this paper, a generic tabu search is presented for three coloring problems: graph coloring, T-colorings and set T-colorings. This algorithm integrates important features such as greedy initialization, solution re-generation, dynamic tabu tenure, incremental evaluation of solutions and constraint handling techniques. Empirical comparisons show that this algorithm approaches the best coloring algorithms and outperforms some hybrid algorithms on a wide range of benchmarks. Experiments on large random instances of T-colorings and set T-colorings show encouraging results.

A recently developed tabu search approach for solving binary quadratic programs has been shown to be highly effective in finding optimal solutions to known difficult problems. Organized chiefly to employ strategic oscillation, based on critical event memory, the method has not only quickly found optimal solutions in those cases where they are known, but has also found high quality (perhaps optimal) solutions to new test problems that are larger than previously reported in the literature.This paper extends our previous work by introducing a simple but effective scheme for accelerating the evaluation of candidates’ moves (for transforming one solution into another), and for updating associated problem information. Accompanying this we also introduce methods for generating advanced starting solutions and additional trial solutions at critical events. Our preliminary computational experiments on a Pentium 200 PC platform show that the method finds optimal solutions (where they are known) in two to six seconds of computation time. We also include tests for problems containing 1000 variables, which are substantially larger than any that appear in the literature prior to this work. Our enhanced approach obtains high quality solutions to these problems within one to four minutes of computation time.

In this paper we study the selection of actuator locations for a constrained multi-frequency active noise control optimization problem. Data regarding the effectiveness of each actuator is gathered from the fuselage of a DC-9 aircraft. A constraint is placed limiting the force that can be applied to each actuator. Tabu search is used to select locations for the actuators and a quadratically constrained complex least squares problem must be solved to determine the control forces for the selected actuators.

We are given a set of rectangular small pieces which may be rotated by 90°, and an unlimited number of identical rectangular large stock pieces. We consider the problem of determining the guillotine-cuttable patterns that provide all the pieces, such that the total number of required stock pieces is minimized. We show how some classical greedy algorithms given in the literature for the case where no rotation is allowed can be adapted to our problem; in addition, an original heuristic algorithm is presented. We then introduce a tabu search approach to the problem, and analyze its average performance through extensive computational testing.

Candidate list strategies play an important role in designing efficient local search heuristics for combinatorial optimization problems. We look at various neighborhood exploration and exploitation strategies for 0/1 MIP problems using a pivoting neighborhood and simple tabu search. This neighborhood is quite costly to evaluate, particularly for large problems. Special attention is also given to the tableau based neighborhood structure. General guidelines based on computational experience are reported.

The problem we deal with is the optimization of mail collecting at several customer sites that are scattered around an urban area. It involves the design of a set of minimum cost routes, originating and terminating at a central depot, for a fleet of vehicles that service those customer sites with known demands. We develop a Tabu Search approach where at each iteration the best move is selected among a large variety of possible moves. This new version of the metaheuristic Tabu leads us to determine a good vehicle fleet mix (cheapest cost incorporating routing and fixed vehicle costs) without violating constraints such as time restrictions and capacity.

The paper deals with a flow line scheduling problem which is an extension of two classic problems of scheduling theory, namely the flow shop and parallel shop, and can be briefly described as follows. There is a set of jobs and a set of processing centers each of which has a set of parallel identical machines. A job consists of a sequence of operations processed at successive centers, and all jobs pass through centers in the same order. At the center, a job can be processed on any machine. The transport time of jobs between centers is job dependant. We want to find a schedule that minimizes the makespan, one of the most frequently used scheduling criteria.To show the problem, its properties, and algorithm, we consider chiefly the case with two centers. To solve the problem stated we propose a fast and easily implementable approximation algorithm based on a tabu search technique with a specific, reduced neighborhood, original search accelerator, and the technique of back jumps on the search trajectory. The neighborhood is constructed using notions of a critical path in a graph and the elimination properties of blocks of jobs. The proposed neighborhood plays an important role in proper guiding the search into the most promising regions of the solution space as well as in the reduction of the costs of the single neighborhood search. The search accelerator, designed with the help of some theoretical properties of the graph, improves additionally and significantly the speed of the algorithm by avoiding superfluous calculations. Candidate list strategy and back jumps on the search trajectory ensure proper balance between the search intensification and diversification.Results of numerical tests (up to 300 jobs) are also provided to show exhaustive numerical characteristics of the proposed algorithm. They confirm its excellent numerical behavior. The proposed approach can be extended to cover a broad class of flexible flow line scheduling problems. Known industrial applications refer among others to chemical branches, polymer and petroleum industries, electronic industry, FMS.

The frequency assignment problem is an important NP-hard problem which involves the assignment of frequencies to a set of transmitters in such a way that certain constraints, defining the frequency separation needed between pairs of transmitters, are satisfied. In this paper we show that good assignments can be found if assignment algorithms assign a subset of the constraints initially. This partial assignment is then used as a starting assignment for the solution of the whole problem. Good results can be found if the subset chosen for the initial assignment corresponds to the subset that produces good lower bounds.

Some real world situations such as cargo loading and investment choice can be modeled by the knapsack problem. When more than one objective is considered, the problem becomes a multiobjective knapsack problem. In this paper, we develop a hybrid heuristic based on the combination of a multiobjective tabu search algorithm and a multiobjective genetic algorithm, and show, through experimentations, the efficiency of the proposed method.

This paper considers a cyclic scheduling problem, which especially is applicable in the area of public transport. The problem is the so-called Irregular Polygon Scheduling Problem with the objective to maximize the distance between the nearest vertices of two different polygons. We give a mixed integer LP-formulation of this NP-hard problem, derive some bounds and present a hybrid meta-heuristic algorithm for solving the problem. The main idea is to combine a Tabu Search with a Genetic Algorithm component. Computational experience, based on comparative results obtained from CPLEX, shows the efficiency of the hybridization approach.

Genetic Algorithms (GA) like other modern metaheuristics claim to be general problem solvers. Though GA have been applied successfully to a wide range of different combinatorial optimization problems, the need for careful and time-consuming tuning of GA constitutes a major drawback as a general problem solver. In this report we introduce the concept of Adaptive Genetic Algorithms (AGA) as a solution to this calibration problem, which dynamically performs an on-line autoconfiguration of the GA-parameters. To demonstrate the superior performance of AGA vs. GA in terms of solution quality, robustness and computational effort, we present computational results for three different combinatorial optimization problems. Our benchmark comprises two standard benchmark problems (Quadratic Assignment Problem and Period Vehicle Routing Problem) and one real-world problem arising in airline scheduling.

It has often been assumed that ordering problems form a special class of problems amenable to a largely uniform treatment. Since successful ordering Genetic Algorithms (GAs) have been defined for optimization of some ordering problems, it has become customary to assume that ordering problems are well solved by ordering GAs fitted with “standard” operators.The success of the standard ordering GAs on some problems led to an indirect approach of solving numerous combinatorial problems as follows: define a decoder of a permutation of items that builds a solution to the original problem, and use the ordering GA to find a permutation that decodes into a good solution of the original problem. Such lavish applications of the standard ordering GA have become pervasive to many types of problems.In this paper, we construct a very simple way of transforming a function defined over bitstrings to a function defined over permutations, and vice versa. As a result, there is a simple way of transforming any function to an “ordering problem”.The implication of this is that should there indeed be a standard way of efficiently solving ordering problems, then the standard ordering GA would be capable of efficiently optimizing all functions. That, however, would contradict the No Free Lunch Theorem for search. Consequently, many ordering problems are not amenable to solution by standard ordering GAs, i.e., the lavish use of the standard ordering GA is unwarranted.We support this claim by experiments in which we attempt to optimize the easy 32-bit ONE-MAX function with an ordering GA, using the simple transformation between permutations and bitstrings. As expected, standard ordering crossover operators perform extremely poorly on that simple function. In order to illustrate how much an ordering crossover for ONE-MAX would have to differ from the standard ones, we then construct an “exotic” tailored crossover that performs well.

We perform a statistical analysis of the structure of the search space of some planar, euclidian instances of the traveling salesman problem. We want to depict this structure from the point of view of iterated local search algorithms. The objective is two-fold: understanding the experimentally known good performance of metaheuristics on the TSP and other combinatorial optimization problems; designing new techniques to search the space more efficiently. This work actually led us to design a hybrid genetic algorithm that competes rather well with other local search heuristics for the TSP, notably Jünger et al.’s version of ILK. This work also opens promising horizons to the study of other combinatorial optimization problems such as the quadratic assignment problem.

We are interested on defining a general evolutionary algorithm that repairs to solve Constraint Satisfaction Problems and which takes into account both advantages of the systematic and traditional methods and of a characteristics of the CSP. We use the knowledge about properties of the constraint network to define a fitness function, and three operators arc-mutation, arc-crossover and constraint dynamic adaptive crossover. The number of constraint checks has also taken into consideration for designing the operators. The algorithm has been tested by running experiments on randomly generated 3-coloring graphs. The results suggest that the technique may be successfully applied to solve CSP.

In this paper we use a recently proposed metaheuristic, the Ant System, to solve the Vehicle Routing Problem in its basic form, i.e., with capacity and distance restrictions, one central depot and identical vehicles. A “hybrid” Ant System algorithm is first presented and then improved using problem-specific information (savings, capacity utilization). Experiments on various aspects of the algorithm and computational results for fourteen benchmark problems are reported and compared to those of other metaheuristic approaches such as Tabu Search, Simulated Annealing and Neural Networks.

Ant colony methods have recently attracted attention for their application to several types of optimization problems, especially those with a ”graph related formulation”. Like other heuristics the ant system was also inspired by the adaptation of biological processes. However, first results have not been very promising for further research on that specific branch of a much broader field of science, that we will draw attention to in this paper, the intelligent agent systems. Besides the experience with ant systems intelligent agent systems may provide a useful paradigm for search processes designed to solve complex problems. These systems are particularly relevant for parallel processing applications and also offer useful strategies for sequential heuristic search. Respective methods can be interpreted as a set of specific formulas (to monitor ”ant traces”) that embody components of strategic principles being fundamental to adaptive memory programming (AMP) processes, as notably represented by tabu search.From a conceptual view we show that the more general framework of intelligent agents, which does not restrict its operation to the limited perspectives embodied in ant colony methods, may provide improved efficiency. Specifically, we examine the use of agents that are more heterogeneous characterized by mechanisms of communication between the agents which are more variable and dynamic. Furthermore, these intelligent agents make fully use of adaptive memory ideas from AMP. The conceptual idea of our AMP system model is exemplified on a classical combinatorial optimization problem, the traveling salesman problem.

In this paper we present an extension of the $$\mathcal{M}\mathcal{A}\mathcal{X} - \mathcal{M}\mathcal{I}\mathcal{N}$$ Ant System and apply it to Traveling Salesman Problems and Quadratic Assignment Problems. The extension involves the use of a modified choice rule and a hybrid scheme allowing ants to improve their solution by local search. The computational results show that this algorithm can be used to efficiently find near-optimal solutions to hard combinatorial optimization problems and that it is one of the best methods for the solution of structured quadratic assignment problems.

We present a first version of a hybrid metaheuristic that combines a cooperative multi-thread parallel tabu search procedure and a genetic search engine. The two algorithms evolve independently while systematically and asynchronously exchanging solutions. The method appears to be the first to propose a cooperation scheme where the initial population of the genetic algorithm is an elite set of solutions obtained by the parallel metaheuristic, while the best individuals generated during the genetic search enrich the pool of solutions available to all tabu search threads. Experimentation with instances of a multicommodity, capacitated, fixed cost network design formulation leads to an initial assessment of the performances of the method.

This paper presents a parallel implementation of a tabu search algorithm based on adaptive parallelism. Adaptive parallelism demonstrates that massively parallel computing using a hundred of heterogeneous machines is feasible to solve large optimization problems. The parallel tabu search algorithm includes different tabu list sizes and new intensification/diversification mechanisms. Encouraging results have been obtained in solving the quadratic assignment problem. We have improved the best known solutions for some large real-world problems.

We describe a fast sequential tabu search algorithm for the job shop scheduling problem. The algorithm uses an efficient way to recompute the path lengths in the graph representation after a step to a neighbouring solution. For a parallel algorithm, that consists of independent runs of the sequential algorithm, we give a probabilistic analysis of the possible speed-up.

Parallel and distributed computer systems are increasingly used to find good solutions to difficult combinatorial optimization problems. An interesting and often used approach consists of executing concurrently different search methods that exchange information gathered in previously explored regions of the solution space. Cooperation among sequential programs strongly affects how the solution space is explored and it is hoped that it improves the efficiency of the search. A formal representation of these cooperative algorithms based on a discrete-time dynamical system model may be used to describe how the search behavior of cooperative programs depends on systems of complex and correlated interactions. We define systemic cooperation as the search behavior for programs interacting within the same system of correlated interactions, and show experimentally the importance of the phenomenon and its independence of specific search design parameters.

The Generalized Traveling Salesman Problem consists of determining a shortest tour passing through each of several clusters of vertices. A version of this problem is examined where the distance matrix is symmetric and where exactly one vertex is visited in each cluster. A Hopfield-Tank neural network model is developed for solving this problem. Numerical results are presented for problems with up to 50 vertices and 10 clusters with either Euclidean or randomly generated distance matrices. A comparison with a recent heuristic shows that the neural network is competitive with respect to solution quality. However, it is computationally more expensive and is restricted to relatively small problems as it often fails to converge to feasible solutions when the search space of possible configurations is too large.

Cybernetic optimization by simulated annealing (COSA) is a method of parallel processing for solving discrete optimization problems. This paper extends the theory of COSA to the continuous domain. This is done by applying the concept of probabilistic feedback control to the generation of candidate solutions in continuous variable problems. Three general principles of candidate generation are presented leading to the formulation of the candidate generationcriterion and its theoretical implications. A practical method of generating candidate solutions is also presented in which the generation of candidate solutions is achieved by making the magnitude of the expected step size to candidate solutions functionally dependent on the proximity of the parallel processors in the solution space. Experimental results show that this method of generating candidate solutions accelerates the convergence of the parallel processors to the global optimum.

The Progressive Party Problem (PPP) is a complex, constrained combinatorial optimization problem. The goal of the problem consists of finding assignments of resources to variables for a given number of time periods while satisfying a set of multiple constraints. So far, two quite different approaches have been tried to solve the problem: Integer Linear Programming and Constraint Programming. All attempts with Integer Linear Programming failed, while Constraint Programming obtained better results. In this work, we present a third approach based on Local Search. We show that this approach gives better results than the previous ones and constitutes a very effective alternative to solve the PPP. We investigate different techniques for solving the problem, in particular issues related to search space, cost function and neighborhood functions.

In this paper we examine a relatively unexplored approach to the design of heuristics, the guided change of neighborhood in the search process. Using systematically this idea and very little more, i.e., only a local search routine, leads to a new metaheuristic, which is widely applicable. We call this approach Variable Neighborhood Search (VNS).

A variable depth search procedure (abbreviated as VDS) is a generalization of the local search method, which was first successfully applied by Lin and Kernighan to the traveling salesman problem and the graph partitioning problem. The main idea is to adaptively change the size of a neighborhood so that it can effectively traverse a larger search space while keeping the amount of computational time reasonable. In this paper, we propose a heuristic algorithm based on VDS for the generalized assignment problem, which is one of the representative combinatorial optimization problems known to be NP-hard. To the authors’ knowledge, most of the previously proposed algorithms (with some exceptions) conduct the search within the feasible region; however, there are instances for which the search within the feasible region is not advantageous because the feasible region is very small or is combinatorially complicated to search. Therefore, we allow our algorithm to search within the infeasible region as well. We also incorporate an adaptive use of two different neighborhoods, shift and swap, within the sequence of neighborhood moves in VDS. Computational experiments exhibit good prospects of the proposed algorithm.

We describe a heuristic solution method for the Vehicle Routing Problem with Time Windows. The method uses four improvement operators in a steepest descent search strategy. The Guided Local Search meta-heuristic is used to avoid local minima. The resulting algorithm is tested on Solomon’s capacitated vehicle routing problems with time windows. We compare our results to the best heuristic approaches reported for the VRPTW. The new method performs significantly better than previous methods on classes where vehicle routes tend to be longer. The method is slightly worse on classes with shorter routes. We report 12 new best solutions for Solomon’s problems.

It is the purpose of this paper to investigate effects of adding randomization to a memory-based heuristic. The algorithms we propose are applied to the Capacitated Minimum Spanning Tree problem (CMST), and we study the combined effects of simultaneously applying a memory-based and a randombased heuristic to the CMST. This paper uses the Adaptive Reasoning Technique (ART) and concepts from the greedy randomized adaptive search procedure for solving the CMST. The resulting hybrid procedure is tested against the stand-alone Esau-Williams heuristic procedure, as well as the stand-alone greedy assignment technique. We find that randomization does not constructively add to the memory-based procedure, as ART alone typically outperforms all other approaches in terms of solution quality, while expending a modest amount of computational effort.

Mathematical programming problems with some or all variables constrained to take on integer values are important in a large number of applications and are receiving a great deal of research attention. Meta-heuristics such as tabu search have been proposed for such problems and have been very successful in some settings but they suffer from the disadvantage that they cannot typically, by themselves, produce provably optimal solutions. Exact methods of solving these problems often include ‘quick’ heuristics to help solve sub-problems and/or improve bounds but incorporation of meta-heuristics has not received very much attention.In this paper we examine an architecture for incorporating meta-heuristics in branch and bound algorithms. Since the meta-heuristics consume non-trivial computational resources, a major issue is deciding whether to launch a search from a node in the branch and bound tree. We propose methods for making this decision that make use of simple priorities, sampling and chunking to facilitate tests for novelty. Computational results are reported for 0–1 problems using XPRESS-MP for the branch and bound processing and a version of Reactive Tabu Search modified to support a novel two-level intensification/diversification strategy for those nodes selected as a starting point for heuristic search.