The so-called heuristics have been widely used in solving combinatorial optimization problems because they provide a simple but effective way to find an approximate solution. These technologies are very useful for users who do not need the exact solution but who care very much about the response time. For every existing heuristic algorithm has its pros and cons, a hyper-heuristic clustering algorithm based on the diversity detection and improvement detection operators to determine when to switch from one heuristic algorithm to another is presented to improve the clustering result in this paper. Several well-known datasets are employed to evaluate the performance of the proposed algorithm. Simulation results show that the proposed algorithm can provide a better clustering result than the state-of-the-art heuristic algorithms compared in this paper, namely, k-means, simulated annealing, tabu search, and genetic k-means algorithm.

Heat Recovery Steam Generator (HRSG) systems in conjunction with a primary gas turbine and a secondary steam turbine can provide advanced modern power generation with high thermal efficiency at low cost. To achieve such low cost efficiencies, near optimal settings of parameters of the HRSG must be employed. Unfortunately, current approaches to obtaining such parameter settings are very limited. The published literature associated with the Tabu Search (TS) metaheuristic has shown conclusively that it is a powerful methodology for the solution of very challenging large practical combinatorial optimization problems. This report documents a hybrid TS-direct pattern search (TS-DPS) approach and applied to the thermoeconomic optimization of a three pressure level HRSG system. To the best of our knowledge, this algorithm is the first to be developed that is capable of successfully solving a practical HRSG system. A requirement of the TS-DPS technique was the creation of a robust simulation module to evaluate the associated extremely complex 19 variable objective function. The simulation module was specially constructed to allow the evaluation of infeasible solutions, a highly preferable capability for methods like TS-DPS. The direct pattern search context is explicitly embodied within the TS neighborhoods permitting different neighborhood structures to be tested and compared. Advanced TS is used to control the associated continuum discretization with minimal memory requirements. Our computational studies show that TS is a very effective method for solving this HRSG optimization problem. / text

The ant system is a new meta-heuristic for hard combinatorial optimization problems. It is a population-based approach that uses exploitation of positive feedback as well as greedy search. It was first proposed for tackling the well known Traveling Salesman Problem (TSP), but has been also successfully applied to problems such as quadratic assignment, job-shop scheduling, vehicle routing and graph coloring.In this paper we introduce a new rank based version of the ant system and present results of a computational study, where we compare the ant system with simulated annealing and a genetic algorithm on several TSP instances. It turns out that our rank based ant system can compete with the other methods in terms of average behavior, and shows even better worst case behavior. (author's abstract) / Series: Working Papers SFB "Adaptive Information Systems and Modelling in Economics and Management Science"

O problema de particionamento balanceado de grafos consiste em encontrar uma partição de tamanho k dos vértices de um grafo, minimizando o número de arestas que participam do corte tal que o tamanho de nenhuma parte exceda [en~k], para algum e e > [1, k). Essa dissertação estuda esse problema, apresentando uma revisão recente de heurísticas construtivas, heurísticas de refinamento e técnicas multinível. Também propomos um novo algoritmo híbrido para resolver esse problema de particionamento. Nós mostramos como diversas estratégias para construir e aprimorar partições, assim como algumas novas propostas, podem ser integradas para formar um GRASP com path-relinking. Reportamos experimentos computacionais que mostram que essa abordagem obtém soluções competitivas com particionadores no estado-da-arte. Em particular, o algoritmo híbrido é capaz de encontrar novos melhores valores conhecidos em algumas das menores instâncias, indicando que tem uma contribuição qualitativa comparado aos métodos existentes. / The balanced graph partitioning problem asks to find a k-partition of the vertex set of an undirected graph, which minimizes the total cut size and such that the size of no part exceeds en/k , for some ee > [1, k]. This dissertation studies this problem, providing a recent review of constructive heuristics, refinement heuristics and multilevel techniques. We also propose a new hybrid algorithm for solving this partitioning problem. We show how several good existing strategies for constructing and improving partitions, as well as some newly proposed ones, can be integrated to form a GRASP with path-relinking. We report computational experiments that show that this approach obtains solutions competitive with state-of-the-art partitioners. In particular, the hybrid algorithm is able to find new best known values in some of the smaller instances, indicating that it can make a qualitative contribution compared to existing methods.

O problema de particionamento balanceado de grafos consiste em encontrar uma partição de tamanho k dos vértices de um grafo, minimizando o número de arestas que participam do corte tal que o tamanho de nenhuma parte exceda [en~k], para algum e e > [1, k). Essa dissertação estuda esse problema, apresentando uma revisão recente de heurísticas construtivas, heurísticas de refinamento e técnicas multinível. Também propomos um novo algoritmo híbrido para resolver esse problema de particionamento. Nós mostramos como diversas estratégias para construir e aprimorar partições, assim como algumas novas propostas, podem ser integradas para formar um GRASP com path-relinking. Reportamos experimentos computacionais que mostram que essa abordagem obtém soluções competitivas com particionadores no estado-da-arte. Em particular, o algoritmo híbrido é capaz de encontrar novos melhores valores conhecidos em algumas das menores instâncias, indicando que tem uma contribuição qualitativa comparado aos métodos existentes. / The balanced graph partitioning problem asks to find a k-partition of the vertex set of an undirected graph, which minimizes the total cut size and such that the size of no part exceeds en/k , for some ee > [1, k]. This dissertation studies this problem, providing a recent review of constructive heuristics, refinement heuristics and multilevel techniques. We also propose a new hybrid algorithm for solving this partitioning problem. We show how several good existing strategies for constructing and improving partitions, as well as some newly proposed ones, can be integrated to form a GRASP with path-relinking. We report computational experiments that show that this approach obtains solutions competitive with state-of-the-art partitioners. In particular, the hybrid algorithm is able to find new best known values in some of the smaller instances, indicating that it can make a qualitative contribution compared to existing methods.

O problema de particionamento balanceado de grafos consiste em encontrar uma partição de tamanho k dos vértices de um grafo, minimizando o número de arestas que participam do corte tal que o tamanho de nenhuma parte exceda [en~k], para algum e e > [1, k). Essa dissertação estuda esse problema, apresentando uma revisão recente de heurísticas construtivas, heurísticas de refinamento e técnicas multinível. Também propomos um novo algoritmo híbrido para resolver esse problema de particionamento. Nós mostramos como diversas estratégias para construir e aprimorar partições, assim como algumas novas propostas, podem ser integradas para formar um GRASP com path-relinking. Reportamos experimentos computacionais que mostram que essa abordagem obtém soluções competitivas com particionadores no estado-da-arte. Em particular, o algoritmo híbrido é capaz de encontrar novos melhores valores conhecidos em algumas das menores instâncias, indicando que tem uma contribuição qualitativa comparado aos métodos existentes. / The balanced graph partitioning problem asks to find a k-partition of the vertex set of an undirected graph, which minimizes the total cut size and such that the size of no part exceeds en/k , for some ee > [1, k]. This dissertation studies this problem, providing a recent review of constructive heuristics, refinement heuristics and multilevel techniques. We also propose a new hybrid algorithm for solving this partitioning problem. We show how several good existing strategies for constructing and improving partitions, as well as some newly proposed ones, can be integrated to form a GRASP with path-relinking. We report computational experiments that show that this approach obtains solutions competitive with state-of-the-art partitioners. In particular, the hybrid algorithm is able to find new best known values in some of the smaller instances, indicating that it can make a qualitative contribution compared to existing methods.

Le problème de planification de trajectoire des bras manipulateurs redondants est largement étudié dans la littérature. Sa résolution nécessite la prise en compte d'un certain nombre de contraintes, qui sont : • le calcul des différentes configurations par lesquelles le robot doit passer ; • l'obtention de courbes lisses (vitesses, accélérations, jerks).La prise en compte de ces deux contraintes dans la démarche de résolution peut se faire de deux manières différentes. La première consiste à supposer au préalable que les différentes courbes suivent des trajectoires lisses (utilisation de fonctions polynomiales ou trigonométriques). La résolution aura pour objectif de calculer les paramètres de chacune des courbes. La deuxième technique consiste à traiter les deux contraintes séparément. Ainsi, on calcule les différentes configurations, puis on procède à une interpolation. Outre ces deux contraintes, on doit aussi résoudre le problème de redondance du robot et la manière de l'exploiter. La première partie de cette thèse est ainsi consacrée à l'étude de cette problématique. La démarche de résolution proposée repose entièrement sur des algorithmes d'optimisation. Les deux contraintes citées précédemment étant traitées séparément, il devient aisé de prendre en compte davantage de critères dans le problème d'optimisation. Ainsi, de nouvelles formulations sont proposées. Ces dernières font appel aux techniques d'optimisation hiérarchique, afin de faciliter le traitement de la redondance, qui est exploitée pour l'évitement d'obstacles et les singularités du robot. Vu la complexité de ces formulations, nous avons préconisé une démarche de résolution approchée, qui fait appel aux métaheuristiques d'optimisation, en particulier les algorithmes génétiques. La validation de la démarche proposée est faite sur le modèle du robot Neuromate. La deuxième partie de cette thèse est consacrée à une application avec le robot Neuromate. Plus particulièrement, nous nous sommes intéressés à l'opération de craniotomie avec le robot Neuromate. L'objectif est de réaliser une petite ouverture au niveau du crâne humain afin que le chirurgien puisse glisser des instruments pour traiter des maladies affectant le cerveau. Réalisée par le chirurgien lui-même, sans assistance robotique, cette opération est très délicate, du fait du manque de précision et de l'allongement du temps d'intervention. Les risques d'aggravation sont particulièrement élevés si la zone d'intervention est proche des veines ou située dans des régions qui ont une fonction importante (région motrice ou région de langage, par exemple). La démarche classique de la craniotomie assistée fait appel à la co-manipulation, qui contraint le chirurgien à participer à l'action, et donc à fournir des efforts. Dans ce travail, une autre démarche est proposée, basée sur l'intégration au robot Neuromate d'un système d'usinage à grande vitesse. Des tests ont été réalisés sur des plaques en polyamide dont les caractéristiques mécaniques sont proches de celles du crâne / The problem of trajectory planning is largely studied in the literature. In order to solve this problem, we need to take into account two important constraints, which are : • the computation of the different configurations in which the robot must pass ; • the smoothness of the resulting curves (velocities, accelerations, jerks).Taking both constraints into consideration can be done in two different ways. The first one is to suppose that all the curves are smooth (using polynomial or trigonometric functions) and then, the aim of the resolution is to find the coefficient of each of them. The second way is to deal the constraints separately. Thus, we compute in first the different configurations in which the robot must pass. After that, we compute the whole curve by interpolation. Adding to the constraints mentioned before, we have to solve the problem of the redundancy of the robot. The first part of this thesis is then devoted to the study of this problem. The proposed solving technique is entirely based on optimization algorithms. The two constraints cited above are treated separately, which allows to take more criteria into account. Thus, new formulations are proposed. They are based on the hierarchical optimization problem, which facilitates handling of the redundancy which is used for the obstacle and the singularities avoidance. Because of the high complexity of the proposed formulations, we chose to use metaheuristics to resolve them, especially the genetic algorithms. We validated the proposed technique on the model of the Neuromate robot. The second part of this thesis is devoted to an application achieved with the Neuromate robot. The procedure of craniotomy is used to perform a very small hole in the human skull in order to allow the surgeon to introduce medical instruments, to take care of some illness that affects brain. Achieved by the surgeon himself, without any robotics aid, this operation is very delicate, because of its lack of precision and increase of processing time. The risks are particularly high if the area of intervention is near the veins. The classical solving technique is based on the co-manipulation principle, which means that the surgeon participates in the action and then, provides an effort. In this work, another solving technique is proposed. It is based on the integration of a machining system with the Neuromate robot. The tests are achieved on plates made of polyamide of which the mechanical characteristics are near to those of the human skull

Cette thèse porte sur la modélisation et la résolution de différents problèmes de tournées de véhicules et plus particulièrement sur des problèmes de transport de personnes. Ces problèmes, demandent, entre autre, de respecter une qualité de service minimale pour les solutions proposées. Pour résoudre ces problèmes, plusieurs méthodes d'optimisation de type métaheuristique sont proposées pour obtenir des solutions de bonne qualité dans des temps raisonnables. Trois problèmes sont traités successivement : le DARP, le TDVRP, le SDARP. Le premier est un problème de transport à la demande (DARP - Dial-A-Ride Problem) qui est le problème de transport de personnes le plus connu de la littérature. Il est proposé dans ce chapitre une méthode de type ELS qui a été comparée aux meilleures méthodes publiées. Les tests montrent que la méthode ELS est compétitive en termes de temps de calcul et de qualité des résultats. Le deuxième problème est une extension du problème de tournées de véhicules (VRP - Vehicle Routing Problem) dans lequel les temps de trajet entre les sommets varient au cours de la journée (TDVRP - Time Dependent Vehicle Routing Problem). Dans ce problème, une distinction existe entre les temps de conduite et les temps de travail des chauffeurs. La différence entre les deux correspond aux temps de pause. Ils sont utilisés ici durant les tournées pour éviter aux chauffeurs de conduire durant les périodes à fort ralentissement du trafic. La méthode proposée permet entre autre de positionner stratégiquement ces pauses afin de réduire le temps de conduite et de proposer de nouvelles solutions. Le dernier problème traité concerne la résolution d'un DARP stochastique. Dans ce problème, les temps de trajet entre les clients ne sont plus déterministes, et ils sont modélisés par une loi de probabilité. L'objectif est de déterminer des solutions robustes aux fluctuations des temps de trajets sur les arcs. Une première approche a permis de calculer des solutions robustes qui ont une probabilité importante d'être réalisables, une seconde approche a permis de générer un ensemble de solutions offrant un équilibre entre la robustesse et le coût. / In this thesis, we are interested in modeling and solving various vehicle routing problems (VRP), especially passenger transportation problems. These problems aim at finding solutions which guarantee a required quality of service. Several metaheuristics are proposed to obtain high quality solutions within reasonable time. Three problems are addressed: the Dial-A-Ride Problem (DARP), the Time-Dependent Vehicle Routing Problem (TDVRP) and the Stochastic DARP (SDARP). The DARP is a well-known on-demand transportation problem. We propose an Evolutionary Local Search (ELS) method. It relies on a new randomized constructive heuristic and on adaptive probabilities for selecting neighborhood structures. This approach is compared with existing methods on classical instances. Results show the interest of the proposed method. The TDVRP is an extension of VRP in which the transportation time varies throughout the day. The driving time is separated from the drivers working time and the difference corresponds to the resting time. The resting time is used to avoid driving during highly congested periods. The proposed method set these resting times in order to reduce the driving time. Hence new solutions avoiding congestion as much as possible are proposed. In the SDARP, the travel time between clients is stochastic and thus follows a probability distribution. The objective is to compute robust solutions, i.e. solutions which handle variations of the transportation time. Two approaches are proposed for this problem. The first one produces robust solutions that have a significant probability of staying feasible. The second one generates a set of compromise solutions, balancing the robustness and the cost.

South African metropolitan areas are experiencing rapid growth and require an increase in network infrastructure. Increased congestion negatively impacts both public and freight transport costs. The concept of City Logistics is concerned with the mobility of cities, and entails the process of optimizing urban logistics activities by concerning the social, environmental, economic, financial, and energy impacts of urban freight movement. In a costcompetitive environment, freight transporters often use sophisticated vehicle routing and scheduling applications to improve fleet utilization and reduce the cost of meeting customer demands. In this thesis, the candidate builds on the observation that vehicle routing and scheduling algorithms are inherent problem specific, with no single algorithm providing a dominant solution to all problem environments. Commercial applications mostly deploy a single algorithm in a multitude of environments which would often be better serviced by various different algorithms. This thesis algorithmically implements the ability of human decision makers to choose an appropriate solution algorithm when solving scheduling problems. The intent of the routing agent is to classify the problem as representative of a traditional problem set, based on its characteristics, and then to solve the problem with the most appropriate solution algorithm known for the traditional problem set. A not-so-artificially-intelligent-vehicle-routing-agent™ is proposed and developed in this thesis. To be considered intelligent, an agent is firstly required to be able to recognize its environment. Fuzzy c-means clustering is employed to analyze the geographic dispersion of the customers (nodes) from an unknown routing problem to determine to which traditional problem set it relates best. Cluster validation is used to classify the routing problem into a traditional problem set. Once the routing environment is classified, the agent selects an appropriate metaheuristic to solve the complex variant of the Vehicle Routing Problem. Multiple soft time windows, a heterogeneous fleet, and multiple scheduling are addressed in the presence of time-dependent travel times. A new initial solution heuristic is proposed that exploits the inherent configuration of customer service times through a concept referred to as time window compatibility. A high-quality initial solution is subsequently improved by the Tabu Search metaheuristic through both an adaptive memory, and a self-selection structure. As an alternative to Tabu Search, a Genetic Algorithm is developed in this thesis. Two new crossover mechanisms are proposed that outperform a number of existing crossover mechanisms. The first proposed mechanism successfully uses the concept of time window compatibility, while the second builds on an idea used from a different sweeping-arc heuristic. A neural network is employed to assist the intelligent routing agent to choose, based on its knowledge base, between the two metaheuristic algorithms available to solve the unknown problem at hand. The routing agent then not only solves the complex variant of the problem, but adapts to the problem environment by evaluating its decisions, and updating, or reaffirming its knowledge base to ensure improved decisions are made in future. / Thesis (PhD (Industrial Engineering))--University of Pretoria, 2007. / Industrial and Systems Engineering / PhD / unrestricted

Metaheuristics are used to find feasible solutions to hard Combinatorial Optimization Problems (COPs). Constraint Satisfaction Problems (CSPs) may be formulated as COPs, where the objective is to reduce the number of violated constraints to zero. The popular puzzle Sudoku is an NP-complete problem that has been used to study the effectiveness of metaheuristics in solving CSPs. Applying the Simulated Annealing (SA) metaheuristic to Sudoku has been shown to be a successful method to solve CSPs. However, the ‘easy-hard-easy’ phase-transition behavior frequently attributed to a certain class of CSPs makes finding a solution extremely difficult in the hard phase because of the vast search space, the small number of solutions and a fitness landscape marked by many plateaus and local minima. Two key mechanisms that metaheuristics employ for searching are diversification and intensification. Diversification is the method of identifying diverse promising regions of the search space and is achieved through the process of heating/reheating. Intensification is the method of finding a solution in one of these promising regions and is achieved through the process of cooling. The hard phase area of the search terrain makes traversal without becoming trapped very challenging. Running the best available method - a Constraint Propagation/Depth-First Search algorithm - against 30,000 benchmark problem-instances, 20,240 remain unsolved after ten runs at one minute per run which we classify as very hard. This dissertation studies the delicate balance between diversification and intensification in the search process and offers a hybrid SA algorithm to solve very hard instances. The algorithm presents (a) a heating/reheating strategy that incorporates the lowest solution cost for diversification; (b) a more complex two-stage cooling schedule for faster intensification; (c) Constraint Programming (CP) hybridization to reduce the search space and to escape a local minimum; (d) a three-way swap, secondary neighborhood operator for a low expense method of diversification. These techniques are tested individually and in hybrid combinations for a total of 11 strategies, and the effectiveness of each is evaluated by percentage solved and average best run-time to solution. In the final analysis, all strategies are an improvement on current methods, but the most remarkable results come from the application of the “Quick Reset” technique between cooling stages.