Heuristic and exact methods for the cutting sequencing problem

Cutting stock problems deal with the generation of a set of cutting patterns that minimizes waste. Sometimes it is also important to find the processing sequence of this set of patterns to minimize the maximum queue of partially cut orders. In such instances a cutting sequencing problem has to be solved. This paper presents a new mathematical model and a three-phase approach for the cutting sequencing problem. In the first phase, a greedy algorithm produces a good starting solution that is improved in the second phase by a tabu search, or a generalized local search procedure, while, in the last phase, the problem is optimally solved by an implicit enumeration procedure that uses the best solution previously found as an upper bound. Computing experience, based on 300 randomly generated problems, shows the good performance of the heuristic methods presented.     

Tabu search for graph partitioning

In this paper, we develop a tabu search procedure for solving the uniform graph partitioning problem. Tabu search, an abstract heuristic search method, has been shown to have promise in solving several NP-hard problems, such as job shop and flow shop scheduling, vehicle routing, quadratic assignment, and maximum satisfiability. We compare tabu search to other heuristic procedures for graph partitioning, and demonstrate that tabu search is superior to other solution approaches for the uniform graph partitioning problem both with respect to solution quality and computational requirements.     

A hybrid tabu search based heuristic for the periodic distribution inventory problem with perishable goods

Most of the research on integrated inventory and routing problems ignores the case when products are perishable. However, considering the integrated problem with perishable goods is crucial since any discrepancy between the routing and inventory cost can double down the risk of higher obsolescence costs due to the limited shelf-life of the products. In this paper, we consider a distribution problem involving a depot, a set of customers and a homogeneous fleet of capacitated vehicles. Perishable goods are transported from the depot to customers in such a way that out-of-stock situations never occur. The objective is to simultaneously determine the inventory and routing decisions over a given time horizon such that total transportation cost is minimized. We present a new “arc-based formulation” for the problem which is deemed more suitable for our new tabu search based approach for solving the problem. We perform a thorough sensitivity analysis for each of the tabu search parameters individually and use the obtained gaps to fine-tune the parameter values that are used in solving larger sized instances of the problem. We solve different sizes of randomly generated instances and compare the results obtained using the tabu search algorithm to those obtained by solving the problem using CPLEX and a recently published column generation algorithm. Our computational experiments demonstrate that the tabu search algorithm is capable of obtaining a near-optimal solution in less computational time than the time required to solve the problem to optimality using CPLEX, and outperforms the column generation algorithm for solving the “path flow formulation” of the problem in terms of solution quality in almost all of the considered instances.     

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.     

A hybrid algorithm for the manufacturing cell formation problem

In this paper we compare different heuristic methods for the manufacturing cell formation problem considering part process sequence: a GRASP algorithm, a reactive GRASP algorithm and a hybrid algorithm which combines reactive GRASP and tabu search. All algorithms are tested with a set of instances from the literature. The results from the GRASP algorithm are compared to those of the reactive GRASP in order to evaluate the advantages of automatically adjusting the parameter value within the randomized greedy procedure. Also the reactive GRASP results are compared to those of the hybrid algorithm to evaluate the contribution to solution quality of replacing the local search phase of the GRASP algorithm with tabu search.     

Backbone guided tabu search for solving the UBQP problem

We propose a backbone-guided tabu search (BGTS) algorithm for the Unconstrained Binary Quadratic Programming (UBQP) problem that alternates between two phases: (1) a basic tabu search procedure to optimize the objective function as far as possible; (2) a strategy using the TS notion of strongly determined variables to alternately fix and free backbone components of the solutions which are estimated likely to share values in common with an optimal solution. Experimental results show that the proposed method is capable of finding the best-known solutions for 21 large random instances with 3000 to 7000 variables and boosts the performance of the basic TS in terms of both solution quality and computational efficiency.     

A framework for analyzing sub-optimal performance of local search algorithms

This paper presents a framework for analyzing and comparing sub-optimal performance of local search algorithms for hard discrete optimization problems. The β-acceptable solution probability is introduced that captures how effectively an algorithm has performed to date and how effectively an algorithm can be expected to perform in the future. Using this probability, the necessary conditions for a local search algorithm to converge in probability to β-acceptable solutions are derived. To evaluate and compare the effectiveness of local search algorithms, two estimators for the expected number of iterations to visit a β-acceptable solution are obtained. Computational experiments are reported with simulated annealing and tabu search applied to four small traveling salesman problem instances, and the Lin-Kernighan-Helsgaun algorithm applied to eight medium to large traveling salesman problem instances (all with known optimal solutions), to illustrate the application of these estimators.     

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.     

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.     

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.     

Scatter tabu search for multiobjective clustering problems

We propose a hybrid heuristic procedure based on scatter search and tabu search for the problem of clustering objects to optimize multiple criteria. Our goal is to search for good approximations of the efficient frontier for this class of problems and provide a means for improving decision making in multiple application areas. Our procedure can be viewed as an extension of SSPMO (a scatter search application to nonlinear multiobjective optimization) to which we add new elements and strategies specially suited for combinatorial optimization problems. Clustering problems have been the subject of numerous studies; however, most of the work has focused on single-objective problems. Clustering using multiple criteria and/or multiple data sources has received limited attention in the operational research literature. Our scatter tabu search implementation is general and tackles several problems classes within this area of combinatorial data analysis. We conduct extensive experimentation to show that our method is capable of delivering good approximations of the efficient frontier for improved analysis and decision making.     

An integrated tabu search algorithm for the lot streaming problem in job shops

In this paper, we focus on solving the lot streaming problem in a job shop environment, where consistent sublots are considered. The presented three-phase algorithm incorporates the predetermination of sublot sizes, the determination of schedules based on tabu search and the variation of sublot sizes. With regard to tabu search implementation, a constructive multi-level neighbourhood is developed, which effectively connects three isolated neighbourhood functions. Moreover, enhancements of the basic version of tabu search are conducted. Combined with the procedure for varying sublot sizes, the algorithm further exploits the improvement potential. All tested instances show a rapid convergence to their lower bounds. The well-known difficult benchmark problems also achieve substantial makespan reduction. In addition, the performance of specific components is intensively examined in our study.     

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.     

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

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

Tabu search for discrete–continuous scheduling problems with heuristic continuous resource allocation

Problems of scheduling non-preemptable, independent jobs on parallel identical machines under an additional continuous renewable resource to minimize the makespan are considered. Each job simultaneously requires for its processing a machine and an amount (unknown in advance) of the continuous resource. The processing rate of a job depends on the amount of the resource allotted to this job at a time. The problem is to find a sequence of jobs on machines and, simultaneously, a continuous resource allocation that minimize the makespan. A heuristic procedure for allocating the continuous resource is used. The tabu search metaheuristic to solve the considered problem is presented. The results produced by tabu search are compared with optimal solutions for small instances, as well as with the results generated by simple search methods – multi-start iterative improvement and random sampling for larger instances.     

Bike sharing systems: Solving the static rebalancing problem

This paper deals with a new problem that is a generalization of the many to many pickup and delivery problem and which is motivated by operating self-service bike sharing systems. There is only one commodity, initially distributed among the vertices of a graph, and a capacitated single vehicle aims to redistribute the commodity in order to reach a target distribution. Each vertex can be visited several times and also can be used as a buffer in which the commodity is stored for a later visit. This problem is NP-hard, since it contains several NP-hard problems as special cases (the TSP being maybe the most obvious one). Even finding a tractable exact formulation remains problematic.This paper presents efficient algorithms for solving instances of reasonable size, and contains several theoretical results related to these algorithms. A branch-and-cut algorithm is proposed for solving a relaxation of the problem. An upper bound of the optimal solution of the problem is obtained by a tabu search, which is based on some theoretical properties of the solution, once fixed the sequence of the visited vertices. The possibility of using the information provided by the relaxation receives a special attention, both from a theoretical and a practical point of view. It is proven that to build a feasible solution of the problem by using the one obtained by the relaxation is an NP-hard problem. Nevertheless, a tabu search initialized with the optimal solution of the relaxation often shows that it is the optimal one.The algorithms have been tested on a set of instances coming from the literature, proving their effectiveness.     

A tabu search heuristic procedure for the capacitated facility location problem

A tabu search heuristic procedure is developed, implemented and computationally tested for the capacitated facility location problem. The procedure uses different memory structures. Visited solutions are stored in a primogenitary linked quad tree. For each facility, the recent move at which the facility changed its status and the frequency it has been open are also stored. These memory structures are used to guide the main search process as well as the diversification and intensification processes. Lower bounds on the decreases of total cost are used to measure the attractiveness of the moves and to select moves in the search process. A specialized network algorithm is developed to exploit the problem structure in solving transportation problems. Criterion altering, solution reconciling and path relinking are used to perform intensification functions. The performance of the procedure is tested through computational experiments using test problems from the literature and new test problems randomly generated. It found optimal solutions for almost all test problems from the literature. As compared to the heuristic method of Lagrangean relaxation with improved subgradient scheme, the tabu search heuristic procedure found much better solutions using much less CPU time.     

A cooperative parallel tabu search algorithm for the quadratic assignment problem

In this study, we introduce a cooperative parallel tabu search algorithm (CPTS) for the quadratic assignment problem (QAP). The QAP is an NP-hard combinatorial optimization problem that is widely acknowledged to be computationally demanding. These characteristics make the QAP an ideal candidate for parallel solution techniques. CPTS is a cooperative parallel algorithm in which the processors exchange information throughout the run of the algorithm as opposed to independent concurrent search strategies that aggregate data only at the end of execution. CPTS accomplishes this cooperation by maintaining a global reference set which uses the information exchange to promote both intensification and strategic diversification in a parallel environment. This study demonstrates the benefits that may be obtained from parallel computing in terms of solution quality, computational time and algorithmic flexibility. A set of 41 test problems obtained from QAPLIB were used to analyze the quality of the CPTS algorithm. Additionally, we report results for 60 difficult new test instances. The CPTS algorithm is shown to provide good solution quality for all problems in acceptable computational times. Out of the 41 test instances obtained from QAPLIB, CPTS is shown to meet or exceed the average solution quality of many of the best sequential and parallel approaches from the literature on all but six problems, whereas no other leading method exhibits a performance that is superior to this.     

Solving the CLSP by a Tabu Search Heuristic

The multi-item, single-level, capacitated, dynamic lot-sizing problem, commonly abbreviated as CLSP, is considered. The problem is cast in a tight mixed-integer programming model (MIP); tight in the sense that the gap between the optimal value of MIP and that of its linear programming relaxation (LP) is small. The LP relaxation of MIP is then solved by column generation. The resulting feasible solution is further improved by adopting the corresponding set-up schedule and re-optimizing variable costs by solving a minimum-cost network flow (trans-shipment) problem. Subsequently, the improved solution is used as a starting solution for a tabu search procedure, with the worth of moves assessed using the same trans-shipment problem. Results of computational testing of benchmark problem instances are presented. They show that the heuristic solutions obtained are effective, in that they are extremely close to the best known solutions. The computational efficiency makes it possible to solve realistically large problem instances routinely on a personal computer; in particular, the solution procedure is most effective, in terms of solution quality, for larger problem instances.     

A metaheuristic for the vehicle-routeing problem with soft time windows

This paper develops a metaheuristic for the vehicle-routeing and scheduling problem with soft time window constraints. A tabu search solution method is developed, which utilizes a mixed neighbourhood structure and an advanced recovery procedure to generate high-quality solutions. Computational results on test problems from the literature are reported. The metaheuristic achieves solutions that compare favourably with previously reported results.