Rozprawy doktorskie na temat „Heuristique de recherche tabou”
Utwórz poprawne odniesienie w stylach APA, MLA, Chicago, Harvard i wielu innych
Sprawdź 50 najlepszych rozpraw doktorskich naukowych na temat „Heuristique de recherche tabou”.
Przycisk „Dodaj do bibliografii” jest dostępny obok każdej pracy w bibliografii. Użyj go – a my automatycznie utworzymy odniesienie bibliograficzne do wybranej pracy w stylu cytowania, którego potrzebujesz: APA, MLA, Harvard, Chicago, Vancouver itp.
Możesz również pobrać pełny tekst publikacji naukowej w formacie „.pdf” i przeczytać adnotację do pracy online, jeśli odpowiednie parametry są dostępne w metadanych.
Przeglądaj rozprawy doktorskie z różnych dziedzin i twórz odpowiednie bibliografie.
Gómez-Villouta, Giglia. "Méthodes heuristiques pour le problème de placement sur bande en deux dimensions". Angers, 2010. http://www.theses.fr/2010ANGE0022.
Pełny tekst źródłaPacking problems are usually NP-hard, or NP-complete according to the objective. One has to locate a set of objects into one or more “container(s)”, with fix dimensions or of infinite height, while respecting constraints related to some characteristics (weight, quantity, rotation, stability, guillotine cuts. . . ). Themain interest of these problems are the numerous practical applications from various domains. The most effective solution strategies for these problems are usually approximate methods, local search in particular. In this thesis, we are interested in a particular two-dimensional packing problem (without rotation nor guillotine cuts) known as “strip packing” (SPP). The objective of this problem, after locating rectangular objects without overlap, is to minimize the height of the resulting packing. We developed two “meta-heuristic” approaches for the SPP, both including innovative components based on problem knowledge. The first one is a genetic algorithm with a new (highly “visual”) crossover and a hierarchical fitness function. The second one is a tabu search with “direct” representation (i. E. Not using the classical permutations) whose main characteristics are a consistent neighborhood, a “well-informed” diversification (based on the search history), and a fitness function able to evaluate possibly partial solutions. The two proposed approaches, assessed on a well-known and very difficult benchmark, show good performances compared with other strategies
Kuri, Josué. "Problèmes d'optimisation dans les réseaux optiques de transport avec des connexions planifiées". Paris, ENST, 2003. http://www.theses.fr/2003ENST0028.
Pełny tekst źródłaWe investigate optimization problems arising in the engineering of an Optical Transport Network (OTN). We propose a dynamic deterministic traffic model called Scheduled Lightpath Demands (SLDs) in which a connection demand is represented by a tuple (s, d, n, a, o); s and d are the source and destination nodes, n is the number of requested connections and a/o are the set-up/tear-down dates of the connections. The model captures the time and space distribution of a set of demands and eases the use of combinatorial optimization techniques to solve network optimization problems. We address 3 OTN engineering problems involving SLDs: Routing and Wavelength Assignment, Diverse Routing and Spare Capacity Assignment, and Routing and Grooming in a multi-granularity switching network. We formulate the problems as optimization problems and propose meta-heuristic algorithms to compute approximate solutions. The algorithms provide solutions of good quality in reasonable computing time
Khemakhem, Mahdi. "Heuristiques pour un Problème de m-Tournées Sélectives". Phd thesis, Université de Valenciennes et du Hainaut-Cambresis, 2008. http://tel.archives-ouvertes.fr/tel-00440494.
Pełny tekst źródłaGomez-Villouta, Giglia. "Méthodes heuristiques pour le problème de placement sur bande en deux dimensions". Phd thesis, Université d'Angers, 2010. http://tel.archives-ouvertes.fr/tel-00575859.
Pełny tekst źródłaSbihi, Abdelkader. "Les Méthodes Hybrides en Optimisation Combinatoire :Algorithmes Exacts et Heuristiques". Phd thesis, Université Panthéon-Sorbonne - Paris I, 2003. http://tel.archives-ouvertes.fr/tel-00012188.
Pełny tekst źródłamodélisation et de la résolution algorithmique. Dans cette thèse, nous étudions deux variantes
NP-difficiles de problèmes de type sac-à-dos. Plus précisément, nous traitons le problème de
la distribution équitable (le Knapsack Sharing Problem : KSP) et le problème du sac-à-dos
généralisé à choix multiple (le Multiple-choice Multidimensional Knapasck Problem : MMKP).
Dans la première partie de cette thèse, nous nous intéressons au développement d'algorithmes
approchés pour les deux variantes évoquées du problème de type sac-à-dos. La deuxième partie
traite essentiellement de la résolution exacte du problème du sac-à-dos généralisé à choix multiple.
L'approche exacte que nous proposons est de type séparation et évaluation s'appuyant
principalement sur : (i) le calcul des bornes inférieure et supérieure et (ii) l'utilisation de la
stratégie par le meilleur d'abord en développant des branches à double noeuds fils et frère.
La première partie porte sur l'étude et la résolution approchée des deux problèmes KSP et
MMKP. Concernant le problème de la distribution équitable, nous proposons dans un premier
temps, une première version de l'algorithme exploitant certaines caractéristiques de la
recherche tabou. Dans un deuxième temps, nous développons une deuxième version de l'algorithme dont l'idée principale consiste à tenter de combiner l'intensification de la recherche dans l'espace des solutions et la diversification de la solution obtenue. Nous soulignons la rapidité
de la première version et l'efficacité de la deuxième. Ensuite nous nous intéressons au problème
de sac-à-dos généralisé à choix multiple. Nous proposons deux heuristiques de recherche locale
itérative. Le premier algorithme s'appuie sur une “recherche guidée”. Le deuxième algorithme
est une recherche locale que nous appelons réactive avec stratégies de déblocage et de dégradtion améliorantes de la solution et basées sur l'inter-change local.
Dans la deuxième partie de cette thèse, nous proposons une méthode de résolution exacte de type séparation et évaluation pour le problème du sac-à-dos généralisé à choix multiple. D'une part, nous nous proposons la réduction du problème initial au problème auxiliaire MMKPaux qui n'est autre que le problème de sac-à-dos à choix multiple MCKP. Nous calculons une borne supérieure pour le MMKPaux et nous établissons le résultat théorique pour lequel une borne supérieure pour le MMKPaux est une borne supérieure pour le MMKP. D'autre part, nous proposons le calcul d'une borne supérieure ainsi qu'une borne inférieure de départ pour le problème étudié qui sont nécessaires pour la réduction de l'espace de recherche. L'étude expérimentale montre l'efficacité de la méthode proposée sur différents groupes d'instances de petite et moyenne taille.
Nous expliquons enfin pourquoi cet algorithme exact atteint ses limites de résolution, dˆues
principalement à la complexité intrinsèque du modèle étudié. D'autant la résolution dépend de
la taille et la densité des instances traitées.
Duvivier, David. "Étude de l'hybridation des méta-heuristiques, application à un problème d'ordonnancement de type jobshop". Phd thesis, Université du Littoral Côte d'Opale, 2000. http://tel.archives-ouvertes.fr/tel-00008729.
Pełny tekst źródłaPlus que les performances en elles-mêmes, nous nous intéressons tout particulièrement à la compréhension du fonctionnement des méthodes de résolution ainsi qu'à l'analyse de l'influence de la coopération de plusieurs méthodes de recherche sur la qualité des solutions engendrées.
Dans un premier temps, nous évaluons l'apport de critères secondaires intégrés dans la fonction coût. Nous utilisons des algorithmes itératifs de recherche pour étudier l'impact de l'intégration de ces critères sur le paysage adaptatif ainsi que sur la qualité des ordonnancements engendrés.
Nous proposons ensuite quelques améliorations du schéma d'application des opérateurs dans les algorithmes génétiques.
Finalement, nous étudions quelques modèles d'hybridation des méta-heuristiques basés sur la recherche tabou et les algorithmes évolutifs.
Mynard, Laurent. "Exploration locale oscillante heuristiquement ordonnée". Paris 6, 1998. http://www.theses.fr/1998PA066255.
Pełny tekst źródłaZribi, Nozha. "Ordonnancement de job-shops flexibles sous contraintes de disponibilité des machines". Ecole Centrale de Lille, 2005. http://www.theses.fr/2005ECLI0012.
Pełny tekst źródłaKhanafer, Ali. "Algorithmes pour des problèmes de bin packing mono- et multi-objectif". Thesis, Lille 1, 2010. http://www.theses.fr/2010LIL10088/document.
Pełny tekst źródłaThe bin packing problem consists in minimizing the number of containers (bins) needed to place a set of objects. This NP-complete problem has been, for many years, the subject of multiple theoretical and practical researches. It appears in many industrial applications such as cutting steel, wood and glass. The literature on the bin packing problem is rich and the algorithms and resolution approaches are also very are very diversified. However, solutions offered by these algorithms may not be useful when we deal with real industrial problems. In this thesis, we consider several types of constraints such as compatibility relations between objects. These constraints are issued from real life industrial applications. The research topic of this thesis focuses on solving a variety of bin packing problems. We are interested in lower and upper bounds for three problems: a bin packing problem with conflicts in which some compatibility relations exist between pairs of objects, a problem bi-objective bin packing in which two criteria are to minimize: the number of bins used and the number of conflicting couples of objects placed in the same bin, a problem of bin packing with fragile objects in which the sum of the sizes of objects placed in a bin does not exceed the fragility of any of these objects
Wilbaut, Christophe. "Heuristiques hybrides pour la résolution de problèmes en variables 0-1 mixtes". Phd thesis, Université de Valenciennes et du Hainaut-Cambresis, 2006. http://tel.archives-ouvertes.fr/tel-00409493.
Pełny tekst źródłaMalca, Franck. "Méthodes d'aide à la décision pour la gestion d'une flotte de véhicules en temps réel". Valenciennes, 2005. https://ged.uphf.fr/nuxeo/site/esupversions/ff6e9333-7852-4e06-b9b0-05d13b8c795d.
Pełny tekst źródłaThis thesis focuses on the real-time management of a fleet of vehicles. Recent improvements in communication and information technologies provide new data sets in real-time which lead to the development of new applications in transportation area. New decision-making methods are required to help the manager with the planning of the activities for all vehicles. This thesis addresses a pickup and delivery problem with time windows and a finite size fleet. First, we propose constructive heuristics and a tabu search approach to optimize the road planning when all requests to be assigned are known a priori. The main contribution consists of the extraction and the exploitation of informations to reduce the search space, which leads to cut computation times. In real-time, new demands occur while vehicles are in route. To manage the fleet in real-time, we capitalize on the methods defined for the static case to propose an adapted version. This research works were motivated by the TESS project (Transport ESpace et Société). Proposed methods were integrated in an optimization system, which has been included in a decision support system for the fleet management. This software was developped in collaboration with our partners (CNES and the CGx company)
Hail, Nourredine. "Méthodes algorithmiques pour les lignes de production avec des machines parallèles". Université Joseph Fourier (Grenoble), 1995. http://www.theses.fr/1995GRE10019.
Pełny tekst źródłaKammarti, Ryan. "Approches évolutionnistes pour la résolution du 1-PDPTW statique et dynamique". Ecole Centrale de Lille, 2006. https://pepite-depot.univ-lille.fr/LIBRE/Th_Num/2006/50376-2006-Kammarti.pdf.
Pełny tekst źródłaNowadays, goods and people transportation take an important place in all societies daily life and business. The single pickup and delivery problem is one of the most faced problems. Having a set of request to satisfy the transportation vehicle will carry goods from providers to respective customers respecting their each time windows and its self-transportation capacity. In this work, we present a review of the scientific literature on the 1-PDPTW and we present some new approaches to resolve the static and the dynamic cases of this problem. Our approaches use mainly evolutionary algorithms based on the use of special genetic operators conceived in to improve the solutions quality and to decrease the computation time. They are also based on the use of the Pareto optimality approach to provide to the decision maker a set of good feasible solutions. Some of our approaches use distance end tardiness lower bounds to evaluate the obtained solutions. A hybridization stage, consisting on a special Tabu search, can be applied to improve the solutions given by the evolutionary algorithms. Finally, we present some simulations and results elaborated with benchmarks especially conceived for the 1-PDPTW and other benchmarks issued from the literature
Amrani-Benhalima, Faïza. "Problèmes de MIN-MAX en variables 0-1 : Algorithmes de résolution exacts et approchés". Valenciennes, 1997. https://ged.uphf.fr/nuxeo/site/esupversions/6fb2c7ce-df58-4bc6-bb55-a1a7c0529fcf.
Pełny tekst źródłaCao, Xiaokang. "Le problème de renouvellement des équipements multi-période". Compiègne, 2011. http://www.theses.fr/2011COMP1920.
Pełny tekst źródłaThis thesis looks at the Multi-Period Renewal equipment problem (MPR). It is inspired by a specific real-life situation where a set of hardware items is to be managed and their replacement dates determined, given a budget over a time horizon comprising a set of periods. The particularity of this problem is the possibility of carrying forward any unused budget from one period to the next. We begin with a state of art. Links with other knapsack problems cited in the literature are also established and studied. A complexity study of MPR via several special cases is then reported. In particular, it is established that one of the special cases can be solved in polynomial time via a minimum-cost flow model, and that two others can be solved in pseudo-polynomial time, while the problem itself is strongly NP-hard when the number of periods is unbounded. We propose two greedy heuristics and two Tabu search methods based on the exploration of sequences corresponding to the priorities of renewing items. We propose a Branch-and-Bound method in order to solve MPR to optimality. This method is also based on the enumeration of priority sequences of items. We propose several types of instances in order to test our methods. In order to evaluate the quality of our methods, we have compared with the results obtained with CPLEX 11 by solving the MIP of MPR
Karray, Asma. "Contribution à l’ordonnancement d’ateliers agroalimentaires utilisant des méthodes d’optimisation hybrides". Thesis, Ecole centrale de Lille, 2011. http://www.theses.fr/2011ECLI0024/document.
Pełny tekst źródłaThe purpose of our works is the implementation of methodologies for the resolution of the agro-food industry scheduling problem. Three new approaches based on genetic algorithms are proposed to solve multi-objectives scheduling problems: sequential genetic algorithms (SGA), parallel genetic algorithms (PGA) and parallel sequential genetic algorithms (PSGA). Two high-level hybrid algorithms, SH_GA/TS et SH_GA/SA, are also proposed. The purpose in this hybridization is to benefit the exploration of the solution space by a population of individuals with the exploitation of solutions through a smart search of the local search algorithm
Hadj, Khalifa Ismahène. "Approches de modélisation et d'optimisation pour la conception d'un système interactif d'aide au déplacement dans un hypermarché". Phd thesis, Ecole Centrale de Lille, 2011. http://tel.archives-ouvertes.fr/tel-00605118.
Pełny tekst źródłaAhmad, Maqsood. "Mathematical models and methods based on metaheuristic approach for timetabling problem". Thesis, Clermont-Ferrand 2, 2013. http://www.theses.fr/2013CLF22393/document.
Pełny tekst źródłaIn 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. (...)
Gomez, Urrutia Edwin David. "Optimisation intégrée des décisions en planification et ordonnancement dans une chaîne logistique". Thesis, Saint-Etienne, EMSE, 2014. http://www.theses.fr/2014EMSE0744/document.
Pełny tekst źródłaIn this thesis, we study the optimization of flow planning and scheduling, within a strategy to integrate decisions for supply chain planning at tactical level, taking into account operational constraints. The goal of this work is to address the need for consistency between decisions arising from production planning and scheduling. These decisions are often taken in a sequential order, leading most of the time to unfeasible production plans. We propose an integrated approach to solve single-level and multi-level problems in multi-item multi-resource systems configured as job-shops.Both capacitated production planning and scheduling problems, in complex manufacturing systems, are NP-hard. Therefore, integrating constraints of both problems generates a new problem which is even more difficult to solve. We propose a decomposition of the integrated problem into a set of several sub-problems with fixed sequence, solved by Lagrangian Relaxation. The sequence improvement is guided by a Tabu Search. The efficiency of the integrated approach comparing to a standard solver is proved in terms of solution quality and computational effort. In case of multi-level problems, we propose a new mathematical model based on the concept of echelon stock, as well as new algorithms and smoothing strategies to build production plans respecting detailed capacity and bill-of-materials constraints
Baccouche, Mohamed. "Métaheuristiques hybrides d'optimisation d'atterrissage d'avions multipistes". Le Havre, 2007. http://www.theses.fr/2007LEHA0008.
Pełny tekst źródłaWe studied in this thesis a complex problem, mixed aircraft scheduling and runway assignment, the Aircraft landing Problem. The complexity of this optimization problem is the result of its combinatorial aspects (problems size), of the strong interdependence between functions (assignment and scheduling), constraints and perturbations. Airport landing capacities constitute genuine bottlenecks, making it impossible to respond to an increase in air traffic. The largest airports are already operating at maximum capacity and only increased optimization of the landing sequences will make it possible to cope. We developed and tested different hybrid approaches based on metaheuristics techniques such as evolutionary algorithms and taboo search and on exact methods. We have compared different approaches with a large choice of parameters, analyzed computational complexity and performances and discussed the best values. We used the experience plans method in order to optimize the choice of parameters of developed algorithms
Hadj, Khalifa Ismahène. "Approches de modélisation et d’optimisation pour la conception d’un système interactif d’aide au déplacement dans un hypermarché". Thesis, Ecole centrale de Lille, 2011. http://www.theses.fr/2011ECLI0008/document.
Pełny tekst źródłaThe present work focuses on the technical feasibility study of i-GUIDE system which is a real time indoor navigation system dedicated to assist persons inside hypermarkets. We detailed its functional analysis. Then, we studied the impact of integrating the system inside hypermarkets. We opted for an UML design to describe its main functionalities and objects required. We presented architecture of i-GUIDE system based on RFID technology with an Android application. Furthermore, we introduced optimization approaches based on tabu search to compute the route visiting items existing in a shopping list for two problems. The first one treats the shortest path to pick up items and the second one adds a time constraint for promotional items. Before computing the shortest path, we introduced a method to determine distance between each two items existing in the hypermarket
Kammoun, Mohamed Firas. "Conception et déploiement d'un algorithme pour l'optimisation des réseaux optiques". Mémoire, Université de Sherbrooke, 2010. http://savoirs.usherbrooke.ca/handle/11143/1638.
Pełny tekst źródłaPalpant, Mireille. "Recherche exacte et approchée en optimisation combinatoire : schémas d'intégration et applications". Avignon, 2005. http://www.theses.fr/2005AVIG0138.
Pełny tekst źródłaBoulanger, Célia. "Heuristiques basées sur la programmation mathématique pour des problèmes de localisation et de routage". Valenciennes, 2010. http://ged.univ-valenciennes.fr/nuxeo/site/esupversions/097f03a9-5364-4c57-afd3-697ff1edf975.
Pełny tekst źródłaThe aim of this PHD is the modelisation of two transportation problems of operationnal research. . These problems are routing problem and location problem. The first one studied is the location-routing problem with capacity constraints on facilities. Three methods are proposed to solve this problem. The two first are hybrid heuristics, mixing linear programs and a tabou search. The third method is based on a column generation method. These three contributions have been developped and tested to see their efficienty. We obtain good results, the best method giving most of the best results of the thirty instances. The second problem studied is a biobjectif travelling salesman problem on a particular graphe where some vertices have to be visited. A heuristic has been developed to solve this biobjective problem. To evaluate results obtained, an exacte method has been developed too
Danna, Emilie. "Intégration des techniques de recherche locale à la programmation linéaire en nombres entiers". Avignon, 2004. http://www.theses.fr/2004AVIG0132.
Pełny tekst źródłaWe present several algorithms for integrating local search technique into mixed integer programming (MIP). We first introduce a cooperation scheme between local search and branch-and-price that generalizes the concept of branch-and-cut heuristics to branch-and-price and we apply it successfully to the vehicle routing problem with time windows. We then present a new MIP heuristic that we call Relaxation Induced Neighborhood Search (RINS). This heuristic finds good integer solutions on models that previously were very difficult to solve. It is now implemented in ILOG CPLEX 9. RINS exploits the three fundamental concepts of local search (neighborhood, intensification, and diversification) and transposes them to mixed integer programming. This heuristic is generic : it can be applied to any MIP model, with no other input than the model itself. RINS allows us to formalize the notion of "hybrid in spirit'' algorithms. This development paradigm consists in using only one optimization technique and integrating into its framework concepts of other resolution techniques instead of having several software components cooperate. RINS performances and our analysis of difficulties encountered by existing hybrid algorithms suggest that this class of algorithms is promising. We finally concentrate on the job-shop scheduling problem with earliness and tardiness costs on which RINS is particularly effective. We propose several improvements and extensions of the disjunctive model for this problem and a heuristic (MCORE : big-M COefficient REduction) that could be generalized to other MIP models of similar structure. MCORE is also a "hybrid in spirit'' algorithm
Tremblay, Bergeron. "L'empathie comme modèle de communication dans l'enseignement aux adultes, bune recherche heuristique". Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape8/PQDD_0020/MQ48319.pdf.
Pełny tekst źródłaTremblay, Michèle B. "L'empathie comme modèle de communication dans l'enseignement aux adultes : une recherche heuristique /". Thèse, Chicoutimi : Université du Québec à Chicoutimi, 1999. http://theses.uqac.ca.
Pełny tekst źródłaLeroy, Cassandre. "Élicitation incrémentale combinée à la recherche heuristique pour l'optimisation combinatoire multi-objectifs". Electronic Thesis or Diss., Sorbonne université, 2022. https://accesdistant.sorbonne-universite.fr/login?url=https://theses-intra.sorbonne-universite.fr/2022SORUS367.pdf.
Pełny tekst źródłaThis thesis is concerned with solving combinatorial domain decision problems using incremental regret-based preference elicitation methods for interactive optimization. It is situated at the intersection of decision theory, operations research and artificial intelligence, in algorithmic decision theory. It is assumed that the decision maker's preferences can be represented by a parameterised scalarization function (weighted sum, OWA and Choquet integral), but the parameters (e.g. set of weights) are not known at the beginning. The active learning of the parameters is intertwined with the solution of the problem in order to learn only that part of the information about the parameter that is useful to solve the given problem. The originality of this work lies in the use of methods based on heuristic search coupled with incremental elicitation to determine the best solution for the decision maker. In first we propose two methods for solving multi-objective combinatorial optimisation problems with imprecise preferences, the first based on local search and the second on a genetic algorithm. We then propose two approaches for the elicitation of a linear, submodular and super-modular set function with the construction of an optimal independent subset subject to a matroid constraint. The first approach is based on a greedy algorithm and the other on local search. In order to demonstrate the practical effectiveness of our approaches, our algorithms are numerically tested on different problems and evaluated in terms of computation time, number of queries and empirical error
Chelouah, Rachid. "Adaptation aux problemes a variables continues de plusieurs metaheuristiques d'optimisation combinatoire : la methode tabou, les algorithmes genetiques et les methodes hybrides. application en controle non destructif". Cergy-Pontoise, 2000. http://www.theses.fr/2000CERG0108.
Pełny tekst źródłaWu, Tingying. "Models and algorithms for two-echelon capacitated facility location problem with facility size selection". Thesis, Université Paris-Saclay (ComUE), 2015. http://www.theses.fr/2015SACLE029.
Pełny tekst źródłaFacility location is one of the most important strategic decisions for firms in globalization. Previous works on facility location in the literature mainly focus on determining the locations of facilities and the flows of products from facilities to customers with the goal of minimizing the sum of facility opening costs, production and logistic costs. However, it’s very important to determine at the same time the appropriate sizes for these facilities because they greatly affects these costs on the long term. Determining facility location and size is always an open problem.In this thesis, we study three new two-echelon capacitated facility location problems (TECFLP) with facility size selection. The two first parts of the wok focus on two-echelon facility location problems with plant and depot size selection, respectively. The third part concentrates on TECFLP considering simultaneously plant and depot size selection. For these problems, three corresponding mixed integer programming models are formulated and then Lagrangean relaxation approaches according to the problems’ characteristics are developed. To further improve the best solutions obtained by the Lagrangean Relaxation approaches, a tabu search, a hybrid variable neighborhood tabu search and a hybrid simulated annealing tabu search are adapted for the three problems respectively. The developed algorithms are tested and evaluated through 810 randomly generated instances. Computational results show ours algorithms can provide high quality solutions within a reasonable computation time
Fournier, David. "Metro regenerative braking energy : optimization through rescheduling : mathematical model and greedy heuristics compared to MILP and CMA-ES". Paris 7, 2014. http://www.theses.fr/2014PA077144.
Pełny tekst źródłaThe use of regenerative braking is a key factor to reduce the energy consumption of a metro line. In the case where no device can store the energy produced during braking, only the metros that are accelerating at the same time can benefit from it. Maximizing the power transfers between accelerating and braking metros thus provides a simple strategy to benefit from regenerative energy without any other hardware device. In this thesis, we use a mathematical timetable model to classify various metro energy optimization rescheduling problems studied in the literature and prove their NP-hardness by polynomial reductions of SAT. We then focus on the problem of minimizing the global energy consumption of a metro timetable by modifying the dwell times in stations. We present a greedy heuristic algorithm which aims at locally synchronizing braking metros along the timetable with accelerating metros in their time neighbourhood, using a non-linear approximation of energy transfers. On a benchmark of six small size timetables, we show that our greedy heuristics performs better than CPLEX using a MILP formulation of the problem, even when it is able to prove the optimality of a linear approximation of the objective function. We also show that it runs ten times faster than a state-of-the-art evolutionary algorithm, called the covariance matrix adaptation evolution strategy (CMA-ES), using the saure non-linear objective function on these small size instances. On real data leading to 10000 decision variables on which both MILP and CMA-ES do not provide solutions, the dedicated algorithm of our thesis computes solutions with a reduction of energy consumption ranging from 5% to 9%
Canon, Cyril. "Application des techniques de recherche opérationnelle à la planification de centres de contacts en milieu multicompétent". Tours, 2005. http://www.theses.fr/2005TOUR4039.
Pełny tekst źródłaThe aim of a call center is to manage the contacts between their clients and their customers. Agents are not equivalent. Knowing the forecasted incoming calls for four weeks and knowing the data concerning the agents, the problem is to determine the detailed planning of the agents, for each week. Firstly the forecasted number of calls is used to determine for each eriod the number of agents needed to satisfy the required quality of service. Then knowing the constraints related tothe labor code, the number of working hours for each week per agent has tobe deterined. Then the shifts of all the agents plus the position of the breaks and the days-off, with respect of the loading curve, have to be determined. Finally, we have to assign the activities to agents. In case of unfeasibility, some constraints are added to the third phase, and the process iterates until a feasible solution is found. Heuristic approaches are proposed and tested on randomly generated instances
Abid, Mohamed Amine. "Étude des algorithmes de recuit simulé, de recherche tabou et génétique implémentés dans un système de construction d'horaires de cours universitaires". Mémoire, Université de Sherbrooke, 2008. http://savoirs.usherbrooke.ca/handle/11143/1478.
Pełny tekst źródłaPessan, Cedric Néron Emmanuel. "Optimisation de changements de séries par ordonnancement des tâches de réglage". S. l. : S. n, 2008. http://theses.abes.fr/2008TOUR4026.
Pełny tekst źródłaVignier, Antony. "Contribution à la résolution des problèmes d'ordonnancement de type monogamme, multimachine (Flow-Shop Hybride)". Tours, 1997. http://www.theses.fr/1997TOUR4026.
Pełny tekst źródłaGalinho, Thierry. "Algorithme heuristique de placement pour l'ordonnancement : étude comparative et recherche d'expertise sur les stratégies de contrôle". Rouen, 1994. http://www.theses.fr/1994ROUES040.
Pełny tekst źródłaDeguet, Joris. "Intégration de l'émergence au sein des systèmes multi-agent : une étude appliquée à la recherche heuristique". Grenoble 1, 2008. http://www.theses.fr/2008GRE10051.
Pełny tekst źródłaEmergence and multi-agent systems are two domains with share similar problems. Through the study of emergence in the context of multi-agent systems, this work is centred on their principal common point; the search for a collective advantage gained through the interaction among the agents, when the global result is due to interaction. This situation is often summarized by a whole that is more than the sum of its parts. One contribution of this thesis is identifying interactions whose impact can be evaluated through the side-by-side comparison of systems including these interactions or not. Such collective benefits are defined for problem-solving by a heuristic search with a hierarchical multi-agent model. This work includes a multi-agent model of that kind of search that identifies collective benefits, which are called synergies. Three kinds of synergies are considered: the synergy between heuristics searching the same problem, the one between similar problems, and the synergy between a human user and the artificial search system. These possible synergies are included in the discussion about emergence. In this framework, some heuristic populations match the idea of a ``true composite'' that is a composed system whose result is due to interactions between components and not to its composition. The interaction between local and global levels fits in the levels induced by the model's hierarchical organisation. This way, a contribution to the study of emergence is given, by the definition possibilities that a multi-agent model allows for emergence
Haïtami, Mehdi. "Optimisation multicouche des réseaux optiques wdm : heuristiques tabou pour la résolution à moindre coût du problème de groupage de routage et d’affectation de longueurs d’ondes". Thèse, Université de Sherbrooke, 2014. http://hdl.handle.net/11143/5985.
Pełny tekst źródłaBontoux, Boris. "Techniques hybrides de recherche exacte et appochée : application à des problèmes de transport". Avignon, 2008. http://www.theses.fr/2008AVIG0166.
Pełny tekst źródłaWe are interested in this thesis in the possibilities of hybridization between the exact methods and the methods heuristics to be able to take advantage of each of both approaches: optimality of the exact resolution, the less determinist character and the speed of the constituent heuristics. In the objective to resolve problems NP-hard of relatively important size such as the transportation problems, we are interested in the last two parts of this report in the conception of incomplete methods based on these hybridizations. In the first part, we are going to be interested in the methods of resolution by tree search. We introduce a new approach for the management of the decisions of connection, which we call Dynamic Learning Search ( DLS). This method defines in a dynamic way rules of priority for the selection of variables in every knot and the order of the values on which to connect. These rules are conceived in an optics of genericity, so as to be able to use the method independently of the treated problem. The general principle is to take into account by a technique of learning of the impact which had the decisions of connection in the parts already investigated in the tree. We estimate the efficiency of the method proposed on two classic problems: a combinatorial optimization problem and a constraints satisfaction problem. The second part of this report handles large neighborhood search. We present a new operator of neighborhood, who determines by an algorithm of dynamic programming the optimal sub-sequence of a road in a graph. We show that this operator is quite particularly intended for problems of tours for which all the vertices do not require to be visited. We call this class of problem the Problems of Tours with Partial Cover and present some problems being a part of this class. Chapters 3 and 4 show, through consequent experimental tests, the efficiency of the operator which we propose by applying this search to wide neighborhood on two problems, respectively the Traveling Purchaser Problem (TPP) and Generalized Traveling Salesman Problem ( GTSP). We show while this operator can be combined in a effective way with classic metaheuristics, such as genetic algorithms or algorithms of Ant Colony Optimization
Hamel, Johanne. "Création artistique et identité professionnelle: une étude heuristique". Thèse, Université de Sherbrooke, 2011. http://hdl.handle.net/11143/8290.
Pełny tekst źródłaT'Kindt, Vincent. "Etude des problèmes d'ordonnancement multicritères". Tours, 1999. http://www.theses.fr/1999TOUR4017.
Pełny tekst źródłaBelmecheri, Farah. "Optimisation des tournées de véhicules en transport de type messagerie". Troyes, 2010. http://www.theses.fr/2010TROY0023.
Pełny tekst źródłaThis thesis focuses on the transportation problem of a local carrier TCP-Distribution. The study is on the node routing problem (VRP) and specifically to cases with Heterogeneous fleet (H), with Mixed Backhauls (MB), and Time Windows (TW), the problem is called HVRPMBTW. It is few studied in literature. After a general introduction to the transportation problems, and a complete description of the problem studied, we suggest several resolution approaches. A mathematical model is developed; it is a linear model with real and binary variables (mixed LP) which is used by an exact method. The first metaheuristic approach is proposed, it is based on an Ant Colony Optimization (ACO) combined with an efficient local search. This method has shown its effectiveness on HVRPMBTW. A second approach is developed, called a Particle Swarm Optimization (PSO) combined with the effective local search. The new results obtained improve the previous results. The last part of this thesis is dedicated to an industrial application. The methods developed are applied to the industrial cases. A Performance Management Tool is implemented and used with a graphic box developed. Its aim is to calculate and analyze the indicators, and to use the optimization methods
Reghioui, Hamzaoui Mohamed. "Problèmes de tournées de véhicules avec fenêtres horaires ou préemption des tâches". Troyes, 2008. http://www.theses.fr/2008TROY0018.
Pełny tekst źródłaThis thesis studies the node and arc routing problems which are the two main types of routing problems encountered in most transportation applications. We focus particularly on the cases with time windows or split deliveries. This work is divided into two main parts. The first part is devoted to the node and arc routing problems with time windows (VRPTW for the Vehicle Routing Problem with Time Windows and CARPTW for the Capacitated Arc Routing Problem with Time Windows). Contrary to the VRPTW which has been the subject of intensive research over the past decade, few studies have considered the CARPTW. In this part of the thesis, we propose a method based on the metaheuristic GRASP combined with a path-relinking process for the CARPTW and a memetic algorithm for the VRPTW. The second part of the thesis focuses on the node and arc routing problems with split deliveries (SDVRP for the Split Delivery Vehicle Routing Problem and SDCARP for the Split Delivery Capacitated Arc Routing Problem). Since the SDCARP is a relatively new problem, we started by developing mathematical models. We then proposed lower and upper bounds. The lower bounds are obtained by two cutting plane methods while the upper bounds are determined by a memetic algorithm with population management and a new metaheuristic. The memetic algorithm was also adapted to the SDVRP, giving rise to competitive results
Thanh, Phuong Nga. "Conception et planification stratégique des réseaux logistiques complexes". Nantes, 2008. http://www.theses.fr/2008NANT2067.
Pełny tekst źródłaIn a context of strong competition, many companies will seok to improve the performance of their supply chain. Changes are necessary when the supply chain becomes obsolete or in case of signicative changes like mergers, outsourcing or substantial variations of the demand. This research aims at modelling and solving a supply chain design and planning problem over a strategic horizon with some operations research algorithms. The main decision variables concern the facilities that may be opened, expanded or closed, as well as capacity planning and the management of material flow along the supply chain. The objective is to minimise the total logistic cost while satisfying the demand. Additional options include, among others, the possibility to subcontract a part of the production, the possibility to increase the capacity of some facilities. The problem is modeled by a mixed-integer linear program where the integer variables are binary. Three resolution methods are developed. The first is a heuristic based on linear relaxation and some rounding procedures. An improved version of this method is developed by replacing the linear relaxation with the Difference of Convex Functions (D. C. ) approach. The last method is a decomposition method based on Lagrangean relaxation. The results of these methods are compared with the ones obtained with the solver Xpress-MP
Picarougne, Fabien. "Recherche d'information sur Internet par algorithmes évolutionnaires". Phd thesis, Tours, 2004. http://tel.archives-ouvertes.fr/tel-00008013.
Pełny tekst źródłaBelaïdouni, Mériéma. "Métaheuristiques et paysages de recherche". Angers, 2001. http://www.theses.fr/2001ANGE0022.
Pełny tekst źródłaMetaheuristics are a class of methods which are able to provide solutions of good quality in a reasonnable amount of time for difficult combinatorial problems. There exist a large number of applications of these methods but only few studies concern their fondamental aspects. This thesis is devoted to study some fondamental issues of metaheuristics. Three tightly related axis are explored : 1)the study of problems properties and measures, 2)the study of dynamics of metaheuristics, 3)the establishment of the relations between measures of problems and dynamics of metaheuristics. To validate this approach we have apllied it to two NP-complete problems : MAX-CSP and SAT
Bertel, Sylvain. "Problèmes d'ordonnancement dans un flowshop hybride avec recirculation sous contraintes de gestion du personnel". Tours, 2001. http://www.theses.fr/2001TOUR4029.
Pełny tekst źródłaThis work has been achieved within the context of the research collaboration with an industry (CIFRE), the customer management service Atos-Origin and the computer science laboratory of the university of Tours (LI). In this document, we propose in a first time a survey on hybrid flowshop schedulling problems that minimize the wheighted number of late jobs and manpower scheduling problem. A scheduling problem from an industrial context of cheque processing is studied. For this problem, two heuristics based on priority rules and a metaheuristic are proposed. From developed heuristics, we describe an integrated procedure which can be used at different decision levels. Regarding manpower scheduling, we propose linear programming model and a heuristic that gives the size of the workshop. We notice that a planning defined at a tactical level is moire efficient than a planning defined at an operational level. We end this document with the presentation of a software called PLANIF'00
Weill, Jean-Christophe. "Programmes d'échecs de championnat : architecture logicielle, synthèse de fonctions d'évaluation, parallélisme de recherche". Paris 8, 1995. http://www.theses.fr/1995PA080954.
Pełny tekst źródłaZemali, Yacine. "Morcellement de l'espace de recherche en planification : étude théorique et utilisation pour le calcul d'heuristiques". École nationale supérieure de l'aéronautique et de l'espace (Toulouse ; 1972-2007), 2004. http://www.theses.fr/2004ESAE0006.
Pełny tekst źródłaGaland, Lucie. "Méthodes exactes pour l'optimisation multicritère dans les graphes : recherche de solutions de compromis". Paris 6, 2008. http://www.theses.fr/2008PA066153.
Pełny tekst źródła