Retour au site du LAAS-CNRS

Laboratoire d’analyse et d’architecture des systèmes
Choisir la langue : FR | EN

10documents trouvés

16478
07/12/2016

Harnessing tractability in constraint satisfaction problems

C.CARBONNEL

ROC

Doctorat : INP de Toulouse, 7 Décembre 2016, 138p., Président: N.CREIGNOU, Rapporteurs: S.SZEIDER, S.ZIVNY, Examinateurs: P.JEGOU, Directeurs de thèse: M.CCOPER, E.HEBRARD , N° 16478

Lien : https://hal.laas.fr/tel-01444799

Diffusable

Plus d'informations

Abstract

The Constraint Satisfaction Problem (CSP) is a fundamental NP-complete problem with many applications in artificial intelligence. This problem has enjoyed considerable scientific attention in the past decades due to its practical usefulness and the deep theoretical questions it relates to. However, there is a wide gap between practitioners, who develop solving techniques that are efficient for industrial instances but exponential in the worst case, and theorists who design sophisticated polynomial-time algorithms for restrictions of CSP defined by certain algebraic properties. In this thesis we attempt to bridge this gap by providing polynomial-time algorithms to test for membership in a selection of major tractable classes. Even if the instance does not belong to one of these classes, we investigate the possibility of decomposing efficiently a CSP instance into tractable subproblems through the lens of parameterized complexity. Finally, we propose a general framework to adapt the concept of kernelization, central to parameterized complexity but hitherto rarely used in practice, to the context of constraint reasoning. Preliminary experiments on this last contribution show promising results.

Résumé

Le problème de satisfaction de contraintes (CSP) est un problème NP-complet classique en intelligence artificielle qui a suscité un engouement important de la communauté scientifique grâce à la richesse de ses aspects pratiques et théoriques. Cependant, au fil des années un gouffre s’est creusé entre les praticiens, qui développent des méthodes exponentielles mais efficaces pour résoudre des instances industrielles, et les théoriciens qui conçoivent des algorithmes sophistiqués pour résoudre en temps polynomial certaines restrictions de CSP dont l’intérˆet pratique n’est pas avéré. Dans cette thèse nous tentons de réconcilier les deux communaut és en fournissant des méthodes polynomiales pour tester automatiquement l’appartenance d’une instance de CSP à une sélection de classes traitables majeures. Anticipant la possibilité que les instances réelles ne tombent que rarement dans ces classes traitables, nous analysons également de manière systématique la possibilité de décomposer efficacement une instance en sous-problèmes traitables en utilisant des méthodes de complexité paramétrée. Finalement, nous introduisons un cadre général pour exploiter dans les CSP les idées développées pour la kernelization, un concept fondamental de complexité paramétrée jusqu’ici peu utilisé en pratique. Ce dernier point est appuyé par des expérimentations prometteuses.

Mots-Clés / Keywords
Backdoor; Classe traitable; Complexité paramétrée; Kernelization; Polymorphisme; Problème de satisfaction de contraintes;

138577
16373
17/11/2016

Calcul d'itinéraires multiples et de trajets synchronisés dans des réseaux de transport multimodaux

G.SCANO

ROC

Doctorat : INSA de Toulouse, Novembre 2016, 132p., Président: E.NERON, Rapporteurs: C.GUERET, A.OULAMARA, Examinateurs: N.EL FAOUZI, P.LACOMME, Directeurs de thèse: M.J.HUGUET, S.U.NGUEVEU , N° 16373

Non diffusable

Plus d'informations

Abstract

Efficiency and simplicity are two conditions upon which the use of a transportation system is relevant. May it be intentional or imposed, an increasing mobility triggers the need to enhance the transportation offer. In turn, such a response encourages an even more demanding mobility in a constantly adapting cycle. In parallel, new and forthcoming means of transportation emerge from time to time with unknown practices and renewed actors : exactly like what carpooling is stirring at the moment. Passenger information systems can technically deal with such evolutions thanks to improved technologies but they still struggle to keep up with constantly changing usage expectations. From this perspective the computation of several paths from an origin to a destination becomes increasingly relevant. This issue is even more crucial in dense transportation networks in which many modes and lines of transportation are combined. Indeed, giving some travelling choices to the end user reduces the feeling of exclusion, anxiety and the lack of understanding which may arise when facing arbitrary decisions dictated by a software or an internet application. It is also helpful to estimate the quality of the transportation offer since the more paths exist to go from point A to point B within a fixed time window, the better the service is. This thesis focuses on the computation of such alternatives by the gradually increasing enumeration of paths between two points. Given this input, the pruning necessary to obtain such a diverse selection is assumed not to be known in advance. It is left up to transportation professionals who may choose a fitted solution based on their specific knowledge and objectives. Another subject studied in this thesis concerns the itinerary synchronisation of several users for various social uses such as shared travels. It is here seen from the perspective of carpooling. Considering only two users, the problem is to minimise the travelling cost of the users under the constraint that they must share some part of their respective trips with one another. Solving this problem is equivalent to finding a pick up point and a drop off location between which both paths overlap. Multiple corner cases concerning the transportation conditions of each user as well as the special cases of shared origins or destinations are studied. The constraints on the arrival and/or departure times may also vary. Last but not least and since the driver is often penalized when giving up a lift, the restriction to a maximal detour the driver accepts, compared to his shortest path, is analysed with respect to the benefits such a limitation generates. This thesis was funded by the MobiGIS company under the CIFRE (Industrial Agreement of Training through Research) researching context. The related work consisted in the practical implementation of mobility solutions within the framework of the company as well as the experimental performances evaluation of the algorithms proposed to solve them.

Résumé

L’utilisation des réseaux de transport est conditionnée par l’efficacité et la simplicité de leur utilisation. En réponse à une mobilité exacerbée, volontaire ou subie, l’offre de transport se développe et motive tout à la fois, en un cycle continu, des déplacements encore plus exigeants. De manière complémentaire, la mobilité est bousculée par l’arrivée de nouvelles modalités de transport pouvant faire émerger, comme dans le cadre du covoiturage, des acteurs ou des pratiques jusqu’alors inexistants. Si la technologie permet de suivre cette évolution dans les services d’information aux voyageurs, il reste toujours à satisfaire des attentes déterminées par des usages en constante évolution. C’est de ce point de vue que l’obtention de chemins multiples pour relier une origine à une destination est un facteur qui n’est plus à négliger, surtout dans des réseaux de transport denses et comportant de nombreux modes et lignes de transport. Une liberté dans le choix laissé à l’utilisateur du réseau réduit les sentiments d’exclusion, d’incompréhension ou d’anxiété qui peuvent survenir face à une application logicielle ou sur internet et qui effectuent des choix arbitraires de façon autoritaire. De plus, cela permet de vérifier la qualité de l’offre de transport, car plus il existe de moyens différents pour effectuer un trajet dans un intervalle de temps donné, meilleur est le service. Cette thèse s’intéresse au calcul de telles alternatives par le biais de l’énumération par coût croissant des chemins entre deux points, puis par le filtrage de ceux-ci suivant des critères, supposés quelconques et laissés à l’appréciation des professionnels de transport qui peuvent ainsi faire varier les angles d’analyses de leurs offres. Par ailleurs, la synchronisation de trajets de plusieurs utilisateurs, en vue d’usages sociaux ou de déplacements mutualisés, est étudiée dans ce manuscrit sous l’angle du covoiturage. En ne considérant que deux usagers, l’objectif est de minimiser le temps de trajet global des participants sous la contrainte qu’ils partagent une partie de leur chemin entre un point de rencontre et un point de séparation qu’il faut alors déterminer. Sont également étudiées les variantes associées au changement des conditions de transport de chacun des participants comme l’établissement d’une origine ou d’une destination commune parallèlement à des contraintes sur les heures de départ ou d’arrivée des usagers. Enfin, puisque la voiture est très souvent pénalisée par la prise en charge d’un piéton, il convient d’étudier comment ce détour peut être contraint et les impacts sur les gains que cette limitation engendre. Cette thèse a été réalisée dans un contexte CIFRE pour la société MobiGIS. Les travaux qui s’y rapportent ont fait l’objet de réalisations pratiques tant pour fournir des solutions de mobilité dans le cadre des activités de l’entreprise que pour évaluer expérimentalement les performances des algorithmes proposés pour les résoudre.

Mots-Clés / Keywords
Itinéraires alternatifs; Itinéraires synchronisés; Réseaux de transport multimodaux; Alternative itineraries; Multimodal transportatin network; Synchronised itineraries;

138014
16382
18/10/2016

Ordonnancement sous contraintes d’énergie

M.NATTAF

ROC

Doctorat : Université de Toulouse III - Paul Sabatier, 18 Octobre 2016, 198p., Président: A.QUILLOT, Rapporteurs: P.BAPTISTE, C.G.QUIMPER, Examinateurs: C.BRIAND, T.KIS, P.LABORIE, Directeurs de thèse: P.LOPEZ, C.ARTIGUES , N° 16382

Diffusable

Plus d'informations

Résumé

Les problèmes d’ordonnancement à contraintes de ressource ont été largement étudiés dans la littérature. Cependant, dans la plupart des cas, il est supposé que les activités ont une durée fixe et nécessitent une quantité constante de la ressource durant toute leur exécution. Dans cette thèse, nous nous proposons de traiter un problème d’ordonnancement dans lequel les tâches ont une durée et un profil de consommation de ressource variables. Ce profil, qui peut varier en fonction du temps, est une variable de décision du problème dont dépend la durée de la tâche associée. Par ailleurs, la considération de fonctions de rendement linéaires et non linéaires pour la représentation de l’utilisation des ressources complexifie le problème et permet de modéliser de manière réaliste les transferts de ressources énergétiques. Pour ce problème NP-complet, nous présentons plusieurs propriétés permettant de dériver des modèles et méthodes de résolution. Ces méthodes de résolution sont divisées en deux parties. La première partie visualise ce problème du point de vue de la Programmation Par Contraintes et plusieurs méthodes dérivées de ce paradigme sont détaillées dont le développement du raisonnement énergétique sur le problème étudié. La seconde partie de la thèse est dédiée à des approches de Programmation Linéaire Mixte et plusieurs modèles, notamment un modèle à temps continu basé sur les événements, ainsi que des analyses théoriques et des techniques d’amélioration de ces modèles sont présentés. Enfin, des expérimentations viennent appuyer les résultats présentés dans ce manuscrit.

Mots-Clés / Keywords
Ordonnancemment; Energie; Recherche arborescente et locale; Programmation mathématique; Propagation de contraintes; Complexité;

138115
16113
24/06/2016

A dynamic programming operator for metaheuristics to solve vehicle routing problems with optional visits

L.VARGAS SUAREZ

ROC

Doctorat : INSA de Toulouse, Juin 2016, 171p., Président: D.FEILLET, Rapporteurs: L.JOURDAN, C.TANRANTILIS, Examinateurs: , C.PRODHON, Directeurs de thèse: N.JOZEFOWIEZ, S.ULRICH NGUEVEU , N° 16113

Lien : https://tel.archives-ouvertes.fr/tel-01355746

Diffusable

Plus d'informations

Résumé

Les métaheuristiques sont des techniques d’optimisation indépendantes des problèmes traités. Elles ne profitent pas d’une spécificité du problème et, par conséquent, peuvent fournir des cadres généraux qui peuvent être appliqués à de nombreuses classes de problèmes. Les métaheuristiques peuvent fournir une stratégie de guidage dans la conception des heuristiques pour résoudre des problèmes d’optimisation spécifiques. Leur utilisation dans de nombreuses applications montre leur efficacité pour résoudre des problèmes importants et complexes. De nos jours, les métaheuristiques appliquées à la solution des problèmes d’optimisation ont évolué vers l’intégration d’autres techniques d’optimisation, de sorte que les méthodes de résolution peuvent bénéficier des avantages de chacune des composantes. Le travail dans cette thèse vise à contribuer à l’´etude des problèmes de tournées de véhicules avec des visites optionnelles en fournissant un opérateur à base de programmation dynamique intégré dans un processus métaheuristique générique. L’opérateur récupère le tour optimal de clients à visiter, répondant aux contraintes du problème, tout en optimisant l’objectif défini. L’opérateur pose le problème de la sélection des meilleurs clients à visiter comme un problème de plus court chemin avec contraintes de ressources sur un graphe auxiliaire dirigé acyclique représentant les choix de visite possibles. Dans les problèmes de tournées de véhicules avec des visites optionnelles, les clients à servir ne sont pas connus a priori et cela rend plus difficile à résoudre le problème qu’un problème de routage classique qui est lui-même déjà NP-difficile. Les problèmes de tournées avec des visites optionnelles trouvent des applications dans des domaines multiples et variés tels que la conception de la distribution, la logistique humanitaire, la prestation des soins de santé, le tourisme, le recrutement, la collection ou la livraison de marchandises et patrouille en milieu urbain.

Abstract

Metaheuristics are problem independent optimisation techniques. As such, they do not take advantage of any specificity of the problem and, therefore, can provide general frameworks that may be applied to many problem classes. These iterative upper level methodologies can furnish a guiding strategy in designing subordinate heuristics to solve specific optimisation problems. Their use in many applications shows their efficiency and effectiveness to solve large and complex problems. Nowadays, metaheuristics applied to the solution of optimisation problems have shifted towards integrating other optimisation techniques, so that solution methods benefit from the advantages each offers. This thesis seeks to contribute to the study of vehicle routing problems with optional visits by providing a dynamic programming-based operator that works embedded into a generic metaheuristic. The operator retrieves the optimal tour of customers to visit, satisfying the side constraints of the problem, while optimising the defined objective. The operator formulates the problem of selecting the best customers to visit as a Resource Constrained Elementary Shortest Path Problem on an auxiliary directed acyclic graph where the side restrictions of the problem considered act as the constraining resource. In vehicle routing problems with optional visits, the customers to serve are not known a priori and this fact leaves a more difficult to solve problem than a classic routing problem, which per se is already NP-hard. Routing problems with optional visits find application in multiple and diverse areas such as bimodal distribution design, humanitarian logistics, health care delivery, tourism, recruitment, hot rolling production, selected collection or delivery, and urban patrolling among others.

Mots-Clés / Keywords
Metaheuristics; Dynamic programming; Vehicle routing; Métaheuristiques; Programmation dynamique; Tournées de véhicules;

136813
16032
19/01/2016

Recherche de flots stables dans des réseaux de transport multi-agents

N.CHAABANE

ROC

Doctorat : INSA de Toulouse, 19 Janvier 2016, 122p., Président: A.SOUKHAL, Rapporteurs: M.BAIOU, M.LABBE, Examinateurs: A.MOUKRIM, D.QUADRI, Directeurs de thèse: C.BRIAND, M.J.HUGUET , N° 16032

Lien : https://tel.archives-ouvertes.fr/tel-01291878

Diffusable

Plus d'informations

Abstract

In this work, multi-agent network ow problems are addressed. Three types of agents are considered, namely the producer, transportation and customer agents and various network topologies are tackled. Every transportation agent controls the capacities of a set of elementary routes (arcs), each one having a capacity that can be increased up to a certain point at a given cost. The other agents (i.e., customers/producers) are interesting in maximizing their ow of products. For that aim, we assume that they o er to the transportation agents a reward that is proportional to the realized ow value. This particular multi-agent framework is referred to as a multi-agent network expansion game. The transportation agent's strategy consists in deciding upon the capacity of its arcs, an extra-cost being incurred for any capacity expansion. It receives in return a part of the total reward. It is interested in the maximization of its profit and behaves accordingly. Beside that, the producers/customers' strategies consist in deciding the sharing policy for their reward for maximizing their own ow of products. The total network ow value eventually depends on all agents' strategies. We take interest in characterizing and finding particular stable strategies (i.e., Nash Equilibria) that are of interest for this game under various assumptions. Based on this characterization, several cases are de ned and studied. The analysis of the complexity of some decision problems is made. We particularly focus on the problem of finding a Nash Equilibrium that maximizes the value of the total ow. We prove that this problem is NP-hard in the strong sense and show how such a strategy can be characterized considering paths in specific reduced agent-networks. We also provide a mixed integer linear programming (MILP) formulation that solves the problem in the case of a single producer/customer agent and a set of transportation agents. Computational experiments are provided to prove the effectiveness of our approach.

Résumé

Nous considérons dans ce travail, des problèmes d'optimisation dans des graphes de flot multi-agent. Trois types d'agents sont considérés : les agents producteurs, transporteurs et usagers et différentes variétés de topologies de réseaux sont abordées. Chaque agent transporteur contrôle la capacité d'un ensemble de routes élémentaires (arcs), ayant cha- cun une capacité qui peut être augmentée jusqu'à une valeur maximale moyennant un coût fixé. Les autres agents (i.e., usagers/producteurs) sont intéressés par la maximi- sation du flot qu'ils recoivent. Dans ce but, ces derniers offrent une récompense aux agents transporteurs, cette récompense est proportionnelle à la valeur du flot reçu. Ce contexte multi-agent particulier est appelé jeu expansion de réseau multi-agent. La stra- tégie d'un agent transporteur consiste à décider de la capacité de ses arcs sachant qu'un coût supplémentaire est encouru pour toute expansion unitaire de capacité. Il reçoit en contrepartie une part de la récompense. Il est intéressé par la maximisation de son profit et se comporte en conséquence. En outre, la stratégie d'un agent producteur/usa- ger consiste à décider de la politique de partage de sa récompense afin de maximiser le flot qu'il reçoit. Le fl ot total réalisé dépend finalement des stratégies de tous les agents. Dans ces jeux d'expansion de réseau multi-agent, nous nous intéressons à caractériser des stratégies stables (i.e., Equilibre de Nash) selon diverses hypothèses. En se basant sur cette caractérisation, différents cas sont définis et étudiés. L'analyse de la complexité de quelques problèmes de décision est présentée dans ce manuscrit. Nous nous intéressons particulièrement au problème de recherche d'un équilibre de Nash qui maximise la valeur du fl ot total circulant dans le réseau. Nous montrons que ce problème est NP-diffcile au sens fort et nous montrons comment une telle stratégie peut être caractérisée par des che- mins spécifiques dans des graphes résiduels. Nous proposons également un programme linéaire à variables mixtes (PLM) qui résout le problème dans le cas d'un seul agent producteur/usager et un ensemble d'agents transporteurs. Des résultats expérimentaux sont fournis pour prouver l'efficacité de notre approche.

Mots-Clés / Keywords
Réseau de flot multi-agent; Equilibre de Nash; Complexité; Jeu d'expansion; PLM; Multi-agent network flow; Nash equilibria; Complexity; Expansion game; MILP;

136281
15174
13/05/2015

Search, propagation, and learning in sequencing and scheduling problems

M.SIALA

ROC

Doctorat : INSA de Toulouse, Mai 2015, 193p., Président: C.SOLNON, Rapporteurs: F.BACCHUS, C.BESSIERE, Examinateurs: H.CAMBAZARD, G.KATSIRELOS, Directeurs de thèse: C.ARTIGUES, E.HEBRARD , N° 15174

Lien : https://tel.archives-ouvertes.fr/tel-01164291

Diffusable

Plus d'informations

Résumé

Les problèmes de séquencement et d’ordonnancement forment une famille de problèmes combinatoires qui implique la programmation dans le temps d’un ensemble d’opérations soumises à des contraintes de capacités et de ressources. Nous contribuons dans cette thèse à la résolution de ces problèmes dans un contexte de satisfaction de contraintes et d’optimisation combinatoire. Nos propositions concernent trois aspects différents : comment choisir le prochain noeud à explorer (recherche) ? comment réduire efficacement l’espace de recherche (propagation) ? et que peut-on apprendre des échecs rencontrés lors de la recherche (apprentissage) ? Nos contributions commencent par une étude approfondie des heuristiques de branchement pour le problème de séquencement de chaîne d’assemblage de voitures. Cette évaluation montre d’abord les paramètres clés de ce qui constitue une bonne heuristique pour ce problème. De plus, elle montre que la stratégie de branchement est aussi importante que la méthode de propagation. Deuxièmement, nous étudions les mécanismes de propagation pour une classe de contraintes de séquencement à travers la conception de plusieurs algorithmes de filtrage. En particulier, nous proposons un algorithme de filtrage complet pour un type de contrainte de séquence avec une complexité temporelle optimale dans le pire cas. Troisièmement, nous investiguons l’impact de l’apprentissage de clauses pour résoudre le problème de séquencement de véhicules à travers une nouvelle stratégie d’explication réduite pour le nouveau filtrage. L’évaluation expérimentale montre l’importance de l’apprentissage de clauses pour ce problème. Ensuite, nous proposons une alternative pour la génération retardée de variables booléennes pour encoder les domaines. Finalement, nous revisitons les algorithmes d’analyse de conflits pour résoudre les problèmes d’ordonnancement disjonctifs. En particulier, nous introduisons une nouvelle procédure d’analyse de conflits dédiée pour cette famille de problèmes. La nouvelle méthode diffère des algorithmes traditionnels par l’apprentissage de clauses portant uniquement sur les variables booléennes de disjonctions. Enfin, nous présentons les résultats d’une large étude expérimentale qui démontre l’impact de ces nouveaux mécanismes d’apprentissage. En particulier, la nouvelle méthode d’analyse de conflits a permis de découvrir de nouvelle bornes inférieures pour des instances largement étudiées de la littérature.

Abstract

Sequencing and scheduling involve the organization in time of operations subject to capacity and resource constraints. We propose in this dissertation several improvements to the constraint satisfaction and combinatorial optimization methods for solving these problems. These contributions concern three different aspects: how to choose the next node to explore (search)? how much, and how efficiently, one can reduce the search space (propagation)? and what can be learnt from previous failures (learning)? Our contributions start with an empirical study of search heuristics for the well known car-sequencing problem. This evaluation characterizes the key aspects of a good heuristic and shows that the search strategy is as important as the propagation aspect in this problem. Second, we carefully investigate the propagation aspect in a class of sequencing problems. In particular, we propose an algorithm for filtering a type of sequence constraints which worst case time complexity is lower than the best known upper bound, and indeed optimal. Third, we investigate the impact of clause learning for solving the car-sequencing problem. In particular, we propose reduced explanations for the new filtering. The experimental evaluation shows compelling evidence supporting the importance of clause learning for solving efficiently this problem. Next, we revisit the general approach of lazy generation for the Boolean variables encoding the domains. Our proposition avoids a classical redundancy issue without computational overhead. Finally, we investigate conflict analysis algorithms for solving disjunctive scheduling problems. In particular, we introduce a novel learning procedure tailored to this family of problems. The new conflict analysis differs from conventional methods by learning clauses whose size are not function of the scheduling horizon. Our comprehensive experimental study with traditional academic benchmarks demonstrates the impact of the novel learning scheme that we propose. In particular, we find new lower bounds for a well known scheduling benchmark.

Mots-Clés / Keywords
Artificial intelligence; Constraint programming; Boolean satisfiability; Combinatorial optimization; Sequencing; Scheduling; Intelligence artificielle ; Programmation par contraintes; Satisfiabilité booléenne; Optimisation combinatoire; Séquencement; Ordonnancement;

134663
14577
17/12/2014

Modèles mathématiques et techniques d’optimisation non linéaire et combinatoire pour la gestion d'énergie d’un système multi-source : vers une implantation temps-réel pour différentes structures électriques de véhicules hybrides

Y.GAOUA

ROC

Doctorat : INP de Toulouse, 17 Décembre 2014, 193p., Président: T.M.GUERRA, Rapporteurs: M.JACOMINO, A.OULAMARA, Examinateurs: B.LE CUN, B.ROBYNS, Directeurs de thèse: S.CAUX, P.LOPEZ , N° 14577

Lien : https://tel.archives-ouvertes.fr/tel-01104983

Diffusable

Plus d'informations

Abstract

Managing the distribution of electrical energy in a multi-source system (hybrid electric vehicle) is paramount. It increases the system performance by minimizing the fuel used by the primary source, while respecting demand, the differents operating constraints of the energy chain and system security. In this thesis, where the mission profile is known, a combinatorial approach is proposed by modeling the problem of energy management as an optimization problem with constraint satisfaction. The problem is solved using an exact method from operations research, leading to optimal solutions with reduced computation time in comparison with those obtained by applying dynamic programming or optimal control strategies. To test the perturbation sensitivity, robustness study is conducted, based on the analysis of the worst-case solution of the worst scenario, which can be achieved on the vehicle mission profile. In practical cases, the vehicle demand is unknown, and we have only the information about the instantaneous demand, which depends on driving style of the driver. In order to manage on line the energy of the vehicle, an on-line algorithm, based on a fuzzy approach is developed. To measure the quality of the fuzzy solution obtained, a performance study is carried out (finding the optimum solution), using an off-line optimization under reference mission profiles, based on non-linear modeling of the power management problem. The results were used to validate the quality of the resulting fuzzy solution.

Résumé

La gestion de la distribution de l’énergie électrique dans un système multi-source (véhicule hybride électrique) est primordiale. Elle permet d’augmenter les performances du système en minimisant la consommation de combustible utilisée par la source principale, tout en respectant la demande et les différentes contraintes de fonctionnement de la chaîne énergétique et de sécurité du système. Dans cette thèse, dans le cas où le profil de mission est connu, une approche combinatoire est proposée en modélisant le problème de gestion d’énergie sous la forme d’un problème d’optimisation avec satisfaction des contraintes. Celui-ci est résolu par une méthode exacte issue de la recherche opérationnelle, conduisant à des solutions optimales en des temps de calcul fortement réduits en comparaison avec ceux obtenus par l’application de la programmation dynamique ou la commande optimale. Pour éprouver la sensibilité aux perturbations, une étude de robustesse est menée sur la base de l’analyse de la solution de pire cas d’un scénario sur des profils de mission d’un véhicule. Les cas pratiques d’utilisation imposent de ne connaître la demande du moteur électrique qu’à l’instant présent, selon le mode de conduite du chauffeur. Afin de gérer l’énergie du véhicule en temps réel, un algorithme en ligne, basé sur une approche de type floue, est développé. Pour mesurer la qualité de la solution floue obtenue, une étude de performance est réalisée (recherche de l’optimum global), en ayant recours à une optimisation hors ligne sur des profils de mission de référence, basée sur une modélisation non linéaire du problème de gestion d’énergie. Les résultats obtenus ont permis de valider la qualité de la solution floue résultante.

Mots-Clés / Keywords
Gestion de l'énergie; Optimisation combinatoire; Energie distribuée; Implantation temps-réel; Recherche opérationnelle; Robustesse; Energy management; Combinatorial optimisation; Smart grid; Real-time implantation; Operations research; Robustness;

133814
14205
17/04/2014

Planification d'une chaîne logistique: approche par satisfaction de contraintes dynamiques

M.TROJET

ROC

Doctorat : INSA de Toulouse, 17 Avril 2014, 162p., Président: F.ZEGHAL, Rapporteurs: R.DUPAS, O.KORBAA, Examinateurs: H.BOUCHRIHA, P.ESQUIROL, A.ZGHAL, Directeurs de thèse: P.LOPEZ , N° 14205

Lien : http://tel.archives-ouvertes.fr/tel-00996957

Diffusable

Plus d'informations

Résumé

Le sujet de thèse porte sur la planification tactique et opérationnelle d’une chaîne logistique dans un contexte dynamique. Nous proposons un modèle de planification basé sur une structure décisionnelle à deux niveaux. Adoptant un processus dynamique permettant d’actualiser les données à chaque étape de planification, le premier niveau planifie la production en recherchant le meilleur compromis entre les leviers décisionnels disponibles liés aux aspects capacité et coût de production. Le deuxième niveau établit un ordonnancement agrégé des opérations de fabrication en minimisant les en-cours. Le recours à une structure décisionnelle intégrée nous a conduit à établir une interaction entre les niveaux supérieur et inférieur de décision, mise en oeuvre par des contraintes dites de conservation d’énergie. Notre approche est modélisée sous la forme d’un problème de satisfaction de contraintes (CSP, Constraint Satisfaction Problem) et évaluée par simulation dans un contexte de données incertaines. Nous avons mené différentes expérimentations portant sur la variation de la demande, la variation de la capacité et la re-planification de la demande. Toutes les expérimentations sont réalisées par deux méthodes de résolution différentes : une méthode basée sur un CSP statique et une méthode basée sur un CSP dynamique. La performance d’une solution de planification/ordonnancement est renseignée par l’ensemble des mesures de la stabilité et de la robustesse. Les expérimentations réalisées offrent une démonstration de la performance de la méthode de résolution basée sur un CSP dynamique par rapport à la méthode statique.

Abstract

This work focuses on the supply chain operational and tactical planning problem in an uncertain environment. We propose a tactical planning model, based on a two-level decisional structure. Adopting a dynamic process, which enables data updating at each planning step, the first level performs a plan by searching for the best compromise between available decision-making levers for production costs and capacity. The second level establishes an aggregate scheduling of production tasks by minimizing the total weighted completion time. The use of an integrated decision structure involves interaction between the upper and lower decision levels constraints, implemented by constraints known as energy conservation constraints. Our approach is formulated according to a constraint satisfaction problem (CSP) and evaluated by simulation under uncertain data. For this, we have developed various experiments related to the variation of customer demand, resource capacity, and the re-planning of demand. All the experiments are carried out by two different methods: a method based on a static CSP and a method based on a dynamic CSP. The performance of a scheduling/planning solution is reported through a set of robustness and stability measurements. Results of experiments confirm the performance of the method based on a dynamic CSP.

Mots-Clés / Keywords
Chaîne Logistique; Planification / Ordonnancement; Approche intégrée; Problèmes de satisfaction de contraintes; CSP dynamique; Stabilité; Robustesse; Supply chain; Planning / Scheduling; Integrated approach; Dynamic Constraint Satisfaction; Stability; Robustness;

131967
13793
03/12/2013

Optimisation combinatoire multi-objectif : des méthodes aux problèmes, de la Terre à (presque) la Lune

N.JOZEFOWIEZ

ROC

Habilitation à diriger des recherches : 3 Décembre 2013, 215p., Président: F.SEMET, Rapporteurs: M.GENDREAU, P.MAHEY, D.VANDERPOOTEN, Examinateurs: G.LAPORTE, F.MESSINE, D.VIGO , Directeur: P.LOPEZ , N° 13793

Lien : https://tel.archives-ouvertes.fr/tel-01104895

Diffusable

Plus d'informations

Résumé

Ce manuscrit présente une partie des travaux que j'ai réalisés à la suite de ma thèse. Le document se focalise particulièrement sur les études menées dans le cadre de l'optimisation combinatoire multi-objectif. Une première partie se consacre aux méthodes d'optimisation en général. Après avoir fixé un cadre pour les propriétés souhaitées dans les méthodes proposées, trois points sont présentés. Le premier porte sur la définition d'opérateurs de croisement pour les algorithmes génétiques qui prennent en compte l'ensemble des objectifs. Le second point est sur la définition d'un algorithme de séparations et coupes pour l'optimisation multi-objectif. Le dernier point est l'étude de l'utilisation de la génération de colonnes en optimisation combinatoire multi-objectif pour le calcul de bornes inférieures. La seconde moitié du mémoire porte sur l'application de ces méthodes. Deux problèmes de tournées de véhicules sont tout d'abord présentés. Le premier problème consiste en la prise en compte de labels associés aux arêtes du graphe. Le second problème est une variante où une notion de couverture est utilisée pour ne pas avoir à visiter tous les sommets du graphe. Une dernière application est la sélection et la planification de prises de vue par un satellite d'observation de la Terre dans un cadre multi-utilisateur où l'on souhaite garantir une équité entre les utilisateurs.

Abstract

This manuscript presents some of the works I have done since I obtained my Ph.D. degree. The document focuses primarily on studies dealing with multi-objective combinatorial optimization. A first part is dedicated to optimization methods in general. First, desired properties of the methods are exposed as well as a framework to study multi-objective problems. Then, three contributions are done. The first one is about crossover operators for genetic algorithm. It is shown how crossover operators that consider multiple objective at once can be designed. The second point is about the use of branch-and-cut algorithms for multi-objective optimization. Mechanisms are proposed that take into account particularities linked to the presence of multiple objective. Finally, the use of column generation to compute dual bounds is investigated. The remaining of the document is about application to problems. First, two vehicle routing problems are studied. The first one is a variant where labels are associated to the edges of the graph. The second problem deals with covering issues in vehicle routing problems. Every node must not be visited but they must be covered by the solution. The last application is selection and planning of requests for an Earth observing satellite. The study is done in a multi-user context and solutions that are fair between the users are searched.

132949
13570
03/12/2013

Column generation for bi-objective integer linear programs : application to bi-objective vehicle routing problems

B.M.SARPONG

ROC

Doctorat : INSA de Toulouse, 3 Décembre 2013, 128p., Président: D.FEILLET, Rapporteurs: C.DHAENENS, M.LUBBECKE, Examinateurs: D.VANDERPOOTEN, Directeurs de thèse: N.JOZEFOWIEZ, C.ARTIGUES , N° 13570

Lien : http://tel.archives-ouvertes.fr/tel-00919861

Diffusable

Plus d'informations

Résumé

L'optimisation multi-objectif concerne la résolution de problèmes pour lesquels plusieurs objectifs (ou critères) contradictoires sont pris en compte. Contrairement aux problèmes d'optimisation ayant un seul objectif, un problème multi-objectif ne possède pas une valeur optimale unique mais plutôt un ensemble de points appelés "ensemble non dominé". Les bornes inférieures et supérieures d'un problème multi-objectif peuvent être également décrites par des ensembles. Dans la pratique, les variables utilisées en optimisation multiobjectif représentent souvent des objets non fractionnables et on parle alors de problèmes multi-objectif en nombres entiers. Afin d'obtenir de meilleures bornes qui peuvent être utilisées dans la conception de méthodes exactes, certains problèmes sont formulés avec un nombre exponentiel de variables de décision et ces problèmes sont résolus par la méthode de génération de colonnes. Les travaux de cette thèse visent à contribuer à l'étude de l'utilisation de la génération de colonnes en programmation linéaires en nombres entiers multi-objectif. Pour cela nous étudions un problème de tournées de véhicules bi-objectif qui peut être considéré comme une généralisation de plusieurs autres problèmes de tournées de véhicules. Nous proposons des formulations mathématiques pour ce problème et des techniques pour accélérer le calcul des bornes inférieures par génération de colonnes. Les sous-problèmes qui doivent être résolus pour le calcul des bornes inférieures ont une structure similaire. Nous exploitons cette caractéristique pour traiter simultanément certains sous-problèmes plutôt qu'indépendamment.

Abstract

Multi-objective optimization deals with finding solutions to problems for which several objectives (or criteria) are considered. Unlike in single objective optimization, the optimal value of a multi-objective problem is a set of points called “the nondominated set”. Lower and upper bounds of a multi-objective problem can also be described using sets. For most practical problems, the variables considered in multi-objective optimization represent non fractionable items and thus we talk of multi-objective integer programs. In order to obtain good lower and upper bounds that can be used in the design of exact methods, some problems are usually formulated with an exponential number of decision variables and these problems are solved by column generation. The work of this thesis seeks to contribute to the study of the use of column generation in multi-objective integer linear programming. We do this by studying a bi-objective vehicle routing problem which may be seen as a generalization of several other vehicle routing problems. We propose mathematical formulations for this problem and also find ways to quickly compute lower bounds by column generation. Since the subproblems solved when computing lower bounds have similar structures, we propose intelligent ways of treating some of these subproblems simultaneously rather than independently.

Mots-Clés / Keywords
Integer linear programming; Column generation; Multi-objective optimization; Combinatorial optimization; Vehicle routing; Programmation linéaire en nombres entiers; Génération de colonnes; Optimisation multi-objectif; Optimisation combinatoire; Tournées de véhicules;

130930
Les informations recueillies font l’objet d’un traitement informatique destiné à des statistiques d'utilisation du formulaire de recherche dans la base de données des publications scientifiques. Les destinataires des données sont : le service de documentation du LAAS.Conformément à la loi « informatique et libertés » du 6 janvier 1978 modifiée en 2004, vous bénéficiez d’un droit d’accès et de rectification aux informations qui vous concernent, que vous pouvez exercer en vous adressant à
Pour recevoir une copie des documents, contacter doc@laas.fr en mentionnant le n° de rapport LAAS et votre adresse postale. Signalez tout problème de dysfonctionnement à sysadmin@laas.fr. http://www.laas.fr/pulman/pulman-isens/web/app.php/