On solving the forward kinematics of 3RPR planar parallel manipulator using hybrid metaheuristics

Hybrid metaheuristics have been applied with success in solving many real-world problems. This work introduces hybrid metaheuristics to the field of kinematics problem, in particular, for solving the forward kinematics of the 3RPR parallel manipulator. It implements a combination of genetic algorithms and simulated annealing into two popular hybrid metaheuristic techniques. They are combined as teamwork and relay collaborative hybrid metaheuristics and compared to the performance of genetic algorithms and simulated annealing alone. The results show that the meta-heuristic approaches give robust and high quality solutions. Genetic algorithms and teamwork collaborative metaheuristics showed better performance than simulated annealing and relay collaborative metaheuristics. The given metaheuristic methods obtain all the unique solutions and comparisons with algebraic methods show promising results.     

Metaheuristics for a Flexible Assembly System Design Problem

Flexibility has become an important priority in the formulation and implementation of manufacturing strategies. This in turn has opened up a new class of design problems for such systems. Flexible assembly systems (FAS), consisting of a variety of processors and operations, provide the opportunity for improving product manufacturing flexibility, hence gaining competitive advantages. This paper considers a particular design decision problem for FAS. A matrix-based, polynomial-time lower bound algorithm is presented. Simulated annealing and tabu search metaheuristics are formulated to address the problems. Computational experience with these metaheuristics is reported.     

Hybrid Metaheuristics for the Vehicle Routing Problem with Stochastic Demands

This article analyzes the performance of metaheuristics on the vehicle routing problem with stochastic demands (VRPSD). The problem is known to have a computationally demanding objective function, which could turn to be infeasible when large instances are considered. Fast approximations of the objective function are therefore appealing because they would allow for an extended exploration of the search space. We explore the hybridization of the metaheuristic by means of two objective functions which are surrogate measures of the exact solution quality. Particularly helpful for some metaheuristics is the objective function derived from the traveling salesman problem (TSP), a closely related problem. In the light of this observation, we analyze possible extensions of the metaheuristics which take the hybridized solution approach VRPSD-TSP even further and report about experimental results on different types of instances. We show that, for the instances tested, two hybridized versions of iterated local search and evolutionary algorithm attain better solutions than state-of-the-art algorithms.     

Simulated annealing and tabu search for multi-mode resource-constrained project scheduling with positive discounted cash flows and different payment models

In this paper the multi-mode resource-constrained project scheduling problem with discounted cash flows is considered. A project is represented by an activity-on-node (AoN) network. A positive cash flow is associated with each activity. Four different payment models are considered: lump-sum payment at the completion of the project, payments at activities' completion times, payments at equal time intervals and progress payments. The objective is to maximize the net present value of all cash flows of the project. Local search metaheuristics: simulated annealing and tabu search are proposed to solve this strongly NP-hard problem. A comprehensive computational experiment is described, performed on a set of instances based on standard test problems constructed by the ProGen project generator, where, additionally, the activities' cash flows are generated randomly with the uniform distribution. The metaheuristics are computationally compared, the results are analyzed and discussed and some conclusions are given.     

Evolutionary,constructive and hybrid procedures for the bi-objective set packing problem

The bi-objective set packing problem is a multi-objective combinatorial optimization problem similar to the well-known set covering/partitioning problems. To our knowledge and surprise, this problem has not yet been studied whereas several applications have been reported. Unfortunately, solving the problem exactly in a reasonable time using a generic solver is only possible for small instances. We designed three alternative procedures for approximating solutions to this problem. The first is derived from the original ‘Strength Pareto Evolutionary Algorithm’, which is a population-based metaheuristic. The second is an adaptation of the ‘Greedy Randomized Adaptative Search Procedure’, which is a constructive metaheuristic. As underlined in the overview of the literature summarized here, almost all the recent, effective procedures designed for approximating optimal solutions to multi-objective combinatorial optimization problems are based on a blend of techniques, called hybrid metaheuristics. Thus, the third alternative, which is the primary subject of this paper, is an original hybridization of the previous two metaheuristics. The algorithmic aspects, which differ from the original definition of these metaheuristics, are described, so that our results can be reproduced. The performance of our procedures is reported and the computational results for 120 numerical instances are discussed.     

A comprehensive review and evaluation of permutation flowshop heuristics

In this work we present a review and comparative evaluation of heuristics and metaheuristics for the well-known permutation flowshop problem with the makespan criterion. A number of reviews and evaluations have already been proposed. However, the evaluations do not include the latest heuristics available and there is still no comparison of metaheuristics. Furthermore, since no common benchmarks and computing platforms are used, the results cannot be generalised. We propose a comparison of 25 methods, ranging from the classical Johnson's algorithm or dispatching rules to the most recent metaheuristics, including tabu search, simulated annealing, genetic algorithms, iterated local search and hybrid techniques. For the evaluation we use the standard test of Taillard [Eur. J. Operation. Res. 64 (1993) 278] composed of 120 instances of different sizes. In the evaluations we use the experimental design approach to obtain valid conclusions on the effectiveness and efficiency of the different methods tested.     

Metaheuristics approach for solving personalized crew rostering problem in public bus transit

The crew rostering problem in public bus transit aims at constructing personalized monthly schedules for all drivers. This problem is often formulated as a multi-objective optimization problem, since it considers the interests of both the management of bus companies and the drivers. Therefore, this paper attempts to solve the multi-objective crew rostering problem with the weighted sum of all objectives using ant colony optimization, simulated annealing, and tabu search methods. To the best of our knowledge, this is the first paper that attempts to solve the personalized crew rostering problem in public transit using different metaheuristics, especially the ant colony optimization. The developed algorithms are tested on numerical real-world instances, and the results are compared with ones solved by commercial solvers.     

Heuristic algorithms for the cardinality constrained efficient frontier

This paper examines the application of genetic algorithm, tabu search and simulated annealing metaheuristic approaches to finding the cardinality constrained efficient frontier that arises in financial portfolio optimisation. We consider the mean-variance model of Markowitz as extended to include the discrete restrictions of buy-in thresholds and cardinality constraints. Computational results are reported for publicly available data sets drawn from seven major market indices involving up to 1318 assets. Our results are compared with previous results given in the literature illustrating the effectiveness of the proposed metaheuristics in terms of solution quality and computation time.     

Manpower allocation using genetic annealing

In this paper, we focus on a real size manpower allocation problem. It was modeled after a real world problem of distributing the salesmen force over the branches of a company. The problem includes multiple objectives and the number of salesmen at each branch is unspecified. Conventional integer programming approach and conventional metaheuristics seem to have problems with solving the large size version of this problem. The versatility of our proposed heuristics based on a modification of genetic annealing is exemplified through solving the real size manpower allocation problem. For comparison sake, several small sized versions were solved using our method, conventional integer programming approach, and some well known metaheuristics.     

A contribution to the stochastic flow shop scheduling problem

This paper deals with performance evaluation and scheduling problems in m machine stochastic flow shop with unlimited buffers. The processing time of each job on each machine is a random variable exponentially distributed with a known rate. We consider permutation flow shop. The objective is to find a job schedule which minimizes the expected makespan. A classification of works about stochastic flow shop with random processing times is first given. In order to solve the performance evaluation problem, we propose a recursive algorithm based on a Markov chain to compute the expected makespan and a discrete event simulation model to evaluate the expected makespan. The recursive algorithm is a generalization of a method proposed in the literature for the two machine flow shop problem to the m machine flow shop problem with unlimited buffers. In deterministic context, heuristics (like CDS [Management Science 16 (10) (1970) B630] and Rapid Access [Management Science 23 (11) (1977) 1174]) and metaheuristics (like simulated annealing) provide good results. We propose to adapt and to test this kind of methods for the stochastic scheduling problem. Combinations between heuristics or metaheuristics and the performance evaluation models are proposed. One of the objectives of this paper is to compare the methods together. Our methods are tested on problems from the OR-Library and give good results: for the two machine problems, we obtain the optimal solution and for the m machine problems, the methods are mutually validated.     

Comparative analysis of three metaheuristics for short-term open pit block sequencing

This paper presents the application of simulated annealing (SA), Tabu search (TS) and hybrid TS–SA to solve a real-world mining optimisation problem called open pit block sequencing (OPBS). The OPBS seeks the optimum extraction sequences under a variety of geological and technical constraints over short-term horizons. As industry-scale OPBS instances are intractable for standard mixed integer programming (MIP) solvers, SA, TS and hybrid TS–SA are developed to solve the OPBS problem. MIP exact solution is also combined with the proposed metaheuristics to polish solutions in feasible neighbourhood moves. Extensive sensitivity analysis is conducted to analyse the characteristics and determine the optimum sets of values of the proposed metaheuristics algorithms’ parameters. Computational experiments show that the proposed algorithms are satisfactory for solving the OPBS problem. Additionally, this comparative study shows that the hybrid TS–SA is superior to SA or TS in solving the OPBS problem in several aspects.     

A GRASP for Coloring Sparse Graphs

We first present a literature review of heuristics and metaheuristics developed for the problem of coloring graphs. We then present a Greedy Randomized Adaptive Search Procedure (GRASP) for coloring sparse graphs. The procedure is tested on graphs of known chromatic number, as well as random graphs with edge probability 0.1 having from 50 to 500 vertices. Empirical results indicate that the proposed GRASP implementation compares favorably to classical heuristics and implementations of simulated annealing and tabu search. GRASP is also found to be competitive with a genetic algorithm that is considered one of the best currently available for graph coloring.     

Heuristics and metaheuristics for the maximum diversity problem

This paper presents extensive computational experiments to compare 10 heuristics and 20 metaheuristics for the maximum diversity problem (MDP). This problem consists of selecting a subset of maximum diversity from a given set of elements. It arises in a wide range of real-world settings and we can find a large number of studies, in which heuristic and metaheuristic methods are proposed. However, probably due to the fact that this problem has been referenced under different names, we have only found limited comparisons with a few methods on some sets of instances. This paper reviews all the heuristics and metaheuristics for finding near-optimal solutions for the MDP. We present the new benchmark library MDPLIB, which includes most instances previously used for this problem, as well as new ones, giving a total of 315. We also present an exhaustive computational comparison of the 30 methods on the MDPLIB. Non-parametric statistical tests are reported in our study to draw significant conclusions.     

Metaheuristics for multiobjective optimisation

This is a summary of the author’s PhD thesis supervised by Laetitia Jourdan and El-Ghazali Talbi and defended on 8 December 2009 at the Université Lille 1. The thesis is written in French and is available from . This work deals with the design, implementation and experimental analysis of metaheuristics for solving multiobjective optimisation problems, with a particular interest on hard and large combinatorial problems from the field of logistics. After focusing on a unified view of multiobjective metaheuristics, we propose new cooperative, adaptive and parallel approaches. The performance of these methods are experimented on a scheduling and a routing problem involving two or three objective functions. We finally discuss how to adapt such metaheuristics during the search process in order to handle uncertainty that may occur from many different sources.     

The noising methods: A generalization of some metaheuristics

In this paper, an exhaustive review of the principles and of the applications of the noising methods, recent combinatorial optimization metaheuristics, is attempted. The features and the variants of the noising methods are detailed and the tunings of their parameters when applied to different combinatorial optimization problems are summarized. The links between the noising methods and two other metaheuristics (namely, the simulated annealing method and the threshold accepting algorithm) are also studied and that the noising methods can be considered as generalizations of these metaheuristics when their components are properly chosen is shown.     

Stochastic local search for large-scale instances of the haplotype inference problem by pure parsimony

Haplotype Inference is a challenging problem in bioinformatics that consists in inferring the basic genetic constitution of diploid organisms on the basis of their genotype. This information allows researchers to perform association studies for the genetic variants involved in diseases and the individual responses to therapeutic agents. A notable approach to the problem is to encode it as a combinatorial problem (under certain hypotheses, such as the pure parsimony criterion) and to solve it using off-the-shelf combinatorial optimization techniques. The main methods applied to Haplotype Inference are either simple greedy heuristic or exact methods (Integer Linear Programming, Semidefinite Programming, SAT and pseudo-boolean encoding) that, at present, are adequate only for moderate size instances. In this paper, we present and discuss an approach based on the combination of local search metaheuristics and a reduction procedure based on an analysis of the problem structure. Some relevant design issues are first described, then a family of local search metaheuristics is defined to tackle the Haplotype Inference. Results on common Haplotype Inference benchmarks show that the approach achieves a good trade-off between solution quality and execution time.     

Metaheuristics for multi-mode capital-constrained project payment scheduling

This paper involves the multi-mode capital-constrained project payment scheduling problem, where the objective is to assign activity modes and payments so as to maximize the net present value (NPV) of the contractor under the constraint of capital availability. In the light of different payment patterns adopted, four optimization models are constructed using the event-based method. For the NP-hardness of the problem, metaheuristics, including tabu search and simulated annealing, are developed and compared with multi-start iterative improvement and random sampling based on a computational experiment performed on a data set generated randomly. The results indicate that the loop nested tabu search is the most promising procedure for the problem studied. Moreover, the effects of several key parameters on the contractor’s NPV are investigated and the following conclusions are drawn: The contractor’s NPV rises with the increase of the contractor’s initial capital availability, the payment number, the payment proportion, or the project deadline; the contractor has a decreasing marginal return as the contractor’s initial capital availability goes up; the contractor’s NPVs under the milestone event based payment pattern are not less than those under the other three payment patterns.     

A novel non-linear approach to minimal area rectangular packing

This paper discusses the minimal area rectangular packing problem which is to pack a given set of rectangles into a rectangular container of minimal area such that no two rectangles overlap. Current approaches for this problem rely on metaheuristics like simulated annealing, on constraint programming or on non-linear models. Difficulties arise from the non-convexity and the combinatorial complexity. We investigate different mathematical programming approaches for this and introduce a novel approach based on non-linear optimization and the “tunneling effect” achieved by a relaxation of the non-overlapping constraints. We compare our optimization algorithm to a simulated annealing and a constraint programming approach and show that our approach is competitive. Additionally, since it is easy to extend, it is also applicable to a variety of related problems.     

Scatter search for the cutwidth minimization problem

The cutwidth minimization problem consists of finding a linear layout of a graph so that the maximum linear cut of edges is minimized. This NP-hard problem has applications in network scheduling, automatic graph drawing and information retrieval. We propose a heuristic method based on the Scatter Search (SS) methodology for finding approximate solutions to this optimization problem. This metaheuristic explores solution space by evolving a set of reference points. Our SS method is based on a GRASP constructive algorithm, a local search strategy based on insertion moves and voting-based combination methods. We also introduce a new measure to control the diversity in the search process. Empirical results with 252 previously reported instances indicate that the proposed procedure compares favorably to previous metaheuristics for this problem, such as Simulated Annealing and Evolutionary Path Relinking.     

Applying simulated annealing to location-planning models

Simulated annealing is a computational approach that simulates an annealing schedule used in producing glass and metals. Originally developed by Metropolis et al. in 1953, it has since been applied to a number of integer programming problems, including the p-median location-allocation problem. However, previously reported results by Golden and Skiscim in 1986 were less than encouraging. This article addresses the design of a simulated-annealing approach for the p-median and maximal covering location problems. This design has produced very good solutions in modest amounts of computer time. Comparisons with an interchange heuristic demonstrate that simulated annealing has potential as a solution technique for solving location-planning problems and further research should be encouraged.