Retour au site du LAAS-CNRS

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

48documents 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
16392
02/12/2016

Sur la modélisation et la commande de l’anesthésie en milieu clinique

S.ZABI

MAC

Doctorat : Université de Toulouse III - Paul Sabatier, 2 Décembre 2016, 183p., Président: P.DANES, Rapporteurs: M.JUNGERS, M.ALAMIR, Examinateurs: C.IONESCU, Directeurs de thèse: I.QUEINNEC , N° 16392

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

Diffusable

Plus d'informations

Abstract

This thesis deals with the modelling and control of anesthesia from a theoretical and formal angle. The general anesthesia of a patient during an operation consists for the anesthesiologist in checking the hypnotic and analgesic state of the patient (avoid over or under dosage) by adjusting the perfusion of analgesic and/or hypnotics substances based on clinical indicators such as BIS for hypnosis or pupillary surface variation for analgesia. This manuscript consists of three parts. The rst denes the concepts and key words used in the eld of anesthesia, presents an introduction to the modelling and control of anesthesia from the viewpoint of a control systems engineering, recalls the characteristics and constraints of control of the anesthesia systems and establishes a state of the art of works of the literature. The second part concerns the control of hypnosis which is performed in two phases : induction and maintenance. In the rst phase (induction), a minimal time control is calculated to bring the patient from his awakening state to the neighbourhood of a target equilibrium corresponding to an objective of the BIS. Once the patient state is close to the target state, the second phase (maintenance) consists in ensuring that the patient state remains in an invariant set where the BIS is guaranteed between 40 and 60 and possibly follows constant references . In this phase, the synthesis of the control laws (state feedback and dynamic output feedback) takes into account the saturation of the control, the positivity of the system, the variability of the patients, ... In the third part,we begin by proposing a novel indicator for the depth of analgesia and modelling the variation of the pupillary surface. Taking into account the quantication of the measures of this indicator, we propose the synthesis of a dynamic output feedback control. Then, a stability analysis is carried out taking into account the sampling of the measures.

Résumé

138217
16470
02/12/2016

A data-based approach for dynamic classification of functional scenarios oriented to industrial processes

N.BARBOSA ROA

DISCO

Doctorat : Université de Toulouse III - Paul Sabatier, 2 Décembre 2016, 212p., Président: M.V.LE LANN, Rapporteurs: C.V.ISAZA NARVAEZ, R.GOURIVEAU, Examinateurs: G.D.ZAPATA , Directeurs de thèse: L.TRAVE-MASSUYES, V.H.GRISALES PALACIO , N° 16470

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

Diffusable

Plus d'informations

Abstract

The main objective of this thesis is to propose a dynamic clustering algorithm that can handle not only dynamic data but also evolving distributions. This algorithm is particularly fitted for the monitoring of processes generating massive data streams, but its application is not limited to this domain. The main contributions of this thesis are: 1. Contribution to dynamic clustering by the proposal of an approach that uses distance- and density-based analyses to cluster non-linear, non-convex, overlapped data distributions with varied densities. This algorithm, that works in an online fashion, fusions the learning and classification stages allowing to continuously detect and characterize new concepts and at the same time classifying the input samples, i.e. which means recognizing the current state of the system in a supervision application. 2. Contribution to feature extraction by the proposal of a novel approach to extract dynamic features. This approach ,based on piece-polynomial approximation, allows to represent dynamic behaviors without losing magnitude related information and to reduce at the same time the algorithm sensitivity to noise corrupting the signals. 3. Contribution to automatic discrete event modeling for evolving systems by exploiting informations brought by the clustering. The generated model is presented as a timed automaton that provides a high-level representation of the behavior of the process. The latter is adaptive in the sense that its construction is elaborated following the discovery of new concepts by the clustering algorithm.

Résumé

L'objectif principal de cette thèse est de développer un algorithme dynamique de partitionnement de données (classification non supervisée ou ‘’clustering’’ en anglais) qui ne se limite pas à des concepts statiques et qui peut gérer des distributions qui évoluent au fil du temps. Cet algorithme peut être utilisé dans les systèmes de surveillance du processus, mais son application ne se limite pas à ceux-ci. Les contributions de cette thèse peuvent être présentées en trois groupes: 1. Contributions au partitionnement dynamique de données en utilisant : un algorithme de partitionnement dynamique basé à la fois sur la distance et la densité des échantillons est présenté. Cet algorithme ne fait aucune hypothèse sur la linéarité ni la convexité des groupes qu'il analyse. Ces clusters, qui peuvent avoir des densités différentes, peuvent également se chevaucher. L'algorithme développé fonctionne en ligne et fusionne les étapes d'apprentissage et de reconnaissance, ce qui permet de détecter et de caractériser de nouveaux comportements en continu tout en reconnaissant l'état courant du système. 2. Contributions à l'extraction de caractéristiques : une nouvelle approche permettant d'extraire des caractéristiques dynamiques est présentée. Cette approche, basée sur une approximation polynomiale par morceaux, permet de représenter des comportements dynamiques sans perdre les informations relatives à la magnitude et en réduisant simultanément la sensibilité de l'algorithme au bruit dans les signaux analysés. 3. Contributions à la modélisation de systèmes à événements discrets évolutifs a partir des résultats du ‘clustering’ : les résultats de l'algorithme de partitionnement sont utilisés comme base pour l'élaboration d'un modèle à événements discrets du processus. Ce modèle adaptatif offre une représentation du comportement du processus de haut niveau sous la forme d'un automate dont les états représentent les états du processus appris par le partitionnement jusqu'à l'instant courant et les transitions expriment l'atteignabilité des états.

Mots-Clés / Keywords
Dynamic clustering; Fault diagnosis; Monitoring; Pattern recognition; System tracking;

138513
16508
22/11/2016

Développement du système d'analyse des données recueillies par les capteurs et choix du groupement de capteurs optimal pour le suivi de la cuisson des aliments dans un four.

T.MONROUSSEAU

DISCO

Doctorat : 22 Novembre 2016, 115p. , N° 16508

Lien : Président: L.TRAVE-MASSUYES, Rapporteurs: S.CHARBONNIER, P.THOMAS, Examinateurs: C.TRELEA, S.VOLATIER, Directeurs de thèse: M.V.LE LANN

Non diffusable

138894
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
16509
25/10/2016

On distributed control analysis and design for multi-agent systems subject to limited information

L.DAL COL

MAC

Doctorat : INSA de Toulouse, 25 Octobre 2016, 149p., Président: M.KIEFFER, Rapporteurs: M.D.DI BENEDETTO, M.C.TURNER, Examinateurs: D.DIMAROGONAS, P.FRASCA, Directeurs de thèse: S.TARBOURIECH, L.ZACCARIAN , N° 16509

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

Diffusable

Plus d'informations

Résumé

Les systèmes multi-agents sont des systèmes dynamiques composes par plusieurs éléments qui interagissent entre eux. Ces éléments sont appelés agents. Un agent est un système dynamique caractérisé par deux propriétés. La première est que les agents sont autonomes— c’est-a-dire qu’ils ne sont pas dirigés par l’environnement extérieur et ils peuvent évoluer selon un comportement auto-organisé. La seconde est que les agents sont capables de communiquer entre eux pour accomplir des tâches complexes, telles que la coopération, la coordination et la résolution de conflits. L’un des problèmes courants concernant les systèmes multi-agents est la synchronisation. Les agents sont synchronisés lorsque leur évolution dans le temps converge vers une trajectoire commune. Plusieurs applications du monde réel peuvent être conceptualisé comme des problèmes de synchronisation des systèmes multi-agents : par exemple, l’alignement en vitesse (flocking en anglais), et le contrôle de la formation du mouvement de groupes cohérents. La synchronisation des systèmes multi-agents peut être obtenue grâce à différentes techniques de contrôle. Dans cette thèse nous proposons des méthodes de contrôle centralisées et distribuées pour la synchronisation des systèmes multi-agents. Nous développons des conditions nécessaires et suffisantes pour la synchronisation des systèmes multi-agents, composes par des agents identiques et linéaires qui ne changent pas dans le temps, en utilisant une approche Lyapunov. Ces conditions sont utilisées pour la conception de lois de contrôles distribuées. Ensuite, nous étendons les résultats aux systèmes multi-agents soumis `a des perturbations externes, assurant un niveau de performance désiré grâce a une technique de contrôle de type 𝐻∞. Enfin, nous étendons l’analyse aux systèmes multi-agents avec contraintes sur les actionneurs, en utilisant des techniques de contrôle anti-windup. Nous évaluons l’efficacité et les performances des stratégies de contrôle proposées dans plusieurs simulations, dont deux d’entre elles sont inspirées par des applications issues du monde réel. La première est le contrôle du vol en formation d’avions, et la seconde est l’analyse de la transmission de contenus vidéo comme un problème de synchronisation. Nous comparons aussi les résultats obtenus avec des techniques de contrôle alternatives.

Abstract

Multi-agent systems are dynamical systems composed of multiple interacting elements known as agents. Each agent is a dynamical system with two characteristics. First, it is capable of autonomous action—that is, it is able to evolve according to a self-organised behavior, which is not influenced by the external environment. Second, it is able to exchange information with other agents in order to accomplish complex tasks, such as coordination, cooperation, and conflict resolution. One commonly studied problem in multi-agent systems is synchronization. The agents are synchronized when their time evolutions converge to a common trajectory. Many real-world applications, such as flocking and formation control, can be cast as synchronization problems. Agent synchronization can be achieved using different approaches. In this thesis, we propose distributed and centralized control paradigms for the synchronization of multi-agent systems. We develop necessary and sufficient conditions for the synchronization of multi-agent systems, composed by identical linear time-invariant agents, using a Lyapunov-based approach. Then we use these conditions to design distributed synchronization controllers. Then, we extend this result to multi-agent systems subject to external disturbances enforcing disturbance rejection with 𝐻∞ control techniques. Furthermore, we extend the analysis to multi-agent systems with actuator constraints using LMI-based anti-windup techniques. We test the proposed control design strategies in simulated examples among which two are inspired by real-world applications. In the first, we study airplane formation control as a synchronization problem. In the second, we analyze the delivery of video streams as a synchronization problem and we compare the results to existing controllers.

Mots-Clés / Keywords
Consensus and synchronization; Distributed control; Lyapunov approach; Multi-agent systems; Nonlinear systems;

138913
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

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

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
16501
18/10/2016

Estimation of uncertain dynamical systems and related properties. Application to health-monitoring.

C.JAUBERTHIE

DISCO

Habilitation à diriger des recherches : 18 Octobre 2016, 153p., Président: D.MAQUIN, Rapporteurs: A.EL BADIA, L.JAULIN, M.KIEFFER, Examinateurs: M.COMBACAU, L.DENIS-VIDAL, F.LE GALL, Garant: L.TRAVE-MASSUYES , N° 16501

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

Diffusable

Plus d'informations

Résumé

Dans ce travail, nous nous intéressons principalement à la surveillance préventive des systèmes non linéaires à incertitudes bornées, c’est-à-dire des systèmes pour lesquels les incertitudes ne sont définies que par leur appartenance à des intervalles. Pour cela, nous nous sommes placés dans un contexte dit « ensembliste » dans lequel nous avons pu étendre deux propriétés importantes largement étudiées en contexte stochastique qui sont l’identifiabilité et la diagnosticabilité. Au delà des définitions conceptuelles requises par ce travail, nous avons proposé des outils liés à l’algèbre différentielle permettant de vérifier ces deux propriétés. L’impact de l’identifiabilité ensembliste sur les résultats d’une estimation de paramètres a également été analysé, l’estimation de paramètres étant l’une des approches retenues pour la détection et l’isolation de défauts dans ce travail. Nous avons également cherché à améliorer l’estimation de paramètres en développant des critères pour la planification d’expériences, consistant ici en l’optimisation des conditions initiales, entrées et/ou période d’échantillonnage. Ces critères ont été appliqués à deux cas d’étude (pharmacocinétique et aéronautique) avec de très bons résultats. Par ailleurs, nous nous sommes intéressés à la modélisation des systèmes à incertitudes « mixtes », combinant des incertitudes bornées et stochastiques, en proposant notamment une amélioration du filtre de Kalman par intervalles. Le travail réalisé formalise des problèmes non abordés auparavant et pose des jalons pour les recherches futures.

Mots-Clés / Keywords
Diagnosticabilité ensembliste; Estimation; Identifiabilité ensembliste; Incertitudes bornées; Incertitudes mixtes; Planification d'expériences ensembliste; Set-membership diagnosability; Set-membership identifiability; Bounded uncertainties; Mixed uncertainties; Set-membership experiment design;

138753
16354
30/09/2016

Approche intégrée de diagnostic et de pronostic pour la gestion de santé des systèmes hybrides sous incertitude

Q.GAUDEL

DISCO

Doctorat : INSA de Toulouse, 30 Septembre 2016, 181p., Président: F.VERNADAT, Rapporteurs: A.GIUA, R.GOURIVEAU, Examinateurs: D.LEFEBVRE, Directeurs de thèse: E.CHANTHERY, P.RIBOT, Membre invité: J.SEN GUPTA , N° 16354

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

Diffusable

Plus d'informations

Abstract

This study takes place in the field of system health management, which aims at developing maintenance aid tools, but also at improving the systems autonomous decision-making in case of failures. In this context, diagnostic techniques determine whether and why the system is down, while prognostic techniques determine when failures will occur and their consequences. If they seem to be correlated, they are usually studied separately because the time scales manipulated by the two processes are very different. This work aims at developing a tool that integrates both diagnosis and prognosis methods for the monitoring of hybrid systems, whose dynamics are both continuous and discrete. The proposed methodology, based on hybrid particle Petri nets, is applied to a planetary rover to demonstrate its usability in real cases through the management of knowledge-based and data-based uncertainty.

Résumé

Cette étude s’inscrit dans le domaine de la gestion de santé des systèmes, qui vise à développer des outils d’aide à la maintenance, mais également à améliorer les prises de décision en autonomie des systèmes en cas de pannes. Dans ce cadre, des techniques de diagnostic déterminent si et pourquoi le système est en panne, alors que des techniques de pronostic déterminent quand les pannes vont survenir et leurs conséquences. Si elles semblent être corrélées, elles sont généralement étudiées séparément, car les échelles de temps manipulées par les deux processus sont très différentes. Ces travaux ont pour objectif de développer un outil intégrant les méthodes de diagnostic et de pronostic pour la surveillance des système hybrides, dont les dynamiques sont à la fois continues et discrètes. La méthodologie proposée, basée sur les réseaux de Petri hybrides particulaires, est appliquée sur un rover planétaire pour démontrer son utilisabilité en cas réel à travers la gestion des incertitudes liées au système et aux données.

Mots-Clés / Keywords
Diagnostic; Pronostic; Systèmes hybrides; Surveillance basée sur les modèles; Gestion de santé; Incertitudes; Diagnosis; Prognosis; Hybrid systems; Model-based monitoring; Health management; Uncertainty;

138373
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
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/