Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Tabu Search <s> In this paper we discuss the development and application of a new and more powerful method for solving the muldple-machine weighted flow time problem using a basic tabu search (TS) approach. Previous methods of solution used branch and bound and are computationally limited to problems of about 25 jobs. In a set of previously published problems with IS to 30 jobs, the new method achieved optimality in at least an order of magnitude less computation time than branch and bound first achieved the optimum. Studies of larger problems indicate that the new method maintains its ability to achieve superior solutions with only a modest growth in computational effort. <s> BIB001 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Tabu Search <s> We propose an algorithm for combinatorial optimization where an explicit check for the repetition of configurations is added to the basic scheme of Tabu search. In our Tabu scheme the appropriate size of the list is learned in an automated way by reacting to the occurrence of cycles. In addition, if the search appears to be repeating an excessive number of solutions excessively often, then the search is diversified by making a number of random moves proportional to a moving average of the cycle length. The reactive scheme is compared to a “strict” Tabu scheme that forbids the repetition of configurations and to schemes with a fixed or randomly varying list size. From the implementation point of view we show that the Hashing or Digital Tree techniques can be used in order to search for repetitions in a time that is approximately constant. We present the results obtained for a series of computational tests on a benchmark function, on the 0-1 Knapsack Problem, and on the Quadratic Assignment Problem. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499. <s> BIB002 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Tabu Search <s> Abstract The multilevel generalized assignment problem (MGAP) differs from the classical GAP in that agents can perform tasks at more than one efficiency level. Important manufacturing problems, such as lot sizing, can be formulated as MGAPs; however, the large number of variables in the related 0–1 integer program makes the use of commercial optimization packages impractical. In this paper, we present a heuristic approach to the solution of the MGAP, which consists of a novel application of tabu search (TS). Our TS method employs neighborhoods defined by ejection chains, that produce moves of greater power without significantly increasing the computational effort. <s> BIB003 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Tabu Search <s> This paper presents a robust tabu search approach to the traveling-salesman problem with time windows. The approach uses a two-level tour hashing scheme within a reactive tabu search procedure to detect unique repeated solutions and to promote a more diverse search. Strong feasibility conditions restrict the neighborhood of candidate solutions. The search returns optimal, or near-optimal, solutions within a fraction of the time required by optimal methods. The algorithm’s search neighborhood is not restricted to feasible solutions, and superior marginally infeasible solutions are reported to enhance the decision making process. The paper presents computational results for 145 problems from the literature. <s> BIB004 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Tabu Search <s> We describe a tabu search (TS) approach for solving general zero-one mixed integer programming (MIP) problems that exploits the extreme point property of zero-one solutions. Specialized choice rules and aspiration criteria are identified for the problems, expressed as functions of integer infeasibility measures and objective function values. The first-level TS mechanisms are then extended with advanced level strategies and learning. We also look at probabilistic measures in this framework, and examine how the learning tool Target Analysis (TA) can be applied to identify better control structures and decision rules. Computational results are reported on a portfolio of multiconstraint knapsack problems. Our approach is designed to solve thoroughly general 0/1 MIP problems and thus contains no problem domain specific knowledge, yet it obtains solutions for the multiconstraint knapsack problem whose quality rivals, and in some cases surpasses, the best solutions obtained by special purpose methods that have been created to exploit the special structure of these problems. <s> BIB005 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Tabu Search <s> The pickup and delivery problem with time windows requires that a group of vehicles satisfy a collection of customer requests. Each customer request requires the use of a single vehicle both to load a specified amount of goods at one location and to deliver them to another location. All requests must be performed without violating either the vehicle capacity or the customer time window stipulated at each location. In this paper, we present a reactive tabu search approach to solve the pickup and delivery problem with time windows using three distinct move neighborhoods that capitalize on the dominance of the precedence and coupling constraints. A hierarchical search methodology is used to dynamically alternate between neighborhoods in order to negotiate different regions of the solution space and adjust search trajectories. In order to validate our technique's effectiveness, we have constructed a new set of benchmark problems for the pickup and delivery problem with time windows based on Solomon's benchmark vehicle routing problem with time windows data sets. Computational results substantiate the solution quality and efficiency of our reactive tabu search approach. <s> BIB006 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Tabu Search <s> We present a Tabu Search (TS) method that employs a simple version of ejection chains for coloring graphs. The procedure is tested on a set of benchmark problems. Empirical results indicate that the proposed TS implementation outperforms other metaheuristic methods, including Simulated Annealing, a previous version of Tabu Search and a recent implementation of a Greedy Randomized Adaptive Search Procedure (GRASP). <s> BIB007 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Tabu Search <s> High dimensional inputs coupled with scarcity of labeled data are among the greatest challenges for classification of hyperspectral data. These problems are exacerbated if the number of classes is large. High dimensional output classes can often be handled effectively by decomposition into multiple two-(meta)class problems, where each sub-problem is solved using a suitable binary classifier, and outputs of this collection of classifiers are combined in a suitable manner to obtain the answer to the original multi-class problem. This approach is taken by the binary hierarchical classifier (BHC). The advantages of the BHC for output decomposition can be further exploited for hyperspectral data analysis by integrating a feature selection methodology with the classifier. Building upon the previously developed best bases BHC algorithm with greedy feature selection, a new method is developed that selects a subset of band groups within metaclasses using reactive tabu search. Experimental results obtained from analysis of Hyperion data acquired over the Okavango Delta in Botswana are superior to those of the greedy feature selection approach and more robust than either the original BHC or the BHC with greedy feature selection. <s> BIB008 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Tabu Search <s> We develop a Reactive Tabu Search (RTS) algorithm for solving the Unicost Set Covering Problem (SCP) â€“ USCP-TS. We solve a Linear Programming (LP) relaxation of the problem and use the LP optimum to construct a quality solution profile. We cluster the problem variables based on this profile and partition the solution space into orbits. We tested our algorithm on 65 benchmark problems and compared the results against the previous best-known solutions and those obtained by CPLEX 9.0 under varied settings. USCP-TS outperforms CPLEX in solution quality for 32 of the problems and achieves the same solution as CPLEX faster on 21 of the remaining problems. <s> BIB009 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Tabu Search <s> The quadratic assignment problem (QAP) is a well-known combinatorial optimization problem with a wide variety of applications, prominently including the facility location problem. The acknowledged difficulty of the QAP has made it the focus of many metaheuristic solution approaches. In this paper, we show the benefit of utilizing strategic diversification within the tabu search (TS) framework for the QAP, by incorporating several diversification and multistart TS variants. Computational results for an extensive and challenging set of QAP benchmark test problems demonstrate the ability of our TS variants to improve on a classic TS approach that is one of the principal and most extensively used methods for the QAP. We also show that our new procedures are highly competitive with the best recently introduced methods from the literature, including more complex hybrid approaches that incorporate the classic TS method as a subroutine. <s> BIB010 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Tabu Search <s> We apply a tabu search method to a scheduling problem of a company producing cables for cars: the task is to determine on what machines and in which order the cable jobs should be produced in order to save production costs. First, the problem is modeled as a combinatorial optimization problem. We then employ a tabu search algorithm as an approach to solve the specific problem of the company, adapt various intensification as well as diversification strategies within the algorithm, and demonstrate how these different implementations improve the results. Moreover, we show how the computational cost in each iteration of the algorithm can be reduced drastically from O(n 3 ) (naive implementation) to O(n) (smart implementation) by exploiting the specific structure of the problem (n refers to the number of cable orders). Copyright The Author(s) 2011 <s> BIB011
Tabu search  was first proposed by Glover in 1986. Tabu search (TS) is a metaheuristic that guides a local search heuristic both to escape from local minima and to implement an exploration scheme. The simple TS algorithm applies a best improvement local search where at each iteration the best solution in the neighborhood is selected as the new current solution. A short-term memory is implemented as a tabu list where solution attributes are stored to avoid short term cycling. A term Aspiration criteria are defined which is allowed to include some unvisited solution of good quality which are excluded from allowed set. Starting from the basic search strategy a number of developments and elaboration have been proposed over the years. These include Introduction of intensification and diversification mechanisms. They are implemented via different forms of long term memories. Adaptive memories provides a mechanism to diversity and intensity of the search so as to create more flexible search behaviors. Frequency memories provides a form of continuous diversity by introducing a bias in the evaluation of neighborhood solution. The probabilistic TS introduce randomization into the search method. It can be attained by linking probabilities with moves contributing to the neighborhood solution. Unified tabu search is aimed at developing simpler, more flexible TS code another example of this style is the granular TS.  proposed tabu search methods for a single machine scheduling problem. The approach consists of the use of three local search methods within a tabu search to solve the problem. Also a hybrid TS is developed that utilize both swap and insert moves  . BIB001 proposes static TC for solving the multiple mechanic weighted flow time problem. The proposed approach provides superior result in comparison to the Branch and Bound method BIB001 . BIB002 introduced the reactive search which uses the history of the search for dynamically adjusting search parameters. In particular, when configurations are frequently occurring the dimensions of tabu list are automatically increased to avoid short term cycle BIB002 . BIB003 applied a TS method to solve the multilevel generalized assignment problem in which at each iteration, list of candidate moves are generated by using ejection chains BIB003 . BIB004 applied reactive TS to solve Travelling Salesman problem. In this a robust tabu search is applied to traveling salesman problem with time window. The approach uses a two level hashing method within a reactive tabu search to find unique repeated solution and to upgrade a more diverse search BIB004 . BIB005 applied TS to solve general zeroone mixed integer programming problem. In this specialized choice rule and aspiration criteria are discovered for the problem, expressed as a function of integer that measures infeasibility and objective function values BIB005 . BIB006 applied reactive TS to solve a pick up and delivery problem with the constraint of vehicle capacity and customer time windows BIB006 . Gonzalez-Velarde et al. (2002) applied TS to solve graph coloring problem. In this paper, a tabu search method is proposed that applies a simple version of ejection chains for coloring graph BIB007 . BIB008 merged TS within a classification algorithm using reactive TS to improve classification accuracy BIB008 . Scrich et al.  applied TS to solve the problem of scheduling job with the aim of minimizing total tardiness [107] .  applied TS to solve the aerial fleet refueling using group theoretic. They applied group theory to partitioning and ordering combinatorial optimization  .  applied adaptive TS to solve two dimensional orthogonal packing problems  . BIB009 proposed a group theoretic TS algorithm to solve the unicost set covering problem by partitioning the solution space into orbits. In this a linear programming relaxation of the problem is solved and a quality solution profile is constructed by using linear programming optimization. Problem variables will be clustered based on this profile and partition the solution space into orbits BIB009 . BIB010 showed the advantages of applying strategic diversification within Tabu search (TS) model for the quadratic assignment problem by including many diversification and multi start TS variants BIB010 . Ulrike (2011) applied TS to Scheduling problem then with the help of intensification and diversification strategies demonstrates that the result achieved is quite better BIB011 .