Search

Metaheuristic algorithms are widely recognized as one of the most practical approaches for combinatorial optimization problems. Among representative metaheuristics are genetic algorithms, simulated annealing, tabu search, and so on. In this paper, we explain essential ideas used in such metaheuristic algorithms within a generalized framework of local search. We then conduct numerical experiments of metaheuristic algorithms using rather simple implementations, to observe general tendencies of their performance. From these results, we propose a few recommendations about the use of metaheuristics as simple optimization tools. We also mention some advanced techniques to enhance the ability of metaheuristics. Finally, we summarize some theoretical results on metaheuristic algorithms. © 2001 Scripta Technica, Syst Comp Jpn, 32(3): 33–55, 2001

Multi-story mechanical parking facilities are becoming popular in crowded cities, as they are spatially efficient. When many cars are waiting to enter or to leave, it is important to schedule the movement of two rail-mounted automated carriers on each floor so that the makespan is minimized. We consider the problem of finding an optimal schedule when an ordered set of car placing and car removing is given. We propose an exact algorithm based on dynamic programming, and approximate algorithms using metaheuristics.

For problems SAT and MAX SAT, local search algorithms are widely acknowledged as one of the most effective approaches. Most of the local search algorithms are based on the 1-flip neighborhood, which is the set of solutions obtainable by flipping the truth assignment of one variable. In this paper, we consider r-flip neighborhoods for r ≥ 2, and propose, for r = 2, 3, new implementations that reduce the number of candidates in the neighborhood without sacrificing the solution quality. For 2-flip (resp., 3-flip) neighborhood, we show that its expected size is O(n + m) (resp., O(m + t2n)), which is usually much smaller than the original size O(n2) (resp., O(n3)), where n is the number of variables, m is the number of clauses and t is the maximum number of appearances of one variable. Computational results tell that these estimates by the expectation well represent the real performance.

In this paper, we propose a variable depth search (VDS) algorithm for the generalized assignment problem (GAP), which is one of the representative combinatorial optimization problems, and is known to be NP-hard. The VDS is a generalization of the local search. The main idea of VDS is to change the size of the neighborhood adaptively so that the algorithm can effectively traverse larger search space within reasonable computational time. In our previous paper (M. Yagiura, T. Yamaguchi and T. Ibaraki, “A variable depth search algorithm for the generalized assignment problem,” Proc. 2nd Metaheuristics International Conference (MIC97), 1997 129-130 (full version is to appear in the post-conference book)), we proposed a simple VDS algorithm for the GAP, and obtained good results. To further improve the performance of the VDS, we examine the effectiveness of incorporating branching search processes to construct the neighborhoods. Various types of branching rules are examined, and it is observed that appropriate ...

Many real life optimization problems do not have accurate estimates of the problem parameters at the optimization phase. For this reason, the min-max regret criteria are widely used to obtain robust solutions. In this paper we consider the generalized assignment problem (GAP) with min-max regret criterion under interval costs. We show that the decision version of this problem is Σp 2 -complete. We present two heuristic methods: a fixed-scenario approach and a dual substitution algorithm. For the fixed-scenario approach, we show that solving the classical GAP under a median-cost scenario leads to a solution of the min-max regret GAP whose objective function value is within twice the optimal value. We also propose exact algorithms, including a Benders' decomposition approach and branch-and-cut methods which incorporate various methodologies, including Lagrangian relaxation and variable fixing. The resulting Lagrangian-based branch-and-cut algorithm performs satisfactorily on benchmark instances.

In a new system of container terminal, its yard is divided into buffer area and stack area in order to separate ship loading/unloading and yard operations. Such a system then necessitates the shift operations between buffer areas and stack areas; import containers are moved from buffer area to stack area and export containers are moved from stack area to buffer area by two RMGs which travel on the same rails. As a result of analyzing the movements of two RMGs, which may interfere each other, we have reduced the scheduling problem of shift operations into two graph theoretical problems, paring problem and sequencing problem, where the paring problem is the maximum weight matching problem with degree constraints and the sequencing problem is a problem of seeking a shortest path that visits a given number of nodes, both of which have been studied in operations research. Furthermore, to deal with multilayer stacks of containers, the scheduling period is decomposed into overlapping subperiods, to which the above scheduling algorithm is applied. The resulting algorithm shows good performance in both quality of solutions and computational speed, and will be in operation in a real system of container terminal from April 1996.

To deal with computationally hard problems, approximate algorithms are used to provide reasonably good solutions in practical time. Genetic algorithms are an example of the meta-heuristics which were recently introduced and which have been successfully applied to a variety of problems. We propose to use dynamic programming in the process of obtaining new generation solutions in the genetic algorithm, and call it a genetic DP algorithm. To evaluate the effectiveness of this approach, we choose three representative combinatorial optimization problems, the single machine scheduling problem, the optimal linear arrangement problem and the traveling salesman problem, all of which ask to compute optimum permutations of n objects and are known to be NP-hard. Computational results for randomly generated problem instances exhibit encouraging features of genetic DP algorithms.

We consider the two-dimensional cutting stock problem that arises in many applications in industries. In recent industrial applications, it is argued that the setup cost for changing patterns becomes more dominant and it is impractical to use many different cutting patterns. Therefore, we consider the pattern restricted two-dimensional cutting stock problem, in which the total number of applications of cutting patterns is minimized while the number of different cutting patterns is given as a parameter n. For this problem, we develop local search algorithms. As the neighborhood size plays a crucial role in determining the efficiency of local search, we propose to use linear programming techniques for the purpose of restricting the number of solutions in the neighborhood. In this process, to generate a cutting pattern, it is required to place all the given products (rectangles) into the stock sheet (two-dimensional area) without mutual overlap. For this purpose, we develop a heuristic algorithm using an existing rectangle packing algorithm with the sequence pair coding scheme. Finally, we generate random test instances of this problem and conduct computational experiments, to evaluate the effectiveness of the proposed algorithms.

Preface.- Metaheuristic Agent Processes (MAPs).- GRASP with Path-Relinking: Recent advances and applications.- A Tabu Search Heuristic for a University Timetabling Problem.- An Investigation of Automated Planograms Using a Simulated Annealing Based Hyper-Heuristic.- Validation and Optimization of an Elevator Simulation Model with Modern Search Heuristics.- Multi-Objective Hyper-Heuristic Approaches for Space Allocation and Timetabling.- Theory and Practice of the Minimum Shift Design Problem.- Local Search Algorithms for the Two-Dimensional Cutting Stock Problem with a Given Number of Different Patterns.- A Generic Object-Oriented Tabu Search Framework.- Bi-Objective Sequencing of Cutting Patterns: An application for the paper industry.- Metaheuristics Approach for Rule Acquisition in Flexible Shop Scheduling Problems.- Predicting Colorectal Cancer Recurrence: A hybrid neural Networks-based approach.- A Constructive Genetic Approach to Point-Feature Cartographic Label Placement.- Parallel Strategies for GRASP with Path-Relinking.- Speeding Up Local Search Neighborhood Evaluation for a Multi-Dimensional Knapsack Problem.- Computationally Difficult Instances for the Uncapacitated Facility Location Problem.- Consistent Neighborhood in a Tabu Search.- Constraint Oriented Neighborhoods - A New Search Strategy in Metaheuristics.

As the setup cost of cutting patterns becomes more important in modern cutting industry, we consider the pattern restricted one dimensional cutting stock problem (1D-PRP), in which the number of stock rolls is minimized while the number of different cutting patterns is constrained within a bound given by a program parameter. For this problem, we propose a new heuristic algorithm based on local search, and incorporate a heuristic algorithm that provides a small subset of neighborhood which tends to contain good solutions in the original neighborhood. According to our computational experiments, the proposed algorithm attains a wide variety of good solutions which are comparable to the existing heuristic approaches for the one dimensional cutting stock problem (without pattern restriction).

One of the attractive features of recent metaheuristics is in its robustness and simplicity. To investigate this direction, the single machine scheduling problem is solved by various metaheuristics, such as random multi start local search (MLS), genetic algorithm (GA), simulated annealing (SA) and tabu search (TS), using rather simple inside operators. The results indicate that: (1) simple implementation of MLS is usually competitive with (or even better than) GA; (2) GA combined with local search is quite effective if longer computational time is allowed, and its performance is not sensitive to crossovers; (3) SA is also quite effective if longer computational time is allowed, and its performance is not much dependent on parameter values; (4) there are cases in which TS is more effective than MLS, however, its performance depends on how to define the tabu list and parameter values; and (5) the definition of neighborhood is very important for all of MLS, SA and TS.

A variable depth search procedure (abbreviated as VDS) is a generalization of the local search method, which was first successfully applied by Lin and Kernighan to the traveling salesman problem and the graph partitioning problem. The main idea is to adaptively change the size of a neighborhood so that it can effectively traverse a larger search space while keeping the amount of computational time reasonable. In this paper, we propose a heuristic algorithm based on VDS for the generalized assignment problem, which is one of the representative combinatorial optimization problems known to be NP-hard. To the authors’ knowledge, most of the previously proposed algorithms (with some exceptions) conduct the search within the feasible region; however, there are instances for which the search within the feasible region is not advantageous because the feasible region is very small or is combinatorially complicated to search. Therefore, we allow our algorithm to search within the infeasible region as well. We also incorporate an adaptive use of two different neighborhoods, shift and swap, within the sequence of neighborhood moves in VDS. Computational experiments exhibit good prospects of the proposed algorithm.

One of the attractive features of recent metaheuristics is in its robustness and simplicity. To investigate this direction, the single machine scheduling problem is solved by various genetic algorithms (GA) and random multi-start local search algorithms (MLS), using rather simple definitions of neighbors, mutations and crossovers. The results indicate that: (1) the performance of GA is not sensitive about crossovers if implemented with mutations, (2) simple implementation of MLS is usually competitive with (or even better than) GA, (3) GRASP type modification of MLS improves its performance to some extent, and (4) G A combined with local search is quite effective if longer computational time is allowed.