Fitness Landscape Analysis for Scalable Multicast RRM Problem in Cellular Network

This paper aims to solve the Radio Resource Management (RRM) problem for Multimedia Broadcast Multicast Service (MBMS) system in cellular network. We develop a flexible model to perform dynamic radio resource allocation for MBMS service by using metaheuristic approach. We conduct fitness landscape analysis to study the characteristics of the proposed model, which helps us to select appropriate search strategy. Simulation results show that the proposed algorithm provides better performance than existing algorithms.     

Multimethodology in Metaheuristics

As a combination of different methodologies or parts of methodologies, Multimethodology is becoming more frequent in OR practice. This paper contributes with a new proposal and a new field of application: the employment of Multimethodology in problem solving with Metaheuristics (Mh). A convenient selection of soft and hard methods will be considered, from Soft OR, Creativity and Metaheuristics, such as Strategic Choice Approach, SWOT Analysis and Divergent and Convergent thinking. Formulating the ‘right’ optimisation problem, choosing a method based on Mh and accomplishing an effective implementation is an imprecise decision-making process, which may require skills and ideas that are beyond the ordinary boundaries of Mh practice. The relevance and success of Mh have been well-known for decades, but some open questions concerning choice and implementation strategies, for instance, still remain. If these questions are not adequately answered, they may lose credibility in the long term. The quality of solutions and computational times are not the only criteria used to analyse Mh, nor are they the most important. Very often, the effectiveness of an approach has to be evaluated from the perspective of modelling and practical problem solving. This paper investigates the advantages of Multimethodology and, furthermore, it sketches a framework for a coherent and comprehensive comparison of Mh and recommends a dynamic guiding tool for their implementation.     

Metaheuristics for High School Timetabling

In this paper we present the results of an investigation of the possibilities offered by three well-known metaheuristic algorithms to solve the timetable problem, a multi-constrained, NP-hard, combinatorial optimization problem with real-world applications. First, we present our model of the problem, including the definition of a hierarchical structure for the objective function, and of the neighborhood search operators which we apply to matrices representing timetables. Then we report about the outcomes of the utilization of the implemented systems to the specific case of the generation of a school timetable. We compare the results obtained by simu lated annealing, tabu search and two versions, with and without local search, of the genetic algorithm. Our results show that GA with local search and tabu search based on temporary problem relaxations both outperform simulated annealing and handmade timetables.     

Metaheuristics: A bibliography

Metaheuristics are the most exciting development in approximate optimization techniques of the last two decades. They have had widespread successes in attacking a variety of difficult combinatorial optimization problems that arise in many practical areas. This bibliography provides a classification of a comprehensive list of 1380 references on the theory and application of metaheuristics. Metaheuristics include but are not limited to constraint logic programming; greedy random adaptive search procedures; natural evolutionary computation; neural networks; non-monotonic search strategies; space-search methods; simulated annealing; tabu search; threshold algorithms and their hybrids. References are presented in alphabetical order under a number of subheadings.     

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.     

Metaheuristics in Combinatorial Optimization

The emergence of metaheuristics for solving difficult combinatorial optimization problems is one of the most notable achievements of the last two decades in operations research. This paper provides an account of the most recent developments in the field and identifies some common issues and trends. Examples of applications are also reported for vehicle routing and scheduling problems.     

Metaheuristics can solve sudoku puzzles

In this paper we present, to our knowledge, the first application of a metaheuristic technique to the very popular and NP-complete puzzle known as ‘sudoku’. We see that this stochastic search-based algorithm, which uses simulated annealing, is able to complete logic-solvable puzzle-instances that feature daily in many of the UK’s national newspapers. We also introduce a new method for producing sudoku problem instances (that are not necessarily logic-solvable) and use this together with the proposed SA algorithm to try and discover for what types of instances this algorithm is best suited. Consequently we notice the presence of an ‘easy-hard-easy’ style phase-transition similar to other problems encountered in operational research.     

Metaheuristics for robust graph coloring

This paper studies a robust graph coloring problem, which is a variant of the classical graph coloring problem, where penalties are charged for non-adjacent vertices that are assigned the same color. The problem can be formulated as an unconstrained quadratic programming problem, and has many applications in industry. Since the problem is known to be strongly NP-complete, we develop a number of metaheuristics for it, which are based on various encoding schemes, neighborhood structures, and search algorithms. Extensive experiments suggest that our metaheuristics with a partition based encoding scheme and an improvement graph based neighborhood outperform other methods tested in our study.     

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.      

A Taxonomy of Hybrid Metaheuristics

Hybrid metaheuristics have received considerable interest these recent years in the field of combinatorial optimization. A wide variety of hybrid approaches have been proposed in the literature. In this paper, a taxonomy of hybrid metaheuristics is presented in an attempt to provide a common terminology and classification mechanisms. The taxonomy, while presented in terms of metaheuristics, is also applicable to most types of heuristics and exact optimization algorithms.As an illustration of the usefulness of the taxonomy an annoted bibliography is given which classifies a large number of hybrid approaches according to the taxonomy.     

Metaheuristics for the team orienteering problem

The Team Orienteering Problem (TOP) is the generalization to the case of multiple tours of the Orienteering Problem, known also as Selective Traveling Salesman Problem. A set of potential customers is available and a profit is collected from the visit to each customer. A fleet of vehicles is available to visit the customers, within a given time limit. The profit of a customer can be collected by one vehicle at most. The objective is to identify the customers which maximize the total collected profit while satisfying the given time limit for each vehicle. We propose two variants of a generalized tabu search algorithm and a variable neighborhood search algorithm for the solution of the TOP and show that each of these algorithms beats the already known heuristics. Computational experiments are made on standard instances.     

CLAM: Clustering Large Applications Using Metaheuristics

Clustering remains one of the most difficult challenges in data mining. This paper proposes a new algorithm, CLAM, using a hybrid metaheuristic between VNS and Tabu Search to solve the problem of k-medoid clustering. The new technique is compared to the well-known CLARANS. Experimental results show that, given the same computation times, CLAM is more effective.     

Metaheuristics approach to the aircrew rostering problem

The solution of the aircrew-scheduling problem is represented by a set of rotations developed from a given set of flight segments. Once the set of rotations to be made by aircrew members has been determined, the air carrier must solve the aircrew rostering problem that entails the monthly assignment of aircrew members to planned rotations. This paper attempts to solve the aircrew rostering problem, thus constructing personalized monthly schedules using Simulated Annealing, Genetic Algorithms, and Tabu Search techniques. The developed models are tested on numerical examples that consist of constructing schedules for pilots. Dimensions of the considered examples are characteristic of small and medium-sized airlines.     

Solving Vehicle Routing Problems Using Constraint Programming and Metaheuristics

Constraint Programming typically uses the technique of depth-first branch and bound as the method of solving optimization problems. Although this method can give the optimal solution, for large problems, the time needed to find the optimal can be prohibitive. This paper introduces a method for using local search techniques within a Constraint Programming framework, and applies this technique to vehicle routing problems. We introduce a Constraint Programming model for vehicle routing, and a system for integrating Constraint Programming and local search techniques. We then describe how the method can be accelerated by handling core constraints using fast local checks, while other more complex constraints are left to the constraint propagation system. We have coupled our local search method with a meta-heuristic to avoid the search being trapped in local minima. Several meta-heuristics are investigated ranging from a simple Tabu Search method to Guided Local Search. An empirical study over benchmark problems shows the relative merits of these techniques. Investigations indicate that the specific long-term memory technique used by Guided Local Search can be used as a diversification method for Tabu Search, resulting in significant benefit. Several new best solutions on the Solomon problems are found in relatively few iterations of our algorithm.     

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.     

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.