To see the other types of publications on this topic, follow the link: METAHEURISTIC APPROACH.
Dissertations / Theses on the topic 'METAHEURISTIC APPROACH'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'METAHEURISTIC APPROACH.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
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.
Full textAbstract:
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.
2
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.
Full textAbstract:
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.
3
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.
Full textAbstract:
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.
4
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.
Full textAbstract:
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.
5
Ahmad, Maqsood. "Mathematical models and methods based on metaheuristic approach for timetabling problem." Thesis, Clermont-Ferrand 2, 2013. http://www.theses.fr/2013CLF22393/document.
Full textAbstract:
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. (...)
6
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.
Full textAbstract:
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
7
Saremi, Alireza. "Mathematical programming enhanced metaheuristic approach for simulation-based optimization in outpatient appointment scheduling." Elsevier, 2013. http://hdl.handle.net/1993/21710.
Full textAbstract:
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.
8
Alvarez, Fernandez Stephanie Milena. "A metaheuristic and simheuristic approach for the p-HUB median problem from a telecommunication perspective." Doctoral thesis, Universitat Oberta de Catalunya, 2018. http://hdl.handle.net/10803/666752.
Full textAbstract:
Els últims avenços en la indústria de les telecomunicacions ofereixen grans oportunitats per a ciutadans i organitzacions en un món globalment connectat, però alhora presenten reptes als quals s'enfronten tècnics i enginyers que prenen decisions. Alguns d'aquests reptes es poden modelitzar com a problemes d'optimització. El primer objectiu d'aquest treball és proporcionar un revisió de la literatura sobre com s'han utilitzat aquestes tècniques tradicionalment per a tractar els problemes d'optimització associats a sistemes de telecomunicació, detectant les principals tendències i desafiaments. Particularment, l'estudi es centra en els problemes de disseny de xarxes, encaminament i problemes d'assignació de recursos. A causa de la naturalesa d’aquests problemes, aquest treball també analitza com es poden combinar les tècniques metaheurístiques amb metodologies de simulació per a ampliar les capacitats de resoldre problemes d'optimització estocàstics. A més, es tracta un popular problema d'optimització amb aplicacions pràctiques per a xarxes de telecomunicació, el problema de la p mediana no capacitat, analitzant-lo des d'escenaris deterministes i estocàstics.Los recientes avances en la industria de las telecomunicaciones ofrecen grandes oportunidades para ciudadanos y organizaciones en un mundo globalmente conectado, pero también presentan una gran cantidad de desafíos complejos a los que se enfrentan diariamente técnicos e ingenieros. Algunos de estos desafíos se pueden modelar como problemas de optimización. El primer objetivo de esta tesis es proporcionar una revisión de la literatura de cómo se han utilizado estas técnicas tradicionalmente para tratar los problemas de optimización asociados a sistemas de telecomunicaciones, detectando las principales tendencias y desafíos. En particular, el estudio se centra en los problemas de diseño de red, direccionamiento y problemas de asignación de recursos. Debido a la naturaleza de estos problemas, este trabajo también analiza cómo se pueden combinar las técnicas metaheurísticas con metodologías de simulación para ampliar las capacidades de resolver problemas de optimización estocásticos. Después se trata un popular problema de optimización con aplicaciones prácticas para redes de telecomunicaciones, el problema de la p mediana no capacitado, analizándolo desde escenarios deterministas y estocásticos.
Recent advances in the telecommunications industry offer great opportunities to citizens and organizations in a globally-connected world, but they also create a vast number of complex challenges that decision-makers must face. Some of these challenges can be modelled as optimization problems. First, this thesis reviews how metaheuristics have been used to date to deal with optimization problems associated with telecommunication systems, detecting the main trends and challenges. In particular, the analysis focuses on problems in network design, routing, and allocation. Given the nature of these challenges, this work also discusses how the hybridization of metaheuristics with methodologies such as simulation can be employed to increase metaheuristics' capabilities when solving stochastic optimization problems. In addition, a popular optimization problem with practical applications in the design of telecommunications networks, the Uncapacitated Single Allocation p-Hub Median Problem (USApHMP) – where a fixed number of hubs have unlimited capacity, each non-hub node is allocated to a single hub and the number of hubs is known in advance –, is analysed in deterministic and stochastic scenarios.
9
Güttinger, Dennis [Verfasser], Johannes [Akademischer Betreuer] Fürnkranz, and Karsten [Akademischer Betreuer] Weihe. "A New Metaheuristic Approach for Stabilizing the Solution Quality of Simulated Annealing and Applications / Dennis Güttinger. Betreuer: Johannes Fürnkranz ; Karsten Weihe." Darmstadt : Universitäts- und Landesbibliothek Darmstadt, 2013. http://d-nb.info/110645376X/34.
Full text
10
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.
Full text
11
Landa, Silva Jesus Dario. "Metaheuristic and multiobjective approaches for space allocation." Thesis, University of Nottingham, 2003. http://eprints.nottingham.ac.uk/10147/.
Full textAbstract:
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.
12
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.
Full text
13
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.
Full textAbstract:
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.
14
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.
Full text
15
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/.
Full textAbstract:
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.
16
Esseghir, Mohamed Amir. "Metaheuristics for the feature selection problem : adaptive, memetic and swarm approaches." Thesis, Artois, 2011. http://www.theses.fr/2011ARTO0206/document.
Full textAbstract:
Afin d’améliorer la qualité de prédiction des techniques de classification automatique et de fouilles de données, plusieurs modèles ont été proposés dans la littérature en vue d’extraire des connaissances à partir des données. Toutefois, avec l’expansion des systèmes d’information et des technologies associées, ces techniques d’apprentissage s’avèrent de moins en moins adaptées aux nouvelles tailles et dimensions des données. On s’intéresse dans cette étude aux problèmes de grande dimensionnalité et à l’amélioration du processus d’apprentissage des méthodes de classification à travers les techniques de filtrage et de sélection d’attributs. Le problème « d’identification d’attributs pertinents » (Feature Selection Problem), tel qu’il est défini dans la littérature, relève d’une nature combinatoire. Dans le cadre de cette thèse, on s’est intéressé au développement de nouvelles techniques d’optimisation approchées et spécifiques au problème traité ainsi qu’à l’amélioration d’algorithmes existants. La conception, l’implémentation et l’étude empirique ont montré l’efficacité et la pertinence des métaheuristiques proposéesAlthough the expansion of storage technologies, networking systems, and information system methodologies, the capabilities of conventional data processing techniques remain limited. The need to knowledge extraction, compact representation and data analysis are highly motivated by data expansion. Nevertheless, learning from data might be a complex task, particularly when it includes noisy, redundant and information-less attributes. Feature Selection (FS) tries to select the most relevant attributes from raw data, and hence guides the construction of final classification models or decision support systems. Selected features should be representative of the underlying data and provide effective usefulness to the targeted learning paradigm (i.e. classification). In this thesis, we investigate different optimization paradigms as well as its adaptation to the requirements of the feature selection challenges, namely the problem combinatorial nature. Both theoritical and empirical aspects were studied, and confirm the effectiveness of the adopted methodology as well as the proposed metaheuristic based approaches
17
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.
Full text
18
Bogdanov, Daniil. "A Comparative Evaluation of Metaheuristic Approaches to the Problem of Curriculum-Based Course Timetabling." Thesis, KTH, Skolan för teknikvetenskap (SCI), 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-168009.
Full textAbstract:
Timetabling is an active area of research and used in a wide range of applications. As the development of most of these applications is on its way towards automation, the need for automated timetabling increases. Despite many years of research and development of automated approaches, solving NP-hard problems such as timetabling problems remains a challenge. Metaheuristic-based approaches to these problems are constantly being refined and further developed as the complexity of these applications increases. But despite the increase in complexity, the time it takes for these algorithms to solve these problems is constantly being challenged. While this thesis covers the fundamentals in metaheuristic approaches to the problem of timetabling, its main focus is to compare how two known metaheuristic algorithms, Tabu Searchand Simulated Annealing, perform across different scales of resources that are to be scheduled. To attempt fairness, similar implementations of these two algorithms were made in order to eliminate systematic biases. For each set of resources the algorithms solves a timetabling problem under a limited amount of time and computational capacity. The collective quality of all the produced timetables were compared. The results show that Simulated Annealing perform slightly better in the majority of the instances but with little margin for the collective quality of all tables. Despite trying to set a common ground for the these similar metaheuristic approaches, the underlying difficulties in comparing algorithms are discussed.Schemaläggning är ett aktivt forskningsområde och har ett stort antal tillämpningsområden. Då utvecklingen av de flesta av dessa tillämpningar är på väg mot automatisering, ökar behovet avautomatiserad schemaläggning. Trots många års forskning och utveckling av automatiserade tillvägagångssätt, är det fortfarande en utmaning att lösa NP-svåra problem såsom schemaläggningsproblem. Metaheuristiska metoder som löser dessa problem förfinas ständigt och vidare utvecklasi takt med ökande komplexitet i de tillämpningar dem löser. Men trots den ökade komplexiteten utmanas ständigt tiden det tar för dessa algoritmer att lösa dessa problem. Då denna avhandling behandlar grunderna i metaheuristiska tillvägagångssätt till schemaläggningsproblem, är dess huvudsakliga fokus att jämföra hur två kända metaheuristiska algoritmer,Tabu Search och Simulated Annealing, presterar vid olika skalor av de resurser som skall schemaläggas. För att göra jämförelsen rättvis, implementerades dessa två algoritmer likartat vilket syftar till att eliminera systematiska fel. För varje uppsättning av resurser löser algoritmerna ett schemaläggningsproblem under en begränsad tid och beräkningskapacitet. Den kollektiva kvalitén hos de producerade tidtabellerna jämförs. Resultaten visar att Simulated Annealing presterar något bättre i de flesta av fallen men med lite marginal sett till den kollektivakvalitén hos respektive algoritm. Trots försök att fastställa en gemensam grund för dessa liknande metoder, diskuteras de underliggande svårigheterna i att jämföra algoritmer.
19
Ancora, Gabriele <1993>. "The three-dimensional single-bin-size bin packing problem: combining metaheuristic and machine learning approaches." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2022. http://amsdottorato.unibo.it/10476/1/tesiFrontespizioOK.pdf.
Full textAbstract:
The Three-Dimensional Single-Bin-Size Bin Packing Problem is one of the most studied problem in the Cutting & Packing category. From a strictly mathematical point of view, it consists of packing a finite set of strongly heterogeneous “small” boxes, called items, into a finite set of identical “large” rectangles, called bins, minimizing the unused volume and requiring that the items are packed without overlapping. The great interest is mainly due to the number of real-world applications in which it arises, such as pallet and container loading, cutting objects out of a piece of material and packaging design. Depending on these real-world applications, more objective functions and more practical constraints could be needed. After a brief discussion about the real-world applications of the problem and a exhaustive literature review, the design of a two-stage algorithm to solve the aforementioned problem is presented. The algorithm must be able to provide the
spatial coordinates of the placed boxes vertices and also the optimal boxes input sequence, while guaranteeing geometric, stability, fragility constraints and a reduced computational time. Due to NP-hard complexity of this type
of combinatorial problems, a fusion of metaheuristic and machine learning techniques is adopted. In particular, a hybrid genetic algorithm coupled with a feedforward neural network is used. In the first stage, a rich dataset is created starting from a set of real input instances provided by an industrial company and the feedforward neural network is trained on it. After its training, given a new input instance, the hybrid genetic algorithm is able to run using the neural network output as input parameter vector, providing as output the optimal solution. The effectiveness of the proposed works is confirmed via several experimental tests.
20
Ghaffari, Mejlej Vahid [Verfasser]. "Adaptive search approach in the multidisciplinary optimization of lightweight structures using hybrid metaheuristics / Vahid Ghaffari Mejlej." München : Verlag Dr. Hut, 2019. http://d-nb.info/1202169643/34.
Full text
21
Ghaffari, Majlej Vahid Verfasser], Thomas [Akademischer Betreuer] [Vietor, and Axel [Akademischer Betreuer] Schumacher. "Adaptive search approach in the multidisciplinary optimization of lightweight structures using hybrid metaheuristics / Vahid Ghaffari Majlej ; Thomas Vietor, Axel Schumacher." Braunschweig : Technische Universität Braunschweig, 2019. http://d-nb.info/1202919847/34.
Full text
22
Younes, Abdunnaser. "Adapting Evolutionary Approaches for Optimization in Dynamic Environments." Thesis, University of Waterloo, 2006. http://hdl.handle.net/10012/2835.
Full textAbstract:
Many important applications in the real world that can be modelled as combinatorial optimization problems are actually dynamic in nature. However, research on dynamic optimization focuses on continuous optimization problems, and rarely targets combinatorial problems. Moreover, dynamic combinatorial problems, when addressed, are typically tackled within an application context. In this thesis, dynamic combinatorial problems are addressed collectively by adopting an evolutionary based algorithmic approach. On the plus side, their ability to manipulate several solutions at a time, their robustness and their potential for adaptability make evolutionary algorithms a good choice for solving dynamic problems. However, their tendency to converge prematurely, the difficulty in fine-tuning their search and their lack of diversity in tracking optima that shift in dynamic environments are drawbacks in this regard.
Developing general methodologies to tackle these conflicting issues constitutes the main theme of this thesis. First, definitions and measures of algorithm performance are reviewed. Second, methods of benchmark generation are developed under a generalized framework. Finally, methods to improve the ability of evolutionary algorithms to efficiently track optima shifting due to environmental changes are investigated. These methods include adapting genetic parameters to population diversity and environmental changes, the use of multi-populations as an additional means to control diversity, and the incorporation of local search heuristics to fine-tune the search process efficiently.
The methodologies developed for algorithm enhancement and benchmark generation are used to build and test evolutionary models for dynamic versions of the travelling salesman problem and the flexible manufacturing system. Results of experimentation demonstrate that the methods are effective on both problems and hence have a great potential for other dynamic combinatorial problems as well.
23
Teonacio, Bezerra Leonardo. "A component-wise approach to multi-objective evolutionary algorithms: From flexible frameworks to automatic design." Doctoral thesis, Universite Libre de Bruxelles, 2016. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/232586.
Full textAbstract:
Multi-objective optimization is a growing field of interest for both theoretical and applied research, mostly due to the higher accuracy with which multi-objective problems (MOPs) model real- world scenarios. While single-objective models simplify real-world problems, MOPs can contain several (and often conflicting) objective functions to be optimized at once. This increased accuracy, however, comes at the expense of a higher difficulty that MOPs pose for optimization algorithms in general, and so a significant research effort has been dedicated to the development of approximate and heuristic algorithms. In particular, a number of proposals concerning the adaptation of evolutionary algorithms (EAs) for multi-objective problems can be seen in the literature, evidencing the interest they have received from the research community.This large number of proposals, however, does not mean that the full search power offered by multi- objective EAs (MOEAs) has been properly exploited. For instance, in an attempt to propose significantly novel algorithms, many authors propose a number of algorithmic components at once, but evaluate their proposed algorithms as monolithic blocks. As a result, each time a novel algorithm is proposed, several questions that should be addressed are left unanswered, such as (i) the effectiveness of individual components, (ii) the benefits and drawbacks of their interactions, and (iii) whether a better algorithm could be devised if some of the selected/proposed components were replaced by alternative options available in the literature. This component-wise view of MOEAs becomes even more important when tackling a new application, since one cannot antecipate how they will perform on the target scenario, neither predict how their components may interact. In order to avoid the expensive experimental campaigns that this analysis would require, many practitioners choose algorithms that in the end present suboptimal performance on the application they intend to solve, wasting much of the potential MOEAs have to offer.In this thesis, we take several significant steps towards redefining the existng algorithmic engineering approach to MOEAs. The first step is the proposal of a flexible and representative algorithmic framework that assembles components originally used by many different MOEAs from the literature, providing a way of seeing algorithms as instantiations of a unified template. In addition, the components of this framework can be freely combined to devise novel algorithms, offering the possibility of tailoring MOEAs according to the given application. We empirically demonstrate the efficacy of this component-wise approach by designing effective MOEAs for different target applications, ranging from continuous to combinatorial optimization. In particular, we show that the MOEAs one can tailor from a collection of algorithmic components is able to outperform the algorithms from which those components were originally gathered. More importantly, the improved MOEAs we present have been designed without manual assistance by means of automatic algorithm design. This algorithm engineering approach considers algorithmic components of flexible frameworks as parameters of a tuning problem, and automatically selects the component combinations that lead to better performance on a given application. In fact, this thesis also represents significant advances in this research direction. Primarily, this is the first work in the literature to investigate this approach for problems with any number of objectives, as well as the first to apply it to MOEAs. Secondarily, our efforts have led to a significant number of improvements in the automatic design methodology applied to multi-objective scenarios, as we have refined several aspects of this methodology to be able to produce better quality algorithms.A second significant contribution of this thesis concerns understanding the effectiveness of MOEAs (and in particular of their components) on the application domains we consider. Concerning combina- torial optimization, we have conducted several investigations on the multi-objective permutation flowshop problem (MO-PFSP) with four variants differing as to the number and nature of their objectives. Through thorough experimental campaigns, we have shown that some components are only effective when jointly used. In addition, we have demonstrated that well-known algorithms could easily be improved by replacing some of their components by other existing proposals from the literature. Regarding continuous optimization, we have conducted a thorough and comprehensive performance assessment of MOEAs and their components, a concrete first step towards clearly defining the state-of-the-art for this field. In particular, this assessment also encompasses many-objective optimization problems (MaOPs), a sub-field within multi-objective optimization that has recently stirred the MOEA community given its theoretical and practical demands. In fact, our analysis is instrumental to better understand the application of MOEAs to MaOPs, as we have discussed a number of important insights for this field. Among the most relevant, we highlight the empirical verification of performance metric correlations, and also the interactions between structural problem characteristics and the difficulty increase incurred by the high number of objectives.The last significant contribution from this thesis concerns the previously mentioned automatically generated MOEAs. In an initial feasibility study, we have shown that MOEAs automatically generated from our framework are able to consistently outperform the original MOEAs from where its components were gathered both for the MO-PFSP and for MOPs/MaOPs. The major contribution from this subset, however, regards continuous optimization, as we significantly advance the state-of-the-art for this field. To accomplish this goal, we have extended our framework to encompass approaches that are primarily used for this continuous problems, although the conceptual modeling we use is general enough to be applied to any domain. From this extended framework we have then automatically designed state-of- the-art MOEAs for a wide range of experimental scenarios. Moreover, we have conducted an in-depth analysis to explain their effectiveness, correlating the role of algorithmic components with experimental factors such as the stopping criterion or the performance metric adopted.Finally, we highlight that the contributions of this thesis have been increasingly recognized by the scientific community. In particular, the contributions to the research of MOEAs applied to continuous optimization are remarkable given that this is the primary application domain for MOEAs, having been extensively studied for a couple decades now. As a result, chapters from this work have been accepted for publication in some of the best conferences and journals from our field.Doctorat en Sciences de l'ingénieur et technologie
info:eu-repo/semantics/nonPublished
24
Fink, Martin [Verfasser], Rainer [Akademischer Betreuer] Kolisch, Rainer [Gutachter] Kolisch, and Guy [Gutachter] Desaulniers. "The Vehicle Routing Problem with Worker and Vehicle Synchronization: Metaheuristic and Branch-and-Price Approaches / Martin Fink ; Gutachter: Rainer Kolisch, Guy Desaulniers ; Betreuer: Rainer Kolisch." München : Universitätsbibliothek der TU München, 2016. http://d-nb.info/1170321348/34.
Full text
25
Dik, Guvenc. "A mathematical approach to synchronise and optimise emergency department operations." Thesis, Queensland University of Technology, 2019. https://eprints.qut.edu.au/130764/1/Guvenc_Dik_Thesis.pdf.
Full textAbstract:
This study develops a mathematical optimisation approach to tackle the patient flow problem. This problem arises from emergency department operations and its interactions with ambulance and hospital services. A predictive scheduling model is developed based on the flexible job shop scheduling framework. The developed approach can be embedded in real-time intelligent decision support systems. These systems can provide hospitals with quantitatively identified clinical resources causing transitional bottlenecks and risk evaluation whilst conforming to performance targets. Moreover, it can provide optimal treatment and diagnostic action sequences. Thus, health care professionals can improve the quality of emergency care for their patients.
26
Chen, Yuning. "Hybrid Metaheuristics for Quadratic Knapsack Problems Iterated responsive threshold search for the quadratic multiple knapsack problem A “reduce and solve” approach for the multiple-choice multidimensional knapsack problem." Thesis, Angers, 2016. http://www.theses.fr/2016ANGE0062.
Full textAbstract:
Cette thèse considère quatre problèmes d’optimisation combinatoire connus sous le nom de Problèmes de Sac-à-Dos Quadratiques : le problème de sac-à-dos quadratique (QSP), le problème de sac-à-dos multiple quadratique (QMSP), le problème de sac-à-dos multiple quadratique généralisé (GQMSP) et le nouveau problème de sac-à-dos multiple quadratique bi-objectif (BO-QMSP) présenté dans cette thèse. Parmi eux, le QSP est le modèle de base tandis que les trois autres introduisent des contraintes ou des fonctions objectives supplémentaires. Ces problèmes ont de nombreuses applications pratiques. Étant donné qu’ils appartiennent à la famille NP-difficile, il est difficile de les résoudre dans le cas général. Pour cette raison, cette thèse est consacrée à la création d’approches métaheuristiques hybrides efficaces pour résoudre ces quatre problèmes difficiles. Plus précisément, nous développons une approche itérative d’exploration hyperplane pour le QSP, deux algorithmes hybrides ("Iterative responsive threshold search" et "Evolutionary path relinking") pour le QMSP, un algorithme mémétique pour le GQMSP et une approche hybride en deux étapes pour le BO-QMSP. Ces algorithmes partagent certains ingrédients fondamentaux (e.g., les opérateurs de mouvement de base et les heuristiques gloutonnes) qui avec quelques adaptations sont généralement applicables à d’autres problèmes de sac-à-dos quadratiques. Ils possèdent également un certain nombre de conceptions spécifiques aux problèmes étudiés. Tous les algorithmes ont été expérimentalement démontrés être en mesure de rivaliser favorablement avec les méthodes de l’état de l’artThis thesis considers four combinatorial optimization problems known under the name Quadratic Knapsack Problems: the quadratic (single) knapsack problem (QKP), the quadratic multiple knapsack problem (QMKP), the generalized quadratic multiple knapsack problem (GQMKP) and the new bi-objective quadratic multiple knapsack problem (BO-QMKP) introduced in this thesis. Among them, the QKP is the most basic model while the other three generalize upon it by introducing additional constraints or objective functions. These problems have a wide range of practical applications. Given that they belong to the NP-hard family, it is computationally difficult to solve them in the general case. For this reason, this thesis is devoted to developing effective hybrid metaheuristic approaches to tackle these four challenging problems. Specifically, we develop an iterated hyperplane exploration approach for the QKP, two hybrid metaheuristic algorithms (iterated responsive threshold search and evolutionary path relinking) for the QMKP, an effective memetic algorithm for the GQMKP and a hybrid two-stage approach for the BO-QMKP. These algorithms share some fundamental ingredients (e.g., move operators and greedy heuristics) which with small adaptations are generally applicable to other Quadratic Knapsack Problems. They also possess a number of problem-specific designs. All algorithms were experimentally demonstrated to be able to compete favourably with state-of-the-art methods
27
Segretier, Wilfried. "Approche évolutionnaire et agrégation de variables : application à la prévision de risques hydrologiques." Thesis, Antilles-Guyane, 2013. http://www.theses.fr/2013AGUY0673/document.
Full textAbstract:
Les travaux de recherche présentés dans ce mémoire s'inscrivent dans la lignée des approches de modélisation hydrologiques prédictives dirigées par les données. Nous avons particulièrement développé leur application sur le contexte difficile des phénomènes de crue éclairs caractéristiques des bassins versants de la région Caraïbe qui pose un dé fi sé.curi taire. En envisageant le problème de la prévision de crues comme un problème d'optimisation combinatoire difficile nous proposons d'utiliser la notion de métaneuristiques, à travers les algorithmes évolutionnaire notamment pour leur capacité à parcourir efficacement de grands espaces de recherche et fi fournir des solutions de bOlIDe qualité en des temps d'exécution raisonnables. Nous avons présenté l'approche de prédiction AV2D : Aggregate Variable Data Driven dom le concept central est la notion de variable agrégée. L'idée sous-jacente à ce concept est de considérer le pouvoir prédictif de nouvelles variables définies comme le résultat de fonctions tatistiques, dites d'agrégation calculées sur de donnée' correspondant à des périodes de temps précédent uo événem nt à prédire. Ces variable sont caractérisées par des ensembles de paramètres correspondant a leur pJ:opriétés. Nous avons imroduitle variables agrégées hydrométéorologiques permettant de répondre au problème de la classification d événements hydrologiques. La complexité du parcours de l'espace de recherche engendré par les paramètres définissant ces variables a été prise en compte grâce à la njse en oeuvre d'un algorithme évolutionnaire particulier dont les composants ont été spécifiquement définis pour ce problème. Nous avons montré, à travers une étude comparative avec d'autres approches de modélisation dirigées par les données, menée sur deux cas d'études de bassins versant caribéens, que l'approche AV2D est particulièrement bien adaptée à leur contexte. Nous étudions par la suite les bénéfices offerts par les approches de modélisation hydrologiques modulaires dirigées par les données, en définissant un procédé de division en sous-processus prenant en compte les caractéristiques paniculières des bassins versants auxquels nous nous intéressons. Nou avons proposé une extension des travaux précédents à travers la définition d'une approche de modélisation modulaire M2D: Spatial Modular Data Driven, consistant à considérer des sous-processus en divisant l'ensemble des exemples à classifier en sous-ensembles correspondant à des comportements hydrologiques homogènes. Nous avons montré à travers une étude comparative avec d autres approches dU'igées par les données mises en oeuvre sur les mêmes sous-ensembles de données que celte approche permet d améliorer les résultats de prédiction particulièrement à coun Lenne. Nous avons enfin proposé la modélisation d un outil de piThe work presented in this thesis is in the area of data-driven hydrological modeling approaches. We particularly investigared their application on the difficult problem of flash flood phenomena typically observed in Caribbean watersheds. By considering the problem of flood prediction as a combinatorial optimization problem, we propose to use the notion of Oleraheuristics, through evolutionary algorithms, especially for their capacity ta visit effjciently large search space and to provide good solutions in reasonable execution times. We proposed the hydrological prediction approach AV2D: Aggregate Variable Data Driven which central concept is the notion of aggregate variable. The underlying idea of this [concept is to consider the predictive power of new variables defined as the results of statistical functions, called aggregation functions, computed on data corresponding ta time periods before an event ta predict. These variables are characterized by sets of parameters corresponding ta their specifications. We introduced hydro-meteorological aggregate variables allowing ta address the classification problem of hydrological events. We showed through a comparative study on two typical caribbean watersheds, using several common data driven modelling techniques that the AV2D approach is panicul.rly weil fitted ta the studied context. We also study the benefits offered by modulaI' approaches through the definition of the SM2D: Spatial Modular DataDriven approach, consisting in considering sub-processes partly defined by spatial criteria. We showed that the results obtained by the AV2D on these sub-processes allows to increase the performances particularly for short term prediction. Finally we proposed the modelization of a generic control tool for hydro-meteorological prediction systems, H2FCT: Hydro-meteorological Flood Forecasting Control 1'001
28
Arbaoui, Taha. "Modeling and solving university timetabling." Thesis, Compiègne, 2014. http://www.theses.fr/2014COMP2167/document.
Full textAbstract:
Cette thèse s’intéresse aux problèmes d’emploi du temps d’universités. Ces problèmes sont rencontrés chaque année par les utilisateurs. Nous proposons des bornes inférieures, des méthodes heuristiques et des modèles de programmation mixte en nombres entiers et de programmation par contraintes. Nous traitons le problème d’emploi du temps d’examens et celui d’affectation des étudiants. Nous proposons de nouvelles méthodes et formulations et les comparons aux approches existantes. Nous proposons, pour le problème d’emploi du temps d’examens, une amélioration d’un modèle mathématique en nombres entiers qui permettra d’obtenir des solutions optimales. Ensuite, des bornes inférieures, une formulation plus compacte des contraintes et un modèle de programmation par contraintes sont proposés. Pour le problème d’emploi du temps d’examens à l’Université de Technologie de Compiègne, nous proposons une approche mémétique. Enfin, nous présentons un modèle mathématique pour le problème d’affectation des étudiants et nous étudions sa performance sur un ensemble d’instances réellesThis thesis investigates university timetabling problems. These problems occur across universities and are faced each year by the practitioners. We propose new lower bounds, heuristic approaches, mixed integer and constraint programming models to solve them. We address the exam timetabling and the student scheduling problem. We investigate new methods and formulations and compare them to the existing approaches. For exam timetabling, we propose an improvement to an existing mixed integer programming model that makes it possible to obtain optimal solutions. Next, lower bounds, a more compact reformulation for constraints and a constraint programming model are proposed. For the exam timetabling problem at Université de Technologie de Compiègne, we designed a memetic approach. Finally, we present a new formulation for the student scheduling problem and investigate its performance on a set of real-world instances
29
Lu, Zhi. "Optimization approaches for minimum conductance graph partitioning." Thesis, Angers, 2020. http://www.theses.fr/2020ANGE0013.
Full textAbstract:
Le problème de partitionnement de graphe de conductance minimale (MCGPP) est un problème d’optimisation combinatoire NP-difficile avec de nombreuses applications pratiques dans divers domaines tels que la détection communautaire, la bioinformatique et la vision par ordinateur. Etant donnée sa complexité intrinsèque, des approches heuristiques et métaheuristiques constituent un moyen convenable pour résoudre des instances de grande taille. Cette thèse est consacrée au développement d’algorithmes métaheuristiques performants pour le MC-GPP. Plus précisément, nous proposons un algorithme «Stagnation aware Breakout Tabu Search», un algorithme évolutif hybride (MAMC) et un algorithme multiniveaubasé sur le recuit simulé (IMSA). Nous présentons des résultats expérimentaux sur de nombreux graphes de grande dimension de la littérature ayant jusqu’à 23 millions de sommets. Nous montrons la haute performance de nos algorithmes par rapport à l’état de l’art. Nous analysons les éléments algorithmiques et stratégies de recherche pour mettre en lumière leur influence sur la performance des algorithmes proposésThe minimum conductance graph partitioning problem (MC-GPP) is an important NP-hard combinatorial optimization problem with numerous practical applications in various areas such as community detection, bioinformatics, and computer vision. Due to its high computational complexity, heuristic and metaheuristic approaches constitute a highly useful tool for approximating this challenging problem. This thesis is devoted to developing effective metaheuristic algorithms for the MC-GPP. Specifically, we propose a stagnation-aware breakout tabu search algorithm (SaBTS), a hybrid evolutionary algorithm (MAMC), and an iterated multilevel simulated annealing algorithm (IMSA). Extensive computational experiments and comparisons on large and massive benchmark instances (with more than 23 million vertices) demonstrate that the proposed algorithms compete very favorably with stateof- the-art algorithms in the literature. Furthermore, the key issues of these algorithms are analyzed to shed light on their influences over the performance of the proposed algorithms
30
Montoya, Jose-Alejandro. "Electric Vehicle Routing Problems : models and solution approaches." Thesis, Angers, 2016. http://www.theses.fr/2016ANGE0020/document.
Full textAbstract:
Étant donné leur faible impact environnemental, l’utilisation des véhicules électriques dans les activités de service a beaucoup augmenté depuis quelques années. Cependant, leur déploiement est freiné par des contraintes techniques telles qu’une autonomie limitée et de longs temps de charge des batteries. La prise en compte de ces contraintes a mené à l’apparition de nouveaux problèmes de tournées de véhicules pour lesquels, en plus d’organiser les tournées,il faut décider où et de combien charger les batteries. Dans cette thèse nous nous intéressons à ces problèmes au travers de quatre études. La première concerne le développement d’une métaheuristique en deux phases simple mais performante pour résoudre un problème particulier appelé "Green VRP”. Dans la seconde, nous nous concentrons sur la modélisation d’un aspect essentiel dans ces problèmes : le processus de chargement des batteries. Nous étudions différentes stratégies pour modéliser ce processus et montrons l’importance de considérer la nature non linéaire des fonctions de chargement. Dans la troisième étude nous proposons une recherche locale itérative pour résoudre des problèmes avec des fonctions de chargement non linéaires. Nous introduisons un voisinage dédié aux décisions de chargement basé sur un nouveau problème de chargement sur une tournée fixée. Dans la dernière étude, nous traitons un problème réel de tournées de techniciens avec des véhicules classiques et électriques. Ce problème est résolu par une métaheuristique qui décompose le problème en plusieurs sous-problèmes plus simples résolus en parallèle, puis qui assemble des parties des solutions trouvées pour construire la solution finaleElectric vehicles (evs) are one of the most promising technologies to reduce the greenhouse gas emissions. For this reason, the use of evs in service operations has dramatically increased in recent years. Despite their environmental benefits, evs still face technical constraints such as short autonomy and long charging times. Taking into account these constraints when planning ev operations leads to a new breed of vehicle routing problems (vrps), known as electricVrps (evrps). In addition, to the standard routing decisions, evrps are concerned with charging decisions: where and how much to charge. In this ph. D thesis, we address evrps through 4 different studies. In the first study, we tackle the green vehicle routing problem. To solve the problem, we propose a simple, yet effective, two-phase matheuristic. In the second study, we focus a key modelling aspects in evrps: the battery charging process. We study different strategies to model this process and show the importance of considering the nonlinear nature of the battery charging functions. InThe third study, we propose an iterated local search to tackle evrp with non-linear charging functions. We introduce a particular local search operator for the charging decisions based on a new fixedroute charging problem. The fourth and last study considers a real technician routing problem with conventional and electric vehicles (trp-cev). To tackle this problem, we propose a parallel matheuristic that decomposes the problem into a set of easier-to-solve subproblemsThat are solved in parallel processors. Then the approach uses parts of the solutions found to the subproblems to assemble final solution to the trp-cev
31
Maalouf, Elie. "A distributed approach for smart production management in cellular manufacturing system for mass customization." Electronic Thesis or Diss., Compiègne, 2022. http://www.theses.fr/2022COMP2689.
Full textAbstract:
Cette recherche tente de répondre à la question suivante : Comment optimiser la planification de la production (y compris la planification et l'ordonnancement des processus) pour les produits personnalisés en masse et le système de fabrication cellulaire dans un contexte d'industrie 4.0, donc dans une usine et une chaîne d'approvisionnement intelligentes et connectées ? Cette recherche propose une approche distribuée pour la gestion intelligente de la production dans les systèmes de fabrication cellulaire pour la customisation de masse. Plus précisément, il propose une approche complète pour la planification et le contrôle de la fabrication pour CMS et MC basée sur la planification et l'ordonnancement dynamiques et distribués des processus/production. Il repose sur trois niveaux de décision : 1 - Niveau usine appelé master planning, intégrant en temps réel les données de la supply chain ; 2 - Niveau cellulaire, appelé planification cellulaire ; 3 - Niveau de l'atelier appelé système d'enchères, traitant des événements inattendus. Les principales contributions à la recherche sont : 1 - L'approche distribuée complète intégrant la planification, l'ordonnancement et l'allocation de la manutention tout en tenant compte des données en temps réel de la chaîne d'approvisionnement ; 2 - Une formulation mathématique du problème d'optimisation multi-objectifs pour le master planning (niveau usine) ; 3 - Deux approches de résolution basées sur les séquences mises en œuvre sur deux métaheuristiques, l'algorithme génétique de tri non dominé II (NSGAII) et l'optimisation d'essaim de particules multi-objectifs à vitesse contrainte (SMPSO)This research tries to answer the following question: How to optimize production planning (including process planning and scheduling) for mass customized products and cellular manufacturing system in an industry 4.0 context, hence in a smart connected factory and supply chain? It proposes a distributed approach for smart production management in cellular manufacturing systems for mass customization. More precisely, it proposes a full approach for manufacturing planning and control for CMS and MC based on dynamic and distributed process/production planning and scheduling. It is based on three decision making levels: 1 - factory level called master planning, integrating real time data from the supply chain; 2 - cell level, called cell planning; 3 - shop floor level called bidding system, dealing with unexpected events. The main research contributions are: 1 - The full distributed approach integrating planning, scheduling, and material handling allocation while considering real time data from the supply chain. 2 - A multi-objective optimization formulation for the master planning problem (factory level). 3 - Two sequence-based resolution approaches implemented on two metaheuristics, Non-dominated Sorting Genetic Algorithm II (NSGAII), and Speed-constrained Multi-Objective Particle Swarm Optimization (SMPSO)
32
Cáceres, Cruz José de Jesús. "Randomized Algorithms for Rich Vehicle Routing Problems: From a Specialized Approach to a Generic Methodology." Doctoral thesis, Universitat Oberta de Catalunya, 2013. http://hdl.handle.net/10803/127153.
Full textAbstract:
El Problema de Enrutamiento de Vehículos (VRP) y sus diferentes variantes básicas son un dominio ampliamente estudiado en la comunidad científica de optimización. Algunos estudios han utilizado combinaciones específicas de restricciones encontradas en la vida real para definir los emergentes VRP Enriquecidos. Este trabajo aborda la integración de heurísticas, probabilidad sesgada, simulación, técnicas de computación distribuida & paralelas, y programación con restricciones. Los enfoques propuestos han solucionado algunas variantes del VRP: en primer lugar, las familias deterministas: VRP con flotas Heterogéneas (HVRP), VRP con flotas Heterogéneas y costo variable (HVRP-V), VRP con flota Heterogénea y Múltiples viajes (HVRPM), VRP con matriz de costo Asimétrica (AVRP), VRP con flota Heterogénea y matriz de costo Asimétrica (HAVRP), VRP con ventanas de Tiempo (VRPTW), y VRP Distancia limitada (DCVRP); en segundo lugar, las familias de naturaleza estocástica: VRP con Demandas estocásticas (VRPSD), y Problemas de Inventario y Enrutamiento de Vehículos con Demandas estocásticas (IRPSD). Una extensa revisión bibliográfica se ha realizado para cada una de estas variantes. Un primer enfoque propone la combinación de una aleatorización sesgada con heurísticas clásicas para la solución de problemas deterministas. Un segundo enfoque se centra en la combinación de heurísticas aleatorias con simulación (Simheuristics) para ser aplicados sobre los problemas estocásticos comentados. Por último, se propone un tercer enfoque basado en el trabajo conjunto de heurísticas aleatorias con programación de restricciones para resolver varios tipos de problemas de enrutamiento. Los algoritmos heurísticos desarrollados han sido aplicados en varios casos de referencia --entre ellos, dos estudios de casos reales de distribución en España-- y los resultados obtenidos son, en general, prometedores y útiles para los decisores.The Vehicle Routing Problem (VRP) is a well known domain in optimization research community. Its different basic variants have been widely explored in the literature. Some studies have considered specific combinations of real-life constraints to define the emerging Rich VRP scopes. This work deals with the integration of heuristics, biased probability, simulation, parallel & distributed computing techniques, and constraint programming. The proposed approaches are tested for solving some variants of VRPs, namely, first, the deterministic families: Heterogeneous VRP (HVRP), Heterogeneous VRP with Variable cost (HVRP-V), Heterogeneous fleet VRP with Multi-trips (HVRPM), Asymmetric cost matrix VRP (AVRP), Heterogeneous fleet with Asymmetric cost matrix VRP (HAVRP), VRP with Time Windows (VRPTW), and Distance-Constrained VRP (DCVRP); second, the stochastic nature families: VRP with Stochastic Demands (VRPSD), and Inventory Routing Problem with Stochastic Demands (IRPSD). An extensive literature review is performed for all these variants, focusing on the main contributions of each work. A first approach proposes a biased-randomization of classical heuristics for solving the deterministic problems addressed here. A second approach is centered on the combination of randomized heuristics with simulation (Simheuristics) to be applied on the commented stochastic problems. Finally, a third approach based on the joined work of randomized heuristics with constraint programming is proposed to solve several types of routing problems. The developed heuristic algorithms are tested in several benchmark instances --between these, two real-life case studies in Spain are considered-- and the results obtained are, on average, highly promising and useful for decision makers.
33
Messaoudi, Bilal. "Approches par décomposition pour des problèmes réels de planification et de tournées de véhicules." Electronic Thesis or Diss., Université de Lorraine, 2020. http://www.theses.fr/2020LORR0211.
Full textAbstract:
Différents acteurs du monde de l'industrie rencontrent quotidiennement des problèmes d'optimisation impliquant des décisions à prendre soit à un niveau tactique, comme pour déterminer le meilleur emplacement d'entrepôts à installer pour couvrir une zone géographique donnée, ou bien à un niveau opérationnel, comme pour améliorer le rendement d'un processus de production. L'objectif de cette thèse Cifre est de proposer des approches de résolution en se focalisant sur des problèmes de planification et de tournées de véhicules issus de clients industriels. Dans un premier temps, nous mettrons en lumière les principales difficultés que l'on peut rencontrer dans le processus d'aide à la décision avec le client industriel, pour ensuite aborder trois cas concrets de problématiques complexes que nous avons traités durant cette thèse. Nous utilisons essentiellement des approches par décomposition pour résoudre ces problèmes au vu de leur complexité et à la taille des instances industrielles traitées. Pour valider l'efficacité de certaines méthodes de résolution, nous les comparons aux meilleures bornes obtenues en relaxant certaines contraintes et aux solutions optimales de problèmes similaires existants dans la littérature lorsque cela s'avère possibleDifferent players in the industry face every day new optimization problems involving decisions to be made either at a tactical level, such as determining the best warehouses’ location intended to cover a given geographical area, or at an operational level, such as improving efficiency of a production process. The objective of this 'Cifre' thesis is to propose solution approaches while focusing on planning and vehicle routing problems faced by industrial customers. We will highlight first the main difficulties that can be encountered in aiding decisions process with the industrial customer, and then address three case studies of complex problems that we have dealt with during the thesis. We mainly use decomposition approaches to solve these problems due to their complexity and large size of the corresponding instances. To assess the performance of some solution methods, we compare them to the best bounds obtained by relaxing some constraints and to optimal solutions of similar problems existing in the literature when possible
34
Samir, Sara. "Approches coopératives pour certaines classes de problèmes d'optimisation non convexe : Algorithmes parallèles / distribués et applications." Electronic Thesis or Diss., Université de Lorraine, 2020. http://www.theses.fr/2020LORR0039.
Full textAbstract:
Dans cette thèse, nous nous intéressons au développement des approches coopératives pour la résolution de certaines classes de problèmes d'optimisation non convexe qui jouent un rôle très important de par leurs applications dans de nombreux domaines. Il s'agit de combiner plusieurs algorithmes connus sous les noms des algorithmes composants (participants). La combinaison est basée principalement sur la programmation DC (Difference of Convex Functions) et DCA (DC Algorithm) avec des métaheuristiques. Pour la conception des logiciels nous utilisons les paradigmes de la programmation parallèle et distribuée. Chaque processus s'occupe d'un algorithme et communique avec les autres en appelant les fonctions de la bibliothèque MPI (Message Passing Interface) qui est un protocole de communication en programmation parallèle et distribuée. Outre l'introduction et la conclusion, la thèse est composée de quatre chapitres. Le chapitre 1 concerne les outils théoriques et algorithmiques comme servant de base méthodologique aux chapitres suivants. Le chapitre 2 s'articule autour les problèmes linéaires à variables mixtes binaires. Pour la résolution de ces problèmes, nous proposons une approche coopérative entre DCA et VNS (Variable Neighborhood Search). Puisque le schéma est constitué de deux algorithmes, nous optons pour la communication point à point entre les processus. Nous adaptons notre schéma pour résoudre le problème de localisation de l'installation avec des contraintes de capacités. Dans le chapitre 3, nous étudions la programmation quadratique à variables binaires. Nous développons une coopération entre DCA-Like (une nouvelle version de DCA) et deux autres métaheuristiques : GA (Genetic Algorithm) et MBO (Migrating Birds Optimization). Pour la communication entre les processus, nous utilisons la communication collective. Plus précisément une fonction qui permet la diffusion simultanée l'information d'un processus à tous les autres. Cette approche est adaptée et appliquée au problème d'affectation quadratique. Dans le chapitre 4, nous résolvons les problèmes de "clustering" via la minimisation de la somme des carrés par deux approches coopératives. La première consiste à combiner le DCA avec VNS et TS (Tabu Search). Quant à la deuxième, elle utilise la MBO avec les trois derniers algorithmes précités. Dans ces deux approches, nous utilisons une fonction de communication qui permet au processus d'accéder aux mémoires des autres et y enregistrer son information sans un temps d'attenteIn this thesis, we are interested in developing new cooperative approaches for solving some classes of nonconvex problems which play a very important role to model real-world problems. To design the schemes of our approaches, we combine several algorithms which we call the component (participant) algorithms. The combination is mainly based on DC (Difference of Convex Functions) and DCA (DC Algorithm) with metaheuristics. To develop our solution methods, we use the paradigm of parallel and distributed programming. Therefore, each process deals with an algorithm and communicates with the others by calling the functions of the MPI (Message Passing Interface) library which is a communication protocol in parallel and distributed programming. Besides the introduction and conclusion, this thesis is composed of four chapters. Chapter 1 concerns the theoretical and algorithmic tools serving as a methodological basis for the following chapters. Chapter 2 is about the mixed binary linear programs. To solve these problems, we propose a cooperative approach between DCA and VNS (Variable Neighborhood Search). Since the scheme is constituted by two algorithms, we use the point to point communication between the processes. As an application, we adapt our scheme to solve the capacitated facility location problem. Concerning chapter 3, we study the class of binary quadratic problems. Regarding the solution methods, we develop a cooperation between DCA-like which is a new version of DCA and two other metaheuristics: GA (Genetic Algorithm) and MBO (Migrating Birds Optimization). The exchange of information between the processes is expressed by using collective communication's function. More precisely, we call a function which allows broadcasting information of a process to all the others at the same time. This cooperative approach is adapted to the quadratic assignment problem. In chapter 4, we solve the MSSC (Minimum-Sum-of-Squares Clustering) using two cooperative approaches. The first combines DCA, VNS, and TS (Tabu Search). As for the second, it combines the MBO with the other three algorithms cited before. In these two approaches, we use a function of communication that allows a process to access the memories of the others and save the information there without blocking the work of the receiving processes
35
Souza, Neto José Ferreira de. "Modelagem e meta-heurísticas para o problema de roteamento de veículos com janelas de tempo, múltiplos entregadores e múltiplas viagens em uma empresa de distribuição de bebidas." Universidade Federal de São Carlos, 2016. https://repositorio.ufscar.br/handle/ufscar/7942.
Full textAbstract:
Submitted by Izabel Franco (izabel-franco@ufscar.br) on 2016-10-06T17:59:08Z
No. of bitstreams: 1
DissJFSN.pdf: 5729965 bytes, checksum: 946688f479f7780db197fa49b4b4c853 (MD5)Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T13:51:08Z (GMT) No. of bitstreams: 1 DissJFSN.pdf: 5729965 bytes, checksum: 946688f479f7780db197fa49b4b4c853 (MD5)
Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T13:51:14Z (GMT) No. of bitstreams: 1 DissJFSN.pdf: 5729965 bytes, checksum: 946688f479f7780db197fa49b4b4c853 (MD5)
Made available in DSpace on 2016-10-20T13:51:20Z (GMT). No. of bitstreams: 1 DissJFSN.pdf: 5729965 bytes, checksum: 946688f479f7780db197fa49b4b4c853 (MD5) Previous issue date: 2016-03-21
Não recebi financiamento
Vehicle routing problems occur in many practical situations where the pickup and/or delivery of goods is required. In this context, the present research aims to contribute to the study of logistic operations that arise in companies that deliver products on a regular basis to customers in densely populated urban areas. The problem consists in designing minimal cost daily routes serving the maximal number of customers. To this end, the crew of each vehicle comprise multiple deliverymen as means to reduce service times. Based on a case study in a drinks producer and distributor in the state of São Paulo, it is proposed a mixed integer linear programming model that comprise costs with own and chartered vehicles and the number of deliverymen, and various operational constraints such as time windows in customers, multiple daily trips, time limitations for the circulation of some vehicle types in specific areas, compatibility between vehicles and customers, maximum load in each vehicle, maximum route time and minimum load for the realization of a second trip. Results obtained by solving the model with real instances through exact (branch&cut), heuristic (constructive, local search, GRASP and Simulated Annealing) and hybrid (GRASP and branch&cut) approaches demonstrate the good quality of the generated solutions, and indicate the potential of application of some of these methods in practice.
Problemas de roteamento de veículos ocorrem em diversas situações práticas onde se faz necessária a distribuição e/ou coleta de produtos. Nesse contexto, a presente pesquisa visa o estudo das operações logísticas presentes em empresas que entregam produtos em base regular a clientes localizados em áreas urbanas de alta densidade demográfica. O problema consiste na obtenção de rotas de mínimo custo visando o atendimento do maior número de clientes da carteira diária. Para tal, a tripulação de cada veículo pode contemplar múltiplos entregadores para redução dos tempos de serviço. Com base em um estudo de caso em uma distribuidora de bebidas do interior do Estado de São Paulo, é proposto um modelo de programação linear inteira mista que considera custos com frota própria e fretada e com o número de entregadores, e diversas restrições operacionais, tais como janelas de tempo em clientes, múltiplas viagens diárias, limitações de horários de circulação de tipos de veículos, compatibilidade entre veículos e clientes, capacidade máxima de carga a ser transportada em cada veículo, tempo máximo de rota e carga mínima para realização da segunda viagem. Resultados da resolução do modelo para instâncias reais por meio de abordagens exatas (branch&cut), heurísticas (construtiva, busca local, GRASP e Simulated Annealing) e híbrida (GRASP e branch&cut), demonstram a boa qualidade das soluções geradas, e evidenciam o potencial de uso dessas metodologias na prática.
36
Wang, Chenghao. "Contribution à l’optimisation robuste de réseaux." Thesis, Compiègne, 2021. http://www.theses.fr/2021COMP2632.
Full textAbstract:
Cette thèse a pour objectif la proposition de nouvelles approches algorithmiques et de modélisation pour la résolution de certains problèmes d’optimisation de réseau dans les domaines des transports et des télécommunications. Plus précisément, les problèmes étudiés tombent dans le domaine du transport aérien, nommément le problème d’affectation des niveaux de vol dans l’espace aérienne, et dans le domaine des télécommunications où on traite des problèmes d’allocation de ressources dans les réseaux 5G. Un aspect important qui a été pris en compte dans cette étude est l’incertitude des données, c’est-à-dire le fait qu’une partie des données d’entrée ne sont pas connues de façon précise. Notre tâche a consisté à modéliser chacun des problèmes, proposer une formulation compacte des variantes déterministe et robuste, et proposer des approches appropriées pour les résoudre. Les problèmes étudiés tombent dans la catégorie des problèmes NP-complets et ils sont difficile à résoudre même pour des instances de taille modeste. Ils deviennent encore plus difficiles dans leur version robuste. Pour le problème d’affectation des niveaux de vols, nous avons considéré les incertitudes liées à l’heure de départ qui sont modélisées via un modèle de mélange gaussien. Le problème est modélisé comme un « chance-constrained problem » et résolu par un algorithme heuristique de génération de contraintes. Il s’agit d’une approche générale qui trouvera des applications plus large que ceux étudiés dans cette thèse. Ensuite, nous avons étudié la conception optimale des réseaux sans fil de 5ème génération (5G) dans le contexte de l’architectures Superfluid. Plus précisément, l’architecture 5G Superfluid est basée sur des entités de réseau appelées « Bloc Fonctionnel Réutilisable » (RFB) qui sont à la base des réseaux 5G. Nous avons étudié le problème de conception d’un tel réseau Superfluid à coût minimum pour lequel une formulation en programme linéaire mixte suivie d’une approche de résolution utilisant la décomposition de Benders a été implémentée ont été proposées. Enfin, le problème spécifique de conception de réseaux virtuels a été considéré sous l’angle de l’efficacité énergétique. Nous avons proposé une formulation de programmation linéaire en nombres entiers mixte du problème robuste, et présentons une nouvelle matheuristique basée sur la combinaison d’un algorithme génétique avec la recherche de voisinage. Les résultats numériques ont porté sur des instances de taille réalistes et ont montré la validité des modèles et des approches proposéesThis Ph.D. Thesis is focused on proposing new optimization modeling and algorithmic approaches for dealing with real-world network optimization problems arising in the transportation and telecommunications fields. Since the focus has been on real-world applications, a relevant aspect that has been taken into account is data uncertainty, i.e. the fact that the value of a subset of input data of the problem is not exactly known when the problem is solved. More precisely, in the context of transportation problems, it was considered the flight level assignment problem, which arises in air traffic management. It aims at establishing the flight levels of a set of aircraft in order to improve the total assignment revenue, to reduce the total number of flight conflicts and also the total en-route delay. In this context, we proposed a new chance-constrained optimization problem and iterative constraint-generation heuristic which is based on both analytical and sampling methods. Besides transportation problems, this Thesis has also focused on the optimal design of 5th generation of wireless networks (5G) considering Superfluid and virtual architectures. Specifically, the 5G Superfluid architecture is based on atomic virtual entities called Reusable Functional Block (RFB). We investigated the problem of minimizing the total installation costs of a 5G Superfluid network (composed of virtual entities and realized over a physical network) while guaranteeing constraint on user coverage, downlink traffic performance and technical constraints on RFBs of different nature. To solve this hard problem, we proposed a Benders decomposition approach. Concerning instead the design of general virtual networks, we adopted a green paradigm that pursues energy-efficiency and tackled a state-of-the-art robust mixed integer linear programming formulation of the problem, by means of a new matheuris tic based on combining a genetic algorithm with exact large neighborhood searches. Results of computational tests executed considering realistic problem instances have shown the validity of all the new optimization modeling and algorithmic approaches proposed in this Thesis for the transportation and telecommunications problems sketched above
37
Cho, Yuh-Jen, and 卓裕仁. "A New Metaheuristic Approach for HVRP and PVRP." Thesis, 2001. http://ndltd.ncl.edu.tw/handle/67115137462732599561.
Full textAbstract:
博士國立交通大學
運輸工程與管理系
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.
38
Kinney, Gary W. Barnes J. Wesley. "A group theoretic approach to metaheuristic local search for partitioning problems." 2005. http://repositories.lib.utexas.edu/bitstream/handle/2152/1594/kinneyg73946.pdf.
Full text
39
Kinney, Gary W. "A group theoretic approach to metaheuristic local search for partitioning problems." Thesis, 2005. http://hdl.handle.net/2152/1594.
Full text
40
翁毓夆. "Hybrid Metaheuristic Approach for Integrated Multi-Plant Order Allocation and Ship Routing Problem." Thesis, 2013. http://ndltd.ncl.edu.tw/handle/38812113428448945683.
Full text
41
Güttinger, Dennis. "A New Metaheuristic Approach for Stabilizing the Solution Quality of Simulated Annealing and Applications." Phd thesis, 2013. https://tuprints.ulb.tu-darmstadt.de/3288/1/doctoralThesis.pdf.
Full textAbstract:
In this work we describe a new metaheuristical approach for global optimization that is based on the simulated annealing algorithm. Within this new approach a preoptimization step with a Greedy strategy is performed to compute an initial solution for the intrinsic iterations of the simulated annealing algorithm. Furthermore, the probability distribution which is used for generation of a new solution candidate is adjusted in a way that candidates in the optimization direction are chosen with a higher probability. We will empirically show the superiority of our metaheuristic for three different combinatorical optimization problems of practical relevance in comparison to other standard techniques that are usually applied to compute solutions of the corresponding problems. Moreover, the dependence of the solution quality on the choice of specific input parameters for simulated annealing can be reduced significantly with our metaheuristic. Finally, we will consider a fourth complex problem class, where our metaheuristic is unable to compute significantly better solutions in comparison to simple local optimization strategies. Consequently, for this problem class local optimization is sufficient for practical applications to determine an adequately good solution near the global optimum.
42
Busetti, Franco Raoul. "Metaheuristic approaches to realistic portfolio optimisation." Diss., 2000. http://hdl.handle.net/10500/16224.
Full textAbstract:
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)
43
Ganguly, Abhijeet. "Economic Design of Control Charts Using Metaheuristic Approaches." Thesis, 2016. http://ethesis.nitrkl.ac.in/8021/2/2010_511me102_Abhijeet_ganguly_economic.pdf.
Full textAbstract:
Statistical Process Control (SPC) is a collection of problem solving tools useful in achieving process stability and improving capability through the reduction of variability using statistical methods. It can help industries in reduction of cost, improvement of quality and pursuit of continuous improvement. Among all the SPC tools, the control chart is most widely used in practice. Out of all the control charts, chart is the simplest to use and hence most popularly used for monitoring and controlling processes in an industry.A process may go out-of-control due to shift in process mean and/or process variance. To detect both types of shifts, R chart is often used along with chart.
The design of chart refers to selection of three design variables such as sample size (n), sampling interval (h) and width of control limits (k). On the other hand, the joint design of and R charts involves four design variables i.e., sample size (n), sampling interval (h), and widths of control limits for both charts (i.e., k1 and k2). There are four types of control chart designs, namely (i) heuristic design, (ii) statistical design, (iii) economic design, and (iv) economic statistical design. In heuristic design, the values of design variables are selected using some thumb rules. In statistical design, the design variables are selected in such a way that the two statistical errors, namely Type-I error ( ), and Type-II error ( ) are kept at minimum values. In economic design, a cost function is constructed involving various costs like the cost of sampling and testing, the cost of false alarm, the cost to detect and eliminate the assignable cause(s), and the cost of producing non-conforming products when the process is operating out-of-control. The design parameters of the control chart are then selected so that this cost function is minimized. The design based on combined features of statistical design and economic design is termed as economic statistical design where the cost function is minimized while satisfying the statistical constraints. The effectiveness of economic design or economic statistical design depends on the accuracy of minimization of cost function. So, use of effectively designed control charts is highly essential for ensuring quality control at minimum cost.
Most of the researchers have used either approximate or traditional optimization techniques for minimizing the cost function. With time, more and more efficient optimization methods have been utilized for this purpose. There are a number of metaheuristic algorithms reported in literature for optimization in various types of design problems. Out of them one each from two different groups are selected for the present work i.e., simulated annealing (SA) and teaching-learning based optimization (TLBO). SA is a point to point based metaheuristic technique, whereas TLBO is population based technique. SA is one of the oldest metaheuristic algorithms and proved to be the most robust one, whereas TLBO is one of the most recent and promising techniques. The present work requires optimization techniques that can solve non-linear, non-differentiable, multi-variable, unconstrained as well as constrained type of objective function. Both the above techniques are capable of optimizing this type of objective function. However, from literature review it is observed that neither of these two metaheuristic approaches has been applied in economic or economic statistical design of any type of control chart. In this work, both these metaheuristic techniques (i.e., SA and TLBO) have been applied for minimization of cost function for economic as well as economic statistical design point of view for individual chart, and by taking and R charts jointly in case of continuous as well as discontinuous process. Thus, a total of the following eight distinct design cases have been considered for their optimization.
1. Economic design of chart for continuous process
2. Economic design of chart for discontinuous process
3. Economic statistical design of chart for continuous process
4. Economic statistical design of chart for discontinuous process
5. Joint economic design of and R charts for continuous process
6. Joint economic design of and R charts for discontinuous process
7. Joint economic statistical design of and R charts for continuous process
8. Joint economic statistical design of and R charts for discontinuous process
All the above designs are illustrated through numerical examples taken from literature using two metaheuristics i.e., SA and TLBO separately. These two independent techniques are used to validate their results with each other. Their results are found to be superior to that reported earlier in the literature. Thus, eight types of methodologies based on SA or TLBO approach are recommended in this thesis for designing control charts from economic point of view.
Sensitivity analysis has been carried out using fractional factorial design of experiments and analysis of variance for each of the eight design cases, to examine the effects of all the cost and process parameters on all the output responses such as sample size, sampling interval, width of control limits and expected loss costper unit time. The process parameters which significantly affect the output responses are identified in each of the eight design cases. These results are expected to be helpful for quality control personnel in identifying the significant factors and thereby taking utmost care in choosing their values while designing the control charts on economic basis.
44
Chien, Wei-Che, and 簡暐哲. "Metaheuristics for WRSN Charger Deployment by using Layoff Approach." Thesis, 2016. http://ndltd.ncl.edu.tw/handle/76549184442217574751.
Full textAbstract:
碩士國立宜蘭大學
資訊工程學系碩士班
105
Power consumption is an important issue in the wireless sensor networks (WSNs). In order to ensure all of sensors are able to work normally, many scholars have put a lot of effort into extending network lifetime of WSNs. However, lifetime of sensors depend on the battery capacity so that each sensor will still run out of energy someday. Recently, Wireless Rechargeable Sensor Network (WRSN) has been proposed for this pending issues since wireless charging technology has gradually matured. There are many researches focus on the outdoor scenario of WRSN, but is less for in indoor scenario. Actually, this technique is a great need for the indoor scenario, ex: detection of the product yield and disaster prevention. If we can guarantee that all of sensors can continue to work uninterrupted, humans life will be more convenient because sensors can help us to do more. These examples illustrate WRSN deployment for indoor environment is necessary. In this thesis, we focus on the charger deployment problem. The good deployment method should not only reduce cost of deployment but also guarantees that all of sensors will not run out of energy. Most of deployment methods for indoor scenario also adopted greedy-based algorithm so that solution will fall into local optimal in the process of solution searching. So we try to use metaheuristic algorithm to optimize the quality of solution, however it still has some defects. The process of metaheuristic algorithm needs to run many times iteration. It will waste a large of computation cost even falls into local optimal which means that some sensors may not be covered. To solve these problems, we proposed Layoff algorithm (LA) to enhance used metaheuristic algorithms. The concept of proposed method is that removing the unnecessary candidate charger to make solution can converge quicker and the solution quality cannot be decreased. The simulation results show that this method is able to guarantee that all of sensors can be covered by chargers as well as a lot of computation time will be improved. Finally, we will analyze the respective applicable environment of both metaheuristic algorithms.
45
Dahal, Keshav P., and N. Chakpitak. "Generator maintenance scheduling in power systems using metaheuristic-based hybrid approaches." 2007. http://hdl.handle.net/10454/4070.
Full textAbstract:
NoThe effective maintenance scheduling of power system generators is very important for the economical and reliable operation of a power system. This represents a tough scheduling problem which continues to present a challenge for efficient optimization solution techniques. This paper presents the application of metaheuristic approaches, such as a genetic algorithm (GA), simulated annealing (SA) and their hybrid for generator maintenance scheduling (GMS) in power systems using an integer representation. This paper mainly focuses on the application of GA/SA and GA/SA/heuristic hybrid approaches. GA/SA hybrid uses the probabilistic acceptance criterion of SA within the GA framework. GA/SA/heuristic hybrid combines heuristic approaches within the GA/SA hybrid to seed the initial population. A case study is formulated in this paper as an integer programming problem using a reliability-based objective function and typical problem constraints. The implementation and performance of the metaheuristic approaches and their hybrid for the test case study are discussed. The results obtained are promising and show that the hybrid approaches are less sensitive to the variations of technique parameters and offer an effective alternative for solving the generator maintenance scheduling problem.
46
Shahnawaz, Sanjana. "Optimization of patients appointments in chemotherapy treatment unit: heuristic and metaheuristic approaches." 2012. http://hdl.handle.net/1993/8876.
Full textAbstract:
This research aims to improve the performance of the service of a Chemotherapy Treatment Unit by reducing the waiting time of patients within the unit. In order to fulfill the objective, initially, the chemotherapy treatment unit is deduced as an identical parallel machines scheduling problem with unequal release time and single resource. A mathematical model is developed to generate the optimum schedule. Afterwards, a Tabu search (TS) algorithm is developed. The performance of the TS algorithm is evaluated by comparing results with the mathematical model and the best results of benchmark problems reported in the literature. Later on, an additional resource is considered which converted the problem into a dual resources scheduling problem. Three approaches are proposed to solve this problem; namely, heuristics, a Tabu search algorithm with heuristic (TSHu), and Tabu search algorithm for dual resources (TSD).
47
Claro, João Alberto Vieira de Campos Pereira. "Multiobjective metaheuristic approaches for mean-risk combinatorial optimisation with applications to capacity expansion." Doctoral thesis, 2007. http://hdl.handle.net/10216/11214.
Full text
48
Claro, João Alberto Vieira de Campos Pereira. "Multiobjective metaheuristic approaches for mean-risk combinatorial optimisation with applications to capacity expansion." Tese, 2007. http://hdl.handle.net/10216/11214.
Full text
49
Musacchia, Francesco. "Biclustering of gene expression data: hybridization of GRASP with other heuristic/metaheuristic approaches." Tesi di dottorato, 2013. http://www.fedoa.unina.it/9309/1/tesi_PhD_Musacchia.pdf.
Full textAbstract:
Researchers who work on large amount of data have to face vari- ous problems such as data mining and information retrieval: this is the case of gene expression. The general scope of these experiments is to find co-regulated genes, in order to understand the biologic pathways underlying a particular phenomenon. A clustering con- cept can be used to find out if co-regulated genes can be active only over some conditions. Recently, some biclustering approaches have been used to find groups of co-regulated genes into a data matrix. Among them, several heuristic algorithms have been developed to find good solutions in a reasonable running time.
In the current Ph.D. thesis, a GRASP-like (Greedy Randomized Adaptive Search Procedure) approach was developed to perform biclustering of microarray data. A new local search has been devel- oped composed of three simple steps based on a concept inspired by the social aggregation of groups. It is very fast and allows to ob- tain results similar to those achieved using some of the best known biclustering algorithms. Other new algorithms have also been pro- posed using novel combinations of iterated local search and MST clustering.
The different biclustering algorithms were then tested on four different datasets of gene expression data. Results are encouraging because they are similar or even better to those obtained with the
former GRASP-like algorithm. Possible future improvements could be obtained by implementing further combinations of heuristics and testing them onto different datasets in order to evaluate their general application to different kinds of data.
50
Martin, Kiel. "An advanced tabu search approach to the intratheater airlift operations problem with split loading." Thesis, 2012. http://hdl.handle.net/2152/ETD-UT-2012-08-5974.
Full textAbstract:
This dissertation details an algorithm to solve the Intratheater Airlift Operations Problem (IAOP) using advanced tabu search. A solution to the IAOP determines the routes and assignment of customer requests to a fleet of aircraft over a given time horizon. This problem and other variants comprise an ongoing challenge for United States Air Force (USAF) planners who manage detailed logistics throughout many theaters of operations. Attributes of the IAOP include cargo time windows, multiple cargo types, multiple vehicle cargo bay configurations, vehicle capacity, route duration limits, and port capacities. The IAOP multi-criteria objective embraces several components with the primary goal of satisfying as much of the demand as possible while minimizing cost.
The algorithm is extended to allow split load deliveries of customer requests, allowing a shipment to be split into two or more sub-loads which are delivered separately to the customer. The split load relaxation, while significantly increasing the complexity of the problem, allows for possible improvement in the solution. The necessary changes to the model and algorithm are detailed, providing a foundation to extend any local search algorithm solving a vehicle routing problem to allow split loading. Results allowing split loading are presented and compared with results without split loading.
The algorithm is also extended to include a rolling time horizon. Starting from a solution found at a previous time step, the algorithm is limited on how the solution can be modified. This reflects the reality of operations in which near-term plans are locked as they approach and enter execution while longer-term plans are continually updated as new information arrives.text