Search

This chapter reviews heuristic and metaheuristic algorithms for generalized assignment problem and explores the problem formally and introduces some related problems and their complexities. It explains basic strategies of greedy method and local search and describes Lagrangian relaxation problems. The chapter provides some basic ideas of Lagrangian heuristics and also describes the basics of branch-and-bound. It analyses some computational results of various metaheuristic algorithms and branch-and-bound methods. The chapter focuses on polynomial-time approximation algorithms with performance guarantees. There are several useful tools used to design approximation algorithms. Metaheuristic algorithms are widely recognized as one of the most practical approaches for hard combinatorial optimization problems. Algorithm path relinking with ejection chains applies ejection chains probes to solutions generated by path relinking, which is a methodology to generate solutions from two or more solutions.

ILS and GDA metaheuristics for the linear ordering problem are introduced.They are able to tackle large instances in line with real applications.Introduced methods are the first of their kind ever applied to large-sized instances.All best known solutions of the large-sized instances are improved. This paper presents iterated local search and great deluge trajectory metaheuristics for the linear ordering problem (LOP). Both metaheuristics are based on the TREE local search method introduced in Sakuraba and Yagiura (2010) that is the only method ever applied to a set of large-sized instances that are in line with the scale of nowadays real applications. By providing diversification and intensification features, the introduced methods improve all best known solutions of the large-sized instances set. Extensive numerical experiments show that the introduced methods are capable of tackling sparse and dense large-scale instances with up to 8000 vertices and 31,996,000 edges in a reasonable amount of time; while they also performs well in practice when compared with other state-of-the-art methods in a benchmark with small and medium-scale instances.

Vehicle routing and scheduling problems have a wide range of applications and have been intensively studied in the past half century. The condition that enforces each vehicle to start service at each customer in the period specified by the customer is called the time window constraint. This paper reviews recent results on how to handle hard and soft time window constraints, putting emphasis on its different definitions and algorithms. With these diverse time windows, the problem becomes applicable to a wide range of real-world problems.

Given a directed graph with n vertices, m edges and costs on the edges, the linear ordering problem consists of finding a permutation π of the vertices so that the total cost of the reverse edges is minimized. We present two local search algorithms, named LIST and TREE, for the neighborhood of the insert move, which can handle larger instances than existing methods. LIST is simpler and can search the whole neighborhood in O(m) time and TREE performs the neighborhood search in O(n+Δlog Δ) time, where Δ represents the maximum vertex degree. Computational experiments show good results for sparse instances using LIST, while TREE presents the best results independent of the density of the instance.

The set covering problem (SCP) calls for a minimum cost family of subsets from n given subsets, which together covers the entire ground set. In this paper, we propose a local search algorithm for SCP, which has the following three characteristics. (1) The use of 3-flip neighborhood, which is the set of solutions obtainable from the current solution by exchanging at most three subsets. As the size of 3-flip neighborhood is O(n3), the neighborhood search becomes expensive if implemented naively. To overcome this, we propose an efficient implementation that reduces the number of candidates in the neighborhood without sacrificing the solution quality. (2) We allow the search to visit the infeasible region, and incorporate the strategic oscillation technique realized by adaptive control of penalty weights. (3) The size reduction of the problem by using the information from the Lagrangian relaxation is incorporated, which is indispensable for solving very large instances. According to computational comparisons on benchmark instances with other existing heuristic algorithms for SCP, our algorithm performs quite effectively for various types of problems, especially for very large-scale instances.

One-dimensional cutting stock problem (1D-CSP) is one of the representative combinatorial optimization problems, which arises in many industrial applications. Since the setup costs for switching different cutting patterns become more dominant in recent cutting industry, we consider a variant of 1D-CSP, called the pattern restricted problem (PRP), to minimize the number of stock rolls while constraining the number of different cutting patterns within a bound given by users. For this problem, we propose a local search algorithm that alternately uses two types of local search processes with the 1-add neighborhood and the shift neighborhood, respectively. To improve the performance of local search, we incorporate it with linear programming (LP) techniques, to reduce the number of solutions in each neighborhood. A sensitivity analysis technique is introduced to solve a large number of associated LP problems quickly. Through computational experiments, we observe that the new algorithm obtains solutions of better quality than those obtained by other existing approaches.

We propose a tabu search algorithm for the generalized assignment problem, which is one of the representative combinatorial optimization problems known to be NP-hard. The algorithm features an ejection chain approach, which is embedded in a neighborhood construction to create more complex and powerful moves. We also incorporate an adaptive mechanism for adjusting search parameters, to maintain a balance between visits to feasible and infeasible regions. Computational results on benchmark instances of small sizes show that the method obtains solutions that are optimal or that deviate by at most 0.16% from the best known solutions. Comparisons with other approaches from the literature show that, for instances of larger sizes, our method obtains the best solutions among all heuristics tested.

As the cost associated with the change of cutting patterns become more important in recent industry, we consider 1D-CSP in which the number of different cutting patterns is constrained within a given bound. The proposed approach is based on metaheuristics, and incorporates an adaptive pattern generation technique. According to our computational experiments, it is observed that the proposed algorithm provides comparable solutions to other existing heuristic approaches for 1D-CSP.

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 e 2, 3, and examine their effectiveness by computational experiments. In the accompanying paper, we proposed new implementations of these neighborhoods, and showed that the expected size of 2-flip neighborhood is O(n + m) and that of 3-flip neighborhood is O(m + t2n), compared to their original size O(n2) andO(n3), respectively, where n is the number of variables, m is the number of clauses and t is the maximum number of appearances of one variable. These are used in this paper under the framework of tabu search and other metaheuristic methods, and compared with other existing algorithms with 1-flip neighborhood. The results exhibit good prospects of larger neighborhoods.

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 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.

We propose a path relinking approach for the vehicle routing problem with time windows. The path relinking is an evolutionary mechanism that generates new solutions by combining two or more reference solutions. In our algorithm, those solutions generated by path relinking operations are improved by a local search whose neighborhood consists of slight modifications of the representative neighborhoods called 2-opt*, cross exchange and Or-opt. To make the search more efficient, we propose a neighbor list that prunes the neighborhood search heuristically. Infeasible solutions are allowed to be visited during the search, while the amount of violation is penalized. As the performance of the algorithm crucially depends on penalty weights that specify how such penalty is emphasized, we propose an adaptive mechanism to control the penalty weights. The computational results on well-studied benchmark instances with up to 1000 customers revealed that our algorithm is highly efficient especially for large instances. Moreover, it updated 41 best known solutions among 356 instances.

In this paper, we consider the crew pairing problem in airline scheduling that calls for assigning crew members in order to cover all flights with the minimum total person-days under the constraints that the schedule of each crew member does not violate given constraints on the total working time, flying time, and the number of landings. In practical applications, it is difficult to create an efficient schedule satisfying all the constraints. We formulate the problem as a set covering problem and apply an LP-based column generation approach to generate a candidate set of schedules. We propose a branch-and-bound method based upon a resource constrained dynamic programming for the column generation procedure. Computational results are given for a number of large-scale instances with up to 10,000 flights.

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.

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. These neighborhoods are then used under the framework of tabu search etc., and compared with other existing algorithms based on 1-flip neighborhood. The results exhibit good prospects of the proposed algorithms.

We propose a metaheuristic algorithm for the multi-resource generalized assignment problem (MRGAP). MRGAP is a generalization of the generalized assignment problem, which is one of the representative combinatorial optimization problems known to be NP-hard. The algorithm features a very large-scale neighborhood search, which is a mechanism of conducting the search with complex and powerful moves, where the resulting neighborhood is efficiently searched via the improvement graph. We also incorporate an adaptive mechanism for adjusting search parameters, to maintain a balance between visits to feasible and infeasible regions. Computational comparisons on benchmark instances show that the method is effective, especially for types D and E instances, which are known to be quite difficult.

We generalize the standard vehicle routing problem with time windows by allowing both traveling times and traveling costs to be time-dependent functions. In our algorithm, we use a local search to determine routes of the vehicles. When we evaluate a neighborhood solution, we must compute an optimal time schedule for each route. We show that this subproblem can be efficiently solved by dynamic programming, which is incorporated in the local search algorithm. The neighborhood of our local search consists of slight modifications of the standard neighborhoods called 2- opt∗, cross exchange and Or-opt. We propose an algorithm that evaluates solutions in these neighborhoods more efficiently than the ones computing the dynamic programming from scratch by utilizing the information from the past dynamic programming recursion used to evaluate the current solution. We further propose a filtering method that restricts the search space in the neighborhoods to avoid many solutions having no prospect of improvement. We then develop an iterated local search algorithm that incorporates all the above ingredients. Finally we report computational results of our iterated local search algorithm compared against existing methods, and confirm the effectiveness of the restriction of the neighborhoods and the benefits of the proposed generalization.

We generalize the standard vehicle routing problem by allowing soft time window and soft traveling time constraints, where both constraints are treated as cost functions. With the proposed generalization, the problem becomes very general. In our algorithm, we use local search to determine the routes of vehicles. After fixing the route of each vehicle, we must determine the optimal start times of services at visited customers. We show that this subproblem is NP-hard when cost functions are general, but can be efficiently solved with dynamic programming when traveling time cost functions are convex even if time window cost functions are non-convex. We deal with the latter situation in the developed iterated local search algorithm. Finally we report computational results on benchmark instances, and confirm the benefits of the proposed generalization.