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.

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.

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.
 

Simulation en conception électrique : Atelier pour la gestion des Modèles par Apprentissage Automatique

Doctorante : Adam DESORMIÈRE

Laboratoire INSA : DISP

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

Ce travail de thèse se place dans le contexte des simulations effectuées par Intel pour estimer la consommation électrique de ses futurs produits. L’entreprise, qui réutilise souvent des circuits électriques similaires dans ses produits, ne tire pas suffisamment parti du savoir acquis dans les nombreuses simulations qu’elle effectue. Les modèles de simulations sont mal répertoriés, peu réutilisés par les ingénieurs en charge, et il est souvent nécessaire de repartir d’une page blanche pour un travail partiellement effectué par le passé.
Notre objectif est de proposer à l'entreprise des méthodes pour mieux gérer ses modèles de simulation de consommation électrique pour faciliter la réutilisation du savoir capitalisé dans les simulations précédentes. Il s’agit par exemple de détecter les modèles simulant des circuits classiques (mémoires, cœurs…), très souvent créés, afin de proposer aux ingénieurs des bibliothèques prêtes à l’emploi pour ces modèles. Nous avons choisi de nous focaliser sur l’extraction et l’exploitation des données issues des modèles, pour permettre à l’entreprise de mettre en place un PLM dans un second temps. Afin d’atteindre ces objectifs, nous employons des méthodes d’apprentissage automatique afin d’exploiter les métadonnées attachées aux modèles et les données contenues dans les modèles.
Nous proposons d’abord un algorithme qui exploite trois métadonnées attachées aux modèles pour évaluer la distance entre chaque paire de modèles de simulation. Nous utilisons ensuite ces distances, pondérables, pour proposer aux ingénieurs chargés de la simulation des groupes de modèles similaires grâce à un clustering hiérarchique.
Pour les données contenues dans les modèles, nous proposons d’utiliser un algorithme de traitement automatique du langage mathématique. Nous exploitons en particulier l’équation décrivant la consommation électrique du circuit modélisé pour quantifier la distance entre deux modèles de simulation. A nouveau, nous utilisons cette distance pour regrouper les modèles dits similaires selon ce critère, grâce à l’algorithme de clustering OPTICS.

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.

De la transparence des graphes de connaissances à un cadre général pour la définition de mesures d'évaluation

Doctorante : Jennie ANDERSEN

Laboratoire INSA : LIRIS

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

De nombreux graphes de connaissances (KG) sont disponibles sur le Web, et il peut être difficile de décider avec lequel travailler. Au-delà de la pertinence du domaine et du contenu, l'utilisation de standards, l'identification des créateurs... peuvent également influencer ce choix. En effet, la mise à disposition de toujours plus de données s'accompagne d’attentes supplémentaires en termes de qualité et de transparence.
Pour aider les utilisateurs à choisir un KG plutôt qu'un autre, nous voulons fournir une estimation de la transparence des KG. Les informations liées à la transparence sont essentielles pour renforcer la confiance dans les données et favoriser leur réutilisation. Cependant, il n’existe pas de définition consensuelle de la transparence. Pour mieux la comprendre, nous explorons tout d'abord cette notion et ses concepts associés (accessibilité, vérifiabilité...). Face à l’absence d'exigences précises concernant la transparence, nous nous concentrons ensuite sur un concept proche, et proposons une mesure de « l’accountability » des KG. Nous utilisons notre mesure pour évaluer des centaines de KGs disponibles via des SPARQL endpoints. Enfin, nous comparons notre mesure avec d'autres mesures pour les KG sur la qualité des données et les principes FAIR.
Ces comparaisons mettent en évidence des spécificités et des points communs pour ces multiples mesures. Aussi, choisir la mesure appropriée pour évaluer les KG dans le cadre d'une tâche donnée n’est pas aisé, d’autant plus qu'elles sont décrites de manières variées. Puisque beaucoup reposent sur une structure hiérarchique, nous proposons de définir une base formelle pour décrire les mesures dans un cadre commun. Nous souhaitons ainsi faciliter leur compréhension, leur réutilisation, leur comparaison et leur partage en définissant des opérateurs permettant de les manipuler, soit pour en créer de nouvelles, soit pour les comparer. Nous prolongeons ce cadre en proposant une application web.

Programming language abstractions for the Internet of Things era

Doctorant : Patrik FORTIER

Laboratoire INSA : CITI

Ecole doctorale : ED512 : InfoMaths

The challenges posed by the Internet of Things (IoT) require modern applications to handle large volumes of data streaming from tiny devices, which then undergo processing, storage, and analysis. Developers have embraced the microservices architecture to address scalability concerns and facilitate a fast software delivery process. However, emerging computing paradigms like Fog and Edge computing introduce diverse resources and configurations, making it necessary for developers to adapt to increasingly complex environments and ecosystems. The emergence of new development methodologies like Function-as-a-Service and Serverless models has shifted the focus towards code simplicity. However, this has raised concerns that developers are now coding for infrastructures they have limited control over. In resource-constrained environments such as edge computing, applications even often compete for resources. Therefore, developers require tailored tools with appropriate abstractions to address modern challenges without succumbing to rising complexity.

In this thesis, we present programming language abstractions tailored for developing distributed software in the era of the Internet of Things. We have consolidated these abstractions into a framework that allows for the construction of distributed dataflow applications in the form of microservice applications, all within the same codebase. This framework abstracts both the underlying infrastructure on which applications run and the communication between services. We demonstrate the overhead introduced by our approach and compare it with existing Function-as-a- Service frameworks.

To offer precise control over the infrastructure, we introduce language primitives and a local runtime that manages contextual information about the cluster. Additionally, we introduce entropy as an innovative placement metric for applications. Developers can dictate how they want their application to be positioned within the cluster and how it should respond to scenarios such as resource contention between applications sharing the same infrastructure. These techniques enable a user-defined dynamic placement policy with a high level of granularity in an environment where they may not have complete control.

Multi-Objective Optimization in Short and Mid-term Home Health Care Planning

Doctorante : Jiao ZHAO

Laboratoire INSA : DISP

Ecole doctorale : ED512 Infomaths

L'industrie des Soins de Santé à Domicile (SSD) offre des soins essentiels aux personnes âgées, handicapées et malades chroniques, financée par l'assurance sociale et la fiscalité. Les entreprises SSD doivent planifier efficacement pour maximiser l'utilisation des ressources et assurer des soins de qualité.
Dans les entreprises de SSD, les gestionnaires acceptent un nombre limité de patients, évaluant leur niveau de dépendance et planifiant leurs services hebdomadaires. Les soignants, internes et externes, visitent les patients selon des itinéraires et horaires définis. L'objectif est de créer ces itinéraires et horaires tout en considérant le nombre de soignants différents. Une approche de programmation linéaire en nombres entiers mixtes est utilisée, intégrant une recherche de grand voisinage dans un cadre de recherche locale améliorée. Les résultats montrent une performance supérieure à la méthode augmentée de contrainte et enfin des recommandations de gestion sont données.
Suite à la planification hebdomadaire en soins à domicile, des incertitudes liées aux temps de service peuvent survenir, affectant la qualité du service. Pour y remédier, nous introduisons un problème d'optimisation bi-objectif pour la planification et le routage incertains. Nous proposons des versions déterministes et stochastiques d'une recherche adaptative de grand voisinage intégrée dans un cadre de recherche locale multidirectionnelle améliorée, offrant une efficacité supérieure comparée au Solveur Gurobi. La robustesse de notre modèle et méthode est confirmée par une analyse de sensibilité. Enfin, l'application pratique de cette méthode est démontrée par un cas réel, accompagnée de recommandations managériales.
 

Planning Problems in a Multi-Tethered-Robot System

Doctorante : Xiao PENG

Laboratoire INSA : CITI
Ecole doctorale : ED512 : Infomaths

Multiple robot systems are widely applied in our real life. As a special type of mobile system, tethered robots play a crucial role in special contexts, particularly in challenging conditions, where cables provide stable access to power and network connectivity. However, constraints imposed by cables also introduce new challenges for motion planning in these applications. This thesis focuses on planning problems for a team of tethered robots, addressing two major problems: non-crossing Anonymous Multi-Agent Path Finding (AMAPF) and Multiple Tethered Coverage Path Planning (MTCPP).

The goal of non-crossing AMAPF is to find a set of non-crossing paths such that the makespan is minimal. The study is carried out in two cases, considering whether the robots are treated as point-sized or not. This hypothesis significantly influences the computation of makespan. The problem is abstracted to the Euclidean Bipartite Assignment problem and we show that bounds can be efficiently computed by solving linear assignment problems. We introduce a variable neighborhood search method to improve upper bounds, and a Constraint Programming model to compute optimal solutions. The approach is experimentally evaluated on three different kinds of instances.

The MTCPP problem is addressed by initially partitioning the workspace into equitable connected subregions, enabling each robot to operate independently in its assigned area. We propose an approach based on the additively weighted Voronoi diagram, ensuring an equitable partitioning that enforces relative star-convexity of each subregion to the associated anchor point, thereby avoiding cable entanglement. For the coverage path planning of each robot, the Spanning Tree Coverage method is shown to effectively solve the problem while respecting cable constraints.

Building Autonomous Agents with Hybrid Navigation Policies

Doctorant : Assem SADEK

Laboratoire INSA : LIRIS

Ecole doctorale : ED512 Informatique Et Mathématiques de Lyon

Les progrès récents de l'IA, et plus particulièrement de l'apprentissage automatique, permettent aux robots de s'intégrer de manière plus transparente dans nos habitudes quotidiennes. L'objectif de cette thèse est de faire un pas de plus vers le développement d'agents autonomes intelligents qui peuvent être intégrés dans notre environnement quotidien, comme les maisons, les hôpitaux, les centres commerciaux, etc. Ces agents devraient posséder la capacité de naviguer efficacement dans leur environnement pour atteindre un certain objectif, comme atteindre une certaine zone de l'environnement ou trouver un certain objet. C'est pourquoi nous examinons le large éventail de techniques existantes pour la construction d'un agent de navigation incarné. Ces techniques peuvent entièrement être apprises par des réseaux neuronaux (techniques basées sur l'apprentissage) ou elles peuvent être des techniques basées sur la géométrie qui reposent sur une modélisation explicite de l'agent et de son environnement. Dans cette thèse, nous construisons des approches hybrides qui utilisent les deux techniques afin de pouvoir fonctionner, non seulement dans une simulation, mais également dans un environnement physique réel. Il s'agit d'un objectif commun à toutes les contributions à ce travail.