Scatter search for chemical and bio-process optimization

Scatter search is a population-based method that has recently been shown to yield promising outcomes for solving combinatorial and nonlinear optimization problems. Based on formulations originally proposed in 1960s for combining decision rules and problem constraints such as the surrogate constraint method, scatter search uses strategies for combining solution vectors that have proved effective in a variety of problem settings. In this paper, we develop a general purpose heuristic for a class of nonlinear optimization problems. The procedure is based on the scatter search methodology and treats the objective function evaluation as a black box, making the search algorithm context-independent. Most optimization problems in the chemical and bio-chemical industries are highly nonlinear in either the objective function or the constraints. Moreover, they usually present differential-algebraic systems of constraints. In this type of problem, the evaluation of a solution or even the feasibility test of a set of values for the decision variables is a time-consuming operation. In this context, the solution method is limited to a reduced number of solution examinations. We have implemented a scatter search procedure in Matlab (Mathworks, 2004) for this special class of difficult optimization problems. Our development goes beyond a simple exercise of applying scatter search to this class of problems, but presents innovative mechanisms to obtain a good balance between intensification and diversification in a short-term search horizon. Computational comparisons with other recent methods over a set of benchmark problems favor the proposed procedure.     

Scatter search for the vehicle routing problem with time windows

In this paper we use a scatter search framework to solve the vehicle routing problem with time windows (VRPTW). Our objective is to achieve effective solutions and to investigate the effects of reference set design parameters pertaining to size, quality and diversity. Both a common arc method and an optimization-based set covering model are used to combine vehicle routing solutions. A reactive tabu search metaheuristic and a tabu search with an advanced recovery feature, together with a set covering procedure are used for solution improvement. Our approach led to a robust solution method, generating solution quality that is competitive with the current best metaheuristics.     

An evolutionary approach for bandwidth multicoloring problems

In this paper we consider some generalizations of the vertex coloring problem, where distance constraints are imposed between adjacent vertices (bandwidth coloring problem) and each vertex has to be colored with more than one color (bandwidth multicoloring problem). We propose an evolutionary metaheuristic approach for the first problem, combining an effective tabu search algorithm with population management procedures. The approach can be applied to the second problem as well, after a simple transformation. Computational results on instances from the literature show that the overall algorithm is able to produce high quality solutions in a reasonable amount of time, outperforming the most effective algorithms proposed for the bandwidth coloring problem, and improving the best known solution of many instances of the bandwidth multicoloring problem.     

Scatter search for trainees to software project requirements stable allocation

In this paper, we study a centralized, stable matching scheme, which allocates trainees to software project requirements, to minimize retraining and relocation costs when the preference lists of the project requirements may contain ties of arbitrary lengths. This particular trainees’ assignment problem is important because the allocation decisions not only influence the costs but also impact software project deliverables and intern attrition rates. It is also an NP-hard problem because of the inclusion of the ties, and the costs in the stable allocation model. We, therefore, have designed a GRASP-based scatter search method, to solve the large size instances of our assignment problem efficiently. The GRASP method uses randomized algorithms to generate initial trial solutions. A repair heuristic based on regret minimization idea is designed to convert an unstable solution to a stable solution during an improvement phase. Computational experiments suggest that the proposed algorithm significantly reduces run time compared to the CPLEX, and produces solutions that are at an average 4.5% away from the best CPLEX solutions for the large size problem instances. Moreover, our scatter search method consistently provides better quality solutions than the two state of the art methods from the prior literature.     

Heuristical labour scheduling to optimize airport passenger flows

We describe the development and implementation of a decision support system for the optimization of passenger flow by trading off service quality and labour costs at an airport. The system integrates a simulation module with an optimization module that requires that Dantzig's labour scheduling problem be solved in the order of thousands of times. We developed a customized scatter search to give the system the capability of finding high-quality solutions to the labour scheduling problems in short computational times. Our experiments verify that our scatter search implementation meets the needed requirements.     

A black-box scatter search for optimization problems with integer variables

The goal of this work is the development of a black-box solver based on the scatter search methodology. In particular, we seek a solver capable of obtaining high quality outcomes to optimization problems for which solutions are represented as a vector of integer values. We refer to these problems as integer optimization problems. We assume that the decision variables are bounded and that there may be constraints that require that the black-box evaluator is called in order to know whether they are satisfied. Problems of this type are common in operational research areas of applications such as telecommunications, project management, engineering design and the like.Our experimental testing includes 171 instances within four classes of problems taken from the literature. The experiments compare the performance of the proposed method with both the best context-specific procedures designed for each class of problem as well as context-independent commercial software. The experiments show that the proposed solution method competes well against commercial software and that can be competitive with specialized procedures in some problem classes.     

Principles of scatter search

Scatter search is an evolutionary method that has been successfully applied to hard optimization problems. The fundamental concepts and principles of the method were first proposed in the 1970s, based on formulations dating back to the 1960s for combining decision rules and problem constraints. In contrast to other evolutionary methods like genetic algorithms, scatter search is founded on the premise that systematic designs and methods for creating new solutions afford significant benefits beyond those derived from recourse to randomization. It uses strategies for search diversification and intensification that have proved effective in a variety of optimization problems.This paper provides the main principles and ideas of scatter search and its generalized form path relinking. We first describe a basic design to give the reader the tools to create relatively simple implementations. More advanced designs derive from the fact that scatter search and path relinking are also intimately related to the tabu search (TS) metaheuristic, and gain additional advantage by making use of TS adaptive memory and associated memory-exploiting mechanisms capable of being tailored to particular contexts. These and other advanced processes described in the paper facilitate the creation of sophisticated implementations for hard problems that often arise in practical settings. Due to their flexibility and proven effectiveness, scatter search and path relinking can be successfully adapted to tackle optimization problems spanning a wide range of applications and a diverse collection of structures, as shown in the papers of this volume.     

A scatter search algorithm for the distributed permutation flowshop scheduling problem

The distributed permutation flowshop problem has been recently proposed as a generalization of the regular flowshop setting where more than one factory is available to process jobs. Distributed manufacturing is a common situation for large enterprises that compete in a globalized market. The problem has two dimensions: assigning jobs to factories and scheduling the jobs assigned to each factory. Despite being recently introduced, this interesting scheduling problem has attracted attention and several heuristic and metaheuristic methods have been proposed in the literature. In this paper we present a scatter search (SS) method for this problem to optimize makespan. SS has seldom been explored for flowshop settings. In the proposed algorithm we employ some advanced techniques like a reference set made up of complete and partial solutions along with other features like restarts and local search. A comprehensive computational campaign including 10 existing algorithms, together with statistical analyses, shows that the proposed scatter search algorithm produces better results than existing algorithms by a significant margin. Moreover all 720 known best solutions for this problem are improved.     

Incorporating scatter search and threshold accepting in finding maximum likelihood estimates for the multinomial probit model

This paper presents a procedure that incorporates scatter search and threshold accepting to find the maximum likelihood estimates for the multinomial probit (MNP) model. Scatter search, widely used in optimization-related studies, is a type of evolutionary algorithm that uses a small set of solutions as the selection pool for mating and generating new solutions to search for a globally optimal solution. Threshold accepting is applied to the scatter search to improve computational efficiency while maintaining the same level of solution quality. A set of numerical experiments, based on synthetic data sets with known model specifications and error structures, were conducted to test the effectiveness and efficiency of the proposed framework. The results indicated that the proposed procedure enhanced performance in terms of likelihood function value and computational efficiency for MNP model estimation as compared to the original scatter search framework.     

A hybrid single and dual population search procedure for the job shop scheduling problem

This paper presents a genetic algorithm and a scatter search procedure to solve the well-known job shop scheduling problem. In contrast to the single population search performed by the genetic algorithm, the scatter search algorithm splits the population of solutions in a diverse and high-quality set to exchange information between individuals in a controlled way. The extension from a single to a dual population, by taking problem specific characteristics into account, can be seen as a stimulator to add diversity in the search process. This has a positive influence on the important balance between intensification and diversification. Computational experiments verify the benefit of this diversity on the effectiveness of the meta-heuristic search process. Various algorithmic parameters from literature are embedded in both procedures and a detailed comparison is made. A set of standard instances is used to compare the different approaches and the best obtained results are benchmarked against heuristic solutions found in literature.     

RAMP for the capacitated minimum spanning tree problem

This paper introduces dual and primal-dual RAMP algorithms for the solution of the capacitated minimum spanning tree problem (CMST). A surrogate constraint relaxation incorporating cutting planes is proposed to explore the dual solution space. In the dual RAMP approach, primal-feasible solutions are obtained by simple tabu searches that project dual solutions onto primal feasible space. A primal-dual approach is achieved by including a scatter search procedure that further exploits the adaptive memory framework. Computational results from applying the methods to a standard set of benchmark problems disclose that the dual RAMP algorithm finds high quality solutions very efficiently and that its primal-dual enhancement is still more effective.     

A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling

We develop a heuristic procedure for solving the discrete time/resource trade-off problem in the field of project scheduling. In this problem, a project contains activities interrelated by finish-start-type precedence constraints with a time lag of zero, which require one or more constrained renewable resources. Each activity has a specified work content and can be performed in different modes, i.e. with different durations and resource requirements, as long as the required work content is met. The objective is to schedule each activity in one of its modes in order to minimize the project makespan. We use a scatter search algorithm to tackle this problem, using path relinking methodology as a solution combination method. Computational results on randomly generated problem sets are compared with the best available results indicating the efficiency of the proposed algorithm.     

Heuristic solutions to the problem of routing school buses with multiple objectives

In this paper we address the problem of routing school buses in a rural area. We approach this problem with a node routing model with multiple objectives that arise from conflicting viewpoints. From the point of view of cost, it is desirable to minimise the number of buses used to transport students from their homes to school and back. From the point of view of service, it is desirable to minimise the time that a given student spends en route. The current literature deals primarily with single-objective problems and the models with multiple objectives typically employ a weighted function to combine the objectives into a single one. We develop a solution procedure that considers each objective separately and search for a set of efficient solutions instead of a single optimum. Our solution procedure is based on constructing, improving and then combining solutions within the framework of the evolutionary approach known as scatter search. Experimental testing with real data is used to assess the merit of our proposed procedure.     

A Tabu Search Heuristic Procedure for Solving the Transportation Problem with Exclusionary Side Constraints

A new heuristic procedure for the transportation problem with exclusionary side constraints is developed and implemented. Tabu search, a meta-heuristic method, is used to guide the search to follow a path selectively to prevent from being trapped at local optimal solutions in order to find a global optimal or near global optimal solution. The simplex method on a graph is employed to lead the search from one solution to an adjacent solution in order to take advantage of the underlying network structure of the problem. In the procedure, net changes in cost and in infeasibility are used to measure the attractiveness of a move, and strategic oscillation is used to implement the intensification and diversification functions. A computational experiment was conducted to test the performance of the heuristic procedure and substantial computational results are reported. These results show that the new heuristic procedure finds very good quality solutions and outperforms an existing heuristic procedure in terms of both solution quality and CPU time.     

A solution procedure for the discrete time, cost and quality tradeoff problem using electromagnetic scatter search

Decisions concerning a project’s expedition, traditionally involved considerations regarding time and cost tradeoff. It was recently suggested that the quality of a project should also be taken into considerations. In this paper, we propose a meta-heuristic solution procedure for the discrete time, cost and quality tradeoff problem. This problem involves the scheduling of project activities in order to minimize the total cost of the project while maximizing the quality of the project and also meeting a given deadline. We apply a so called electromagnetic scatter search to solve this problem. In this process, we initially generate a population of feasible solutions. In so doing, we use frequency memory to well sample the feasible region. A number of these solutions are then selected and improved locally. The improved solutions are then combined to generate new set of solutions. The combination process utilizes attraction–repulsion mechanisms borrowed from the electromagnetism theory. The whole process is stopped when no significant improvement in the set of solutions are observed. The validity of the proposed solution procedure is demonstrated, and its applicability is tested on a randomly generated large and complex problem having 19,900 activities.     

A library of local search heuristics for the vehicle routing problem

The vehicle routing problem (VRP) is a difficult and well-studied combinatorial optimization problem. Real-world instances of the VRP can contain hundreds and even thousands of customer locations and can involve many complicating constraints, necessitating the use of heuristic methods. We present a software library of local search heuristics that allows one to quickly generate solutions to VRP instances. The code has a logical, object-oriented design and uses efficient data structures to store and modify solutions. The core of the library is the implementation of seven local search operators that share a similar interface and are designed to be extended to handle additional options with minimal code change. The code is well-documented, straightforward to compile, and is freely available online. The code contains several applications that can be used to generate solutions to the capacitated VRP. Computational results indicate that these applications are able to generate solutions that are within about one percent of the best-known solution on benchmark problems.     

A novel metaheuristics approach for continuous global optimization

This paper proposes a novel metaheuristics approach to find the global optimum of continuous global optimization problems with box constraints. This approach combines the characteristics of modern metaheuristics such as scatter search (SS), genetic algorithms (GAs), and tabu search (TS) and named as hybrid scatter genetic tabu (HSGT) search. The development of the HSGT search, parameter settings, experimentation, and efficiency of the HSGT search are discussed. The HSGT has been tested against a simulated annealing algorithm, a GA under the name GENOCOP, and a modified version of a hybrid scatter genetic (HSG) search by using 19 well known test functions. Applications to Neural Network training are also examined. From the computational results, the HSGT search proved to be quite effective in identifying the global optimum solution which makes the HSGT search a promising approach to solve the general nonlinear optimization problem.     

A Population-Based Approach to the Resource-Constrained Project Scheduling Problem

We present a population-based approach to the RCPSP. The procedure has two phases. The first phase handles the initial construction of a population of schedules and these are then evolved until high quality solutions are obtained. The evolution of the population is driven by the alternative application of an efficient improving procedure for locally improving the use of resources, and a mechanism for combining schedules that blends scatter search and path relinking characteristics. The objective of the second phase is to explore in depth those vicinities near the high quality schedules. Computational experiments on the standard j120 set, generated using ProGen, show that our algorithm produces higher quality solutions than state-of-the-art heuristics for the RCPSP in an average time of less than five seconds.     

Parallel Metaheuristics for Workforce Planning

Workforce planning is an important activity that enables organizations to determine the workforce needed for continued success. A workforce planning problem is a very complex task requiring modern techniques to be solved adequately. In this work, we describe the development of three parallel metaheuristic methods, a parallel genetic algorithm, a parallel scatter search, and a parallel hybrid genetic algorithm, which can find high-quality solutions to 20 different problem instances. Our experiments show that parallel versions do not only allow to reduce the execution time but they also improve the solution quality.      

Bounding,filtering and diversification in CP-based local branching

Local branching is a general purpose heuristic method which searches locally around the best known solution by employing tree search. It has been successfully used in Mixed-Integer Programming where local branching constraints are used to model the neighborhood of an incumbent solution and improve the bound. We propose the integration of local branching in Constraint Programming (CP). This integration is not simply a matter of implementation, but requires a number of significant extensions. The original contributions of this paper are: the definition of an efficient and incremental bound computation for the neighborhood, a cost-based filtering algorithm for the local branching constraint and a novel diversification strategy that can explore arbitrarily far regions of the search tree w.r.t. the already found solutions. We demonstrate the practical value of local branching in CP by providing an extensive experimental evaluation on the hard instances of the Asymmetric Traveling Salesman Problem with Time Windows.