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 Algorithm for Quadratic 0—1 Programming Problem

1.IntroductionThemathematicalmodelofaquaduatico-1programmingproblemisasfollows:MinimizesubjecttwhereI,AsfaraspaperL1'2Jcanseemedel(I)(fordu=O)isveryimPOrtantinthemarshallingofsinglegrouptrainbetweenmarshallingstationsinrailwaynetworkandthemarshallingoftraininnetw0rkwiththetw0types0fvehiclefl0w,butproblem(I)isNP-C.C0nsiderarelax-ationproblemasf0llows:MinimizeIngeneral,solvingrelaxati0nproblemiseasierthansolvingcombinatiorial0ptimalpr0b-lem,thesameaslinearpr0grammingproblemissolvableinPOly…     

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

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

Solution of the Cumulative Assignment Problem With a Well-Structured Tabu Search Method

The Cumulative Assignment Problem is an NP-complete problem obtained by substituting the linear objective function of the classic Linear Assignment Problem, with a non-linear cumulative function. In this paper we present a first attempt to solve the Cumulative Assignment Problem with metaheuristic techniques. In particular we consider two standard techniques, namely the Simulated Annealing and the Multi-Start methods, and we describe the eXploring Tabu Search: a new structured Tabu Search algorithm which uses an iterative multi-level approach to improve the search. The new method is analyzed through extensive computational experiments and proves to be more effective than the standard methods.     

双层级医疗设施选址问题及禁忌搜索算法

分级诊疗有利于充分利用已有的医疗资源,是医疗卫生体制改革的重要内容,因而在医疗设施选址时需要考虑医疗机构的层级性。本文以两个层级的医疗设施作为选址研究对象,建立了双层级多样流的混合整数规划模型。针对该模型的特点,设计了一种基于禁忌搜索的算法确定最优选址策略。最后,以上海市某区社区卫生服务中心以及区域医疗中心为研究对象,给出相应两个层级医疗设施的选址方案,并对相关参数对选址结果的影响进行了分析。算法求解结果为有就医需求的居民提供指派,使该区域的医疗资源利用率得到了提高,医疗设施配置也更加合理均衡。     

多目标定位路线问题模型及禁忌搜索算法研究

在一个完整的物流系统中,总费用和工作量平衡是影响决策的两个基本标准,拓展对员工重要的公平原则-工作量平衡,并权衡工作量与总费用之间的平衡.在此基础上,考虑了带路线分配决策的多目标定位-路线问题,建立了数学模型,采用禁忌搜索算法对模型的求解,为检验车辆多次使用的效果,针对算法设计了联立和序贯两种不同的车辆路线分配形式.算法分析结果表明:区域特征在区分算法两种形式的性能时具有重要的地位.     

A Tabu Search Algorithm for Access Network Design

We present a fast tabu search method for the design of access tree networks. We connect a population of users to a set of switches using a variety of SONET channels on fiber optics links and ADM equipment at the nodes. We specifically take into account the economies of scale provided by the transmission systems and the transmission hierarchy of SONET systems.We describe in detail the parameters used for defining neighborhoods, penalty parameters, data structure and indicate how this can lead to substantial improvements of the overall computational time while providing costs lower than those of a more straightforward method. Results are provided for a set of random cases as well as for a real network.     

求解带组换装时间单机调度问题的禁忌搜索算法

以包头某钢铁线材企业生产实际调度问题为背景,研究了一类带组换装时间的单机调度问题.由于该问题是NP难的,本文提出了一类适合该问题的禁忌搜索算法.此外,本文将问题性质引入了禁忌搜索算法以进一步提高算法寻优性能,降低算法运行时间.本文提出的算法在随机问题和实际问题上均进行了测试,实验结果表明,本文提出的算法能在不到10秒的时间内获得实际问题的一个近似最优解.     

Efficient Filtering and Tabu Search on a Consistent Neighbourhood for the Frequency Assignment Problem with Polarisation

This article presents a specific filtering algorithm for the Frequency Assignment Problem with Polarisation, which combines arc-consistency and path-inverse-consistency adapted to the specificities of the constraints. The effectiveness of this filtering algorithm enabled us to improve the Tabu Search on a Consistent Neighbourhood (CN-Tabu) using two different approaches. So, after a short recall of this general methodology and a presentation of its obtained results on the FAPP, we propose a behavioural study of the two approaches by comparing the results.     

Tabu Search for Frequency Assignment in Mobile Radio Networks

The main goal of the Frequency Assignment Problem in mobile radio networks consists of assigning a limited number of frequencies to each radio cell in a cellular network while minimizing electromagnetic interference due to the reuse of frequencies. This problem, known to be NP-hard, is of great importance in practice since better solutions will allow a telecommunications operator to manage larger cellular networks. This paper presents a new Tabu Search algorithm for this application. The algorithm is tested on realistic and large problem instances and compared with other methods based on simulated annealing, constraint programming and graph coloring algorithms. Empirical evidence shows that the Tabu algorithm is very competitive by giving the best solutions to the tested instances.     

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.     

A Tabu Search Approach for the Prize Collecting Traveling Salesman Problem

The Prize Collecting Traveling Salesman Problem is a generalization of the Traveling Salesman Problem. A salesman collects a prize for each visited city and pays a penalty for each non visited city. The objective is to minimize the sum of the travel costs and penalties, but collecting a minimum pre-established amount of prizes. This problem is here addressed by a simple, but efficient tabu search approach which had improved several upper bounds of the considered instances.     

Categorized Assignment Scheduling: a Tabu Search Approach

The assignment problem (AP) and bottleneck assignment problem (BAP) are well studied in operational research literature. In this paper we consider two related problems which simultaneously generalize both AP and BAP. Unlike AP and BAP, these generalizations are strongly NP-complete. We propose two heuristics to solve these generalized problems: one based on a greedy principle and the other based on tabu search. Computational results are presented which show that these heuristics, when used together, produce good quality solutions. Our adaptation of tabu search also gives some new insight into the application of tabu search on permutation problems.     

A hybrid Granular Tabu Search algorithm for the Multi-Depot Vehicle Routing Problem

In this paper, we propose a hybrid Granular Tabu Search algorithm to solve the Multi-Depot Vehicle Routing Problem (MDVRP). We are given on input a set of identical vehicles (each having a capacity and a maximum duration), a set of depots, and a set of customers with deterministic demands and service times. The problem consists of determining the routes to be performed to fulfill the demand of the customers by satisfying, for each route, the associated capacity and maximum duration constraints. The objective is to minimize the sum of the traveling costs related to the performed routes. The proposed algorithm is based on a heuristic framework previously introduced by the authors for the solution of the Capacitated Location Routing Problem (CLRP). The algorithm applies a hybrid Granular Tabu Search procedure, which considers different neighborhoods and diversification strategies, to improve the initial solution obtained by a hybrid procedure. Computational experiments on benchmark instances from the literature show that the proposed algorithm is able to produce, within short computing time, several best solutions obtained by the previously published methods and new best solutions.     

A Guided Tabu Search for the Vehicle Routing Problem with two-dimensional loading constraints

We present a metaheuristic methodology for the Capacitated Vehicle Routing Problem with two-dimensional loading constraints (2L-CVRP). 2L-CVRP is a generalisation of the Capacitated Vehicle Routing Problem, in which customer demand is formed by a set of two-dimensional, rectangular, weighted items. The purpose of this problem is to produce the minimum cost routes, starting and terminating at a central depot, to satisfy the customer demand. Furthermore, the transported items must be feasibly packed into the loading surfaces of the vehicles. We propose a metaheuristic algorithm which incorporates the rationale of Tabu Search and Guided Local Search. The loading aspects of the problem are tackled using a collection of packing heuristics. To accelerate the search process, we reduce the neighbourhoods explored, and employ a memory structure to record the loading feasibility information. Extensive experiments were conducted to calibrate the algorithmic parameters. The effectiveness of the proposed metaheuristic algorithm was tested on benchmark instances and led to several new best solutions.     

An Application of a Multi-Objective Tabu Search Algorithm to a Bicriteria Flowshop Problem

This paper proposes a new tabu search algorithm for multi-objective combinatorial problems with the goal of obtaining a good approximation of the Pareto-optimal or efficient solutions. The algorithm works with several paths of solutions in parallel, each with its own tabu list, and the Pareto dominance concept is used to select solutions from the neighborhoods. In this way we obtain at each step a set of local nondominated points. The dispersion of points is achieved by a clustering procedure that groups together close points of this set and then selects the centroids of the clusters as search directions. A nice feature of this multi-objective algorithm is that it introduces only one additional parameter, namely, the number of paths. The algorithm is applied to the permutation flowshop scheduling problem in order to minimize the criteria of makespan and maximum tardiness. For instances involving two machines, the performance of the algorithm is tested against a Branch-and-Bound algorithm proposed in the literature, and for more than two machines it is compared with that of a tabu search algorithm and a genetic local search algorithm, both from the literature. Computational results show that the heuristic yields a better approximation than these algorithms.     

Tabu Search heuristics for the Vehicle Routing Problem with Time Windows

This paper surveys the research on the Tabu Search heuristics for the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW can be described as the problem of designing least cost routes for a fleet of vehicles from one depot to a set of geographically scattered points. The routes must be designed in such a way that each point is visited only once by exactly one vehicle within a given time interval; all routes start and end at the depot, and the total demands of all points on one particular route must not exceed the capacity of the vehicle. In addition to describing basic features of each method, experimental results for Solomon’s benchmark test problems are presented and analyzed. This work was partially supported by the Emil Aaltonen Foundation, Liikesivistysrahasto Foundation, the Canadian Natural Science and Engineering Research Council and the TOP program funded by the Research Council of Norway. This support is gratefully acknowledged.     

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.     

非平衡交通分配的拟Frank-Wolfe迭代算法

提出了基于最短路动态生成的一种新的非平衡交通分配迭代算法.在每轮迭代中,将按全有全无方法在当前最短路上分配的交通量与前一轮迭代所得到的交通量加权组合,而各O-D对的加权系数则依据Logit原则来确定.和Frank-Wolfe算法不同,不必通过一维搜索确定加权系数.同时又避免了Logit方法要求枚举所有路径的困难.本文还证明了算法的收敛性,而计算实例显示,由本算法所得结果与平衡交通分配非常接近,因而它是一个高效而可靠的交通分配算法,适用于大、中型道路交通网络的交通分配计算.     

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.