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 Improved Petal Heuristic for the Vehicle Routeing Problem

Solutions produced by the first generation of heuristics for the vehicle routeing problem are often far from optimal. Recent adaptations of local search improvement heuristics, like tabu search, produce much better solutions but require increased computing time. However there are situations where good solutions must be obtained quickly. The algorithm proposed in this paper yields solutions almost as good as those produced by tabu search adaptations, but at only a small fraction of their computing time. This heuristic can be seen as an improved version of the original petal heuristic. On 14 benchmark test problems, the proposed heuristic yields solutions whose values lie on average within 2.38% of that of the best known solutions.     

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.     

An effective heuristic for minimising makespan on unrelated parallel machines

Scheduling independent tasks on unrelated machines is a relatively difficult and challenging problem. In this paper, we develop a tabu search based heuristic for minimising makespan for the above problem that can provide good quality solutions for practical size problems within a reasonable amount of computational time. Our adaptation of this tabu search uses hashing to control the tabu restrictions of the search process and requires fewer critical parameters than many of the common tabu search approaches employed for combinatorial optimisation. Hashing is simple to implement and very effective in providing a near-optimal solution. Computational results are presented to demonstrate the effectiveness of the proposed heuristic.     

A neighbourhood scheme with a compressed solution space for the early/tardy scheduling problem

The single machine, distinct due date, early/tardy machine scheduling problem closely models the situation faced by Just-In-Time manufacturers. This paper develops a new method of finding good quality solutions to this scheduling problem by using the concept of a ‘compressed solution space’, based on a binary representation of the early/tardy scheduling problem, and tabu search. A heuristic which simultaneously sequences and schedules the jobs is developed to perform the conversion between the compressed and physical solution spaces. Results show that the compressed solution space performs well with small problems, and is superior to standard tabu search solution spaces for large-scale, realistically sized problems.     

Heuristics for a coupled-operation scheduling problem

In this paper, we study a strongly NP-hard single machine scheduling problem in which each job consists of two operations that are separated by a time delay which lies within a specified range. The objective is to minimize the makespan. Determining the feasibility and, if applicable, makespan of any proposed permutation of the operations is non-trivial, requiring a longest path algorithm with O(n²) complexity for each permutation. Several heuristic algorithms are proposed: a deterministic and randomized construction algorithm, three descent algorithms and two reactive tabu search algorithms. The local search algorithms use a first improvement neighbourhood and mainly visit only feasible solutions within the search space. Results of extensive computational tests are reported, showing that the heavy computational burden of testing potential solutions renders the local search algorithms uncompetitive in comparison to the construction algorithms. The iterated descent algorithm performs least well.     

A priority list based heuristic for the job shop problem: part 2 tabu search

Following a recent paper by the same author, a priority list-based tabu search heuristic is compared with the leading schedule-based tabu search heuristic of Nowicki and Smutnicki. More search neighbourhoods are required to achieve a given average makespan, but each priority list neighbourhood is searched much faster than the corresponding neighbourhood in the space of feasible schedules. Priority list-based tabu search therefore outperforms schedule-based tabu search in terms of elapsed CPU time.     

A Tabu Search Algorithm for the Resource-Constrained Assignment Problem

Efficient algorithms are availabe to solve the unconstrained assignment problem. However, when resource or budgetary restrictions are imposed, the problem becomes difficult to solve. We consider such a resource-constrained assignment problem and present a tabu search heuristic to solve it. Extensive computational results are presented which establish the superiority of the proposed algorithm over the existing algorithms. Our adaptation of tabu search uses strategic oscillation, randomized short-term memory and multiple start as a means of search diversification.     

Routing and scheduling in project shipping

Tramp shipping companies are committed to transport a set of contracted cargoes and try to derive additional revenue from carrying optional spot cargoes. Here, we present a real life ship routing and scheduling problem for a shipping company operating in project shipping, a special segment of tramp shipping. This segment differs from more traditional tramp segments, as the cargoes are usually transported on a one-time basis. Because of the special nature of the cargoes, complicating requirements regarding stowage onboard the ships and cargo coupling must be considered while determining routes and schedules for the ships in the fleet. A mathematical model is presented and a tabu search heuristic is proposed to solve the problem. Computational results show that the tabu search heuristic provides optimal or near-optimal solutions in a reasonable amount of time, and that it can give significant improvements to manual planning for the shipping company.     

A tabu search algorithm for solving economic lot scheduling problem

The economic lot scheduling problem has driven considerable amount of research. The problem is NP-hard and recent research is focused on finding heuristic solutions rather than searching for optimal solutions. This paper introduces a heuristic method using a tabu search algorithm to solve the economic lot scheduling problem. Diversification and intensification schemes are employed to improve the efficiency of the proposed Tabu search algorithm. Experimental design is conducted to determine the best operating parameters for the Tabu search. Results show that the tabu search algorithm proposed in this paper outperforms two well known benchmark algorithms.     

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.     

An empirical study of a new metaheuristic for the traveling salesman problem

We present a deceptively simple, yet empirically powerful metaheuristic, called jump search, for solving traveling salesman problems that has been found to be more effective than tabu search on both random and benchmark test problems from the literature. While the underlying philosophy of jump search — applying local search from different starting points — has been discussed in the literature previously (using random starting points), the use of construction-based heuristic solutions has heretofore not been considered. Extensive empirical analysis shows the method to be surprisingly effective vis a vis a randomized strategy and in comparison with tabu search. The approach is quite robust and suggests that a systematic search among neighborhoods of good, not random, solutions provides distinct advantages. This suggests that further research be focused on better construction heuristics and hybrid schemes that incorporate jump search in, for example, tabu search.     

A divide and merge heuristic for the multiprocessor scheduling problem with sequence dependent setup times

This article proposes lower bounds, as well as a divide and merge heuristic for the multiprocessor scheduling problem with sequence dependent setup times (MSPS). The heuristic is tested on randomly generated instances and compared with a previously published tabu search algorithm. Results show that the proposed heuristic is much faster than tabu search while providing similar quality solutions.     

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.     

Single machine scheduling with sequence-dependent family setups to minimize maximum lateness

Motivated by a real-life scheduling problem in a steel wire factory in China,this paper considers the single machine scheduling problem with sequence-dependent family setup times to minimize maximum lateness. In view of the NP-hard nature of the problem, structural (dominance and neighbourhood)properties of the problem are described and used in the tabu search algorithms to find optimal or near-optimal schedules. These proposed structural properties quickly exclude unpromising and/or non-improving neighbours from further search.Empirical results on the randomly generated and real-life problem instances from a factory in China show that the proposed heuristic algorithms utilizing the structural properties can obtain optimal or near optimal solutions with a reasonable computational effort.     

Heuristic Techniques for Single Line Train Scheduling

Optimising a train schedule on a single line track is known to be NP-Hard with respect to the number of conflicts in the schedule. This makes it difficult to determine optimum solutions to real life problems in reasonable time and raises the need for good heuristic techniques. The heuristics applied and compared in this paper are a local search heuristic with an improved neighbourhood structure, genetic algorithms, tabu search and two hybrid algorithms. When no time constraints are enforced on solution time, the genetic and hybrid algorithms were within five percent of the optimal solution for at least ninety percent of the test problems.     

A methodology to create robust job rotation schedules

This research proposes a methodology for developing robust job rotation schedules to reduce the likelihood of low back injury due to lifting. We consider settings that have uncertain task demands and different worker profiles in order to simulate real settings. We begin by considering deterministic versions of the problem and solve these using mathematical programming. Because mathematical programming cannot be readily applied to stochastic versions of the problem, heuristic solution methods are developed. The effectiveness of these methods is demonstrated by comparing the results with provably optimal solutions from the deterministic problems and with an enumerative approach that is applied to the stochastic version of the problem. Across the test problems, the proposed heuristics are effective at finding good job rotation solutions. The proposed methods could also be applied to solve other job rotation objectives such as maximizing productivity and reducing exposure to other work environmental factors such as excessive noise.     

混合启发式算法求解多配送人员车辆路径问题

为解决带时间窗和多配送人员的车辆路径问题,本文采用混合启发式算法对其进行求解。该算法主要由整数规划重组、局部搜索算法和模拟退火算法三部分组成。在算法中,整数规划重组有效提高了解的质量,局部搜索算法和模拟退火算法保证了算法搜索的深入性和广泛性。通过与CPLEX和禁忌搜索算法进行对比,证实了混合启发式算法实用价值更高,求解效果更好。     

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 Based Procedure for Solving the 0-1 MultiObjective Knapsack Problem: The Two Objectives Case

We consider in this paper the solving of 0-1 knapsack problems with multiple linear objectives. We present a tabu search approach to generate a good approximation of the efficient set. The heuristic scheme is included in a redu tion decision space framework. The case of two objectives is developed in this paper. TS principles viewed into the multiobjective context are discussed. According to a prospective way, several variations of the algorithm are investigate. Numerical experiments are reported and compared with available exact efficient solutions. Intuitive justifications for the observed empirical behavior of the procedure and open questions are discussed.