Reinforcement learning enhanced multi-neighborhood tabu search for the max-mean dispersion problem

This paper presents a highly effective reinforcement learning enhancement of multi-neighborhood tabu search for the max-mean dispersion problem. The reinforcement learning component uses the Q-learning mechanism that incorporates the accumulated feedback information collected from the actions performed during the search to guide the generation of diversified solutions. The tabu search component employs 1-flip and reduced 2-flip neighborhoods to collaboratively perform the neighborhood exploration for attaining high-quality local optima. A learning automata method is integrated in tabu search to adaptively determine the probability of selecting each neighborhood. Computational experiments on 80 challenging benchmark instances demonstrate that the proposed algorithm is favorably competitive with the state-of-the-art algorithms in the literature, by finding new lower bounds for 3 instances and matching the best known results for the other instances. Key elements and properties are also analyzed to disclose the source of the benefits of our integration of learning mechanisms and tabu search.     

Tabu search for the single row facility layout problem using exhaustive 2-opt and insertion neighborhoods

The single row facility layout problem (SRFLP) is the problem of arranging facilities with given lengths on a line, while minimizing the weighted sum of the distances between all pairs of facilities. The problem is NP-hard. In this paper, we present two tabu search implementations, one involving an exhaustive search of the 2-opt neighborhood and the other involving an exhaustive search of the insertion neighborhood. We also present techniques to significantly speed up the search of the two neighborhoods. Our computational experiments show that the speed up techniques are effective, and our tabu search implementations are competitive. Our tabu search implementations improved previously known best solutions for 23 out of the 43 large sized SRFLP benchmark instances.     

Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem

The capacitated minimum spanning tree (CMST) problem is to find a minimum cost spanning tree with an additional cardinality constraint on the sizes of the subtrees incident to a given root node. The CMST problem is an NP-complete problem, and existing exact algorithms can solve only small size problems. Currently, the best available heuristic procedures for the CMST problem are tabu search algorithms due to Amberg et al. and Sharaiha et al. These algorithms use two-exchange neighborhood structures that are based on exchanging a single node or a set of nodes between two subtrees. In this paper, we generalize their neighborhood structures to allow exchanges of nodes among multiple subtrees simultaneously; we refer to such neighborhood structures as multi-exchange neighborhood structures. Our first multi-exchange neighborhood structure allows exchanges of single nodes among several subtrees. Our second multi-exchange neighborhood structure allows exchanges that involve multiple subtrees. The size of each of these neighborhood structures grows exponentially with the problem size without any substantial increase in the computational times needed to find improved neighbors. Our approach, which is based on the cyclic transfer neighborhood structure due to Thompson and Psaraftis and Thompson and Orlin transforms a profitable exchange into a negative cost subset-disjoint cycle in a graph, called an improvement graph, and identifies these cycles using variants of shortest path label-correcting algorithms. Our computational results with GRASP and tabu search algorithms based on these neighborhood structures reveal that (i) for the unit demand case our algorithms obtained the best available solutions for all benchmark instances and improved some; and (ii) for the heterogeneous demand case our algorithms improved the best available solutions for most of the benchmark instances with improvements by as much as 18%. The running times our multi-exchange neighborhood search algorithms are comparable to those taken by two-exchange neighborhood search algorithms. Received: September 1998 / Accepted: March 2001?Published online May 18, 2001     

An Ant Colony Optimization Algorithm for Shop Scheduling Problems

We deal with the application of ant colony optimization to group shop scheduling, which is a general shop scheduling problem that includes, among others, the open shop scheduling problem and the job shop scheduling problem as special cases. The contributions of this paper are twofold. First, we propose a neighborhood structure for this problem by extending the well-known neighborhood structure derived by Nowicki and Smutnicki for the job shop scheduling problem. Then, we develop an ant colony optimization approach, which uses a strong non-delay guidance for constructing solutions and which employs black-box local search procedures to improve the constructed solutions. We compare this algorithm to an adaptation of the tabu search by Nowicki and Smutnicki to group shop scheduling. Despite its general nature, our algorithm works particularly well when applied to open shop scheduling instances, where it improves the best known solutions for 15 of the 28 tested instances. Moreover, our algorithm is the first competitive ant colony optimization approach for job shop scheduling instances.     

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     

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.     

A tabu search heuristic for ship routing and scheduling

The purpose of this paper is to solve a planning problem faced by many shipping companies dealing with the transport of bulk products. These shipping companies are committed to carrying some contract cargoes and will try to derive additional revenue from optional spot cargoes. An efficient tabu search algorithm has been developed to ensure quick decision support for the planners. The solutions generated by the tabu search heuristic are compared with those produced by a previously published multi-start local search heuristic. Computational results show that the tabu search heuristic yields optimal or near-optimal solutions to real-life instances within reasonable time. For large and tigthly constrained cases, the tabu search heuristic provides much better solutions than the multi-start local search heuristic. A version of the tabu search heuristic will be integrated as an improved solver in a prototype decision support system used by several shipping companies.     

带有资源转移时间的RCPSP资源流模型及算法

本文在传统资源受限项目调度问题(resource-constrained project scheduling problem, RCPSP)中引入资源转移时间,为有效获得问题的最优解,采用资源流编码方式表示可行解,建立了带有资源转移时间的RCPSP资源流优化模型,目标为最小化项目工期。根据问题特征设计了改进的资源流重构邻域算子,分别设计了改进的禁忌搜索算法和贪心随机自适应禁忌搜索算法求解模型。数据实验结果表明,相较于现有文献中的方法,所提两种算法均可针对更多的项目实例求得最优解,并且得到最优解的时间更短,求解效率更高。此外,分析了算法在求解具有不同特征的项目实例时的性能,所得结果为项目经理结合项目特征评价算法适用性提供了指导。     

Genetic and hybrid algorithms for graph coloring

Some genetic algorithms are considered for the graph coloring problem. As is the case for other combinatorial optimization problems, pure genetic algorithms are outperformed by neighborhood search heuristic procedures such as tabu search. Nevertheless, we examine the performance of several hybrid schemes that can obtain solutions of excellent quality. For some graphs, we illustrate that genetic operators can fulfill long-term strategic functions for a tabu search implementation that is chiefly founded on short-term memory strategies.     

Multistart Tabu Search Strategies for the Unconstrained Binary Quadratic Optimization Problem

This paper describes and experimentally compares five rather different multistart tabu search strategies for the unconstrained binary quadratic optimization problem: a random restart procedure, an application of a deterministic heuristic to specially constructed subproblems, an application of a randomized procedure to the full problem, a constructive procedure using tabu search adaptive memory, and an approach based on solving perturbed problems. In the solution improvement phase a modification of a standard tabu search implementation is used. A computational trick applied to this modification – mapping of the current solution to the zero vector – allowed to significantly reduce the time complexity of the search. Computational results are provided for the 25 largest problem instances from the OR-Library and, in addition, for the 18 randomly generated larger and more dense problems. For 9 instances from the OR-Library new best solutions were found.     

A two-phase tabu search based evolutionary algorithm for the maximum diversity problem

In this paper, we study the maximum diversity problem (MDP) which is equivalent to the quadratic unconstrained binary optimization (QUBO) problem with cardinality constraint. The MDP aims to select a subset of elements with given cardinality such that the sum of pairwise distances between any two elements in the selected subset is maximized. For solving this computationally challenging problem, we propose a two-phase tabu search based evolutionary algorithm (TPTS/EA), which integrates several distinguishing features to ensure the diversity and the quality of the evolution, such as a two-phase tabu search algorithm which consists of a dynamic candidate list (DCL) strategy-based traditional tabu search in the first phase and a solution-based tabu search procedure to refine the search in the second phase, and two path-relinking based recombination operators to generate new offspring solutions. Tested on three sets of totally 140 public instances in the literature, the study demonstrates the efficacy of the proposed TPTS/EA algorithm in terms of both solution quality and computational efficiency. Specifically, our proposed TPTS/EA algorithm is able to improve the previous best known results for 2 instances, while matching the previous best-known solutions for 130 instances. We also provide experimental evidences to highlight the beneficial effect of several important components in our TPTS/EA algorithm.     

Local search for the undirected capacitated arc routing problem with profits

This paper deals with a recently introduced routing problem variant called the undirected capacitated arc routing problem with profits (UCARPP). The UCARPP model considered in the present study is primarily aimed at generating the route set which maximizes the profit collected from a set of potential customers, represented by edges of the examined transportation network. The secondary objective is to minimize the total route travel time. The generated routes are subject both to capacity and travel time constraints. To tackle the examined problem, we propose a local search metaheuristic development which explores two solution neighborhood structures. The conducted search is effectively diversified by means of the promises concept which is based on the aspiration criteria used in tabu search approaches. The proposed algorithm was tested on UCARPP benchmark instances taken from the literature. It efficiently produced high-quality results, improving several previously best known solutions.     

Enhanced Adjacent Extreme-point Search and Tabu Search for the Minimum Concave-cost Uncapacitated Transshipment Problem

Practicable methods for optimising concave-cost, uncapacitated transshipment networks are non exact. In this paper, one such effective method, that of adjacent extreme point search, is further developed to enhance its overall computational efficiency. The enhanced search algorithm is then imbedded in a tabu search scheme which proved capable of finding better solutions, by a wide margin in some instances. Another tabu search scheme, somewhat inferior in terms of solution quality but computationally more efficient, is also developed to provide an alternative solution vehicle for larger networks. Results of extensive computational testing are included.     

Solving a minimum-power covering problem with overlap constraint for cellular network design

We consider a type of covering problem in cellular networks. Given the locations of base stations, the problem amounts to determining cell coverage at minimum cost in terms of the power usage. Overlap between adjacent cells is required in order to support handover. The problem we consider is NP-hard. We present integer linear models and study the strengths of their continuous relaxations. Preprocessing is used to reduce problem size and tighten the models. Moreover, we design a tabu search algorithm for finding near-optimal solutions effectively and time-efficiently. We report computational results for both synthesized instances and networks originating from real planning scenarios. The results show that one of the integer models leads to tight bounds, and the tabu search algorithm generates high-quality solutions for large instances in short computing time.     

A tabu search algorithm for the minmax regret minimum spanning tree problem with interval data

This paper deals with the strongly NP-hard minmax regret version of the minimum spanning tree problem with interval costs. The best known exact algorithms solve the problem in reasonable time for rather small graphs. In this paper an algorithm based on the idea of tabu search is constructed. Some properties of the local minima are shown. Exhaustive computational tests for various classes of graphs are performed. The obtained results suggest that the proposed tabu search algorithm quickly outputs optimal solutions for the smaller instances, previously discussed in the existing literature. Furthermore, some arguments that this algorithm performs well also for larger instances are provided.     

Strategic oscillation for the capacitated hub location problem with modular links

The capacitated single assignment hub location problem with modular link capacities is a variant of the classical hub location problem in which the cost of using edges is not linear but stepwise, and the hubs are restricted in terms of transit capacity rather than in the incoming traffic. We propose a metaheuristic algorithm based on strategic oscillation, a methodology originally introduced in the context of tabu search. Our method incorporates several designs for constructive and destructive algorithms, together with associated local search procedures, to balance diversification and intensification for an efficient search. Computational results on a large set of instances show that, in contrast to exact methods that can only solve small instances optimally, our metaheuristic is able to find high-quality solutions on larger instances in short computing times. In addition, the new method, which joins tabu search strategies with strategic oscillation, outperforms the previous tabu search implementation.     

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.     

An evolutionary approach for bandwidth multicoloring problems

In this paper we consider some generalizations of the vertex coloring problem, where distance constraints are imposed between adjacent vertices (bandwidth coloring problem) and each vertex has to be colored with more than one color (bandwidth multicoloring problem). We propose an evolutionary metaheuristic approach for the first problem, combining an effective tabu search algorithm with population management procedures. The approach can be applied to the second problem as well, after a simple transformation. Computational results on instances from the literature show that the overall algorithm is able to produce high quality solutions in a reasonable amount of time, outperforming the most effective algorithms proposed for the bandwidth coloring problem, and improving the best known solution of many instances of the bandwidth multicoloring problem.     

Improved tabu search algorithm for the handling of route duration constraints in vehicle routing problems with time windows

This note introduces a refinement to a previously proposed tabu search algorithm for vehicle routing problems with time windows. This refinement yields new best known solutions on a set of benchmark instances of the multi-depot, the periodic and the site-dependent vehicle routing problems with time windows.     

A hybrid metaheuristic approach to solving the UBQP problem

This paper presents a hybrid metaheuristic approach (HMA) for solving the unconstrained binary quadratic programming (UBQP) problem. By incorporating a tabu search procedure into the framework of evolutionary algorithms, the proposed approach exhibits several distinguishing features, including a diversification-based combination operator and a distance-and-quality based replacement criterion for pool updating. The proposed algorithm is able to easily obtain the best known solutions for 31 large random instances up to 7000 variables (which no previous algorithm has done) and find new best solutions for three of nine instances derived from the set-partitioning problem, demonstrating the efficacy of our proposed algorithm in terms of both solution quality and computational efficiency. Furthermore, some key elements and properties of the HMA algorithm are also analyzed.