Spelling suggestions: "subject:"multiobjective optimization "" "subject:"multiobjectives optimization ""
91 |
Solution of Constrained Clustering Problems through Homotopy TrackingEasterling, David R. 15 January 2015 (has links)
Modern machine learning methods are dependent on active optimization research to improve the set of methods available for the efficient and effective extraction of information from large datasets. This, in turn, requires an intense and rigorous study of optimization methods and their possible applications to crucial machine learning applications in order to advance the potential benefits of the field. This thesis provides a study of several modern optimization techniques and supplies a mathematical inquiry into the effectiveness of homotopy methods to attack a fundamental machine learning problem, effective clustering under constraints.
The first part of this thesis provides an empirical survey of several popular optimization algorithms, along with one approach that is cutting-edge. These algorithms are tested against deeply challenging real-world problems with vast numbers of local minima, and compares and contrasts the benefits of each when confronted with problems of different natures.
The second part of this thesis proposes a new homotopy map for use with constrained clustering problems. This thesis explores the connections between the map and the problem, providing several theorems to justify the use of the map and making use of modern homotopy tracking software to compare an optimization that employs the map with several modern approaches to solving the same problem. / Ph. D.
|
92 |
Optimisation du développement de nouveaux produits dans l'industrie pharmaceutique par algorithme génétique multicritère / Multiobjective optimization of New Product Development in the pharmaceutical industryPerez Escobedo, José Luis 03 June 2010 (has links)
Le développement de nouveaux produits constitue une priorité stratégique de l'industrie pharmaceutique, en raison de la présence d'incertitudes, de la lourdeur des investissements mis en jeu, de l'interdépendance entre projets, de la disponibilité limitée des ressources, du nombre très élevé de décisions impliquées dû à la longueur des processus (de l'ordre d'une dizaine d'années) et de la nature combinatoire du problème. Formellement, le problème se pose ainsi : sélectionner des projets de Ret D parmi des projets candidats pour satisfaire plusieurs critères (rentabilité économique, temps de mise sur le marché) tout en considérant leur nature incertaine. Plus précisément, les points clés récurrents sont relatifs à la détermination des projets à développer une fois que les molécules cibles sont identifiées, leur ordre de traitement et le niveau de ressources à affecter. Dans ce contexte, une approche basée sur le couplage entre un simulateur à événements discrets stochastique (approche Monte Carlo) pour représenter la dynamique du système et un algorithme d'optimisation multicritère (de type NSGA II) pour choisir les produits est proposée. Un modèle par objets développé précédemment pour la conception et l'ordonnancement d'ateliers discontinus, de réutilisation aisée tant par les aspects de structure que de logique de fonctionnement, a été étendu pour intégrer le cas de la gestion de nouveaux produits. Deux cas d'étude illustrent et valident l'approche. Les résultats de simulation ont mis en évidence l'intérêt de trois critères d'évaluation de performance pour l'aide à la décision : le bénéfice actualisé d'une séquence, le risque associé et le temps de mise sur le marché. Ils ont été utilisés dans la formulation multiobjectif du problème d'optimisation. Dans ce contexte, des algorithmes génétiques sont particulièrement intéressants en raison de leur capacité à conduire directement au front de Pareto et à traiter l'aspect combinatoire. La variante NSGA II a été adaptée au problème pour prendre en compte à la fois le nombre et l'ordre de lancement des produits dans une séquence. A partir d'une analyse bicritère réalisée pour un cas d'étude représentatif sur différentes paires de critères pour l'optimisation bi- et tri-critère, la stratégie d'optimisation s'avère efficace et particulièrement élitiste pour détecter les séquences à considérer par le décideur. Seules quelques séquences sont détectées. Parmi elles, les portefeuilles à nombre élevé de produits provoquent des attentes et des retards au lancement ; ils sont éliminés par la stratégie d'optimistaion bicritère. Les petits portefeuilles qui réduisent les files d'attente et le temps de lancement sont ainsi préférés. Le temps se révèle un critère important à optimiser simultanément, mettant en évidence tout l'intérêt d'une optimisation tricritère. Enfin, l'ordre de lancement des produits est une variable majeure comme pour les problèmes d'ordonnancement d'atelier. / New Product Development (NPD) constitutes a challenging problem in the pharmaceutical industry, due to the characteristics of the development pipeline, namely, the presence of uncertainty, the high level of the involved capital costs, the interdependency between projects, the limited availability of resources, the overwhelming number of decisions due to the length of the time horizon (about 10 years) and the combinatorial nature of a portfolio. Formally, the NPD problem can be stated as follows: select a set of R and D projects from a pool of candidate projects in order to satisfy several criteria (economic profitability, time to market) while copying with the uncertain nature of the projects. More precisely, the recurrent key issues are to determine the projects to develop once target molecules have been identified, their order and the level of resources to assign. In this context, the proposed approach combines discrete event stochastic simulation (Monte Carlo approach) with multiobjective genetic algorithms (NSGA II type, Non-Sorted Genetic Algorithm II) to optimize the highly combinatorial portfolio management problem. An object-oriented model previously developed for batch plant scheduling and design is then extended to embed the case of new product management, which is particularly adequate for reuse of both structure and logic. Two case studies illustrate and validate the approach. From this simulation study, three performance evaluation criteria must be considered for decision making: the Net Present Value (NPV) of a sequence, its associated risk defined as the number of positive occurrences of NPV among the samples and the time to market. Theyv have been used in the multiobjective optimization formulation of the problem. In that context, Genetic Algorithms (GAs) are particularly attractive for treating this kind of problem, due to their ability to directly lead to the so-called Pareto front and to account for the combinatorial aspect. NSGA II has been adapted to the treated case for taking into account both the number of products in a sequence and the drug release order. From an analysis performed for a representative case study on the different pairs of criteria both for the bi- and tricriteria optimization, the optimization strategy turns out to be efficient and particularly elitist to detect the sequences which can be considered by the decision makers. Only a few sequences are detected. Among theses sequences, large portfolios cause resource queues and delays time to launch and are eliminated by the bicriteria optimization strategy. Small portfolio reduces queuing and time to launch appear as good candidates. The optimization strategy is interesting to detect the sequence candidates. Time is an important criterion to consider simultaneously with NPV and risk criteria. The order in which drugs are released in the pipeline is of great importance as with scheduling problems.
|
93 |
Optimisation multiobjectif de réseaux de transport de gaz naturel / Multiobjective optimization of natural gas transportation networksHernandez-Rodriguez, Guillermo 19 September 2011 (has links)
L'optimisation de l'exploitation d'un réseau de transport de gaz naturel (RTGN) est typiquement un problème d'optimisation multiobjectif, faisant intervenir notamment la minimisation de la consommation énergétique dans les stations de compression, la maximisation du rendement, etc. Cependant, très peu de travaux concernant l'optimisation multiobjectif des réseaux de gazoducs sont présentés dans la littérature. Ainsi, ce travail vise à fournir un cadre général de formulation et de résolution de problèmes d'optimisation multiobjectif liés aux RTGN. Dans la première partie de l'étude, le modèle du RTGN est présenté. Ensuite, diverses techniques d'optimisation multiobjectif appartenant aux deux grandes classes de méthodes par scalarisation, d'une part, et de procédures évolutionnaires, d'autre part, communément utilisées dans de nombreux domaines de l'ingénierie, sont détaillées. Sur la base d'une étude comparative menée sur deux exemples mathématiques et cinq problèmes de génie des procédés (incluant en particulier un RTGN), un algorithme génétique basé sur une variante de NSGA-II, qui surpasse les méthodes de scalarisation, de somme pondérée et d'ε-Contrainte, a été retenu pour résoudre un problème d'optimisation tricritère d'un RTGN. Tout d'abord un problème monocritère relatif à la minimisation de la consommation de fuel dans les stations de compression est résolu. Ensuite un problème bicritère, où la consommation de fuel doit être minimisée et la livraison de gaz aux points terminaux du réseau maximisée, est présenté ; l'ensemble des solutions non dominées est répresenté sur un front de Pareto. Enfin l'impact d'injection d'hydrogène dans le RTGN est analysé en introduisant un troisième critère : le pourcentage d'hydrogène injecté dans le réseau que l'on doit maximiser. Dans les deux cas multiobjectifs, des méthodes génériques d'aide à la décision multicritère sont mises en oeuvre pour déterminer les meilleures solutions parmi toutes celles déployées sur les fronts de Pareto. / The optimization of a natural gas transportation network (NGTN) is typically a multiobjective optimization problem, involving for instance energy consumption minimization at the compressor stations and gas delivery maximization. However, very few works concerning multiobjective optimization of gas pipelines networks are reported in the literature. Thereby, this work aims at providing a general framework of formulation and resolution of multiobjective optimization problems related to NGTN. In the first part of the study, the NGTN model is described. Then, various multiobjective optimization techniques belonging to two main classes, scalarization and evolutionary, commonly used for engineering purposes, are presented. From a comparative study performed on two mathematical examples and on five process engineering problems (including a NGTN), a variant of the multiobjective genetic algorithm NSGA-II outmatches the classical scalararization methods, Weighted-sum and ε-Constraint. So NSGA-II has been selected for performing the triobjective optimization of a NGTN. First, the monobjective problem related to the minimization of the fuel consumption in the compression stations is solved. Then a biojective problem, where the fuel consumption has to be minimized, and the gas mass flow delivery at end-points of the network maximized, is presented. The non dominated solutions are displayed in the form of a Pareto front. Finally, the study of the impact of hydrogen injection in the NGTN is carried out by introducing a third criterion, i.e., the percentage of injected hydrogen to be maximized. In the two multiobjective cases, generic Multiple Choice Decision Making tools are implemented to identify the best solution among the ones displayed of the Pareto fronts.
|
94 |
Optimisation multicritère de réseaux d'eau / Multiobjective optimization of water networksBoix, Marianne 28 September 2011 (has links)
Cette étude concerne l’optimisation multiobjectif de réseaux d’eau industriels via des techniques de programmation mathématique. Dans ce travail, un large éventail de cas est traité afin de proposer des solutions aux problèmes de réseaux les plus variés. Ainsi, les réseaux d’eau monopolluants sont abordés grâce à une programmation mathématique linéaire (MILP). Cette méthode est ensuite utilisée dans le cadre d’une prise en compte simultanée des réseaux d’eau et de chaleur. Lorsque le réseau fait intervenir plusieurs polluants, le problème doit être programmé de façon non linéaire (MINLP). L’optimisation multicritère de chaque réseau est basée sur la stratégie epsilon-contrainte développée à partir d’une méthode lexicographique. L’optimisation multiobjectif suivie d’une réflexion d’aide à la décision a permis d’améliorer les résultats antérieurs proposés dans la littérature de 2 à 10% en termes de consommation de coût et de 7 à 15% en ce qui concerne la dépense énergétique. Cette méthodologie est étendue à l’optimisation de parcs éco-industriels et permet ainsi d’opter pour une solution écologique et économique parmi un ensemble de configurations proposées. / This study presents a multiobjective optimization of industrial water networks through mathematical programming procedures. A large range of various examples are processed to propose several feasible solutions. An industrial network is composed of fixed numbers of process units and regenerations and contaminants. These units are characterized by a priori defined values: maximal inlet and outlet contaminant concentrations. The aim is both to determine which water flows circulate between units and to allocate them while several objectives are optimized. Fresh water flow-rate (F1), regenerated water flow-rate (F2),interconnexions number (F3), energy consumption (F4) and the number of heat exchangers (F5) are all minimized. This multiobjective optimization is based upon the epsilon-constraint strategy, which is developed from a lexicographic method that leads to Pareto fronts. Monocontaminant networks are addressed with a mixed linear mathematical programming (Mixed Integer Linear Programming, MILP) model, using an original formulation based on partial water flow-rates. The obtained results we obtained are in good agreement with the literature data and lead to the validation of the method. The set of potential network solutions is provided in the form of a Pareto front. An innovative strategy based on the GEC (global equivalent cost) leads to the choice of one network among these solutions and turns out to be more efficient for choosing a good network according to a practical point of view. If the industrial network deals with several contaminants, the formulation changes from MILP into MINLP (Mixed Integer Non Linear Programming). Thanks to the same strategy used for the monocontaminant problem, the networks obtained are topologically simpler than literature data and have the advantage of not involving very low flow-rates. A MILP model is performed in order to optimize heat and water networks. Among several examples, a real case of a paper mill plant is studied. This work leads to a significant improvement of previous solutions between 2 to 10% and 7 to 15% for cost and energy consumptions respectively. The methodology is then extended to the optimization of eco-industrial parks. Several configurations are studied regarding the place of regeneration units in the symbiosis. The best network is obtained when the regeneration is owned by each industry of the park and allows again of about 13% for each company. Finally, when heat is combined to water in the network of the ecopark, a gain of 11% is obtained compared to the case where the companies are considered individually.
|
95 |
Allocation optimale multicontraintes des workflows aux ressources d’un environnement Cloud Computing / Multi-constrained optimal allocation of workflows to Cloud Computing resourcesYassa, Sonia 10 July 2014 (has links)
Le Cloud Computing est de plus en plus reconnu comme une nouvelle façon d'utiliser, à la demande, les services de calcul, de stockage et de réseau d'une manière transparente et efficace. Dans cette thèse, nous abordons le problème d'ordonnancement de workflows sur les infrastructures distribuées hétérogènes du Cloud Computing. Les approches d'ordonnancement de workflows existantes dans le Cloud se concentrent principalement sur l'optimisation biobjectif du makespan et du coût. Dans cette thèse, nous proposons des algorithmes d'ordonnancement de workflows basés sur des métaheuristiques. Nos algorithmes sont capables de gérer plus de deux métriques de QoS (Quality of Service), notamment, le makespan, le coût, la fiabilité, la disponibilité et l'énergie dans le cas de ressources physiques. En outre, ils traitent plusieurs contraintes selon les exigences spécifiées dans le SLA (Service Level Agreement). Nos algorithmes ont été évalués par simulation en utilisant (1) comme applications: des workflows synthétiques et des workflows scientifiques issues du monde réel ayant des structures différentes; (2) et comme ressources Cloud: les caractéristiques des services de Amazon EC2. Les résultats obtenus montrent l'efficacité de nos algorithmes pour le traitement de plusieurs QoS. Nos algorithmes génèrent une ou plusieurs solutions dont certaines surpassent la solution de l'heuristique HEFT sur toutes les QoS considérées, y compris le makespan pour lequel HEFT est censé donner de bons résultats. / Cloud Computing is increasingly recognized as a new way to use on-demand, computing, storage and network services in a transparent and efficient way. In this thesis, we address the problem of workflows scheduling on distributed heterogeneous infrastructure of Cloud Computing. The existing workflows scheduling approaches mainly focus on the bi-objective optimization of the makespan and the cost. In this thesis, we propose news workflows scheduling algorithms based on metaheuristics. Our algorithms are able to handle more than two QoS (Quality of Service) metrics, namely, makespan, cost, reliability, availability and energy in the case of physical resources. In addition, they address several constraints according to the specified requirements in the SLA (Service Level Agreement). Our algorithms have been evaluated by simulations. We used (1) synthetic workflows and real world scientific workflows having different structures, for our applications; and (2) the features of Amazon EC2 services for our Cloud. The obtained results show the effectiveness of our algorithms when dealing multiple QoS metrics. Our algorithms produce one or more solutions which some of them outperform the solution produced by HEFT heuristic over all the QoS considered, including the makespan for which HEFT is supposed to give good results.
|
96 |
Outils d'aide à la décision pour la conception de procédés agroalimentaires au Sud : application au procédé combiné de séchage, cuisson et fumage de produits carnés / Multicriteria decision analysis tool for food process design : application to the hot-smoking processRaffray, Guilhem 17 October 2014 (has links)
La conception de procédé agroalimentaire est une activité complexe, caractérisée par la grande diversité des produits et des procédés étudiés, ainsi que par la disparité des contextes de production (artisanale ou industrielle). La conception de systèmes de transformation alimentaire adaptés est animée par d'importants enjeux humains, sanitaires, économiques, environnementaux et même culturels. Dans le cas des Pays du Sud, l'explosion démographique et l'urbanisation croissante impliquent de développer un système de production industriel capable de valoriser des produits issus de savoir-faire traditionnels, tout en répondant à des contraintes de coût et de productivité.Pour prévenir toute perte de temps causée par des analyses de type « essai-erreur », et afin d'éviter des coûts de développement superflus, il existe des outils spécifiques à l'analyse décisionnelle multicritères (MCDA) pouvant être déployé dès les phases préliminaires de la conception. En particulier, il est possible d'analyser le potentiel et les limites technologiques d'un concept défini dans un contexte donné, par l'analyse de l'ensemble de solutions les plus performantes, dites Pareto-optimales. Ces solutions se distinguent par les valeurs de leurs variables de conception, qui sont autant de degrés de liberté pour le dimensionnement du concept (géométrie, matériaux, conditions opératoires).Notre cas d'étude concerne l'évaluation d'un concept de fumage à chaud à plaques radiantes, pour la production de poisson fumé, traditionnellement consommé en Afrique Centrale et de l'Ouest. En effet, avant de prétendre à la diffusion de cette technologie déjà brevetée, il faut s'assurer que le procédé puisse satisfaire des objectifs de production et de performances énergétiques, tout en maintenant une qualité du produit satisfaisante. Ainsi, un outil d'optimisation multiobjectif spécifique a été développé en se basant sur la modélisation du comportement du procédé. Une première étude expérimentale a permis de construire un modèle de séchage du poisson dans des conditions d'air variables (température, vitesse et humidité), qui représente à la fois les flux d'évaporation et les flux liés aux écoulements gravitaires de graisses et d'eau. Dans un second temps, un outil de simulation existant a été amélioré afin de représenter des phénomènes ayant un impact significatif sur les performances du procédé, tels que l'aéraulique des fumées, le recyclage de l'air et la régulation thermique. Ainsi, un modèle d'observation a été établi. Il permet de prédire le comportement de différentes solutions possibles, définies par huit variables de conception, et d'évaluer leurs performances sur la base de six variables d'observation.Dans un dernier volet, la formalisation des préférences et de la connaissance experte du procédé permet d'interpréter les performances en termes de désirabilités (satisfaction), qui sont agrégées en un indice de satisfaction global (fonction objectif) par un principe de précaution. Un algorithme génétique permet alors de trouver une solution optimale qui maximise cette fonction objectif, en explorant l'espace des solutions possibles de manière combinatoire. Cette démarche de conception a été fructueuse car elle a permis de proposer un dimensionnement permettant d'obtenir des performances très satisfaisantes. Il a aussi été possible de proposer des améliorations ciblées pour redéfinir le concept actuel du fumoir à plaques. Par ailleurs, il est à noter que le modèle de comportement peut facilement être réadapté pour d'autre type de produits. Dans la perspective d'étendre l'utilisation de cette démarche à d'autres cas d'étude, un effort devra être mené pour la collecte de données fonctionnelles issues de l'expertise. / Food process design is a complex activity, given the wide diversity of existing product and processes, and the plurality of production contexts. Designer must meet the requirements derived from the critical stakes from human, sanitarian, economic, environmental and cultural point of views. In southern countries, the rapid growth of population drives the need of more industrial processes able to valorize traditional products.The savings of development time and extra-expenses are mainly determined by the quality of design choices from the early stage of the designing process, called embodiment design. Multiple criteria decision analysis (MCDA) techniques are used in this purpose, which enable to evaluate and criticize any technological concept. In a specific context, it is possible to generate the Pareto-set of a concept, which is composed of the most efficient possible alternatives. Indeed, every design alternative is defined by some design (or decision) variables which are the degree of freedom for the dimensioning of the system considered. Our case study focuses on a technological innovation to perform hot-smoking using radiant plates (for sanitarian purpose). It is aimed to be developed for the production of traditional hot-smoked catfish widely consumed in West and Central Africa. This is a multicriteria design problem since many objectives have to be satisfied, and concern the product quality, production and energetic performances.In a first work, the mass reduction of catfish dried in hot air conditions was modeled from empirical measurements. In particular, this model takes into account the influence of the drying air conditions (Temperature, Velocity and Relative Humidity) on the calculation of the mass fluxes of evaporation and drips. After that, a global simulation model of the radiant plate hot-smoking process was developed from a previous work. Some key phenomena were described (pressure losses, air recycling, thermal regulation) as they could strongly impact the process performances. The resulting observation model allows predicting the performances of any design alternative defined by a set of 8 design variables.In a final work, expert knowledge and preference were mathematically introduced in a multiobjective optimization tool, meaning some desirability functions. Therefore, every performance variable is converted into desirability indices (traducing the level of satisfaction) and then aggregated into a single global desirability index (thus defining a global objective function). The optimal design of the concept is found using a genetic algorithm.This multiobjective optimization method enabled to find very satisfactory design solution for the radiant plate hot smoking process. More to the point, the analysis of a wide range of Pareto-optimal solutions enabled to better understand what were the strengths and weaknesses, so it was possible to suggest some targeted improvement to the current radiant plate smoking technology. Also, it is noticeable that the current simulation model can be easily adapted to other products. For the purpose of a generalization of the use of such multiobjective methods for the design of food processes, it has been pointed out that efforts should be made to gather expert criteria other relevant functional data.
|
97 |
Contribution à l’optimisation multi-objectifs sous contraintes : applications à la mécanique des structures / Contribution to multi-objective optimization under constraints : applications to structural mechanicsTchvagha Zeine, Ahmed 04 July 2018 (has links)
L’objectif de cette thèse est le développement de méthodes d’optimisation multi-objectif pour la résolution de problèmes de conception des structures mécaniques. En effet, la plupart des problèmes réels dans le domaine de la mécanique des structures ont plusieurs objectifs qui sont souvent antagonistes. Il s’agit, par exemple, de concevoir des structures en optimisant leurs poids, leurs tailles, et leurs coûts de production. Le but des méthodes d’optimisation multi-objectif est la recherche des solutions de compromis entre les objectifs étant donné l’impossibilité de satisfaire tout simultanément. Les métaheuristiques sont des méthodes d’optimisation capables de résoudre les problèmes d’optimisation multi-objective en un temps de calcul raisonnable sans garantie de l’optimalité de (s) solution (s). Au cours des dernières années, ces algorithmes ont été appliqués avec succès pour résoudre le problème des mécaniques des structures. Dans cette thèse deux métaheuristiques ont été développées pour la résolution des problèmes d’optimisation multi-objectif en général et de conception de structures mécaniques en particulier. Le premier algorithme baptisé MOBSA utilise les opérateurs de croisement et de mutation de l’algorithme BSA. Le deuxième algorithme nommé NNIA+X est une hybridation d’un algorithme immunitaire et de trois croisements inspirés de l’opérateur de croisement original de l’algorithme BSA. Pour évaluer l’efficacité et l’efficience de ces deux algorithmes, des tests sur quelques problèmes dans littérature ont été réalisés avec une comparaison avec des algorithmes bien connus dans le domaine de l’optimisation multi-objectif. Les résultats de comparaison en utilisant des métriques très utilisées dans la littérature ont démontré que ces deux algorithmes peuvent concurrencer leurs prédécesseurs. / The objective of this thesis is the development of multi-objective optimization methods for solving mechanical design problems. Indeed, most of the real problems in the field of mechanical structures have several objectives that are often antagonistic. For example, it is about designing structures by optimizing their weight, their size, and their production costs. The goal of multi-objective optimization methods is the search for compromise solutions between objectives given the impossibility to satisfy all simultaneously. Metaheuristics are optimization methods capable of solving multi-objective optimization problems in a reasonable calculation time without guaranteeing the optimality of the solution (s). In recent years, these algorithms have been successfully applied to solve the problem of structural mechanics. In this thesis, two metaheuristics have been developed for the resolution of multi-objective optimization problems in general and of mechanical structures design in particular. The first algorithm called MOBSA used the crossover and mutation operators of the BSA algorithm. The second one named NNIA+X is a hybridization of an immune algorithm and three crossover inspired by the original crossover operator of the BSA algorithm. To evaluate the effectiveness and efficiency of these two algorithms, tests on some problems in literature have been made with a comparison with algorithms well known in the field of multi-objective optimization. The comparison results using metrics widely used in the literature have shown that our two algorithms can compete with their predecessors.
|
98 |
Modélisation et optimisation d’un plan de transport ferroviaire en zone dense du point de vue des voyageurs / Passenger-oriented modelling and optimization of the railway transportation plan in a mass transit systemBrethomé, Lucile Isabelle 20 November 2018 (has links)
La conception d’un plan de transport d’un service ferroviaire est un processus qui se réalise entre deux ans et six mois avant la mise en service de celui-ci. Les principales phases de la conception sont la définition des dessertes, le calcul de la grille horaire et enfin l’organisation des roulements de rames et des conducteurs. La manière dont le plan de transport est conçu peut avoir de nombreuses conséquences sur la qualité de service : fréquence en gare insuffisante qui peut entrainer une perte de clients, robustesse de la grille horaire face à de petits incidents... En zone dense, tous ces éléments sont à prendre en compte, dès la conception de la grille horaire.Aujourd’hui, SNCF Transilien conçoit ses plans de transport en prenant d’abord en compte l’optimisation des ressources de production (sillons, rames et agents de conduite). Toutefois, l’augmentation des ressources mises en œuvre n’améliore plus l’adéquation du plan de transport à la demande des voyageurs. Ce mode de conception ne permet donc plus de faire face à l’augmentation de la demande de mobilité. C’est pourquoi il faut repenser la conception du plan de transport en intégrant immédiatement la dimension voyageuse.Nos travaux se concentrent sur les problématiques de conception de dessertes et de grille horaire, en prenant en compte le point de vue des voyageurs. Nous présentons un modèle multiobjectif de conception de dessertes, puis nous présentons un modèle de conception de grille horaire intégrant le choix d’itinéraire des voyageurs. Ensuite, nous présentons une méthode cherchant à intégrer ces deux modèles. Enfin, nous présentons une évaluation de nos résultats grâce à des indicateurs de fiabilité / The design of a railway transportation plan is a process achieved between two years and six months before it is put into service. The main phases in the design of a transportation plan are the line planning, the timetabling, the rolling stock and the crew scheduling.The design of the transportation plan can have many consequences on the quality of service: an inadequate frequency in station can cause a loss of passengers, sufficient number of seated places, robustness of the timetable in the face of small incidents... In dense area, as in the Ile-de-France region, all these elements must be taken into account as the transportation plan is designed.Today, SNCF Transilien designs its transportation plans by first taking into account the optimization of production resources (train paths, rolling stock units and drivers). However, today, the increase in resources implemented no longer improves the adequacy of the transportation plan to passengers’ demand. This design method no longer makes it possible to cope with the increase in the demand for mobility (+3% each year since 2000). This is why we must rethink the design of the transport plan by immediately integrating the passenger dimension. Our work focuses on issues of line planning and timetabling in a passenger-oriented approach. First, we present a multi-objective model for line planning. Then, we present a model of timetabling incorporating passenger route choice. Then, we initiate a method to integrate these two models. Finally, we present an evaluation of our results thanks to reliability indicators from the literature and a macroscopic simulation of the timetables
|
99 |
Desenvolvimento de estratégias de otimização contínua e discreta para problemas de fluxo de potência ótimo / Development of continuous and discrete optimization strategies to problems of optimal power flowMazzini, Ana Paula 01 April 2016 (has links)
O objetivo do presente trabalho é a investigação e o desenvolvimento de estratégias de otimização contínua e discreta para problemas de Fluxo de Potência Ótimo (FPO), onde existe a necessidade de se considerar as variáveis de controle associadas aos taps de transformadores em-fase e chaveamentos de bancos de capacitores e reatores shunt como variáveis discretas e existe a necessidade da limitação, e/ou até mesmo a minimização do número de ações de controle. Neste trabalho, o problema de FPO será abordado por meio de três estratégias. Na primeira proposta, o problema de FPO é modelado como um problema de Programação Não Linear com Variáveis Contínuas e Discretas (PNLCD) para a minimização de perdas ativas na transmissão; são propostas três abordagens utilizando funções de discretização para o tratamento das variáveis discretas. Na segunda proposta, considera-se que o problema de FPO, com os taps de transformadores discretos e bancos de capacitores e reatores shunts fixos, possui uma limitação no número de ações de controles; variáveis binárias associadas ao número de ações de controles são tratadas por uma função quadrática. Na terceira proposta, o problema de FPO é modelado como um problema de Otimização Multiobjetivo. O método da soma ponderada e o método ε-restrito são utilizados para modificar os problemas multiobjetivos propostos em problemas mono-objetivos. As variáveis binárias associadas às ações de controles são tratadas por duas funções, uma sigmoidal e uma polinomial. Para verificar a eficácia e a robustez dos modelos e algoritmos desenvolvidos serão realizados testes com os sistemas elétricos IEEE de 14, 30, 57, 118 e 300 barras. Todos os algoritmos e modelos foram implementados em General Algebraic Modeling System (GAMS) e os solvers CONOPT, IPOPT, KNITRO e DICOPT foram utilizados na resolução dos problemas. Os resultados obtidos confirmam que as estratégias de discretização são eficientes e as propostas de modelagem para variáveis binárias permitem encontrar soluções factíveis para os problemas envolvendo as ações de controles enquanto os solvers DICOPT e KNITRO utilizados para modelar variáveis binárias não encontram soluções. / The aims of this study are the investigation and the development of continuous and discrete optimization strategies to Optimal Power Flow (OPF) problems, where the control variables are the tap ratios of on-load tap changing (OLTC) transformers and shunt susceptances of switchable capacitors and reactors banks. These controls are discrete variables and a need for the limitation and/or even the minimization of the number of control adjustments is required. In this work, three strategies for solving the OPF problem have been deviced. In the first strategy, the OPF problem is modeled as a nonlinear programming problem with continuous and discrete variables for active power losses minimization; Three approaches using discretization functions for handling discrete variables have been investigated. In the second proposal, the OPF problem with discrete OLTC transformers and continuous shunt susceptances of switchable capacitors and reactors banks has a limitation on the number of control adjustments; binary variables associated with control adjustments are handled by a quadratic function. In the third proposal, the OPF problem is modeled as a multiobjective optimization problem. The weighting method and the ε-constraint method are used to modify the proposed multiobjective problems onto single-objective problems. The binary variables associated with the controls are handled by sigmoidal and polynomial functions. The efficiency and robustness of the models and algorithms are shown for IEEE benchmark test-systems with up to 300 buses. All algorithms and models were implemented in GAMS modeling language and the results are obtained by means of CONOPT, IPOPT, KNITRO and DICOPT solvers. The results confirm that the discretization strategies are efficient and the proposed modeling for binary variables allows finding feasible solutions to problems involving the of controls while DICOPT and KNITRO solvers used to handle binary variables fail to find solutions.
|
100 |
Métodos mono e multiobjetivo para o problema de escalonamento de técnicos de campo. / Mono and multiobjective methods for the field technician scheduling problem.Damm, Ricardo de Brito 28 March 2016 (has links)
Um tema pouco estudado na literatura, mas frequentemente encontrado por empresas prestadoras de serviço, é o Problema de Escalonamento de Técnicos de Campos (Field Technician Scheduling Problem). O problema consiste em associar um número de tarefas - em diversos locais, com diferentes prioridades e com janelas de tempo - a uma quantidade de técnicos - com diferentes horários de expediente e com habilidades distintas - que saem no início do horário de trabalho da sede da empresa, para onde devem retornar antes do fim do expediente. Cada tarefa é atendida por um único técnico. Esse problema é estudado neste trabalho. A primeira parte do trabalho apresenta um modelo de programação linear inteira mista (PLIM) e, dada a complexidade do problema, heurísticas construtivas e meta-heurísticas foram desenvolvidas. Na função objetivo, procura-se principalmente maximizar o número ponderado de tarefas executadas em um dia de trabalho, de acordo com as suas prioridades. Em linhas gerais, as heurísticas construtivas ordenam as tarefas de acordo com um critério pré-estabelecido e, em seguida, designam cada uma a um dos técnicos capazes de realiza-la sem violar as restrições do problema. Tendo em conta o bom desempenho obtido em outros problemas semelhantes, foi adotado um Algoritmo Genético denominado Biased Random-Key Genetic Algorithms (BRKGA), que utiliza chaves aleatórias para codificar e decodificar as soluções. Codificadores e decodificadores adaptados ao problema foram desenvolvidos e testes computacionais são apresentados. As soluções obtidas em problemas de pequenas dimensões são comparadas com as soluções ótimas conhecidas e, para aprimorar a avaliação do desempenho nas instâncias médias e grandes, quatro procedimentos para obter limitantes superiores foram propostos. Testes computacionais foram realizados em 1040 instâncias. O BRKGA encontrou 99% das 238 soluções ótimas conhecidas e, nas 720 instâncias de dimensões médias e grandes, ficou em média a 3,8% dos limitantes superiores. As heurísticas construtivas superaram uma heurística construtiva da literatura em 90% das instâncias. A segunda parte do trabalho apresenta uma nova abordagem para o Problema de Escalonamento de Técnicos de Campo: um modelo biobjetivo, onde uma segunda função objetivo buscará que as tarefas prioritárias sejam realizadas o mais cedo possível. Uma versão multiobjectivo do BRKGA foi desenvolvida, considerando diversas estratégias para classificar a população do algoritmo e escolher as melhores soluções (estratégias de elitismo). Codificadores e decodificadores foram criados para o problema multiobjectivo. Os resultados computacionais obtidos são comparados com os resultados de um Algoritmo Genético conhecido na literatura, o Nondominated Sorting Genetic Algorithm II (NSGA II). Para instâncias de pequenas dimensões, os resultados da meta-heurística proposta também são comparados com a fronteira ótima de Pareto de 234 instâncias, obtidas por enumeração completa. Em média, o BRKGA multiobjectivo encontrou 94% das soluções da fronteira ótima de Pareto e, nas instâncias médias e grandes, superou o desempenho do NSGA-II nas medidas de avaliação adotadas (porcentagem de soluções eficientes, hipervolume, indicador epsílon e cobertura). / An important topic in service companies, but little studied until now, is the field technician scheduling problem. In this problem, technicians have to execute a set of jobs or service tasks. Technicians have different skills and working hours. Tasks are in different locations within a city, with different time windows, priorities, and processing times. Each task is executed by only one technician. This problem is addressed in this thesis. The first part of the research presents the mixed integer linear programming model (MILP) and, due to the complexity of this problem, constructive heuristics and metaheuristics were proposed. The objective function is to maximize the sum of the weighted performed tasks in a day, based on the priority of tasks. In general terms, in the proposed constructive heuristics, jobs are ordered according to a criterion and, after that, tasks are assigned to technicians without violating constraints. A Genetic Algorithm (the Biases Randon Key Genetic Algorithm - -RKGA) is applied to the problem, based on its success in similar problems; the BRKGA uses random keys and a decoder transforms each chromosome of the Genetic Algorithm into a feasible solution of the problem. Decoders and encoders adapted to the problem were developed and computational tests are presented. A comparison between the solutions of the heuristic methods and optimal solutions values was also conducted for small instances and, to analyze medium and large instances, four upper bound models were proposed. Computational experiments with 1040 instances were carried out. The BRKGA reached 99% of the 238 optimal solutions and, for 720 medium and large instances, the average upper bound gap was 3,8%. Constructive heuristics overcame a heuristic of the literature in 90% of the instances. The second part of this research presents a new approach of the Field Technician Scheduling Problem: a multiobjective model, with a second objective function to execute the priority tasks as soon as possible. A multiobjective BRKGA was developed, with different strategies to classify the Genetic Algorithm population and to select the elite solutions (elite strategies). Decoders and encoders were developed for the multiobjective problem too. The results were compared with a known Genetic Algorithm, the Nondominated Sorting Genetic Algorithm II (NSGA II). For 234 small instances, the results were compared with the Pareto optimal solutions, obtained by complete enumeration. On average, the BRKGA found 94% of the Pareto optimal solutions and, for 720 medium and large instances, outperformed the NSGA-II by means of the measures adopted (percentage of efficient solutions, hypervolume, epsilon and coverage).
|
Page generated in 0.5904 seconds