An incremental tabu search heuristic for the generalized vehicle routing problem with time windows

This paper describes an incremental neighbourhood tabu search heuristic for the generalized vehicle routing problem with time windows. The purpose of this work is to offer a general tool that can be successfully applied to a wide variety of specific problems. The algorithm builds upon a previously developed tabu search heuristic by replacing its neighbourhood structure. The new neighbourhood is exponential in size, but the proposed evaluation procedure has polynomial complexity. Computational results are presented and demonstrate the effectiveness of the approach.     

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.     

Search Heuristics for Resource Constrained Project Scheduling

We develop a search procedure for project scheduling problems with multiple resource constraints as well as precedence constraints. The procedure is applied to three popular search heuristics, simulated annealing, tabu search and genetic algorithms. In the heuristics, a solution is represented with a string of numbers each of which denotes priority of each activity. The priorities are used to select an activity for scheduling among competing ones. The search heuristics with this encoding method can always generate feasible neighbourhood solutions for a given solution. Moreover, this encoding method is very flexible in that problems with objective functions of a general functional form (such as a nonlinear function) and complex constraints can be considered without much difficulty. Results of computational tests on the performance of the search heuristics showed that the search heuristics, especially the simulated annealing and tabu search algorithms worked better than existing heuristics.     

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.     

Evaluating the performance of tabu search procedures for flow shop sequencing

We address the problem of minimising makespan in a flow shop by using tabu search procedures. By combining different neighbourhood structures, neighbourhood examinations, and stopping conditions we obtain alternative tabu search procedures. Starting from a common initial solution we evaluate the relative performance of such procedures considering both the solution quality and computational effort.     

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.     

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.     

Heuristics for multiple facility location in a network using the variance criterion

In cyclic networks the p-variance location problem is NP-hard, and therefore it is suitable to use heuristic methods to find approximate solutions to the problem. To this end, two strategies are explored, the first using combinatorial search procedures over the vertex set, whereas the second searches for the solution over the entire network. The initial vertex set solutions are generated by using tabu search, variable neighbourhood search and interchange procedures. The heuristics have been tested on instances of up to 30 vertices and 70 edges, and their performances compared.     

A tabu search heuristic for the generalized minimum spanning tree problem

This paper describes an attribute based tabu search heuristic for the generalized minimum spanning tree problem (GMSTP) known to be NP-hard. Given a graph whose vertex set is partitioned into clusters, the GMSTP consists of designing a minimum cost tree spanning all clusters. An attribute based tabu search heuristic employing new neighborhoods is proposed. An extended set of TSPLIB test instances for the GMSTP is generated and the heuristic is compared with recently proposed genetic algorithms. The proposed heuristic yields the best results for all instances. Moreover, an adaptation of the tabu search algorithm is proposed for a variation of the GMSTP in which each cluster must be spanned at least once.     

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.     

A priority list based heuristic for the job shop problem

A priority list for the job shop scheduling problem is defined to be any permutation of a set of symbols where the symbol for each job appears as many times as the number of its operations. Every priority list can be associated in a natural way with a feasible schedule, and every feasible schedule arises in this way. Priority lists are therefore a representation of feasible schedules that avoid the problems normally associated with schedule infeasibility. As a result, the three ingredients of local search heuristics, namely picking initial starting schedules, constructing search neighbourhoods and computing makespans, become faster and easier when performed in the space of priority lists rather than in the space of feasible schedules. As an illustration of their usefulness, a priority list based simulated annealing heuristic is presented, which, although simple, is competitive with the current leading schedule based simulated annealing and tabu search heuristics.     

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 tour construction heuristic for the travelling salesman problem

The tour construction heuristic that generates initial tours for the tour improvement heuristics plays an important role in solving the travelling salesman problem (TSP). With the help of an effective tour construction heuristic, the performance of a heuristic can be improved. In this study we present a new tour construction algorithm, the construction priority (CP). We incorporate the performance of the CP into metaheuristics such as tabu search, genetic algorithm, space smoothing, and noising methods. The performance of the CP is empirically compared with the nearest neighbour (NN) approach. Extensive computational comparison shows that the CP is considerably more effective compared to NN.     

Using tabu search to schedule activities of stochastic resource-constrained projects

In this paper, a higher level heuristic procedure “tabu search” is proposed to provide good solutions to resource-constrained, randomized activity duration project scheduling problems. Our adaptation of tabu search uses multiple tabu lists, randomized short-term memory, and multiple starting schedules as a means of search diversification. The proposed method proves to be an efficient way to find good solutions to both deterministic and stochastic problems. For the deterministic problems, most of the optimal schedules of the test projects investigated are found. Computational results are presented which establish the superiority of tabu search over the existing heuristic algorithms.     

Reactive tabu adaptive memory programming search for the vehicle routing problem with backhauls

A heuristic approach based on a hybrid operation of reactive tabu search (RTS) and adaptive memory programming (AMP) is proposed to solve the vehicle routing problem with backhauls (VRPB). The RTS is used with an escape mechanism which manipulates different neighbourhood schemes in a sophisticated way in order to get a continuously balanced intensification and diversification during the search process. The adaptive memory strategy takes the search back to the unexplored regions of the search space by maintaining a set of elite solutions and using them strategically with the RTS. The AMP feature brings an extra robustness to the search process that resulted in early convergence when tested on most of the VRPB instances. We compare our algorithm against the best methods in the literature and report new best solutions for several benchmark problems.     

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.     

Simple assembly line balancing—Heuristic approaches

In this paper heuristics for Type 1 and Type 2 of the Simple Assembly Line Balancing Problem (SALBP) are described. Type 1 of SALBP (SALBP-1) consists of assigning tasks to work stations such that the number of stations is minimized for a given production rate whereas Type 2 (SALBP-2) is to maximize the production rate, or equivalently, to minimize the sum of idle times for a given number of stations. In both problem types, precedence constraints between the tasks have to be considered.We describe bidirectional and dynamic extensions to heuristic priority rules widely used for SALBP-1. For the solution of SALBP-2 we present search methods which involve the repetitive application of procedures for SALBP-1. Furthermore, improvement procedures for SALBP-2 are developed and combined with tabu search, a recent strategy to overcome local optimality. Several optional elements of tabu search are discussed. Finally, the application of a nontraditional tabu search approach to solve SALBP-1 is investigated. Computational experiments validate the effectiveness of our new approaches.     

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.     

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.     

Complete Local Search with Memory

Neighborhood search heuristics like local search and its variants are some of the most popular approaches to solve discrete optimization problems of moderate to large size. Apart from tabu search, most of these heuristics are memoryless. In this paper we introduce a new neighborhood search heuristic that makes effective use of memory structures in a way that is different from that in common implementations of tabu search. We report computational experiments with this heuristic on the traveling salesperson problem and the subset sum problem.