Tabu Search for a Network Loading Problem with Multiple Facilities

This paper examines a network design problem that arises in the telecommunications industry. In this problem, communication between a gateway vertex and a number of demand vertices is achieved through a network of fiber optic cables. Since each cable has an associated capacity (bandwidth), enough capacity must be installed on the links of the network to satisfy the demand, using possibly different types of cables. Starting with a network with no capacity or some capacity already installed, a tabu search heuristic is designed to find a solution that minimizes the cost of installing any additional capacity on the network. This tabu search applies a k-shortest path algorithm to find alternative paths from the gateway to the demand vertices. Numerical results are presented on different types of networks with up to 200 vertices and 100 demand vertices.     

On Using Tabu Search for Design Automation of VLSI Systems

Tabu search is a meta-heuristic problem solving technique that, when applied carefully, provides near optimal solutions in a very short time. In this paper, we have described the use of tabu search for solving problems related to very large scale integrated (VLSI) circuit design automation. Specifically, we have demonstrated the use for VLSI circuit partitioning and placement. We present a tabu search based circuit bi-partitioning technique that partitions circuits with the goal of minimizing the size of the cutset between the partitions. Then, we use tabu search techniques along with force directed placement techniques to accomplish the physical placement of VLSI circuits on regular two-dimensional arrays with the goal of minimizing the placement time. We use empirical data from partitioning and placement of benchmark circuits to test our techniques. Our methods show improvement when compared to partitioning techniques from the literature and commercially available placement tools. Relative to the literature, our tabu search bi-partitioning technique improves on the best known minimum cuts for several benchmark circuits. Relative to commercially available computer aided design tools, our tabu search based placement approach shows dramatic (20×) speedup in execution time without negative impact on the quality of the solution.     

Scheduling ambulance crews for maximum coverage

This paper addresses the problem of scheduling ambulance crews in order to maximize the coverage throughout a planning horizon. The problem includes the subproblem of locating ambulances to maximize expected coverage with probabilistic response times, for which a tabu search algorithm is developed. The proposed tabu search algorithm is empirically shown to outperform previous approaches for this subproblem. Two integer programming models that use the output of the tabu search algorithm are constructed for the main problem. Computational experiments with real data are conducted. A comparison of the results of the models is presented.     

Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem

This paper describes serial and parallel implementations of two different search techniques applied to the traveling salesman problem. A novel approach has been taken to parallelize simulated annealing and the results are compared with the traditional annealing algorithm. This approach uses abbreviated cooling schedule and achieves a superlinear speedup. Also a new search technique, called tabu search, has been adapted to execute in a parallel computing environment. Comparison between simulated annealing and tabu search indicate that tabu search consistently outperforms simulated annealing with respect to computation time while giving comparable solutions. Examples include 25, 33, 42, 50, 57, 75 and 100 city problems.     

Assignment of add–drop multiplexer (ADM) rings and digital cross-connect system (DCS) mesh in telecommunication networks

This paper discusses a design of a hybrid ring–mesh network in a survivable communication network. Given a set of traffic demands, the problem is to assign each traffic demand to rings and mesh such that the cost of add–drop multiplexer (ADM) and digital cross-connect system (DCS) equipment required is minimized. This assignment problem can be considered together with the fibre routing of nodes on rings and mesh. As a solution procedure, a tabu search is developed with recency-based short-term and frequency-based long-term memory structures. In computational experiments, the proposed tabu search is compared with the solutions obtained by the branch and bound procedure of CPLEX. We see that the tabu search provides a nearly optimal solution within sufficiently short time periods for all test problems with a gap of approximately 1–4% from the lower bound.     

Local search metaheuristics for discrete–continuous scheduling problems

Problems of scheduling nonpreemptable jobs which require simultaneously a machine from a set of parallel, identical machines and a continuous, renewable resource are considered. For each job there are known: its processing speed as a continuous, concave function of a continuous resource allotted at a time and its processing demand. The optimization criterion is the schedule length. The problem can be decomposed into two interrelated subproblems: (i) to sequence jobs on machines, and (ii) to find an optimal (continuous) resource allocation among jobs already sequenced. Problem (ii) can be formulated as a convex programming problem with linear constraints and solved using proper solvers. Thus, the problem remains to generate a set of all feasible sequences of jobs on machines (this guarantees finding an optimal schedule in the general case). However, the cardinality of this set grows exponentially with the number of jobs. Thus, we propose to use heuristic search methods defined on the space of feasible sequences. Three metaheuristics: tabu search (TS), simulated annealing (SA) and genetic algorithm (GA) have been implemented and compared computationally with a random sampling technique. The computational experiment has been carried out on an SGI PowerChallenge XL computer with 12 RISC R8000 processors. Some directions for further research have been pointed out.     

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.     

Path assignment for call routing: An application of tabu search

We describe an implementation of tabu search that solves the path assignment problem, which is the problem of routing video data through an undercapacitated telecommunications network. Two versions of the tabu search were studied. Our results compare very favourably with those from other methods.This research was supported by a grant from the Colorado Advanced Software Institute. The work of Jennifer Ryan was also partially supported by the Air Force Office of Scientific Research and the Office of Naval Research Contract #F49620-90-C-0033.     

An Application of Tabu Search Heuristic for the Maximum Edge-Weighted Subgraph Problem

The purpose of this article is to describe an efficient search heuristic for the Maximum Edge-weighted Subgraph (MEwS) problem. This problem requires to find a subgraph such that the sum of the weights associated with the edges of the subgraph is maximized subject to a cardinality constraint. In this study a tabu search heuristic for the MEwS problem is proposed. Different algorithms to obtain an initial solution are presented. One neighborhood search strategy is also proposed. Preliminary computational results are reported for randomly generated test problems of MEwS problem with different densities and sizes. For most of test problems, the tabu search heuristic found good solutions. In addition, for large size test problems, the tabu search outperformed the local search heuristic appearing in the literature.     

一种改进的禁忌搜索算法及其在选址问题中的应用

本文研究了选址问题中无容量限制的p-中值问题,在Rolland等人提出的有效禁忌搜索算法基础上,提出了一种以目标函数变化量作为评价函数的改进禁忌搜索算法,并进行了理论分析,然后将其与有效禁忌搜索算法作了性能比较.通过比较三个公共测试数据集的计算结果,验证了本文提出的禁忌搜索算法的可行性和有效性.     

Tabu search algorithms for an industrial multi-product and multi-objective assembly line balancing problem,with reduction of the task dispersion

This paper presents a real-world industrial application of the multi-product and multi-objective assembly line balancing problem, for a company involved in the production of four models of a white goods product. The problem solved is a GALBP-2, with 10 workstations and multiple objectives (to maximize the production rate in order to deal with an increase of the demand forecasted, to reach an equal cycle time of all the models and an equal workload of the different workstations, and finally, to minimize the dispersion of worker tasks on each one of the different models—the common tasks of the different models at the same workstation). The paper presents an integrated approach based on four heuristics cited in the literature and: (1) an improvement procedure based on tabu search, with the objective of minimizing the cycle time; and, subsequently, (2) a second tabu search in order to increase the uniformity of the tasks performed at each workstation (the common tasks at the same workstation).     

A hybridized tabu search approach for the minimum weight vertex cover problem

The minimum weight vertex cover problem is a basic combinatorial optimization problem defined as follows. Given an undirected graph and positive weights for all vertices the objective is to determine a subset of the vertices which covers all edges such that the sum of the related cost values is minimized. In this paper we apply a modified reactive tabu search approach for solving the problem. While the initial concept of reactive tabu search involves a random walk we propose to replace this random walk by a controlled simulated annealing. Numerical results are presented outperforming previous metaheuristic approaches in most cases.     

Solving the frequency assignment problem with polarization by local search and tabu

In the Frequency Assignment Problem with Polarization (FAPP), a given set of links must each be assigned a frequency and a polarization, while respecting given radio-electric compatibility constraints defined on pairs of links. In this paper, we propose a tabu search algorithm for the FAPP. A specialized neighborhood is proposed for the problem. Other key features of the algorithm are an adaptive technique to adjust the tabu tenure, an original diversification technique, and a pre-processing procedure based on arc-consistency techniques. The algorithm is tested on the 40 instances of the ROADEF Challenge 2001. It reaches the best known feasibility level for all instances and finds or improves on the best known solutions of the Challenge for a majority of the instances.Received: July 2003 / Revised version: September 2004MSC classification: 90B18, 68T20All correspondence to: Philippe Galinier     

Design and Evaluation of Tabu Search Algorithms for Multiprocessor Scheduling

Using a simple multiprocessor scheduling problem as a vehicle, we explore the behavior of tabu search algorithms using different tabu, local search and list management strategies. We found that random blocking of the tail of the tabu list always improved performance; but that the use of frequency-based penalties to discourage frequently selected moves did not. Hash coding without conflict resolution was an effective way to represent solutions on the tabu list. We also found that the most effective length of the tabu list depended on features of the algorithm being used, but not on the size and complexity of the problem being solved. The best combination of features included random blocking of the tabu list, tasks as tabus and a greedy local search. An algorithm using these features was found to outperform a recently published algorithm solving a similar problem.     

A multi-class multi-level capacitated lot sizing model

When demand loading is higher than available capacity, it takes a great deal of effort for a traditional MRP system to obtain a capacity-feasible production plan. Also, the separation of lot sizing decisions and capacity requirement planning makes the setup decisions more difficult. In a practical application, a production planning system should prioritize demands when allocating manufacturing resources. This study proposes a planning model that integrates all MRP computation modules. The model not only includes multi-level capacitated lot sizing problems but also considers multiple demand classes. Each demand class corresponds to a mixed integer programming (MIP) problem. By sequentially solving the MIP problems according to their demand class priorities, this proposed approach allocates finite manufacturing resources and generates feasible production plans. In this paper we experiment with three heuristic search algorithms: (1) tabu search; (2) simulated annealing, and (3) genetic algorithm, to solve the MIP problems. Experimental designs and statistical methods are used to evaluate and analyse the performance of these three algorithms. The results show that tabu search and simulated annealing perform best in the confirmed order demand class and forecast demand class, respectively.     

An introduction to population approaches for optimization and hierarchical objective functions: A discussion on the role of tabu search

Population approaches suitable for global combinatorial optimization are discussed in this paper. They are composed of a number of distinguishable individuals called "agents", each one using a particular optimization strategy. Periods of independent search follow phases on which the population is restarted from new configurations. Due to its intrinsic parallelism and the asynchronicity of the method, it is particularly suitable for parallel computers. Results on two test problems are presented in this paper. The individual search optimization strategies for each agent have been chosen having the basic characteristics of tabu search. This has been done in order to avoid mixing the hypothesized properties of these population approaches with those of more elaborate tabu search strategies, but remarking on its main characteristics. A set of four test problem "landscapes" is discussed and their use to improve and benchmark the results by using tabu search as the individual optimization strategy within a population heuristic is suggested and explored. The application of tabu search to new problem areas, like molecular biology, is also investigated.     

Path relinking for the vehicle routing problem

This paper describes a tabu search heuristic with path relinking for the vehicle routing problem. Tabu search is a local search method that explores the solution space more thoroughly than other local search based methods by overcoming local optima. Path relinking is a method to integrate intensification and diversification in the search. It explores paths that connect previously found elite solutions. Computational results show that tabu search with path relinking is superior to pure tabu search on the vehicle routing problem.     

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.     

Iterated tabu search for the car sequencing problem

This paper introduces an iterated tabu search heuristic for the daily car sequencing problem in which a set of cars must be sequenced so as to satisfy requirements from the paint shop and the assembly line. The iterated tabu search heuristic combines a classical tabu search with perturbation operators that help escape from local optima. The resulting heuristic is flexible, easy to implement, and fast. It has produced very good results on a set of test instances provided by the French car manufacturer Renault.     

A parallel multi-neighborhood cooperative tabu search for capacitated vehicle routing problems

This paper presents a parallel tabu search algorithm that utilizes several different neighborhood structures for solving the capacitated vehicle routing problem. Single neighborhood or neighborhood combinations are encapsulated in tabu search threads and they cooperate through a solution pool for the purpose of exploiting their joint power. The computational experiments on 32 large scale benchmark instances show that the proposed method is highly effective and competitive, providing new best solutions to four instances while the average deviation of all best solutions found from the collective best results reported in the literature is about 0.22%. We are also able to associate the beneficial use of special neighborhoods with some test instance characteristics and uncover some sources of the collective power of multi-neighborhood cooperation.