Щоб переглянути інші типи публікацій з цієї теми, перейдіть за посиланням: Metaheuristic.
Дисертації з теми "Metaheuristic"
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся з топ-50 дисертацій для дослідження на тему "Metaheuristic".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Переглядайте дисертації для різних дисциплін та оформлюйте правильно вашу бібліографію.
1
Auer, Jens. "Metaheuristic Multiple Sequence Alignment Optimisation." Thesis, University of Skövde, School of Humanities and Informatics, 2004. http://urn.kb.se/resolve?urn=urn:nbn:se:his:diva-899.
Повний текст джерелаАнотація:
The ability to tackle NP-hard problems has been greatly extended by the introduction of Metaheuristics (see Blum & Roli (2003)) for a summary of most Metaheuristics, general problem-independent optimisation algorithms extending the hill-climbing local search approach to escape local minima. One of these algorithms is Iterated Local Search (ILS) (Lourenco et al., 2002; Stützle, 1999a, p. 25ff), a recent easy to implement but powerful algorithm with results comparable or superior to other state-of-the-art methods for many combinatorial optimisation problems, among them the Traveling Salesman (TSP) and Quadratic Assignment Problem (QAP). ILS iteratively samples local minima by modifying the current local minimum and restarting
a local search porcedure on this modified solution. This thesis will show how ILS can be implemented for MSA. After that, ILS will be evaluated and compared to other MSA algorithms by BAliBASE (Thomson et al., 1999), a set of manually refined alignments used in most recent publications of algorithms and in at least two MSA algorithm surveys. The runtime-behaviour will be evaluated using runtime-distributions.
The quality of alignments produced by ILS is at least as good as the best algorithms available and significantly superiour to previously published Metaheuristics for MSA, Tabu Search and Genetic Algorithm (SAGA). On the average, ILS performed best in five out of eight test cases, second for one test set and third for the remaining two. A drawback of all iterative methods for MSA is the long runtime needed to produce good alignments. ILS needs considerably less runtime than Tabu Search and SAGA, but can not compete with progressive or consistency based methods, e. g. ClustalW or T-COFFEE.
2
Clark, John A. "Metaheuristic search as a cryptological tool." Thesis, University of York, 2001. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.247755.
Повний текст джерела
3
Xu, Ying. "Metaheuristic approaches for QoS multicast routing problems." Thesis, University of Nottingham, 2011. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.546470.
Повний текст джерела
4
Landa, Silva Jesus Dario. "Metaheuristic and multiobjective approaches for space allocation." Thesis, University of Nottingham, 2003. http://eprints.nottingham.ac.uk/10147/.
Повний текст джерелаАнотація:
This thesis presents an investigation on the application of metaheuristic techniques to tackle the space allocation problem in academic institutions. This is a combinatorial optimisation problem which refers to the distribution of the available room space among a set of entities (staff, research students, computer rooms, etc.) in such a way that the space is utilised as efficiently as possible and the additional constraints are satisfied as much as possible. The literature on the application of optimisation techniques to approach the problem mentioned above is scarce. This thesis provides a description and formulation of the problem. It also proposes and compares a range of heuristics for the initialisation of solutions and for neighbourhood exploration. Four well-known metaheuristics (iterative improvement, simulated annealing, tabu search and genetic algorithms) are adapted and tuned for their application to the problem investigated here. The performance of these techniques is assessed and benchmark results are obtained. Also, hybrid approaches are designed that produce sets of high quality and diverse solutions in much shorter time than those required by space administrators who construct solutions manually. The hybrid approaches are also adapted to tackle the space allocation problem from a two-objective perspective. It is also revealed that the use of aggregating functions or relaxed dominance to evaluate solutions in Pareto optimisation, can be more beneficial than the standard dominance relation to enhance the performance of some multiobjective optimisers in some problem domains. A range of single-solution metaheuristics are extended to create hybrid evolutionary approaches based on the scheme of cooperative local search. This scheme promotes the cooperation of a population of local searchers by means of mechanisms to share the information gained during the search. This thesis also reports the best results known so far for a set of test instances of the space allocation problem in academic institutions. This thesis pioneers the application of metaheuristics to solve the space allocation problem. The major contributions are: provides a formulation of the problem together with tests data sets, reports the best known results for these test instances, investigates the multiobjective nature of the problem and proposes a new form of hybridising metaheuristics.
5
Lara, Garazi Zabalo Manrique de. "Metaheuristic Algorithms for Transportation Problems in HealthCare." Doctoral thesis, Università di Siena, 2018. http://hdl.handle.net/11365/1050844.
Повний текст джерелаАнотація:
One of the most challenging problems in healthcare systems nowadays is the one of satisfying all the demand while delivering a high-quality service with very limited resources. That is why optimization problems in healthcare have been the subject of many research studies. During recent years transportation problems in particular have gathered a lot of attention. Healthcare transportation problems can be divided in two main groups, patient transportation and the transportation of goods, such as biological samples. Patient transportation is an important issue in healthcare systems, both for emergency and non-emergency transportation. Non-emergency transportations contain for example, the transfer of patients between hospitals, the transportation between patients’ homes and medical structures and the transportation to nursing homes and rehabilitation centers. The complexity of the above mentioned problems, the many user related constraints and the limited resources make these types of problems very challenging. That is why OR and in particular optimization algorithms have become a useful tool to solve these problems. Pickup and delivery problems (PDP) are a variant of vehicle routing problems (VRP), where a number of loads have to be transported from pickup locations to delivery locations with the aim of finding a routing for a fleet of available vehicles that minimizes the overall routing cost. Each available vehicle has a given capacity and is located in a depot, where it has to return at the end of the service. Each request is characterized by the size of the load and by the location where it has to be picked up (pickup location) and the location where it has to be dropped off (delivery location). Dial-a-ride problem (DARP) is a generalization of the Pickup and Delivery Problem with Time Windows (PDPTW). In DARP, people are transported instead of goods and consequently issues on the quality of the provided service and timing must be carefully taken into account (through additional constraints or by extra terms in the objective function).
In this thesis different metaheuristic algorithms are proposed to solve transportation problems in healthcare. Two real-life transportation problems are presented one focusing on the on-demand patient transportation and the other focused on the collection and transportation of biological samples. The thesis tackles the unforeseen constraints that arise when adapting pickup and delivery (PDP) problems to real scenarios. These unforeseen constraints include the user’s preferences, complex cost functions, user’s quality service for the patient transportation problem and the possibility of transfers for the biological sample transportation problem.
The first addressed problem is a multi-depot dial-a-ride problem arising from a real-world healthcare application, concerning the non-emergency transportation of patients in the Italian region of Tuscany. Different versions of Variable Neighborhood Search (VNS) algorithms have been created able to tackle all the characteristics of the problem. The computational results obtained by testing the VNS algorithms on literature instances and on random instances taken from a real-life healthcare problem show the effectiveness of the proposed approaches.
Finally, the last problem deals with a multi-depot pickup and delivery problem with transfers that arises from a real-world healthcare application, the blood and biological sample transportation in the Metropolitan Area of Bologna, an Italian city. The proposed Adaptive Large Neighborhood Search algorithm is able to tackle all the characteristics of the problem. Computational results on real-life instances show the effectiveness of the proposed approach, in quality of the solution as well as in the distribution of the vehicles to the hospital, compared to the current real situation of the HUB, the main hospital of Bologna.
6
Fan, Lang. "Metaheuristic methods for the urban transit routing problem." Thesis, Cardiff University, 2009. http://orca.cf.ac.uk/54237/.
Повний текст джерелаАнотація:
In our research, we focus on these three issues, and concentrate on developing a metaheuristic framework for solving the UTRP. Embedding simple heuristic algorithms (hill-climbing and simulated annealing) within this framework, we have beaten previously best published results for Mandi’s benchmark problem, which is the only generally available data set. Due to the lack of “standard models” for the UTRP, and a shortage of benchmark data it is difficult for researchers to compare their approaches. Thus we introduce a simplified model and implement a data set generation program to produce realistic test data sets much larger than Mandi’s problem. Furthermore, some Lower Bounds and necessary constraints of the UTRP are also researched, which we use to help validate the quality of our results, particularly those obtained for our new data sets. Finally, a multi-objective optimisation algorithm is designed to solve our urban transit routing problem in which the operator’s cost is modelled in addition to passenger quality of service.
7
Yagiura, Mutsunori. "Studies on Metaheuristic Algorithms for Combinatorial Optimization Problems." Kyoto University, 1999. http://hdl.handle.net/2433/157060.
Повний текст джерелаАнотація:
本文データは平成22年度国立国会図書館の学位論文(博士)のデジタル化実施により作成された画像ファイルを基にpdf変換したものであるKyoto University (京都大学)
0048
新制・論文博士
博士(工学)
乙第10101号
論工博第3416号
新制||工||1146(附属図書館)
UT51-99-G578
(主査)教授 茨木 俊秀, 教授 岩間 一雄, 教授 加藤 直樹
学位規則第4条第2項該当
8
Yang, Yulian. "Metaheuristic based peer rewiring for semantic overlay networks." Thesis, Lyon, INSA, 2014. http://www.theses.fr/2014ISAL0036/document.
Повний текст джерелаАнотація:
Nous considérons une plate-forme pair-à-pair pour la Recherche d'Information (RI) collaborative. Chaque pair héberge une collection de documents textuels qui traitent de ses sujets d'intérêt. En l'absence d'un mécanisme d'indexation global, les pairs indexent localement leurs documents et s'associent pour fournir un service distribué de réponse à des requêtes. Notre objectif est de concevoir un protocole décentralisé qui permette aux pairs de collaborer afin de transmettre une requête depuis son émetteur jusqu'aux pairs en possession de documents pertinents. Les réseaux logiques sémantiques (Semantic Overlay Networks, SON) représentent la solution de référence de l'état de l'art. Les pairs qui possèdent des ressources sémantiques similaires sont regroupés en clusters. Les opérations de RI seront alors efficaces puisqu'une requête sera transmise aux clusters de pairs qui hébergent les ressources pertinentes. La plupart des approches actuelles consistent en une reconfiguration dynamique du réseau de pairs (peer rewiring). Pour ce faire, chaque pair exécute périodiquement un algorithme de marche aléatoire ou gloutonne sur le réseau pair-à-pair afin de renouveler les pairs de son cluster. Ainsi, un réseau à la structure initialement aléatoire évolue progressivement vers un réseau logique sémantique. Jusqu'à présent, les approches existantes n'ont pas considéré que l'évolution de la topologie du réseau puisse influer sur les performances de l'algorithme de reconfiguration dynamique du réseau. Cependant, s'il est vrai que, pour une configuration initiale aléatoire des pairs, une marche aléatoire sera efficace pour découvrir les pairs similaires, lorsque des clusters commencent à émerger une approche gloutonne devient alors mieux adaptée. Ainsi, nous proposons une stratégie qui applique un algorithme de recuit simulé (Simulated Annealing, SA) afin de faire évoluer une stratégie de marche aléatoire vers une stratégie gloutonne lors de la construction du SON. Cette thèse contient plusieurs avancées concernant l'état de l'art dans ce domaine. D'abbord, nous modélisions formellement la reconfiguration dynamique d'un réseau en un SON. Nous identifions un schéma générique pour la reconfiguration d'un réseau pair-à-pair, et après le formalisons en une procédure constituée de trois étapes. Ce framework cohérent offre à ses utilisateurs de quoi le paramétrer. Ensuite, le problème de la construction d'un SON est modélisé sous la forme d'un problème d'optimisation combinatoire pour lequel les opérations de reconfiguration du réseau correspondent à la recherche décentralisée d'une solution locale. Fondée sur ce modèle, une solution concrète à base de recuit simulé est proposée. Nous menons une étude expérimentale poussée sur la construction du SON et la RI sur SONs, et validions notre approcheA Peer-to-Peer (P2P) platform is considered for collaborative Information Retrieval (IR). Each peer hosts a collection of text documents with subjects related to its owner's interests. Without a global indexing mechanism, peers locally index their documents, and provide the service to answer queries. A decentralized protocol is designed, enabling the peers to collaboratively forward queries from the initiator to the peers with relevant documents. Semantic Overlay Network (SONs) is one the state of the art solutions, where peers with semantically similar resources are clustered. IR is efficiently performed by forwarding queries to the relevant peer clusters in an informed way. SONs are built and maintained mainly via peer rewiring. Specifically, each peer periodically sends walkers to its neighborhood. The walkers walk along peer connections, aiming at discovering more similar peers to replace less similar neighbors of its initiator. The P2P network then gradually evolves from a random overlay network to a SON. Random and greedy walk can be applied individually or integrated in peer rewiring as a constant strategy during the progress of network evolution. However, the evolution of the network topology may affect their performance. For example, when peers are randomly connected with each other, random walk performs better than greedy walk for exploring similar peers. But as peer clusters gradually emerge in the network, a walker can explore more similar peers by following a greedy strategy. This thesis proposes an evolving walking strategy based on Simulated Annealing (SA), which evolves from a random walk to a greedy walk along the progress of network evolution. According to the simulation results, SA-based strategy outperforms current approaches, both in the efficiency to build a SON and the effectiveness of the subsequent IR. This thesis contains several advancements with respect to the state of the art in this field. First of all, we identify a generic peer rewiring pattern and formalize it as a three-step procedure. Our technique provides a consistent framework for peer rewiring, while allowing enough flexibility for the users/designers to specify its properties. Secondly, we formalize SON construction as a combinatorial optimization problem, with peer rewiring as its decentralized local search solution. Based on this model, we propose a novel SA-based approach to peer rewiring. Our approach is validated via an extensive experimental study on the effect of network wiring on (1) SON building and (2) IR in SONs
9
Yang, Y. "Metaheuristic based Peer Rewiring for Semantic Overlay Networks." Doctoral thesis, Università degli Studi di Milano, 2014. http://hdl.handle.net/2434/236979.
Повний текст джерелаАнотація:
A Peer-to-Peer (P2P) platform is considered for collaborative Information Retrieval (IR). Each peer hosts a collection of text documents with subjects related to its owner's interests. Without a global indexing mechanism, peers locally index their documents, and provide the service to answer queries. A decentralized protocol is designed, enabling the peers to collaboratively forward queries from the initiator to the peers with relevant documents.
Semantic Overlay Network (SON) is one of the state-of-the-art solutions, where peers with semantically similar resources are clustered. IR can then be efficiently performed by forwarding queries to the relevant peer clusters in an informed way. SONs are built and maintained mainly via peer rewiring. Specifically, each peer periodically sends walkers to its neighborhood. The walkers walk along peer connections, aiming at discovering more similar peers to replace less similar neighbors of its initiator. The P2P network hence gradually evolves from a random overlay network to a SON.
Random and greedy walk can be applied individually or integrated in peer rewiring as a constant strategy during the progress of network evolution. However, the evolution of the network topology may affect their performance. For example, when peers are randomly connected with each other, random walk performs better than greedy walk for exploring similar peers. But as peer clusters gradually emerge in the network, a walker can explore more similar peers by following a greedy strategy. This thesis proposes an evolving walking strategy based on Simulated Annealing (SA), which evolves from a random walk to a greedy walk along the progress of network evolution. According to the simulation results, SA-based strategy outperforms current approaches, both in the efficiency to build a SON and the effectiveness of the subsequent IR.
This thesis contains several advancements with respect to the state-of-the-art in this field. First of all, we identify a generic peer rewiring pattern and formalize it as a three-step procedure. Our technique provides a consistent framework for peer rewiring, while allowing enough flexibility for the users/designers to specify its properties. Secondly, we formalize SON construction as a combinatorial optimization problem, with peer rewiring as its decentralized local search solution. Based on this model, we propose a novel SA-based approach to peer rewiring. Our approach is validated via an extensive experimental study on the effect of network rewiring on (i) SON building and (ii) IR in SONs.
10
Joubert, Johannes Wilhelm. "An integrated and intelligent metaheuristic for constrained vehicle routing." Pretoria : [s.n.], 2006. http://upetd.up.ac.za/thesis/available/etd-07202007-175138.
Повний текст джерела
11
Zhao, Jian-Hua. "The reliability optimization of mechanical systems using metaheuristic approach." Mémoire, École de technologie supérieure, 2005. http://espace.etsmtl.ca/326/1/ZHAO_Jian%2DHua.pdf.
Повний текст джерелаАнотація:
Le problème d'optimisation de fiabilité des systèmes mécaniques est un problème compliqué avec contraintes multicritères, dont la solution optimale est en générale un compromis. Le travail présenté dans ce mémoire se concentre sur l'optimisation de fiabilité des systèmes mécaniques en séries parallèles. Basée sur le ACSRAP (Ant Colony System for Redundancy Apportionment Problem), une nouvelle approche est présentée. Cette approche combine les caractéristiques de l'ACS avec des recherches locales. Donc il optimise la fiabilité globale du système tout en satisfaisant les contraintes en terme de coût, de poids et de volume. Les avantages sur la précision, l'efficacité, et la capacité de la nouvelle approche sont illustrés par les résultats de comparaison de là nouvelle technique avec ceux obtenues par d'autres approches. En outre, l'application de la technique sur une boite de transmission (Gear Train System) est aussi présenté pour montrer les procédures de l'application de la nouvelle technique sur les cas réels.
12
Wu, Yanghui. "Problem dependent metaheuristic performance in Bayesian network structure learning." Thesis, Robert Gordon University, 2012. http://hdl.handle.net/10059/790.
Повний текст джерелаАнотація:
Bayesian network (BN) structure learning from data has been an active research area in the machine learning field in recent decades. Much of the research has considered BN structure learning as an optimization problem. However, the finding of optimal BN from data is NP-hard. This fact has driven the use of heuristic algorithms for solving this kind of problem. Amajor recent focus in BN structure learning is on search and score algorithms. In these algorithms, a scoring function is introduced and a heuristic search algorithm is used to evaluate each network with respect to the training data. The optimal network is produced according to the best score evaluated. This thesis investigates a range of search and score algorithms to understand the relationship between technique performance and structure features of the problems. The main contributions of this thesis include (a) Two novel Ant Colony Optimization based search and score algorithms for BN structure learning; (b) Node juxtaposition distribution for studying the relationship between the best node ordering and the optimal BN structure; (c) Fitness landscape analysis for investigating the di erent performances of both chain score function and the CH score function; (d) A classifier method is constructed by utilizing receiver operating characteristic curve with the results on fitness landscape analysis; and finally (e) a selective o -line hyperheuristic algorithm is built for unseen BN structure learning with search and score algorithms. In this thesis, we also construct a new algorithm for producing BN benchmark structures and apply our novel approaches to a range of benchmark problems and real world problem.
13
Monett, Díaz Dagmar [Verfasser]. "Agent-Based Configuration of (Metaheuristic) Algorithms / Dagmar Monett Díaz." Aachen : Shaker, 2005. http://d-nb.info/1186582278/34.
Повний текст джерела
14
Whitwell, Glenn. "Novel heuristic and metaheuristic approaches to cutting and packing." Thesis, University of Nottingham, 2004. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.416726.
Повний текст джерела
15
ASSIS, FERNANDO APARECIDO DE. "CONSTRUCTIVE METAHEURISTIC ALGORITHM FOR SOLVING TRANSMISSION EXPANSION PLANNING PROBLEMS." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2018. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=35771@1.
Повний текст джерелаАнотація:
PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIROCOORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR
CONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICO
PROGRAMA DE EXCELENCIA ACADEMICA
O planejamento da expansão da transmissão (PET) visa identificar reforços para a rede a fim de permitir uma adequada interligação entre a demanda e a geração de energia elétrica, ambas previstas para um determinado horizonte futuro de planejamento. Um bom plano de expansão deve garantir o adequado equilíbrio entre o custo de investimento e o custo de operação, mantendo ainda um nível satisfatório de confiabilidade no fornecimento da energia. Entretanto, a identificação de bons planos de expansão para a rede de transmissão tem se tornado uma tarefa cada vez mais difícil. Isso se deve, principalmente, às características e dimensões dos sistemas atuais e, ainda, às incertezas inerentes ao problema. Dessa forma, torna-se necessário o desenvolvimento de ferramentas cada vez mais ela-boradas para auxílio dos planejadores. Neste sentido, é proposto nesta tese de dou-torado um algoritmo metaheurístico construtivo, denominado AMC-PET, o qual realiza um processo gradual e concomitante de construção de soluções viáveis (planos de expansão). Por meio de mecanismos baseados principalmente em índices de sensibilidade para avaliação dos reforços candidatos e na troca de informações entre as soluções correntes, o processo construtivo proposto é conduzido, parcimoniosamente, na direção de planos de excelente qualidade. Para validação da metodologia proposta, é utilizado o problema PET estático de longo prazo, considerando o critério de segurança N-1 para a rede de transmissão. Um mode-lo linearizado de rede com a inclusão de perdas ôhmicas é utilizado para análise das configurações obtidas. Dois sistemas teste, comumente utilizados neste tópico de pesquisa e, também, um sistema real de grande porte, que corresponde à rede elétrica do sul do Brasil, são empregados na validação.
The transmission expansion planning (TEP) aims to identify reinforcements for the network in order to allow an adequate interconnection between load and electric power generation, both foreseen for a given future planning horizon. A good expansion plan must ensure the proper balance between investment and operating costs, while preserving a satisfactory reliability level in the energy supply. However, identifying good expansion plans for the transmission network has become an increasingly difficult task. This is mainly due to the characteristics and dimensions of current power systems and also to the uncertainties inherent to the problem. Thus, it becomes necessary to develop even more elaborate tools to assist system planners. This doctoral thesis proposes a new optimization tool named constructive metaheuristic algorithm (CMA-TEP). The proposed CMA-TEP tool performs a gradual and parallel process of building feasible solutions (expansion plans). By means of mechanisms mainly based on sensitivity indices for the evaluation of candidate reinforcements and on the information exchange among current solutions, the proposed constructive process is parsimoniously conducted towards high quality plans. To verify the performance of the proposed methodology, the long-term static PET problem considering the N-1 security criterion for the transmission network is solved. A linearized network model with the inclusion of ohmic losses is used to analyze the obtained configurations. Two test systems, commonly utilized in this research area, and also a real large network, which corresponds to the electric grid of Southern Brazil, are used to validate the proposed method.
16
Martins, Ana Mafalda de Oliveira. "Geometric optimization on visibility problems: metaheuristic and exact solutions." Doctoral thesis, Universidade de Aveiro, 2009. http://hdl.handle.net/10773/2947.
Повний текст джерелаАнотація:
Doutoramento em MatemáticaOs problemas de visibilidade têm diversas aplicações a situações reais. Entre os mais conhecidos, e exaustivamente estudados, estão os que envolvem os conceitos de vigilância e ocultação em estruturas geométricas (problemas de vigilância e ocultação). Neste trabalho são estudados problemas de visibilidade em estruturas geométricas conhecidas como polígonos, uma vez que estes podem representar, de forma apropriada, muitos dos objectos reais e são de fácil manipulação computacional. O objectivo dos problemas de vigilância é a determinação do número mínimo de posições para a colocação de dispositivos num dado polígono, de modo a que estes dispositivos consigam “ver” a totalidade do polígono. Por outro lado, o objectivo dos problemas de ocultação é a determinação do número máximo de posições num dado polígono, de modo a que quaisquer duas posições não se consigam “ver”. Infelizmente, a maior parte dos problemas de visibilidade em polígonos são NP-difíceis, o que dá origem a duas linhas de investigação: o desenvolvimento de algoritmos que estabelecem soluções aproximadas e a determinação de soluções exactas para classes especiais de polígonos. Atendendo a estas duas linhas de investigação, o trabalho é dividido em duas partes. Na primeira parte são propostos algoritmos aproximados, baseados essencialmente em metaheurísticas e metaheurísticas híbridas, para resolver alguns problemas de visibilidade, tanto em polígonos arbitrários como ortogonais. Os problemas estudados são os seguintes: “Maximum Hidden Vertex Set problem”, “Minimum Vertex Guard Set problem”, “Minimum Vertex Floodlight Set problem” e “Minimum Vertex k-Modem Set problem”. São também desenvolvidos métodos que permitem determinar a razão de aproximação dos algoritmos propostos. Para cada problema são implementados os algoritmos apresentados e é realizado um estudo estatístico para estabelecer qual o algoritmo que obtém as melhores soluções num tempo razoável. Este estudo permite concluir que as metaheurísticas híbridas são, em geral, as melhores estratégias para resolver os problemas de visibilidade estudados. Na segunda parte desta dissertação são abordados os problemas “Minimum Vertex Guard Set”, “Maximum Hidden Set” e “Maximum Hidden Vertex Set”, onde são identificadas e estudadas algumas classes de polígonos para as quais são determinadas soluções exactas e/ou limites combinatórios.
Visibility problems have several applications to real-life problems. Among the most distinguished and exhaustively studied visibility problems are the ones involving concepts of guarding and hiding on geometrical structures (guarding and hiding problems). This work deals with visibility problems on geometrical structures known as polygons, since polygons are appropriate representations of many real-world objects and are easily handled by computers. The objective of the guarding problems studied in this thesis is to find a minimum number of device positions on a given polygon such that these devices collectively ''see'' the whole polygon. On the other hand, the goal of the hiding problems is to find a maximum number of positions on a given polygon such that no two of these positions can “see" each other. Unfortunately, most of the visibility problems on polygons are NP-hard, which opens two lines of investigation: the development of algorithms that establish approximate solutions and the determination of exact solutions on special classes of polygons. Accordingly, this work is divided in two parts where these two lines of investigation are considered. The first part of this thesis proposes approximation algorithms, mainly based on metaheuristics and hybrid metaheuristics, to tackle some visibility problems on arbitrary and orthogonal polygons. The addressed problems are the Maximum Hidden Vertex Set problem, the Minimum Vertex Guard Set problem, the Minimum Vertex Floodlight Set problem and the Minimum Vertex k-Modem Set problem. Methods that allow the determination of the performance ratio of the developed algorithms are also proposed. For each problem, the proposed algorithms are implemented and a statistical study is performed to determine which of the developed methods obtains the best solution in a reasonable amount of time. This study allows to conclude that, in general, the hybrid metaheuristics are the best approach to solve the studied visibility problems. The second part of this dissertation addresses the Minimum Vertex Guard Set problem, the Maximum Hidden Set problem and the Maximum Hidden Vertex Set problem, where some classes of polygons are identified and studied and for which are determined exact solutions and/or combinatorial bounds.
17
Jin, Yan. "Hybrid metaheuristic algorithms for sum coloring and bandwidth coloring." Thesis, Angers, 2015. http://www.theses.fr/2015ANGE0062/document.
Повний текст джерелаАнотація:
Le problème de somme coloration minimum (MSCP) et le problème de coloration de bande passante (BCP) sont deux généralisations importantes du problème de coloration des sommets classique avec de nombreuses applications dans divers domaines, y compris la conception de circuits imprimés, la planication, l’allocation de ressource, l’affectation de fréquence dans les réseaux mobiles, etc. Les problèmes MSCP et BCP étant NP-difficiles, les heuristiques et métaheuristiques sont souvent utilisées en pratique pour obtenir des solutions de bonne qualité en un temps de calcul acceptable. Cette thèse est consacrée à des métaheuristiques hybrides pour la résolution efcace des problèmes MSCP et BCP. Pour le problème MSCP, nous présentons deux algorithmes mémétiques qui combinent l’évolution d’une population d’individus avec de la recherche locale. Pour le problème BCP, nous proposons un algorithme hybride à base d’apprentissage faisant coopérer une méthode de construction “informée” avec une procédure de recherche locale. Les algorithmes développés sont évalués sur des instances biens connues et se révèlent très compétitifs par rapport à l’état de l’art. Les principaux composants des algorithmes que nous proposons sont également analysésThe minimum sum coloring problem (MSCP) and the bandwidth coloring problem (BCP) are two important generalizations of the classical vertex coloring problem with numerous applications in diverse domains, including VLSI design, scheduling, resource allocation and frequency assignment in mobile networks, etc. Since the MSCP and BCP are NP-hard problems, heuristics and metaheuristics are practical solution methods to obtain high quality solutions in an acceptable computing time. This thesis is dedicated to developing effective hybrid metaheuristic algorithms for the MSCP and BCP. For the MSCP, we present two memetic algorithms which combine population-based evolutionary search and local search. An effective algorithm for maximum independent set is devised for generating initial solutions. For the BCP, we propose a learning-based hybrid search algorithm which follows a cooperative framework between an informed construction procedure and a local search heuristic. The proposed algorithms are evaluated on well-known benchmark instances and show highly competitive performances compared to the current state-of-the-art algorithms from the literature. Furthermore, the key issues of these algorithms are investigated and analyzed
18
Dahal, Keshav P., Stephen M. Remde, Peter I. Cowling, and N. J. Colledge. "Improving metaheuristic performance by evolving a variable fitness function." Springer Verlag, 2008. http://hdl.handle.net/10454/2498.
Повний текст джерелаАнотація:
In this paper we study a complex real world workforce scheduling
problem. We apply constructive search and variable neighbourhood search
(VNS) metaheuristics and enhance these methods by using a variable fitness
function. The variable fitness function (VFF) uses an evolutionary approach to
evolve weights for each of the (multiple) objectives. The variable fitness
function can potentially enhance any search based optimisation heuristic where
multiple objectives can be defined through evolutionary changes in the search
direction. We show that the VFF significantly improves performance of
constructive and VNS approaches on training problems, and ¿learn¿ problem
features which enhance the performance on unseen test problem instances.
19
Memoli, Silvio. "Metaheuristic approaches for Complete Network Signal Setting Design (CNSSD)." Doctoral thesis, Universita degli studi di Salerno, 2016. http://hdl.handle.net/10556/2501.
Повний текст джерелаАнотація:
2014 - 2015In order to mitigate the urban traffic congestion and increase the travelers’ surplus, several policies can be adopted which may be applied in short or long time horizon. With regards to the short term policies, one of the most straightforward is control through traffic lights at single junction or network level. The main goal of traffic control is avoiding that incompatible approaches have green at the same time. With respect to this aim existing methodologies for Signal Setting Design (NSSD) can be divided into two classes as in following described Approach-based (or Phase-based) methods address the signal setting as a periodic scheduling problem: the cycle length, and for each approach the start and the end of the green are considered as decision variables, some binary variables (or some non-linear constraints) are included to avoid incompatible approaches having green at the same time (see for instance Improta and Cantarella, 1987). If needed the stage composition and sequence may easily be obtained from decision variables. Commercial software codes following this methodology are available for single junction control only, such Oscady Pro® (TRL, UK; Burrow, 1987). Once the green timing and scheduling have been carried out for each junction, offsets can be optimized (coordination) using the stage matrices obtained from single junction optimization (possibly together with green splits again) through one of codes mentioned below. Stage-based signal setting methods dealt with that by dividing the cycle length into stages, each one being a time interval during which some mutually compatible approaches have green. Stage composition, say which approaches have green, and sequence, say their order, can be represented through the approach-stage incidence matrix, or stage matrix for short. Once the stage matrix is given for each junction, the cycle length, the green splits and the offsets can be optimised (synchronisation) through some well established commercial software codes. Two of the most commonly used codes are: TRANSYT14® (TRL, UK) (recently TRANSYT15® has been released) and TRANSYT-7F® (FHWA, USA). Both allow to compute the green splits, the offsets and the cycle length by combining a traffic flow model and a signal setting optimiser. Both may be used for coordination (optimisation of offsets only, once green splits are known) or synchronisation. TRANSYT14® generates several (but not all) significant stage sequences to be tested but the optimal solution is not endogenously generated, while TRANSYT-7F® is able to optimise the stage sequence for each single junction starting from the ring and barrier NEMA (i.e. National Electrical Manufacturers Association) phases. Still these methods do not allow for stage matrix optimisation; moreover the effects of stage composition and sequence on network performance are not well analysed in literature... [edited by Author]
XIV n.s.
20
Bamdad, Masouleh Keivan. "Building energy optimisation using machine learning and metaheuristic algorithms." Thesis, Queensland University of Technology, 2018. https://eprints.qut.edu.au/120281/1/Keivan_Bamdad%20Masouleh_Thesis.pdf.
Повний текст джерелаАнотація:
The focus of this research is on development of new methods for Building Optimisation Problems (BOPs) and deploying them on realistic case studies to evaluate their performance and utility. First, a new optimisation algorithm based on Ant Colony Optimisation was developed for solving simulation-based optimisation approaches. Secondly, a new surrogate-model optimisation method was developed using active learning approaches to accelerate the optimisation process. Both proposed methods demonstrated better performance than benchmark methods. Finally, a multi-objective scenario-based optimisation was introduced to address uncertainty in BOPs. Results demonstrated the capability of the proposed uncertainty methodology to find a robust design.
21
Moret, Cristina <1992>. "GAs and PSO: two metaheuristic methods for portfolio optimization." Master's Degree Thesis, Università Ca' Foscari Venezia, 2018. http://hdl.handle.net/10579/13319.
Повний текст джерелаАнотація:
The thesis begins with the description of the Markowitz model for optimal portfolio selection. Limitations and improvements of such model are described. In the second chapter the concept of metaheuristics is introduced, focusing on two particular metaheuristics: Genetic Algorithms and Particle Swarm Optimization. These concepts are introduced as alternative optimization methods. In the following chapter a portfolio to optimize is chosen as well as the risk measure to use for the portfolio selection model. In the fourth chapter the two metaheuristics, genetic algorithms and particle swarm optimization, are applied in order to find the optimal portfolio. At the end comparisons between the two methods are provided and conclusions are made.
22
Zamperin, Filippo <1994>. "Testing standard technical analysis parameters' efficiency, a metaheuristic approach." Master's Degree Thesis, Università Ca' Foscari Venezia, 2020. http://hdl.handle.net/10579/17564.
Повний текст джерелаАнотація:
The thesis proposed is aimed to exploit the profitability of Technical Analysis (TA) identifying among the wide set of indicators a sub-set of them, widely used both in literature and in practise, to optimize with metaheuristic algorithms and to test using a trading system. Since its introduction, there has been a wide discussion about the profitability of TA and mostly of the time it has been compared with the fundamental and Buy-And-Hold strategy. To achieve superior performance a trading system should be run using TA indicators that promptly signal when it is time to buy and sell. However, to find such TA indicators' values it requires the solution of a complex problem that can be expressed as an optimization one.The thesis proposed wants to compare three different metaheuristic algorithms, Particle Swarm Optimization (PSO), Differential Evolution (DE) and Fireworks (FWA), searching among them which one perform better.
23
Kašpar, Michal. "Theory and practice of manufacturing scheduling." Master's thesis, Vysoká škola ekonomická v Praze, 2008. http://www.nusl.cz/ntk/nusl-12435.
Повний текст джерелаАнотація:
Manufactural activity is the basis of every sound economy. The risk for today's industrial establishments in our let us say european conditions is to hold competitiveness in the terms of global economy. This diploma thesis is focusing on solving problems of manufacturing scheduling with the view of theory and practice. It is impeach of real-life production. Scheduling belongs to hard combinatorial problems and therefore are usually solved by various heuristic or metaheuristic methods. For application of mentioned metaheuristic methods is important to use suitable choice of representative data.
24
Rajab, Rima Sheikh. "Some applications of continuous variable neighbourhood search metaheuristic (mathematical modelling)." Thesis, Brunel University, 2012. http://bura.brunel.ac.uk/handle/2438/6467.
Повний текст джерелаАнотація:
In the real world, many problems are continuous in nature. In some cases, finding the global solutions for these problems is di±cult. The reason is that the problem's objective function is non convex, nor concave and even not differentiable. Tackling these problems is often computationally too expensive. Although the development in computer technologies are increasing the speed of computations, this often is not adequate, particularly if the size of the problem's instance are large. Applying exact methods on some problems may necessitate their linearisation. Several new ideas using heuristic approaches have been considered particularly since they tackle the problems within reasonable computational time and give an approximate solution. In this thesis, the variable neighbourhood search (VNS) metaheuristic (the framework for building heuristic) has been considered. Two variants of variable neighbourhood search metaheuristic have been developed, continuous variable neighbourhood search and reformulation descent variable neighbourhood search. The GLOB-VNS software (Drazic et al., 2006) hybridises the Microsoft Visual Studio C++ solver with variable neighbourhood search metaheuristics. It has been used as a starting point for this research and then adapted and modified for problems studied in this thesis. In fact, two problems have been considered, censored quantile regression and the circle packing problem. The results of this approach for censored quantile regression outperforms other methods described in the literature, and the near-optimal solutions are obtained in short running computational time. In addition, the reformulation descent variable neighbourhood search variant in solving circle packing problems is developed and the computational results are provided.
25
Ödling, David. "A metaheuristic for vehicle routing problems based on reinforcement learning." Thesis, KTH, Optimeringslära och systemteori, 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-224428.
Повний текст джерелаАнотація:
The vehicle routing problem is an old and well-studied problem that arise in last mile logistics. The rapid increase of e-commerce, in particular with an increasing the demand for time scheduled home deliveries on the customer’s terms, is making the problem ever more relevant. By minimizing the cost and environmental impact, we have the setting for mathematical problem called the vehicle routing problem with time windows. Since the problem is NP-Hard, heuristic methods are often used. In practice, they work very well and typically offer a good tradeoff between speed and quality. However, since the heuristics are often tailormade to fit the needs of the underlying problem, no known algorithm dominates the other on all problems. One way to overcome the need for specialization is to produce heuristics that are adaptive. In this thesis, an offline learning method is proposed to generate an adaptive heuristic using local search heuristics and reinforcement learning. The reinforcement learning agents explored in this thesis are situated in both discrete and continuous state representations. Common to all state spaces are that they are inspired by human-crafted reference models where the last action and the result of that action define the state. Four different reinforcement learning models are evaluated in the various environments. By evaluating the models on a subset of the Solomon benchmark instances, we find that all models but one improve upon a random baseline. The average learner from each of the successful models was slightly worse than the human crafted baseline. However, the best among the generated models was an actor-critic based model which outperformed the best human baseline model. Due to the scalar objective function, the results are not directly comparable to the Solomon benchmark results with hierarchal objectives. None the less, the results are encouraging as a proof of principle with results in line with the human crafted baseline. The results indicate two clear paths for further work. First, applying the formulation to more complex environments with more actions and more powerful state spaces. Secondly, investigate models based on stochastic policies and recurrent neural networks to cope with the inherently partially observed environment.Ruttoptimering är ett gammalt och välstuderat optimeringsproblem som uppstår i city-nära logistik. Med en ständigt växande e-handel, ökar efterfrågan av tidspassade hemleveranser på kundens villkor. Att minimera kostnaden och miljöpåverkan blir då ett ruttoptimeringsproblem med tidsfönster. Då optimerinsproblemet är NP-Svårt, används heuristiska lösningsmetoder. I denna uppsatts undersöks möjligheten att generera heuristiker genom att träna på liknande problem. Mer specifikt genererar vi en heurisitik baserad på lokalsök genom att formulera lärningsproblemet som ett reinforcement learning problem. De metoder som används är baserade på både diskreta och kontinuerliga tillståndsrum. Gemensamt för tillståndsrummen är att de är inspirerade av den information som används av mänskligt genererade heuristiker där det tidigare valet valet och dess resultat är informationsbärare. Fyra olika reinforcement learning modeller utvärderas på olika problem samt tillståndsrymnder. Genom att träna modellerna på olika typer av problem från de välkända Solomon problemen och utvärdera dessa på ett oberoende test set, kan vi konstatera att alla utom en modell är bättre än slumpen. Ingen av modellerna slog dock den bästa referensmodellen i medeltal då variationen i utfallet var stort, men de är alla mycket nära. Den bästa bland alla modeller, vilket var en actor critic agent, uppnådde ett bättre resultat än den bästa referensmodellen. På grund av att en skalär målfunktion använts är resultaten inte direkt jämförbara med andras på Solomon problemen då de skall optimeras med en hierarkisk målfunktion. Trotts detta är resultaten goda och visar att metoden som introducerats fungerar bra eftersom de presterar i linje med referensmodellerna baserade på samma information. Resultaten pekar på två vägar framåt för vidare arbete. Det första är en mera kraftfull tillståndsrymd med mera information samt fler handlingsmöjligheter. Det andra är att applicera stokastiska baserade modeller eller motsvarande för att överkomma tillståndsrymndernas inneboende ofullständighet.
26
Lam, Yun-sang Albert, and 林潤生. "Theory of optimization and a novel chemical reaction-inspired metaheuristic." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2009. http://hub.hku.hk/bib/B4322412X.
Повний текст джерела
27
Santilan-Gutierrez, Saul Daniel. "Metaheuristic search using genetic algorithms for Boothroyd's design for assembly." Thesis, Loughborough University, 1997. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.263592.
Повний текст джерела
28
CUNHA, VICTOR ABU-MARRUL CARNEIRO DA. "RESCHEDULING OF OIL EXPLORATION SUPPORT VESSELS WITHIN A METAHEURISTIC APPROACH." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2017. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=30908@1.
Повний текст джерелаАнотація:
PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIROCOORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR
PROGRAMA DE SUPORTE À PÓS-GRADUAÇÃO DE INSTS. DE ENSINO
A dissertação aborda um problema real de reprogramação de uma frota de embarcações do tipo PLSV (Pipe Laying Support Vessel), responsáveis pelas interligações de poços petrolíferos submarinos. O cronograma de curto prazo dessas embarcações está sujeito à inúmeras incertezas inerentes às operações realizadas, acarretando em ociosidade nas embarcações ou postergações na produção de petróleo, que podem resultar em prejuízo de milhões de reais. Uma metaheurística ILS (Iterated Local Search) é proposta para atender a frequente demanda por reprogramações dos PLSVs. O método é composto de uma fase inicial de viabilização, para tratar potenciais inconsistências nas programações. Na sequência, iterativamente, são realizadas perturbações na solução por meio de movimentos de swap e aplicada uma busca local baseada na vizinhança insert, a fim de fugir de ótimos locais e encontrar soluções que aprimorem o cronograma. Foram feitos experimentos com diferentes parâmetros e critérios do ILS, sendo definidas duas abordagens aplicadas a dez instâncias oriundas de uma programação real de PLSVs. A partir de uma função de avaliação, capaz de medir o impacto operacional na programação, o ILS proporcionou uma melhoria média nos cronogramas acima de 91 por cento, quando comparados aos cronogramas originais. As soluções foram obtidas em um tempo computacional médio de 30 minutos, aderente ao processo da companhia. Em função dos resultados alcançados, o método provou ser uma boa base para uma ferramenta de apoio à decisão para a reprogramação dos PLSVs.
This dissertation addresses a real-life rescheduling problem of a Pipe Laying Support Vessels (PLSVs) fleet, in charge of subsea oil wells interconnections. The short-term schedule of these vessels is subject to uncertainties inherent to its operations, resulting in ships idleness or delays in oil production, which may lead to losses of millions of Brazilian Reais. A method based on the ILS (Iterated Local Search) metaheuristic is proposed to meet the frequent demand of PLSVs rescheduling. The first step of this method aims to find a feasible initial solution from an incoming schedule with potencial inconsistencies. The following steps consists in, iteratively, performing a perturbation on a solution through swap movements and applying a local search based on the insertion neighborhood, in order to escape from local optimal and find better solutions. Extensive preliminary experiments were conducted considering different ILS parameters setups. The two most performing setups were selected and applied to ten instances of a real PLSV schedule. Taking into account an objective function that measures the operational impact on schedules, the ILS provided an average improvement above 91 percent in schedules when compared to the original planning. These solutions were obtained in an average computational time of 30 minutes, which fits in the company process. The obtained results showed that the proposed method might be a basis for a decision support tool for the PLSVs rescheduling problem.
29
Lam, Yun-sang Albert. "Theory of optimization and a novel chemical reaction-inspired metaheuristic." Click to view the E-thesis via HKUTO, 2009. http://sunzi.lib.hku.hk/hkuto/record/B4322412X.
Повний текст джерела
30
FADDA, GIANFRANCO. "A metaheuristic approach for the Vehicle Routing Problem with Backhauls." Doctoral thesis, Università degli Studi di Cagliari, 2017. http://hdl.handle.net/11584/249582.
Повний текст джерелаАнотація:
Despite the vivid research activity in the sector of the exact methods, nowadays many Optimization Problems are classified as Np-Hard and need to be solved by heuristic methods, even in the case of instances of limited size. In this thesis a Vehicle Routing Problem with Backhauls is investigated. A Greedy Randomized Adaptive Search Procedure metaheuristic is proposed for this problem.
Several versions of the metaheuristic are tested on symmetric and asymmetric instances. Although the metaheuristic does not outperform the best known solutions, a large number of high-quality routes are determined in several solutions for each instance. Therefore the metaheuristic is a promising approach to generate feasible paths for set-partitioning-based formulations.
31
Whitford, Angela Tracy. "Heuristic approaches to solve the frequency assignment problem." Thesis, Goldsmiths College (University of London), 1999. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.321956.
Повний текст джерела
32
Šandera, Čeněk. "Hybridní model metaheuristických algoritmů." Doctoral thesis, Vysoké učení technické v Brně. Fakulta strojního inženýrství, 2015. http://www.nusl.cz/ntk/nusl-234259.
Повний текст джерелаАнотація:
The main topic of this PhD thesis is metaheuristic algorithm in wider scope. The first chapters are dedicated to a description of broader context of metaheuristics, i.e. various optimization classes, determination of their omplexity and different approaches to their solutions. The consequent discussion about metaheuristics and their typical characteristics is followed by several selected examples of metaheuristics concepts. The observed characteristics serve as a base for building general metaheuristics model which is suitable for developing brand new or hybrid algorithms. The thesis is concluded by illustration of author’s publications with discussion about their adaptation to the proposed model. On the attached CD, there is also available a program implementation of the created model.
33
Nwankwor, Emeka. "A unified metaheuristic and system-theoretic framework for petroleum reservoir management." Thesis, University of Liverpool, 2014. http://livrepository.liverpool.ac.uk/16993/.
Повний текст джерелаАнотація:
With phenomenal rise in world population as well as robust economic growth in China, India and other emerging economies; the global demand for energy continues to grow in monumental proportions. Owing to its wide end-use capabilities, petroleum is without doubt, the world’s number one energy resource. The present demand for oil and credible future forecasts – which point to the fact that the demand is expected to increase in the coming decades – make it imperative that the E&P industry must device means to improve the present low recovery factor of hydrocarbon reservoirs. Efficiently tailored model-based optimization, estimation and control techniques within the ambit of a closed-loop reservoir management framework can play a significant role in achieving this objective. In this thesis, some fundamental reservoir engineering problems such as field development planning, production scheduling and control are formulated into different optimization problems. In this regard, field development optimization identifies the well placements that best maximizes hydrocarbon recovery, while production optimization identifies reservoir well-settings that maximizes total oil recovery or asset value, and finally, the implementation of a predictive controller algorithm which computes corrected well controls that minimizes the difference between actual outputs and simulated (or optimal) reference trajectory. We employ either deterministic or metaheuristic optimization algorithms, such that the choice of algorithm is purely based on the peculiarity of the underlying optimization problem. Altogether, we present a unified metaheuristic and system-theoretic framework for petroleum reservoir management. The proposed framework is essentially a closed-loop reservoir management approach with four key elements, namely: a new metaheuristic technique for field development optimization, a gradient-based adjoint formulation for well rates control, an effective predictive control strategy for tracking the gradient-based optimal production trajectory and an efficient model-updating (or history matching) – where well production data are used to systematically recalibrate reservoir model parameters in order to minimize the mismatch between actual and simulated measurements. Central to all of these problems is the use of white-box reservoir models which are employed in the well placement optimization and production settings optimization. However, a simple data-driven black-box model which results from the linearization of an identified nonlinear model is employed in the predictive controller algorithm. The benefits and efficiency of the approach in our work is demonstrated through the maximization of the NPV of waterflooded reservoir models that are subject to production and geological uncertainty. Our procedure provides an improvement in the NPV, and importantly, the predictive control algorithm ensures that this improved NPV are attainable as nearly as possible in practice.
34
Ahmad, Maqsood. "Mathematical models and methods based on metaheuristic approach for timetabling problem." Thesis, Clermont-Ferrand 2, 2013. http://www.theses.fr/2013CLF22393/document.
Повний текст джерелаАнотація:
Résumé indisponibleIn this thesis we have concerned ourselves with university timetabling problems both course timetabling and examination timetabling problems. Most of the timetabling problems are computationally NP-complete problems, which means that the amount of computation required to find solutions increases exponentially with problem size. These are idiosyncratic nature problems, for example different universities have their own set of constraints, their own definition of good timetable, feasible timetable and their own choice about the use of constraint type (as a soft or hard constraint). Unfortunately, it is often the case that a problem solving approach which is successfully applied for one specific problem may not become suitable for others. This is a motivation, we propose a generalized problem which covers many constraints used in different universities or never used in literature. Many university timetabling problems are sub problems of this generalized problem. Our proposed algorithms can solve these sub problems easily, moreover constraints can be used according to the desire of user easily because these constraints can be used as reference to penalty attached with them as well. It means that give more penalty value to hard constraints than soft constraint. Thus more penalty value constraints are dealt as a hard constraint by algorithm. Our algorithms can also solve a problem in two phases with little modification, where in first phase hard constraints are solved. In this work we have preferred and used two phase technique to solve timetabling problems because by using this approach algorithms have broader search space in first phase to satisfy hard constraints while not considering soft constraints at all. Two types of algorithms are used in literature to solve university timetabling problem, exact algorithms and approximation algorithms. Exact algorithms are able to find optimal solution, however in university timetabling problems exact algorithms constitute brute-force style procedures. And because these problems have the exponential growth rates of the search spaces, thus these kinds of algorithms can be applied for small size problems. On the other side, approximation algorithms may construct optimal solution or not but they can produce good practically useable solutions. Thus due to these factors we have proposed approximation algorithms to solve university timetabling problem. We have proposed metaheuristic based techniques to solve timetabling problem, thus we have mostly discussed metaheuristic based algorithms such as evolutionary algorithms, simulated annealing, tabu search, ant colony optimization and honey bee algorithms. These algorithms have been used to solve many other combinatorial optimization problems other than timetabling problem by modifying a general purpose algorithmic framework. We also have presented a bibliography of linear integer programming techniques used to solve timetabling problem because we have formulated linear integer programming formulations for our course and examination timetabling problems. We have proposed two stage algorithms where hard constraints are satisfied in first phase and soft constraints in second phase. The main purpose to use this two stage technique is that in first phase hard constraints satisfaction can use more relax search space because in first phase it does not consider soft constraints. In second phase it tries to satisfy soft constraints when maintaining hard constraints satisfaction which are already done in first phase. (...)
35
Parisini, Fabio <1981>. "Hybrid constraint programming and metaheuristic methods for large scale optimization problems." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2011. http://amsdottorato.unibo.it/3709/1/parisini_fabio_tesi.pdf.
Повний текст джерелаАнотація:
This work presents hybrid Constraint Programming (CP) and metaheuristic methods for the solution of Large Scale Optimization Problems; it aims at integrating concepts and mechanisms from the metaheuristic methods to a CP-based tree search environment in order to exploit the advantages of both approaches.
The modeling and solution of large scale combinatorial optimization problem is a topic which has arisen the interest of many researcherers in the Operations
Research field; combinatorial optimization problems are widely spread in everyday life and the need of solving difficult problems is more and more urgent.
Metaheuristic techniques have been developed in the last decades to effectively handle the approximate solution of combinatorial optimization problems; we will examine metaheuristics in detail, focusing on the common aspects of different techniques.
Each metaheuristic approach possesses its own peculiarities in designing and guiding the solution process; our work aims at recognizing components which can be extracted from metaheuristic methods and re-used in different contexts.
In particular we focus on the possibility of porting metaheuristic elements to constraint programming based environments, as constraint programming is able to deal with feasibility issues of optimization problems in a very effective manner.
Moreover, CP offers a general paradigm which allows to easily model any type of problem and solve it with a problem-independent framework, differently from
local search and metaheuristic methods which are highly problem specific.
In this work we describe the implementation of the Local Branching framework, originally developed for Mixed Integer Programming, in a CP-based environment. Constraint programming specific features are used to ease the search
process, still mantaining an absolute generality of the approach. We also propose a search strategy called Sliced Neighborhood Search, SNS, that iteratively explores slices of large neighborhoods of an incumbent solution by performing CP-based tree search and encloses concepts from metaheuristic techniques. SNS
can be used as a stand alone search strategy, but it can alternatively be embedded in existing strategies as intensification and diversification mechanism. In particular we show its integration within the CP-based local branching.
We provide an extensive experimental evaluation of the proposed approaches on instances of the Asymmetric Traveling Salesman Problem and of the Asymmetric Traveling Salesman Problem with Time Windows. The proposed approaches achieve good results on practical size problem, thus demonstrating the benefit of integrating metaheuristic concepts in CP-based frameworks.
36
Parisini, Fabio <1981>. "Hybrid constraint programming and metaheuristic methods for large scale optimization problems." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2011. http://amsdottorato.unibo.it/3709/.
Повний текст джерелаАнотація:
This work presents hybrid Constraint Programming (CP) and metaheuristic methods for the solution of Large Scale Optimization Problems; it aims at integrating concepts and mechanisms from the metaheuristic methods to a CP-based tree search environment in order to exploit the advantages of both approaches.
The modeling and solution of large scale combinatorial optimization problem is a topic which has arisen the interest of many researcherers in the Operations
Research field; combinatorial optimization problems are widely spread in everyday life and the need of solving difficult problems is more and more urgent.
Metaheuristic techniques have been developed in the last decades to effectively handle the approximate solution of combinatorial optimization problems; we will examine metaheuristics in detail, focusing on the common aspects of different techniques.
Each metaheuristic approach possesses its own peculiarities in designing and guiding the solution process; our work aims at recognizing components which can be extracted from metaheuristic methods and re-used in different contexts.
In particular we focus on the possibility of porting metaheuristic elements to constraint programming based environments, as constraint programming is able to deal with feasibility issues of optimization problems in a very effective manner.
Moreover, CP offers a general paradigm which allows to easily model any type of problem and solve it with a problem-independent framework, differently from
local search and metaheuristic methods which are highly problem specific.
In this work we describe the implementation of the Local Branching framework, originally developed for Mixed Integer Programming, in a CP-based environment. Constraint programming specific features are used to ease the search
process, still mantaining an absolute generality of the approach. We also propose a search strategy called Sliced Neighborhood Search, SNS, that iteratively explores slices of large neighborhoods of an incumbent solution by performing CP-based tree search and encloses concepts from metaheuristic techniques. SNS
can be used as a stand alone search strategy, but it can alternatively be embedded in existing strategies as intensification and diversification mechanism. In particular we show its integration within the CP-based local branching.
We provide an extensive experimental evaluation of the proposed approaches on instances of the Asymmetric Traveling Salesman Problem and of the Asymmetric Traveling Salesman Problem with Time Windows. The proposed approaches achieve good results on practical size problem, thus demonstrating the benefit of integrating metaheuristic concepts in CP-based frameworks.
37
Novotná, Kateřina. "Heuristické řešení plánovacích problémů." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2013. http://www.nusl.cz/ntk/nusl-236335.
Повний текст джерелаАнотація:
This thesis deals with the implementation of the metaheuristic algorithms into the Drools Planner. The Drools Planner is an open source tool for solving optimization problems. This work describes design and implementation of Ant colony optimization metaheuristics in the Drools Planner. Evaluation of the algorithm results is done by Drools Planner benchmark with different kinds of optimization problems.
38
Vogel, Ulrich [Verfasser]. "A flexible metaheuristic framework for solving rich vehicle routing problems / Ulrich Vogel." Aachen : Shaker, 2012. http://d-nb.info/1069048984/34.
Повний текст джерела
39
Curtois, Timothy. "Novel heuristic and metaheuristic approaches to the automated scheduling of healthcare personnel." Thesis, University of Nottingham, 2008. http://eprints.nottingham.ac.uk/28309/.
Повний текст джерелаАнотація:
This thesis is concerned with automated personnel scheduling in healthcare organisations; in particular, nurse rostering. Over the past forty years the nurse rostering problem has received a large amount of research. This can be mostly attributed to its practical applications and the scientific challenges of solving such a complex problem. The benefits of automating the rostering process include reducing the planner’s workload and associated costs and being able to create higher quality and more flexible schedules. This has become more important recently in order to retain nurses and attract more people into the profession. Better quality rosters also reduce fatigue and stress due to overwork and poor scheduling and help to maximise the use of leisure time by satisfying more requests. A more contented workforce will lead to higher productivity, increased quality of patient service and a better level of healthcare. Basically stated, the nurse rostering problem requires the assignment of shifts to personnel to ensure that sufficient employees are present to perform the duties required. There are usually a number of constraints such as working regulations and legal requirements and a number of objectives such as maximising the nurses working preferences. When formulated mathematically this problem can be shown to belong to a class of problems which are considered intractable. The work presented in this thesis expands upon the research that has already been conducted to try and provide higher quality solutions to these challenging problems in shorter computation times. The thesis is broadly structured into three sections. 1) An investigation into a nurse rostering problem provided by an industrial collaborator. 2) A framework to aid research in nurse rostering. 3) The development of a number of advanced algorithms for solving highly complex, real world problems.
40
Annaballi, RonJon. "A multiple ant colony metaheuristic for the air refueling tanker assignment problem." View thesis, 2002. http://handle.dtic.mil/100.2/ADA400201.
Повний текст джерелаАнотація:
Thesis (M.S.)--Air Force Institute of Technology, 2002.Title from title screen (viewed Oct. 28, 2003). Vita. "AFIT/GOR/ENS/02-01." Includes bibliographical references (leaves 84-86). Also issued in paper format.
41
Kuang, Yue(Yue Rick). "A metaheuristic approach to optimizing a multimodal truck and drone delivery system." Thesis, Massachusetts Institute of Technology, 2019. https://hdl.handle.net/1721.1/122401.
Повний текст джерелаАнотація:
Thesis: M. Eng. in Supply Chain Management, Massachusetts Institute of Technology, Supply Chain Management Program, 2019Cataloged from PDF version of thesis.
Includes bibliographical references (pages 50-51).
The success of e-commerce continues to push the bounds of delivery services as customers expect near instant fulfillment at little additional cost. This demand for delivery performance and operational cost efficiency has led to the exploration of the last-mile delivery problem using creative multimodal delivery systems. One promising system consists of a truck that can carry and deploy multiple autonomous drones to assist in the fulfillment of customer demand. The contribution of this thesis is towards furthering the understanding of the application of autonomous flying drones in such a system and improve parcel delivery performance within the constraint of the current state of technology. This thesis explores the feasibility of deploying drones in last-mile delivery by modeling and then optimizing the cost of serving customers with a system consisting of one truck and multiple drones under multiple customer demand scenarios. While this optimization problem can be solved with mixed integer linear programming (MILP), the computation requirement is such that MILP is inefficient for real world scenarios with 100 or more customers. This research applies metaheuristic methodology to solve the truck-and-drone problem for scenarios with up to 158 customers in approximately 30 minutes of computation time. The test results confirm an average of 7% to 9% in savings opportunity for a 2-drone baseline over traditional single truck delivery tours. This savings opportunity is shown to vary with customer density, number of drones carried, range of drone flight, and speed of drone relative to speed of truck.
by Yue Kuang.
M. Eng. in Supply Chain Management
M.Eng.inSupplyChainManagement Massachusetts Institute of Technology, Supply Chain Management Program
42
Charalambous, Christoforos N. "Short-term scheduling of multi-stage, multipurpose manufacturing systems in the process industry." Thesis, Brunel University, 2000. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.310077.
Повний текст джерела
43
Saremi, Alireza. "Mathematical programming enhanced metaheuristic approach for simulation-based optimization in outpatient appointment scheduling." Elsevier, 2013. http://hdl.handle.net/1993/21710.
Повний текст джерелаАнотація:
In the last two decades, the western world witnessed a continuous rise in the health expenditure. Meanwhile, complaints from patients on excessive waiting times are also increasing. In the past, many researchers have tried to devise appointment scheduling rules to provide trade-offs between maximizing patients’ satisfaction and minimizing the costs of the health providers. For instance, this challenge appears appointment scheduling problems (ASP).
Commonly used methods in ASP include analytical methods, simulation studies, and combination of simulation with heuristic approaches. Analytical methods (e.g., queuing theory and mathematical programming) face challenges of fully capturing the complexities of systems and usually make strong assumptions for tractability of problems. These methods simplify the whole system to a single-stage unit and ignore the actual system factors such as the presence of multiple stages and/or resource constraints. Simulation studies, conversely, are able to model most complexities of the actual system, but they typically lack an optimization strategy to deliver optimal appointment schedules. Also, heuristic approaches normally are based on intuitive rules and do not perform well as standalone methods.
In order to reach an optimal schedule while considering complexities in actual health care systems, this thesis proposes efficient and effective methods that yield (near) optimal appointment schedules by integrating mathematical programming, a tabu search optimization algorithm and discrete event simulation. The proposed methodologies address the challenges and complexities of scheduling in real world multistage healthcare units in the presence of stochastic service durations, a mix of patient types, patients with heterogeneous service sequence, and resource constraints.
Moreover, the proposed methodology is capable of finding the optimum considering simultaneously multiple performance criteria. A Pareto front (a set of optimal solutions) for the performance criteria can be obtained using the proposed methods. Healthcare management can use the Pareto front to choose the appropriate policy based on different conditions and priorities.
In addition, the proposed method has been applied to two case studies of Operating Rooms departments in two major Canadian hospitals. The comparison of actual schedules and the ones yielded by the proposed method indicates that proposed method can improve the appointment scheduling in realistic clinical settings.
44
Aljawawdeh, H. "An interactive metaheuristic search framework for software service identification from business process models." Thesis, University of the West of England, Bristol, 2019. http://eprints.uwe.ac.uk/37959/.
Повний текст джерелаАнотація:
In recent years, the Service-Oriented Architecture (SOA) model of computing has become widely used and has provided efficient and agile business solutions in response to inevitable and rapid changes in business requirements. Software service identification is a crucial component in the production of a service-oriented architecture and subsequent successful software development, yet current service identification methods have limitations. For example, service identification methods are either not sufficiently comprehensive to handle the totality of service identification activities, or they lack computational support, or they pay insufficient attention to quality checks of resulting services. To address these limitations, comprehensive computationally intelligent support for software engineers when deriving software services from an organisation's business process models shows great potential, especially when the impact of human preference on the quality of the resulting solutions can be incorporated. Accordingly, this research attempts to apply interactive metaheuristic search to effectively bridge the gap between business and SOA technology and so increase business agility. A novel, comprehensive framework is introduced that is driven by domain independent role-based business process models, and uses an interactive metaheuristic search-based service identification approach based on a genetic algorithm, while adhering to SOA principles. Termed BPMiSearch, the framework is composed of three main layers. The first layer is concerned with processing inputs from business process models into search space elements by modelling input data and presenting them at an appropriate level of granularity. The second layer focuses on identifying software services from the specified search space. The third layer refines the resulting services to map the business elements in the resulting candidate services to the corresponding service components. The proposed BPMiSearch framework has been evaluated by applying it to a healthcare domain case study, specifically, Cancer Care and Registration (CCR) business processes at the King Hussein Cancer Centre, Amman, Jordan. Experiments show that the impact of software engineer interaction on the quality of the outcomes in terms of search effectiveness, efficiency, and level of user satisfaction, is assessed. Results show that BPMiSearch has rapid search performance to positively support software engineers in the identification of services from role-based business process models while adhering to SOA principles. High-quality services are identified that might not have been arrived at manually by software engineers. Furthermore, it is found that BPMiSearch is sensitive and responsive to software engineer interaction resulting in a positive level of user trust, acceptance, and satisfaction with the candidate services.
45
Raya, Lilysuriazna Binti. "A metaheuristic ant colony optimization algorithm for symmetric and asymmetric traveling salesman problems." Thesis, Brunel University, 2018. http://bura.brunel.ac.uk/handle/2438/17617.
Повний текст джерелаАнотація:
This research addresses solving two types of Travelling Salesman Problems (TSP) which are the symmetric TSP (STSP) and the asymmetric TSP (ATSP). The TSP is a problem of finding a minimal length closed tour that visits each city once. If the distances between each pair of cities are the same in both directions, the problem is a STSP, otherwise, it is an ATSP. In this thesis, a new metaheuristic algorithm which is based on Ant Colony Optimization (ACO) is proposed to solve these problems. The key idea is to enhance the ability of exploration and exploitation by incorporating a metaheuristic approach with an exact method. A new strategy for creating 'Intelligent Ants' is introduced to construct the solution tours. This strategy aims at reducing the computational time by heuristically fixing part of the solution tour and improving the accuracy of the solutions through the usage of a solver, specifically for large size instances. Moreover, this proposed algorithm employs new ways of depositing and evaporating pheromone. A different approach of global updating of pheromone is proposed in which the pheromone is deposited only on the edges belonging to the colony-best ant and evaporated only on the edges belonging to the colony-worst ant that are not in the colony-best ant. Additionally, the parameters of the proposed algorithm which include the number of colonies, the number of ants in each colony, the relative influence of the pheromone trail α and the pheromone evaporation rate ρ are expressed as a function of the problem size. Comparisons with other sets of parameter values suggested in the literature have been investigated which illustrate the advantages of the choice of the proposed parameter settings. Further, in order to evaluate the performance of the proposed algorithm, a set of standard benchmark problems from the TSPLIB with up to 442 cities were solved and the results obtained were compared with other approaches from the literature. The proposed algorithm has proven to be competitive and shows better performance in 63% of the 16 algorithms in terms of solution quality and obtained the optimum solutions in 70% of the 33 instances, proving that it is a good alternative approach to solve these hard combinatorial optimisation problems.
46
Hiremath, Chaitr. "New Heuristic And Metaheuristic Approaches Applied To The Multiple-choice Multidimensional Knapsack Problem." Wright State University / OhioLINK, 2008. http://rave.ohiolink.edu/etdc/view?acc_num=wright1203960454.
Повний текст джерела
47
Busetti, Franco Raoul. "Metaheuristic approaches to realistic portfolio optimisation." Diss., 2000. http://hdl.handle.net/10500/16224.
Повний текст джерелаАнотація:
In this thesis we investigate the application of two heuristic methods, genetic
algorithms and tabu/scatter search, to the optimisation of realistic portfolios. The
model is based on the classical mean-variance approach, but enhanced with floor and
ceiling constraints, cardinality constraints and nonlinear transaction costs which
include a substantial illiquidity premium, and is then applied to a large I 00-stock
portfolio.
It is shown that genetic algorithms can optimise such portfolios effectively and within
reasonable times, without extensive tailoring or fine-tuning of the algorithm. This
approach is also flexible in not relying on any assumed or restrictive properties of the
model and can easily cope with extensive modifications such as the addition of
complex new constraints, discontinuous variables and changes in the objective
function.
The results indicate that that both floor and ceiling constraints have a substantial
negative impact on portfolio performance and their necessity should be examined
critically relative to their associated administration and monitoring costs.
Another insight is that nonlinear transaction costs which are comparable in magnitude
to forecast returns will tend to diversify portfolios; the effect of these costs on
portfolio risk is, however, ambiguous, depending on the degree of diversification
required for cost reduction. Generally, the number of assets in a portfolio invariably
increases as a result of constraints, costs and their combination.
The implementation of cardinality constraints is essential for finding the bestperforming
portfolio. The ability of the heuristic method to deal with cardinality
constraints is one of its most powerful features.Decision Sciences
M. Sc. (Operations Research)
48
Yuan, Fang-Chieh, and 袁芳杰. "Metaheuristic for Solving p-Median Problem." Thesis, 2007. http://ndltd.ncl.edu.tw/handle/11723301844393572570.
Повний текст джерелаАнотація:
碩士元智大學
工業工程與管理學系
95
Basic premises in location allocation problems have been to select appropriate locations and design customers to these locations to minimize cost and provide necessary service. These problems recognize that demand may change over time and attempt to account for the effects of these changes in the initial set of locations. However, future demand often is not known with certainty and has been approximated by a deterministic surrogate. For these reasons, how to reduce the costs by set up facility locations became the most important problem both in public and private sector. One of the most well-known facility-location problems is the p-median problem. We propose a genetic algorithm (GA) to solve p-median problem. The proposed GA uses not only the orthodox genetic processes but also merges a new heuristic “variable neighborhood search (VNS)” in this work. The result is compared with OR-Library test problems.
49
TRIPATHI, ASHISH KUMAR. "BIG DATA ANALYSIS USING METAHEURISTIC ALGORITHMS." Thesis, 2018. http://dspace.dtu.ac.in:8080/jspui/handle/repository/16597.
Повний текст джерелаАнотація:
BigDatahasgotthehugeattentionoftheresearchersfromacademiaandindustryforthe decisionandstrategymaking. Thus,efficientdataanalysismethodsarerequiredformanagingthebigdatasets. Dataclustering,aprominentanalysismethodofdatamining,isbeing efficiently employed in big data analysis since it does not require labeled datasets, which is not easily available for the big data problems. K-means, one of the simplest and popularalgorithm,hasbeenemployedforunfoldingthevariousclusteringproblems. However, theresultsofK-meansalgorithmarehighlydependentoninitialclustercentroidsandeasily traps into local optima. To mitigate this issue, a novel metaheuristic algorithm named Military Dog Based Optimizer has been introduced and validated against 17 benchmark functions. Theproposedalgorithmhasbeenalsotestedon8benchmarkclusteringdatasets and compared with other 5 recent state-of-the-art algorithms. Though, the proposed algorithm witnessed better clustering in terms of accuracy as compared to the conventional methods. However,thealgorithmfailtoperformefficientlyonthebigdatasetsintermsof memory space and the time complexities, due to their sequential execution. To overcome this issue, four novel methods have been developed for the efficient clustering of the big datasets. The first method is a hybrid of K-means and bat algorithm which run in parallel over a cluster of computers. The proposed method outperformed K-means, PSO and bat algorithmon5benchmarkdatasets. Thesecondmethodisanovelvariantofthegreywolf optimizer for clustering the big data set, in which the exploration and exploitation ability
of the grey wolf optimizer is enhanced using the levy flight and binomial crossover. The proposedmethodperformedefficientlyonthe8benchmarkclusteringdatasetsascompared totheconventionalmethods. Moreover,theparallelperformanceofthepresentedmethods hasbeenalsoanalyzedusingthespeedupmeasure. Third,ahybridmethodnamedK-BBO has been developed which utilizes the search ability of the biogeography based optimizer and K-means for better initial population. Fourth, a novel parallel method using MDBO is introduced and tested on four large scale datasets. Furthermore, to test the applicability oftheproposedmethodsinrealworldscenarios,tworeal-worldproblemsnamely,Twitter sentimentanalysisandfakereviewdetectionhavebeensolvedinthebigdataenvironment usingtheproposedmethods.
50
Cho, Yuh-Jen, and 卓裕仁. "A New Metaheuristic Approach for HVRP and PVRP." Thesis, 2001. http://ndltd.ncl.edu.tw/handle/67115137462732599561.
Повний текст джерелаАнотація:
博士國立交通大學
運輸工程與管理系
89
The Heterogeneous Fleet Vehicle Routing Problem (HVRP) and Periodic Vehicle Routing Problem (PVRP) are two important variants of the conventional vehicle routing problem (VRP). Due to the NP-hard complexity of HVRP and PVRP, most existing methods for solving HVRP and PVRP are heuristics or metaheuristics. The major contribution of this research is that we have developed a new metaheuristic approach, i.e. the Generic Intensification and Diversification Search (GIDS), for solving HVRP and PVRP. The GIDS integrates the use of some recently developed generic search methods such as Threshold Accepting (TA) and Great Deluge Algorithm (GDA), and the meta-strategies of intensification and diversification for intelligent search. The GIDS includes three components: Multiple Initialization Constructor (MIC), Generic Search for Intensification (GSI), and Perturbation Search for Diversification (PSD). We also designed five modules and proposed several modified algorithms for the implementation of the GIDS to HVRP and PVRP. As compared with the well-known tabu search, GIDS shares some similar ideas in the search strategies of intensification and diversification but does not require complicated memory scheme for computer implementation. Both HVRP and PVRP benchmark instances were selected and tested by several different implementations of GIDS. The numbers of benchmark instances tested for HVRP and PVRP are twenty and thirty-two respectively. All programs were coded in UNIX C and ran on a SUN SPARC 10 workstation. Computational results are very encouraging; GIDS yielded comparable results with recent successful applications using the tabu search. Using GIDS, we have updated the best-known solutions for six of the PVRP instances. Moreover, for PVRP, the average deviation of our best solutions from the published best-known solutions is merely 0.26 %. For HVRP, the average deviation of our best solutions from the published best-known solutions is 0.58%. Such results imply that GIDS may provide an efficient and robust tool for real-world HVRP and PVRP applications.