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.

Métrologie des techniques de microscopie à sonde locale micro- onde appliquées aux mesures de transport dans le domaine des semiconducteurs

Doctorant :  Damien RICHERT

Laboratoire INSA : INL

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

Cette thèse se focalise sur l’établissement d’une métrologie des mesures de propriétés électrique à l’échelle submicrométrique. Le Scanning Microwave Microscopy (SMM), qui permet d’accéder aux propriétés électriques d’un échantillon (impédance, permittivité électrique, tangente d’angle de perte et concentration de dopant), répond à ces critères. Il s’agit d’un microscope à force atomique interfacé à un analyseur de réseaux vectoriel (VNA). Si la métrologie de la mesure électrique utilisant un VNA est bien établie, ce n’est pas le cas pour les configurations SMM. Un VNA permet, s’il est calibré, d’extraire des propriétés électriques à partir de la mesure du paramètre de réflexion. Pour une configuration SMM, la méthode la plus commune est dérivée de la calibration Short- Open-Load utilisant trois impédances connues sur un échantillon de référence. L’un des résultats clé de cette thèse est l’établissement du bilan d’incertitude associé à la mesure d’impédance par SMM. Pour ce faire, une caractérisation de l’échantillon de référence démontra que l’incertitude associée aux valeurs des impédances présentes (0.3; 9.8 fF) est inférieure à 2.8 %. Fort de ce bilan d’incertitude, un second échantillon de référence fut proposé et caractérisé avec une incertitude associée inférieure à 1.9 %. L’incertitude sur la mesure des capacités de référence par le SMM calibré est inférieure à 3 %. Un cas d’application est l’extraction de la permittivité d’échantillons piézoélectriques avec une incertitude inférieure à 10.6 %. L’incertitude due à l’humidité relative (RH) sur la calibration du SMM fut étudiée empiriquement et par simulation numérique. Le RH impacte la calibration à hauteur de 0.4 % pour les capacités de 0.3 fF et devient négligeable pour les capacités au-dessus de 4 fF. Enfin, des courbes dC/dz furent acquise par microscopie à force électrostatique (EFM) sur un diélectrique connu afin d’assurer la traçabilité de la mesure de constante de raideur de la sonde employé.

Development of Ti-based bulk metallic glasses for dental applications through innovative design strategy, process optimisation and surface functionalisation

Doctorant : Yohan DOUEST

Laboratoire INSA : MATEIS

École doctorale : ED34 : Matériaux de Lyon

Due to their long-range disordered atomic structure, Ti-based bulk metallic glasses (BMGs) exhibit at least twice the mechanical strength of crystalline Ti-alloys currently used in dental implant applications. Ti-based BMGs are therefore candidate materials to downsize dental implant components and reduce their invasiveness. Although numerous research works have emphasised their potential, no commercial products have been made available. Several aspects hinder their practical application. Firstly, they generally contain high amount of copper. Apart the controversy regarding its biological safety, copper has been shown to trigger pitting corrosion in chloride environment of amorphous alloys, thereby limiting their corrosion resistance. Secondly, Ti-based BMGs are challenging to process. Because of their restricted glass forming ability (GFA), they are more prone to the formation of crystalline heterogeneities even when high cooling rates are applied.
This PhD investigates independent research areas related to Ti-based BMGs, ranging from designing strategies and processability to surface functionalisation. At first, a machine learning (ML) model is employed to explore compositional spaces with reduced amount of copper within the Ti-Zr-Cu-Pd system. The model’s predictions are experimentally assessed, and a critical discussion is provided on the relevance of the ML-guided approach. Secondly, the processability of Ti40Zr10Cu36Pd14, a representative composition of Ti-based BMGs, is evaluated. Processing techniques from both laboratory and industry are compared, and the resulting as-cast crystalline heterogeneities are studied to give insights into their formation pathways. Lastly, two surface modifications aimed at reducing the influence of copper on the corrosion resistance of Ti40Zr10Cu36Pd14 are proposed. One solution involves the deposition of coating already used in dental implant systems while the second solution consists of a chemical etching treatment. The results obtained within this PhD aim to contribute both scientific and industrial advancements, while also suggesting new research topics.

Biofloculation dans les procédés à boues activées : rôle des substances polymériques extracellulaires

Doctorante : Zoé FAU

Laboratoire INSA : REVERSAAL

École doctorale : ED206 : Chimie de Lyon (Chimie, Procédés, Environnement)

Les procédés à boues activées sont couramment employés pour traiter les eaux usées domestiques. La mise en œuvre de procédés forte charge ou densifiés peut permettre de diminuer leur demande énergétique et valoriser les polluants de l’eau usée mais nécessite une meilleure compréhension des mécanismes, notamment la biofloculation, qui gouvernent la capture de la matière organique. Le rôle dans ces mécanismes des Substances Polymériques Extracellulaires (EPS) secrétées par les bactéries, est de plus en plus étudié mais les conclusions sont divergentes. Ce travail de thèse a pour objectif d’améliorer la compréhension du rôle des EPS dans le mécanisme de biofloculation dans les procédés à boues activées. Un état de l’art a tout d’abord mis en évidence l’absence de consensus et les verrous, notamment méthodologiques, qui limitent la compréhension du rôle des EPS dans les procédés à boues activées. Des mesures expérimentales sur des boues de station d’épuration ont ensuite permis de 1) sélectionner et adapter les méthodes de caractérisation des EPS appropriées aux boues floculées et 2) proposer une amélioration d’une méthode innovante de caractérisation de la capacité de biofloculation d’une boue (détermination du seuil de floculation - Threshold Of Flocculation, TOF). Ces méthodes, combinées à des méthodes conventionnelles, ont été appliquées sur une trentaine d’échantillons de boues de plusieurs types de procédés (conventionnels, forte charge et densifiés) à l’échelle pilote et à pleine échelle. Cette démarche a révélé qu’une boue présentant de faibles capacités de biofloculation et des flocs peu développés, contient cinq fois plus d’EPS faiblement liées avec une teneur faible en biopolymères (<30 %), qu’une boue avec de bonnes capacités de biofloculation. Ces résultats démontrent qu’améliorer les capacités de biofloculation en contrôlant les EPS (concentration, composition) pourrait accroître la capture de la matière organique et donc le potentiel de valorisation énergétique.
 

Order-based beamforming and its application to rotating machines

Doctorant : Kalasagarreddi KOTTAKOTA

Laboratoire INSA : LVA

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

Dans les machines tournantes, l'identification des sources de bruit joue un rôle essentiel dans le raffinement acoustique. Lorsque ces machines fonctionnent à des vitesses variables, les techniques traditionnelles de formation de voies basées sur la fréquence ne sont plus appropriées car les phénomènes vibroacoustiques générés sont non stationnaires et comportent des tonalités modulées appelées ordres. Le suivi d’ordre est une méthode importante pour traiter les mesures à vitesse variable qui permet d'extraire les ordres, dont les fréquences évoluent proportionnellement à la vitesse de l'arbre de référence. Cette thèse présente une technique appelée Order-Based Beamforming(OBBF) qui combine la formation de voies et le suivi d’ordre pour réaliser une imagerie acoustique sur les ordres. L'OBBF établit une correspondance entre les enveloppes complexes des signaux du réseau de microphones et de la source, ce qui permet d'identifier les sources de bruit tonales en vitesse variable. L'OBBF produit des films sur le rayonnement de la source, chaque image représentant une carte de formation de voies à un régime donné. La thèse présente également le Multi-Pass Order-Based Beamforming(MPOBBF), une application de l'OBBF. Cette méthode permet la resynchronisation des champs sonores tonaux, capturés séquentiellement à partir de multiples mesures d’antenne microphonique à vitesse variable, avec la connaissance de la position angulaire de l'arbre. Les enveloppes complexes d'un ordre extraites de plusieurs mesures séquentielles sont concaténées en un seul ensemble de données, sur lequel l'OBBF est appliqué pour identifier les sources de bruit tonal. La solution proposée permet d'agrandir ou de densifier synthétiquement les antennes microphoniques devant des objets 3D en les capturant successivement à l'aide d'un réseau mobile. Les deux techniques sont détaillées et évaluées à l'aide de simulations numériques et de données obtenues sur un banc d'essai de moteur à induction.

 

Innovative multichannel models for pricing and inventory decisions considering service level

Doctorante : Minh Tam TRAN

Laboratoire INSA : DISP

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

The thesis investigates contemporary challenges in retail management amidst the digital revolution, with a focus on multichannel retailing, dual-channel pricing, and data-driven inventory management. This thesis first begins with an overview of evolving retail dynamics driven by technological advancements and shifting consumer demands, emphasizing the necessity for inventive solutions to navigate these complexities. Second, by exploring multichannel retailing in-depth, the study examines inventory allocation and pricing optimization across physical and online channels. It addresses a multichannel pricing problem, proposing a methodology to ensure optimal solutions and highlighting the importance of channel coordination and service levels on market share and profitability. Thirdly, further delving into dual-channel pricing, the thesis presents a novel pricing model capturing intricate interactions between channels, retailers, and customers. It emphasizes the significance of determining optimal physical store capacity and managing stock-out conversions to online sales with promotions. Fourth, introducing data-driven inventory management methodologies, the study leverages Kernel Density Estimation (KDE) within chance-constrained optimization frameworks. By demonstrating superior performance in achieving target service levels compared to traditional methods, the thesis emphasizes the importance of managing inventory under uncertainty while maintaining service quality. Last but not least, the thesis concludes by promoting a deeper understanding of retail management in the digital age, offering valuable insights and methodologies to navigate modern retailing complexities. By embracing innovation, data-driven approaches, and customer-centric strategies, retailers can position themselves for success in an increasingly dynamic and competitive environment. Future research directions include exploring advanced machine learning techniques and extending the model to consider sustainability and supply chain resilience.

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.
 

Étude de l'amorçage de l'endommagement du sulfure de zinc (ZnS) sous impacts liquides

Doctorant : Pierre GANTIER

Laboratoire INSA : LaMCos

École doctorale : ED162 : MEGA

Les matériaux infrarouges sont couramment utilisés dans l'industrie de défense et dans l'aéronautique dans des applications de guidage, de détection et de suivi. Le ZnS est un de ces matériaux qui jouie de performances optiques uniques, ce qui en fait un excellent candidat pour la plupart des applications nécessitant l'utilisation de rayonnement infrarouge. Cependant, en conditions de vols, sa résistance aux agressions du milieu extérieurs, et en particulier, aux impacts liquides provoqués par la pluie, le brouillard ou les nuages reste limitée et mal connue. Les travaux de thèse ont donc porté à la fois sur la modélisation numérique de l'impact liquide et sur la mise en place et l'utilisation d'un banc d'essai développé à cet effet.