Exact and anytime heuristic search for the Time Dependent Traveling Salesman Problem with Time Windows

Doctorant : Romain FONTAINE

Laboratoire INSA : CITI

École doctorale : ED512 Informatique Et Mathématiques de Lyon

Le problème du voyageur de commerce (TSP, pour Traveling Salesman Problem) dépendant du temps (TD, pour Time Dependent) est une généralisation du TSP qui permet de prendre en compte les conditions de trafic lors de la planification de tournées en milieu urbain : les temps de trajet varient en fonction des horaires de départ au lieu d'être constants. Le TD-TSPTW généralise ce problème en associant à chaque point de passage une fenêtre temporelle (TW, pour Time Window) qui restreint les horaires de visite. Les approches de résolution exactes telles que la programmation linéaire en nombres entiers ou la programmation dynamique passent mal à l’échelle, tandis que les approches heuristiques ne garantissent pas la qualité des solutions obtenues.

Dans cette thèse, nous proposons une nouvelle approche exacte et anytime pour le TD- TSPTW visant à obtenir rapidement des solutions approchées puis à les améliorer progressivement jusqu'à prouver leur optimalité. Nous montrons d'abord comment rapporter le TD-TSPTW à une recherche de meilleur chemin dans un graphe états- transitions. Nous décrivons ensuite des algorithmes permettant de résoudre ce problème en nous concentrant sur les extensions exactes et anytime d'A*, et en proposons une nouvelle par hybridation. Nous montrons comment combiner ces algorithmes avec de la recherche locale — afin de trouver plus rapidement de meilleures solutions — ainsi qu'avec des bornes et de la propagation de contraintes de TW — afin de réduire la taille de l'espace de recherche. Enfin, nous fournissons des résultats expérimentaux visant à
(i) valider nos principaux choix de conception, (ii) comparer notre approche à l'état de l'art en considérant des benchmarks ayant différents degrés de réalisme et différentes granularités temporelles et (iii) comparer ces approches TD à de récents solveurs pour le TSPTW dans le cas constant. Ces résultats montrent que notre approche apporte un bon compromis entre le temps nécessaire pour (i) trouver de bonnes solutions et (ii) trouver des solutions optimales et prouver leur optimalité, aussi bien dans le cas TD que dans le cas constant.

Impact of the viscoelastic properties of the 3D environment on the fate of artificial stem cell spheroids

Doctorant : Lucas LEMARIÉ

Laboratoire : LBTI
École doctorale : ED205 : EDISS (Interdisciplinaire Sciences-Santé)

Le sujet de thèse porte sur l’évaluation de la production de sphéroïdes de cellules humaine iPS aux différentiations induites par les propriétés viscoélastiques de l’environnement 3D. Pour ce faire, différents hydrogels d’alginate-gélatine (3 formulations, à la rigidité significativement différente) ont été préparés et après inclusion de sphéroïdes d’hiPSC, chaque hydrogel est bioimprimé (par microextrusion) et maintenu dans un milieu de culture (DMEM) dépourvu de facteur de croissance. Après 2 semaines de maturation en incubateur, les échantillons sont caractérisés afin mettre en évidence l’impact des propriétés viscoélastiques de ces matrices d’alginate-gélatine sur le devenir des cellules souches.

Prédiction du bruit rayonné d'une structure immergée à partir de données capteurs parcimonieuses

Doctorant : Matthieu DECAUX

Laboratoire INSA : LVA

École doctorale :  ED 162 : MEGA de Lyon (Mécanique, Energétique, Génie civil, Acoustique)

Le bruit rayonné des plateformes navales représente un enjeu majeur. Dans le domaine civil, la nécessité de réduire l'impact des activités humaines sur l'environnement pousse à contrôler et diminuer ce bruit. Dans le domaine militaire, il est primordial de maîtriser la signature acoustique des navires et des sous-marins afin d'avoir un avantage acoustique. L'objectif de cette thèse est de prédire ce bruit rayonné à partir de données accélérométriques. Pour répondre à cet objectif, nous étudions des méthodes permettant de relier des mesures accélérométriques à la pression rayonnée. Nous explorons plusieurs voies : la méthode KH (Kirchhoff-Helmholtz) et l'OTPA (Operational Transfer Path Analysis) en particulier. La méthode KH consiste à discrétiser l'intégrale de rayonnement dans le cas de géométries dont la solution analytique est connue. Le nombre de capteurs est la principale limite de cette approche. L'OTPA, quant à elle, est une méthode permettant d'établir des fonctions dites de "transmissibilité". Elle se caractérise par la résolution directe d'un système "Multiple Input Multiple Output" (MIMO). Elle se décompose en deux étapes : un apprentissage à partir de mesures pour établir une matrice de transmissibilité puis l'utilisation de cette matrice pour reconstruire un nouvel état vibro-acoustique à partir d'un nombre limité de capteurs. Les deux principales limites de la méthode sont le nombre d'états vibratoires lors de la construction de la matrice et l'effet de la nature de l'excitation. Nous testons les performances des approches innovantes sur des systèmes vibroacoustiques de complexité croissante allant d'une plaque à un cylindre immergé. Des études numériques et expérimentales sont menées sur ces cas d'application pour mettre en avant les avantages et inconvénients de chaque approche.

Theoretical foundations of planning in partially observable stochastic games

Doctorant : Aurélien DELAGE

Laboratoire INSA : CITI
École doctorale : ED512 : InfoMaths (Informatique et Mathématiques de Lyon)

Une théorie récente suggère de reformuler les POSG à gain commun en des problèmes non observables via l’introduction d’une statistique suffisante appropriée, ce qui offre des leviers supplémentaires pour rechercher des plans optimaux. Montrer que le principe d’optimalité de Bellman s’applique sur le jeu non-observable permet l’application d’algorithmes efficaces conçus pour les jeux complètement observables (tels que heuristic search value iteration). Les algorithmes exploitant les leviers découverts (par exemple la division des problèmes en sous-problèmes; la généralisation des connaissances entre les sous-problèmes) offrent une garantie de convergence théorique et des résultats compétitifs sur le plan empirique. Cependant, bien que cette approche ait réussi dans des sous-classes de jeux stochastiques partiellement observables à somme nulle et à deux joueurs (zs-POSG), comment l’appliquer dans le cas général reste une question ouverte. De plus, reformuler le problème original en un problème non-observable introduit des problèmes de décision à chaque étape, dont les complexités temporelle et mémorielle deviennent prohibitives pour les jeux de grande envergure. Dans la première contribution de ce manuscrit, nous abordons la première préoccupation et proposons pour la première fois un solveur de type heuristic search value iteration dont nous démontrons qu’il converge vers une solution ε-optimale en temps fini pour n’importe quel zs-POSG. Cela ouvre la voie à une nouvelle famille d’approches prometteuses et complémentaires à celles reposant sur la programmation linéaire ou les méthodes itératives. Dans une deuxième contribution de ce manuscrit, nous examinons des jeux impliquant n joueurs et en supposant (i) qu’ils partagent tous la même fonction de récompense et (ii) que les joueurs sont organisés selon une structure de connaissance hiérarchique (c.-à-d. chaque agent sait ce que son subordonné sait, et ainsi de suite). Nous montrons qu’une spécialisation du schéma algorithmique point-based value iteration tire efficacement parti des leviers offerts par cette sous-classe. Ce travail ouvre la voie à de multiples extensions de la structure hiérarchique proposée tout en conservant le passage à l’échelle du schéma algorithmique proposé. Dans la dernière contribution de ce manuscrit, nous présentons une contribution connexe, bien qu’annexe, aux problèmes d’optimisation min-max avec des propriétés de continuité faibles.
 

Eco-friendly nanoimprinting of TiO2 nanostructures for photonic biosensor application

Doctorante : Huiru REN

Laboratoire INSA : INL
École doctorale : EDA160 : EEA (Électronique, Électrotechnique, Automatique)

Cette thèse vise principalement à développer un procédé à faible impact environnemental pour la fabrication de dispositifs photoniques visant une application d'analyse biomoléculaire à usage unique. Le matériau et le procédé doivent donc offrir de bonnes propriétés optiques pour la biodétection : indice de réfraction élevé, bonne transparence, bonne reproductibilité à l'échelle nanométrique. La stratégie de cette thèse est basée sur la mise au point de dispositifs à des cristaux photoniques dans une couche d'oxyde de titane, fabriqués par une technologie "verte" à fort potentiel : la nanoimpression de sol- gel. Deux voies différentes sont étudiées, la nanoimpression thermique et un processus de soft-NIL.

 

 

Vibration-based damage assessment of rolling element bearings: cage cyclostationarity & trend analysis

Doctorant : Adrien MARSICK

Laboratoire INSA : LVA

École doctorale : ED162 : MEGA de Lyon (Mécanique, Énergétique, Génie civil, Acoustique)

Cette thèse aborde le thème de l'estimation de la gravité des défauts de roulements à partir de signaux vibratoires. Cette tâche, compliquée pour des machines opérantes dans des conditions stationnaires, devient un réel défi dès que les systèmes à surveiller fonctionnent à vitesses et chargements variables. Cette thèse s'inscrit principalement dans un contexte de surveillance de la ligne d'arbre d'éoliennes de l'entreprise Engie Green, partenaire de ce projet. Ce rapport explore deux thématiques pour une meilleure exploitation des signaux vibratoires, avec l'objectif d'aider aux prises de décisions de maintenance. Premièrement, les outils de traitement du signal classiques reposent sur une hypothèse de cyclicité des propriétés statistiques des signatures de défauts par rapport à la rotation des arbres supportant les roulements. Les phénomènes de glissement lors du fonctionnement dégradent les capacités des outils existants. Ce travail propose de lever ce verrou grâce à une réinterprétation de ces propriétés cyclostationnaires en changeant le référentiel de rotation, de l'arbre vers la rotation de la cage. Les causes de ce glissement sont d'abord étudiées. Armé de méthodes d'estimation de la vitesse de rotation de la cage, une méthode de restauration des propriétés cyclostationnaires est proposée. Fort de cette restauration, une adaptation des techniques de moyennage synchrone au cas des roulements est étudiée. Deuxièmement, l'estimation de la dégradation repose sur la capacité à suivre finement l'évolution de différents indicateurs. À ce titre, il manque cruellement d'outils permettant le traitement de séries de signaux vibratoires, la plupart étant centrés sur l'analyse séparée de chaque signal. Les statistiques de rang offrent un cadre robuste et non-paramétrique pour l'analyse de tendance. En se basant sur le test de Mann-Kendall, deux outils sont proposés pour répondre à deux problématiques de la surveillance vibratoire : la sélection de bande informative fréquentielle et l'analyse spectrale.

Nonlinear    rotordynamics    of    a    vibroflot    and    granular    soil interactions during vibro compaction

Doctorant : Florian TEZENAS DU MONTCEL

Laboratoire INSA : LaMCos

École doctorale : ED162 : Mécanique, Énergétique, Génie Civil, Acoustique de Lyon

Vibro compaction is a ground improvement technique which aims to deeply densify sandy soil in order to make stable future infrastructure built on it. Loose soil can be compacted through insertion of vibrating probes, called vibroflots, together with a large volume of water. This enables the sand particles to rearrange themselves in a denser formation and thus increases the overall density of the soil.
Since its invention in the 1930s, the vibro compaction knowledge is mainly based on empirical operational experience, but not on well-founded scientific studies based around fundamentals. This work aims at better understanding how the vibroflot behaves underground and at globally improve the efficiency of the technique. To do so, experimentation and numerical modelling are both implemented.
During site trials the whole process is instrumented to measure the vibroflot - soil system dynamics, which allow to understand the different phenomena involved during compaction. Many geotechnical tests, combined with different sets of execution parameters, permit to quantify soil improvement and define the influence of these parameters, judge the relevancy of geotechnical correlations and get soil parameters which are useful for numerical modelling. Indeed, a multi- physics numerical model is created to predict the dynamic behaviour of the vibroflot in interaction with a granular soil. Models of the induction motor, multi-rotor and soil are strongly coupled but do not predict the compaction rate: the objective is to study the vibroflot dynamics rather than the compaction phenomenon. Key parts of the vibroflot, the dynamic properties of the rubber couplings are determined experimentally and numerically. Simple analytical formulations of the equivalent stiffness and damping parameters are then used in the numerical model. Finally, predicted responses are compared to the measurements collected on site.

   

 

Étude des sources de pertes et des transferts thermiques au sein de paliers à éléments roulants

Doctorant : Florian DE CADIER DE VEAUCE

Laboratoire INSA : LAMCOS

École doctorale : ED162 : MEGA de Lyon (Mécanique, Energétique, Génie civil, Acoustique)

La transition vers des véhicules électriques impose des vitesses toujours plus élevées au sein des transmissions mécaniques, entraînant davantage de pertes, principalement au niveau des paliers à éléments roulants. Afin d'améliorer l'efficacité énergétique des transmissions mécaniques, en particulier des roulements à billes, une compréhension approfondie des phénomènes physiques associés s'avère essentielle. Le présent travail de thèse se concentre sur l'étude des sources de pertes et des transferts thermiques au sein d'un roulement à billes. Les pertes et les températures de deux roulements à billes sont mesurées pour différentes conditions opératoires. Dans un premier temps, les roulements sont lubrifiés par injection. L'influence de plusieurs paramètres, tels que la vitesse de rotation, le débit et la température de l'huile injectée, sur les dissipations de puissance est analysée. Une modélisation thermo-mécanique du roulement est proposée en associant des modèles de calcul des pertes et un réseau thermique. Dans un second temps, les roulements sont lubrifiés par barbotage. Pour une hauteur faible du bain d'huile, les pertes générées sont égales à celles obtenues pour ces mêmes roulements lubrifiés par injection dans des conditions opératoires similaires. Pour des niveaux d'huile plus élevés, le comportement du bain change, entraînant une augmentation des pertes par traînée. Les modèles actuels ne prennent pas en compte la hauteur du bain et un nouveau modèle de pertes par traînée est donc proposé. Les échanges et les écoulements n'étant pas les mêmes entre les deux modes de lubrification, des modifications ont également été apportées au réseau thermique. Les résultats numériques sont en accord avec les résultats expérimentaux. Une modélisation locale du roulement permet d'avoir une bonne précision sur les valeurs de pertes et de températures prédites, mais nécessite une connaissance de la géométrie interne du roulement. Tandis que les modèles globaux nécessitent un minimum d'information.

Des graphes de propriétés aux graphes de connaissances

Doctorant : Julian BRUYAT

Laboratoire INSA : LIRIS

École doctorale : ED512 : InfoMaths de Lyon

Les graphes de propriétés et les graphes RDF sont deux familles populaires de base de données graphe. Néanmoins, malgré le fait qu'elles soient toutes les deux basées sur la notion de graphe, ces deux familles ne sont pas interopérables. Les graphes de propriétés sont une famille d'implémentations de base de données très flexible, où des propriétés peuvent être rattachées aux noeuds et aux arcs du graphe. La seconde est un modèle standardisé de description de connaissances, reposant sur des vocabulaires partagés entre tous les graphes RDF. Dans cette thèse, nous définissons des méthodes pour permettre une interopérabilité sémantique entre graphes de propriétés et graphes RDF configurée à travers un « contexte » fourni par l'utilisateur. La première méthode est une méthode bas niveau, compatible avec n'importe quel graphe de propriétés. La seconde méthode est une méthode haut niveau, reposant sur la notion de schéma de graphe de propriétés, et pour laquelle la réversibilité de certains contextes est étudiée formellement. Enfin, pour faciliter l'écriture des « contextes » en RDF, et plus généralement de n'importe quel document RDF, nous proposons une méthode d’auto- complétion basée sur les vocabulaires de schémas RDF existants.

Proposition et mise en œuvre d'une topologie d'onduleur multifonctionnel à tension de bus régulée pour la traction électrique

Doctorant : Antoine SABRIE

Laboratoire INSA : Ampère

École doctorale : ED160 : EEA (Electronique, Electrotechnique, Automatique)

Dans le cadre de la traction électrique pour les véhicules routiers, il est indispensable de recourir à des onduleurs dont le rôle est de convertir l’énergie électrique entre une source de stockage continue de type batterie et la charge alternative que représente une machine électrique triphasée. Idéalement, cette conversion devrait se faire sans perte de tension. En pratique, il apparaît inévitablement une limitation de la tension avec laquelle un onduleur est capable d’alimenter une machine électrique. Pour bienanalyser cette limitation, nous avons proposé une modélisation fine des chutes de tension de l’onduleur afin de permettre une estimation analytique rapide et fidèle. Les résultats expérimentaux valident le modèle proposé dans la quasi-totalité de points de fonctionnement atteignable. Une solution utilisée industriellement pour palier à cette limitation de l’onduleur est d’ajouter un convertisseur DC - DC élévateur. L’inconvénient de cette solution est qu’elle introduit un deuxième étage pouvant impacter le rendement global et la fiabilité de la chaîne de traction. Ces dernières années, des architectures d’onduleur élévateur en un étage de conversion sont proposées dans la littérature. L’une de ces architectures est apparue et présente des avantages compétitifs par rapport à ses homologues. Il s’agit de l’onduleur à Split Source (SSI). Néanmoins, nous avons montré que ce convertisseur est incompatible à la traction électrique due principalement au manque de réversibilité et à une perte de degré de liberté pour le pilotage de la charge. Par la suite, nous avons proposé une nouvelle architecture triphasée et réversible basée sur le convertisseur SSI, appelée B-ASSI, qui est compatible à l’application visée. L’analyse et la modélisation du convertisseur B-ASSI sont réalisées. Une modulation pour son pilotage, ainsi qu’une stratégie de contrôle de sa tension de bus sont développées. Enfin, le B-ASSI est construit et testé expérimentalement par une preuve de concept de quelques 𝑘𝑘𝑘𝑘. Après avoir étudié les performances du B-ASSI vis-à-vis des architectures existantes, nous nous intéressons à la possibilité d’introduire une fonctionnalité d’abaissement de la tension d’alimentation du B-ASSI. Nous montrons que cela permet d’améliorer les formes d’ondes alimentant la machine, réduire les oscillations de couple utile, améliorer le rendement de la machine, et réduire la montée en températuredu convertisseur. Finalement, une extension du B-ASSI permettant l’abaissement de sa tension de bus est proposée et étudiée. Une première validation en simulation et expérimentale valident le principe de fonctionnement.