A Tabu Search Algorithm for the Quadratic Assignment Problem

Tabu search approach based algorithms are among the widest applied to various combinatorial optimization problems. In this paper, we propose a new version of the tabu search algorithm for the well-known problem, the quadratic assignment problem (QAP). One of the most important features of our tabu search implementation is an efficient use of mutations applied to the best solutions found so far. We tested this approach on a number of instances from the library of the QAP instances—QAPLIB. The results obtained from the experiments show that the proposed algorithm belongs to the most efficient heuristics for the QAP. The high efficiency of this algorithm is also demonstrated by the fact that the new best known solutions were found for several QAP instances.     

Complete Local Search with Memory

Neighborhood search heuristics like local search and its variants are some of the most popular approaches to solve discrete optimization problems of moderate to large size. Apart from tabu search, most of these heuristics are memoryless. In this paper we introduce a new neighborhood search heuristic that makes effective use of memory structures in a way that is different from that in common implementations of tabu search. We report computational experiments with this heuristic on the traveling salesperson problem and the subset sum problem.     

Ant colonies for the quadratic assignment problem

This paper presents HAS–QAP, a hybrid ant colony system coupled with a local search, applied to the quadratic assignment problem. HAS–QAP uses pheromone trail information to perform modifications on QAP solutions, unlike more traditional ant systems that use pheromone trail information to construct complete solutions. HAS–QAP is analysed and compared with some of the best heuristics available for the QAP: two versions of tabu search, namely, robust and reactive tabu search, hybrid genetic algorithm, and a simulated annealing method. 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.     

Variable neighborhood search for the vertex weighted k-cardinality tree problem

This paper presents some new heuristics based on variable neighborhood search to solve the vertex weighted k-cardinality tree problem. An efficient local search procedure is also developed for use within these heuristics. Our computational results demonstrate that the new heuristics substantially outperform the state-of-the-art methodologies, including a tabu search and genetic algorithm recently proposed in the literature. We also show that a decomposition approach is best for larger problem sizes than previously investigated. Thus, our findings advance in a significant way the capacity to solve this important class of problems.     

A hyper-heuristic approach to sequencing by hybridization of DNA sequences

In this paper we investigate the use of hyper-heuristic methodologies for predicting DNA sequences. In particular, we utilize Sequencing by Hybridization. We believe that this is the first time that hyper-heuristics have been investigated in this domain. A hyper-heuristic is provided with a set of low-level heuristics and the aim is to decide which heuristic to call at each decision point. We investigate three types of hyper-heuristics. Two of these (simulated annealing and tabu search) draw their inspiration from meta-heuristics. The choice function hyper-heuristic draws its inspiration from reinforcement learning. We utilize two independent sets of low-level heuristics. The first set is based on a previous tabu search method, with the second set being a significant extension to this basic set, including utilizing a different representation and introducing the definition of clusters. The datasets we use comprises two randomly generated datasets and also a publicly available biological dataset. In total, we carried out experiments using 70 different combinations of heuristics, using the three datasets mentioned above and investigating six different hyper-heuristic algorithms. Our results demonstrate the effectiveness of a hyper-heuristic approach to this problem domain. It is necessary to provide a good set of low-level heuristics, which are able to both intensify and diversify the search but this approach has demonstrated very encouraging results on this extremely difficult and important problem domain.     

A Tabu-Search Hyperheuristic for Timetabling and Rostering

Hyperheuristics can be defined to be heuristics which choose between heuristics in order to solve a given optimisation problem. The main motivation behind the development of such approaches is the goal of developing automated scheduling methods which are not restricted to one problem. In this paper we report the investigation of a hyperheuristic approach and evaluate it on various instances of two distinct timetabling and rostering problems. In the framework of our hyperheuristic approach, heuristics compete using rules based on the principles of reinforcement learning. A tabu list of heuristics is also maintained which prevents certain heuristics from being chosen at certain times during the search. We demonstrate that this tabu-search hyperheuristic is an easily re-usable method which can produce solutions of at least acceptable quality across a variety of problems and instances. In effect the proposed method is capable of producing solutions that are competitive with those obtained using state-of-the-art problem-specific techniques for the problems studied here, but is fundamentally more general than those techniques.     

A graph-based hyper-heuristic for educational timetabling problems

This paper presents an investigation of a simple generic hyper-heuristic approach upon a set of widely used constructive heuristics (graph coloring heuristics) in timetabling. Within the hyper-heuristic framework, a tabu search approach is employed to search for permutations of graph heuristics which are used for constructing timetables in exam and course timetabling problems. This underpins a multi-stage hyper-heuristic where the tabu search employs permutations upon a different number of graph heuristics in two stages. We study this graph-based hyper-heuristic approach within the context of exploring fundamental issues concerning the search space of the hyper-heuristic (the heuristic space) and the solution space. Such issues have not been addressed in other hyper-heuristic research. These approaches are tested on both exam and course benchmark timetabling problems and are compared with the fine-tuned bespoke state-of-the-art approaches. The results are within the range of the best results reported in the literature. The approach described here represents a significantly more generally applicable approach than the current state of the art in the literature. Future work will extend this hyper-heuristic framework by employing methodologies which are applicable on a wider range of timetabling and scheduling problems.     

Search Heuristics for Resource Constrained Project Scheduling

We develop a search procedure for project scheduling problems with multiple resource constraints as well as precedence constraints. The procedure is applied to three popular search heuristics, simulated annealing, tabu search and genetic algorithms. In the heuristics, a solution is represented with a string of numbers each of which denotes priority of each activity. The priorities are used to select an activity for scheduling among competing ones. The search heuristics with this encoding method can always generate feasible neighbourhood solutions for a given solution. Moreover, this encoding method is very flexible in that problems with objective functions of a general functional form (such as a nonlinear function) and complex constraints can be considered without much difficulty. Results of computational tests on the performance of the search heuristics showed that the search heuristics, especially the simulated annealing and tabu search algorithms worked better than existing heuristics.     

Diversification strategies in tabu search algorithms for the maximum clique problem

The purpose of this study is to develop some understanding of the benefits that can be derived from the inclusion of diversification strategies in tabu search methods. To do so, we discuss the implementation of various diversification strategies in several tabu search heuristics developed for the maximum clique problem. Computational results on a large set of randomly generated test problems are reported and compared to assess the impact of these techniques on solution quality and running time.     

A Tabu search-based approach for scheduling job-shop type flexible manufacturing systems

The problem of scheduling parts in a job-shop type flexible manufacturing system (FMS) is investigated when each part can have alternative process plans and each operation required of a part can be performed on alternative machines. The mixed-(binary) integer programming model developed for the problem is proven strongly NP-hard. A higher-level heuristic solution algorithm based on a concept known as ‘tabu search’ is developed to determine the best (near-optimal) solution for problems of industrial merit. A comparison of six different versions of tabu search-based heuristics (TSH 1-TSH 6) is performed to investigate the impact of using long-term memory and the use of fixed versus variable tabu-list sizes. A carefully constructed statistical experiment, based on randomized complete-block design, is used to test the performance on four problem structures ranging from 4–14 parts. The results show that, as the problem size increases, TSH 3 with fixed tabu-list size and long-term memory is preferred over the other heuristics. Further, the branch-and-bound technique, by failing to identify as good a solution as that determined by the heuristics (TSH 1-TSH 6), let alone an optimal solution, for a small problem reinforces the need for developing efficient heuristics for solving real problems encountered in industry practice.     

Local search heuristics for single-machine scheduling with batching to minimize the number of late jobs

Local search heuristics are developed for a problem of scheduling jobs on a single machine. Jobs are partitioned into families, and a set-up time is necessary when there is a switch in processing jobs from one family to jobs of another family. The objective is to minimize the number of late jobs. Four alternative local search methods are proposed: multi-start descent, simulated annealing, tabu search and a genetic algorithm. The performance of these heuristics is evaluated on a large set of test problems. The best results are obtained with the genetic algorithm; multi-start descent also performs quite well.     

A Tabu Search Approach for the Resource Constrained Project Scheduling Problem

An appropriate tabu search implementation is designed to solve the resource constrained project scheduling problem. This approach uses well defined move strategies and a structured neighbourhood, defines appropriate tabu status and tenure and takes account of objective function approximation to speed up the search process. A sound understanding of the problem has helped in many ways in designing and enhancing the tabu search methodology. The method uses diversification, intensification and handles infeasibility via strategic oscillation.The above methodology is tested on existing problems from the literature and also on parametrically generated problems with encouraging results. For comparison of results, optimal solutions are used in the former and lower bounds obtained by Lagrangian heuristics are used in the latter.     

Designing delivery districts for the vehicle routing problem with stochastic demands

This paper considers the problem of designing districts for vehicle routing problems with stochastic demands. In particular, demands are assumed to be uncertain at the time when the districts are made, and these are revealed only after the districting decisions are determined. Tabu search and multistart heuristics for this stochastic districting problem are developed and compared. Computational results show that tabu search is superior over multistart.     

Heuristics for the flow line problem with setup costs

This paper presents two new heuristics for the flowshop scheduling problem with sequence-dependent setup times (SDSTs) and makespan minimization objective. The first is an extension of a procedure that has been very successful for the general flowshop scheduling problem. The other is a greedy randomized adaptive search procedure (GRASP) which is a technique that has achieved good results on a variety of combinatorial optimization problems. Both heuristics are compared to a previously proposed algorithm based on the traveling salesman problem (TSP). In addition, local search procedures are developed and adapted to each of the heuristics. A two-phase lower bounding scheme is presented as well. The first phase finds a lower bound based on the assignment relaxation for the asymmetric TSP. In phase two, attempts are made to improve the bound by inserting idle time. All procedures are compared for two different classes of randomly generated instances. In the first case where setup times are an order of magnitude smaller than the processing times, the new approaches prove superior to the TSP-based heuristic; for the case where both processing and setup times are identically distributed, the TSP-based heuristic outperforms the proposed procedures.     

A tabu search approach for solving a difficult forest harvesting machine location problem

This paper deals with two main problems in forest harvesting. The first is that of selecting the locations for the machinery to haul logs from the points where they are felled to the roadside. The second consists in designing the access road network connecting the existing road network with the points where machinery is installed. Their combination induces a very important and difficult problem to solve in forest harvesting. It can be formulated as a combination of two difficult optimization problems: a plant location problem and a fixed charge network flow problem. In this paper, we propose a solution approach based on tabu search. The proposed heuristic includes several enhancements of the basic tabu search framework. The main difficulty lies in evaluating neighboring solutions, which involves decisions related to location of machinery and to road network arcs. Hence, the neighborhood is more complex than in typical applications of metaheuristics. Minimum spanning tree algorithms and Steiner tree heuristics are used to deal with this problem. Numerical results indicate that the heuristic approach is very attractive and leads to better solutions than those provided by state-of-the-art integer programming codes in limited computation times, with solution times significantly smaller. The numerical results do not vary too much when typical parameters such as the tabu tenure are modified, except for the dimension of neighborhood.     

An Improved Petal Heuristic for the Vehicle Routeing Problem

Solutions produced by the first generation of heuristics for the vehicle routeing problem are often far from optimal. Recent adaptations of local search improvement heuristics, like tabu search, produce much better solutions but require increased computing time. However there are situations where good solutions must be obtained quickly. The algorithm proposed in this paper yields solutions almost as good as those produced by tabu search adaptations, but at only a small fraction of their computing time. This heuristic can be seen as an improved version of the original petal heuristic. On 14 benchmark test problems, the proposed heuristic yields solutions whose values lie on average within 2.38% of that of the best known solutions.     

Avoiding local optima in thep-hub location problem using tabu search and GRASP

In the discretep-hub location problem, various nodes interact with each other by sending and receiving given levels of traffic (such as telecommunications traffic, data transmissions, airline passengers, packages, etc.). It is necessary to choosep of the given nodes to act as hubs, which are fully interconnected; it is also necessary to connect each other node to one of these hubs so that traffic can be sent between any pair of nodes by using the hubs as switching points. The objective is to minimize the sum of the costs for sending traffic along the links connecting the various nodes. Like many combinatorial problems, thep-hub location problem has many local optima. Heuristics, such as exchange methods, can terminate once such a local optimum is encountered. In this paper, we describe new heuristics for thep-hub location problem, based on tabu search and on a greedy randomized adaptive search procedure (GRASP). These recently developed approaches to combinatorial optimization are capable of examining several local optima, so that, overall, superior solutions are found. Computational experience is reported in which both tabu search and GRASP found optimal hub locations (subject to the assumption that nodes must be assigned to the nearest hub) in over 90% of test problems. For problems for which such optima are not known, tabu search and GRASP generated new best-known solutions.     

Integrating Interval Estimates of Global Optima and Local Search Methods for Combinatorial Optimization Problems

The problem of estimating the global optimal values of intractable combinatorial optimization problems is of interest to researchers developing and evaluating heuristics for these problems. In this paper we present a method for combining statistical optimum prediction techniques with local search methods such as simulated annealing and tabu search and illustrate the approach on a single machine scheduling problem. Computational experiments show that the approach yields useful estimates of optimal values with very reasonable computational effort.     

Tabu search and GRASP for the maximum diversity problem

In this paper, we develop new heuristic procedures for the maximum diversity problem (MDP). This NP-hard problem has a significant number of practical applications such as environmental balance, telecommunication services or genetic engineering. The proposed algorithm is based on the tabu search methodology and incorporates memory structures for both construction and improvement. Although proposed in seminal tabu search papers, memory-based constructions have often been implemented in naïve ways that disregard important elements of the fundamental tabu search proposals. We will compare our tabu search construction with a memory-less design and with previous algorithms recently developed for this problem. The constructive method can be coupled with a local search procedure or a short-term tabu search for improved outcomes. Extensive computational experiments with medium and large instances show that the proposed procedure outperforms the best heuristics reported in the literature within short computational times.     

Routing and scheduling in a flexible job shop by tabu search

A hierarchical algorithm for the flexible job shop scheduling problem is described, based on the tabu search metaheuristic. Hierarchical strategies have been proposed in the literature for complex scheduling problems, and the tabu search metaheuristic, being able to cope with different memory levels, provides a natural background for the development of a hierarchical algorithm. For the case considered, a two level approach has been devised, based on the decomposition in a routing and a job shop scheduling subproblem, which is obtained by assigning each operation of each job to one among the equivalent machines. Both problems are tackled by tabu search. Coordination issues between the two hierarchical levels are considered. Unlike other hierarchical schemes, which are based on a one-way information flow, the one proposed here is based on a two-way information flow. This characteristic, together with the flexibility of local search strategies like tabu search, allows to adapt the same basic algorithm to different objective functions. Preliminary computational experience is reported.