Retour au site du LAAS-CNRS

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

16documents trouvés

18414
03/12/2018

Méthodes d'optimisation robuste pour les problèmes d'ordonnancement cyclique

I.HAMAZ

ROC

Doctorat : Université de Toulouse III - Paul Sabatier, 3 Décembre 2018, 148p., Président: A.ROSSI, Rapporteurs: P.CHRETIENNE, M.POSS, Examinateurs: C.ARTIGUES, Directeurs de thèse: L.HOUSSIN, S.CAFIERI , N° 18414

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

Diffusable

Plus d'informations

Abstract

Several studies on cyclic scheduling problems have been presented in the literature. However, most of them consider that the problem parameters are deterministic and do not consider possible uncertainties on these parameters. However, the best solution for a deterministic problem can quickly become the worst one in the presence of uncertainties, involving bad schedules or infeasibilities. Many sources of uncertainty can be encountered in scheduling problems, for example, activity durations can decrease or increase, machines can break down, new activities can be incorporated, etc. In this PhD thesis, we focus on scheduling problems that are cyclic and where activity durations are affected by ("the" a effacer) uncertainties. More precisely, we consider an uncertainty set where each task duration belongs to an interval, and the number of parameters that can deviate from their nominal values is bounded by a parameter called budget of uncertainty. This parameter allows us to control the degree of conservatism of the resulting schedule. In particular, we study two cyclic scheduling problems. The first one is the basic cyclic scheduling problem (BCSP). We formulate the problem as a two-stage robust optimization problem and, using the properties of this formulation, we propose three algorithms to solve it. The second considered problem is the cyclic jobshop problem (CJSP). As for the BCSP, we formulate the problem as two-stage robust optimization problem and by exploiting the algorithms proposed for the robust BCSP we propose a Branch-and-Bound algorithm to solve it. In order to evaluate the efficiency of our method, we compared it with classical decomposition methods for two-stage robust optimization problems that exist in the literature. We also studied a version of the CJSP where each task duration takes uniformly values within an interval and where the objective is to minimize the mean value of the cycle time. In order to solve the problem, we adapted the Branch-and-Bound algorithm where in each node of the search tree, the problem to be solved is the computation of a volume of a polytope. Numerical experiments assess the efficiency of the proposed methods.

Résumé

Plusieurs problèmes d’ordonnancement cyclique ont été étudiés dans la littérature. Cependant, la plupart de ces travaux considèrent que les paramètres sont connus avec certitude et ne prennent pas en compte les différents aléas qui peuvent survenir. Par ailleurs, un ordonnancement optimal pour un problème déterministe peut très vite devenir le pire ordonnancement en présence d’incertitude. Parmi les incertitudes que nous pouvons rencontrer dans les problèmes d’ordonnancement, la variation des durées des tâches par rapport au valeurs estimées, pannes des machines, incorporation de nouvelles tâches qui ne sont pas considérées au départ, etc. Dans cette thèse, nous étudions des problèmes d’ordonnancement cyclique où les durées des tâches sont affectées par des incertitudes. Ces dernières sont décrites par un ensemble d’incertitude où les durées des tâches sont supposées appartenir à des intervalles et le nombre de déviations par rapport aux valeurs nominales est contrôlé par un paramètre appelé budget d’incertitude. Nous étudions deux problèmes en particulier. Le premier est le problème d’ordonnancement cyclique de base (BCSP). Nous formulons celui-ci comme un problème d’optimisation robuste bi-niveau et, à partir des propriétés de cette formulation, nous proposons différents algorithmes pour le résoudre. Le deuxième problème considéré est le problème du jobshop cyclique. De manière similaire au BSCP, nous proposons une formulation en termes de problème d’optimisation bi-niveau et, en exploitant les algorithmes développés pour le problème d’ordonnancement cyclique de base, nous développons un algorithme de Branch-and-Bound pour le résoudre. Afin d’évaluer l’efficacité de notre méthode nous l’avons comparé à des méthodes de décomposition qui existent dans la littérature pour ce type de problèmes. Enfin, nous avons étudié une version du problème du jobshop cyclique où les durées des tâches prennent des valeurs dans des intervalles d’une manière uniforme et dont l’objectif est de minimiser la valeur moyenne du temps de cycle. Pour résoudre ce problème nous avons adopté un algorithme de Branch-and-Bound où chaque sous-problème de l’arbre de recherche consiste à calculer le volume d’un polytope. Enfin, pour montrer l’efficacité de chacune de ses méthodes, des résultats numériques sont présentés.

Mots-Clés / Keywords
Ordonnancement cyclique; Optimisation robuste; Optimisation combinatoire; Cyclic scheduling; Robust optimization; Combinatorial optimization;

145533
18376
11/09/2018

Earth observation systems optimization for free-space optical communications

M.CAPELLE

ROC

Doctorat : Septembre 2018146, 146p., Président: J.C.BILLAUT, Rapporteurs: O.PETON, S.DEMASSEY, Examinateurs: C.PRALET, F.CLAUTIAUX, Directeurs de thèse: M.J.HUGUET, N.JOZEFOWIEZ , N° 18376

Non diffusable

Plus d'informations

Résumé

Depuis plusieurs années, les satellites sont utilisés pour explorer, surveiller et photographier la Terre depuis l’espace. Ces satellites prennent un nombre croissant d’images avec une résolution de plus en plus de plus élevée, générant ainsi de gros volumes de données qui doivent être envoyés vers la Terre. Afin de transférer de telles quantités de données, de nouvelles technologies de communication sont étudiées. Parmi elles, les liaisons optiques en espace libre sont considérées aujourd’hui comme une alternative intéressante aux technologies actuelles basées sur les radio-fréquences. Avec des débits bien supérieurs à ceux actuels, les liaisons optiques sont capables de transférer d’important volumes de données journaliers en à peine quelques minutes. Cependant, les liaisons optiques sont fortement perturbées par les turbulences atmosphériques et, en particulier, les nuages. Afin de limiter l’impact de la couverture nuageuse, il est nécessaire de créer des réseaux de stations sol optiques efficacement réparties dans le monde. De plus, les prévisions météorologiques n’étant pas exactes, des procédures opérationnelles doivent être établies afin de pouvoir planifier les transferts d’images depuis le satellite vers la Terre, en prenant en compte les incertitudes liées aux nuages et aux prévisions de couverture nuageuse. Dans cette thèse, nous nous intéressons à l’utilisation de communications optiques pour la télémétrie image. Dans un premier temps, nous considérons le problème de la création de réseaux terrestres de stations optiques prenant en compte l’impact des nuages. Nous résolvons ce problème en combinant un algorithme de programmation dynamique avec un algorithme de type branch-and-bound. Dans un second temps, nous nous intéressons au problème de planification des transferts d’images d’un point de vue opérationnel, en prenant en compte les incertitudes sur les volumes des images acquises (dues à la compression bord) et celles liées aux communications optiques. Nous proposons une approche flexible où le processus de décision est partagé entre le système sol (centre mission) et le système à bord du satellite.

Abstract

For many years, satellites have been used to explore, analyse and monitor Earth from space. Nowadays, low-earth orbiting satellites are taking a steadily increasing number of pictures, with higher and higher precision, thus generating huge volumes of data that needs to be downloaded. In order to manage such amount of data, new communication technologies are investigated. In this context, free-space optical communications are seen as a key alternative to current radio-frequency ones. With their orders of magnitude higher data rates, free-space optical communications could be able to download daily acquisition volumes in a matter of minutes. Unfortunately, optical communications are strongly impacted by atmospheric turbulence and clouds. In order to cope with the latter, it is necessary to design efficient distributed networks of optical ground stations. Furthermore, since weather forecasts are imperfect, custom operational procedures should be established to schedule the downloads of acquisitions using optical communications to take into account uncertainties regarding clouds. In this thesis, we investigate the use of free-space optical communications for image telemetry. We first consider the problem of designing efficient networks of optical ground stations taking into account the impact of clouds. We solve this problem using a combination of a dynamic programming algorithm and a branch-and-bound algorithm. Then, we look at the operational problem of planning downloads of acquisitions under download channel and image volume uncertainties. We propose a flexible approach where the decision process is shared between ground and on-board systems.

Mots-Clés / Keywords
Optimisation combinatoire; Observation spatiale; Communications optiques; Combinatorial optimization; Spatial observation; Optical telecommunications;

145257
18393
03/07/2018

Codes et jeux de soustraction et de poursuite dans les graphes

P.COUPECHOUX

ROC

Doctorat : INSA de Toulouse, 3 Juillet 2018, 118p., Président: M.J.HUGUET, Rapporteurs: E.DUCHENE, A.QUILLOT, Examinateurs: P.VALICOV, A.PINLOU, Directeurs de thèse: J.MONCEL , N° 18393

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

Diffusable

Plus d'informations

Abstract

Identifying codes were introduced in 1998 by Karpovsky, Chakrabarty and Levitin. An identifying code is a subgraph such that each vertex is uniquely identified by the vertices in its neighborhood. There are several variants of these codes, including a colored version where the vertices are identified by the colors in their neighborhood. In this phd, we want to build an identifying coloring of a large cycle, given a fixed number of colors. We also studied identified codes in a certain class of oriented graphs: tournaments. We have also studied some topics in the game theory. The first one is a generalization of octal games, where we play on a graph instead of a heap. More precisely, the 0.33 game; each player can remove one or two vertices in a graph, with no disconnection allowed. The first player who cannot play loses. We studied this game in some graph classes: subdivided stars and subdivided bistars. The other game is called the Firefighter game. It's a one player game! , where this one wants to contain a spreading fire in a graph. We solved a conjecture about this game, and introduced the online version of the game, for which we found some approximation results.

Abstract

Les codes identifiants ont été introduits en 1998 par Karpovsky, Chakrabarty et Levitin. Un code identifiant est un sous-graphe tel que chaque sommet est identifié de manière unique par les sommets du code qui l'entourent. Il existe plusieurs variantes de ces codes, dont notamment une version colorée dans laquelle les sommets sont identifiés par les couleurs dans leur voisinage. Dans cette thèse, nous cherchons en particulier à construire un cycle le plus grand possible qui admette une coloration identifiante, étant donné un nombre de couleurs fixé. Nous avons aussi étudié le problème des codes identifiants sur une classe particulière de graphes orientés : les tournois. Dans une seconde partie, nous avons aussi étudié deux jeux particuliers. Le premier est une généralisation des jeux octaux - qui se jouent normalement sur un tas - aux graphes. Plus précisemment, le jeu 0.33 ; chaque joueur peut retirer un ou deux sommets voisins d'un graphe, sans déc! onnecter ce dernier. Le premier qui ne peut plus jouer perd. Nous avons été capable de caractériser les issues de ce jeu dans des classes de graphes particulières, les étoiles subdivisées et les bi-étoiles subdivisées. Le second jeu est appelé le jeu du Pompier (Firefighter). Il consiste à arrêter un feu qui se propage dans un graphe en protégeant des sommets à chaque tour. Nous avons résolu une conjecture sur ce jeu, et introduit la version online, pour laquelle nous avons pu donner des résultats d'approximation.

Mots-Clés / Keywords
Théorie des graphes; Théorie des jeux; Codes identifiants; Colorations identifiantes; 0.33; Firefighter; Graphs theory; Game theory; Identifying codes;

145353
18050
24/01/2018

Technologies respectueuses de la vie privée pour le covoiturage. Privacy-Enhancing Technologies for Ridesharing

U.M.AIVODJI

TSF, ROC

Doctorat : Université de Toulouse III - Paul Sabatier, 24 Janvier 2018, 142p., Président: B.NGUYEN, Rapporteurs: J.DOMINGO-FERRER, D.FEILLET, Examinateurs: C.BRIAND, F.FESSANT, B.LE CUN, Directeurs de thèse: M.O.KILLIJIAN, M.J.HUGUET , N° 18050

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

Diffusable

Plus d'informations

Résumé

L’émergence des téléphones mobiles et objets connectés a profondément changé notre vie quotidienne. Ces dispositifs, grâce à la multitude de capteurs qu’ils em- barquent, permettent l’accès à un large spectre de services. En particulier, les capteurs de position ont contribué au développent des services de localisation tels que la navigation, le covoiturage, le suivi de la congestion en temps réel. . . En dépit du confort offert par ces services, la collecte et le traitement des données de localisation portent de sérieuses atteintes à la vie privée des utilisateurs. En effet, ces données peuvent renseigner les fournisseurs de services sur les points d’intérêt (domicile, lieu de travail, orientation sexuelle), les habitudes ainsi que le réseau social des utilisateurs. D’une façon générale, la protection de la vie privée des utilisateurs peut être assurée par des dispositions légales ou techniques. Même si les mesures d’ordre légal peuvent dissuader les fournisseurs de services et les individus malveillants à enfreindre le droit à la vie privée des utilisateurs, les effets de telles mesures ne sont observables que lorsque l’infraction est déjà commise et détectée. En revanche, l’utilisation des technologies renforçant la protection de la vie privée (PET pour Privacy Enhancing Technologies) dès la phase de conception des systèmes permet de réduire le taux de réussite des attaques contre la vie privée des utilisateurs. L’objectif principal de cette thèse est de montrer la viabilité de l’utilisation des PET comme moyens de protection des données de localisation dans les services de covoiturage. Ce type de service de localisation, en aidant les conducteurs à partager les sièges vides dans les véhicules, contribue à réduire les problèmes de congestion, d’émissions et de dépendance aux combustibles fossiles. Dans cette thèse, nous étudions les problèmes de synchronisation d’itinéraires et d’appariement relatifs au covoiturage avec une prise en compte explicite des contraintes de protection des données de localisation (origine, destination). Les solutions proposées dans cette thèse combinent des algorithmes de calcul d’itinéraires multimodaux avec plusieurs techniques de protection de la vie privée telles que le chiffrement homomorphe, l’intersection sécurisée d’ensembles, le secret partagé, la comparaison sécurisée dentier. Elles garantissent des propriétés de protection de vie privée comprenant l’anonymat, la non-chainabilité et la minimisation des données. De plus, elles sont comparées à des so- lutions classiques, ne protégeant pas la vie privée. Nos expérimentations indiquent que les contraintes de protection des données privées peuvent être prise en compte dans les services de covoiturage sans dégrader leurs performances.

Abstract

The emergence of mobile phones and connected objects has profoundly changed our daily lives. These devices, thanks to the multitude of sensors they embark, allow access to a broad spectrum of services. In particular, position sensors have contributed to the development of location-based services such as navigation, ridesharing, real-time congestion tracking. . . Despite the comfort offered by these services, the collection and processing of location data seriously infringe the privacy of users. In fact, these data can inform service providers about points of interests (home, workplace, sexual orientation), habits and social network of the users. In general, the protection of users’ privacy can be ensured by legal or technical provisions. While legal measures may discourage service providers and malicious individuals from infringing users’ privacy rights, the effects of such measures are only observable when the offense is already committed and detected. On the other hand, the use of privacy-enhancing technologies (PET) from the design phase of systems can reduce the success rate of attacks on the privacy of users. The main objective of this thesis is to demonstrate the viability of the usage of PET as a means of location data protection in ridesharing services. This type of location-based ser- vice, by allowing drivers to share empty seats in vehicles, helps in reducing congestion, CO2 emissions and dependence on fossil fuels. In this thesis, we study the problems of synchro- nization of itineraries and matching in the ridesharing context, with an explicit consideration of location data (origin, destination) protection constraints. The solutions proposed in this thesis combine multimodal routing algorithms with sev- eral privacy-enhancing technologies such as homomorphic encryption, private set intersection, secret sharing, secure comparison of integers. They guarantee privacy properties including anonymity, unlinkability, and data minimization. In addition, they are compared to conven- tional solutions, which do not protect privacy. Our experiments indicate that location data protection constraints can be taken into account in ridesharing services without degrading their performance.

Mots-Clés / Keywords
Privacy; Ridesharing; Privacy enhancing technologies; Vie privée; Covoiturage; Technologies renforçant la vie privée;

142777
17434
04/12/2017

Inventory routing problems with explicit energy consideration

Y.HE

ROC

Doctorat : Université de Toulouse III - Paul Sabatier, 4 Décembre 2017, 188p., Président: , Rapporteurs: M.G.SPERANZA, F.SEMET, Examinateurs: N.ABSI, D.QUADRI, Directeurs de thèse: N.JOZEFOWIEZ, C.BRIAND , N° 17434

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

Diffusable

Plus d'informations

Résumé

Dans le problème de tournées avec gestion de stock ou “Inventory Routing Problem” (IRP), le fournisseur a pour mission de surveiller les niveaux de stock d’un ensemble de clients et gérer leur approvisionnement en prenant simultanément en compte les coûts de transport et de stockage. Etant données les nouvelles exigences de développement durable et de transport écologique, nous étudions l’IRP sous une perspective énergétique, peu de travaux s’étant intéressés à cet aspect. Plus précisément, la thèse identifie les facteurs principaux influençant la consommation d’énergie et évalue les gains potentiels qu’une meilleure planification des approvisionnements permet de réaliser. Un problème relatif à l’approvisionnement en composants de chaînes d’assemblage d’automobiles est tout d’abord considéré pour lequel la masse transportée, la dynamique du véhicule et la distance parcourue sont identifiés comme les principaux facteurs impactant la consommation énergétique. Ce résultat est étendu à l’IRP classique et les gains potentiels en termes d’énergie sont analysés. Un problème industriel de tournées avec gestion de stock est ensuite étudié et résolu, notamment à l’aide d’une méthode de génération de colonnes. Ce problème met en évidence les limitations du modèle IRP classique, ce qui nous a amené à définir un modèle d’IRP plus réaliste. Finalement, une méthode de décomposition basée sur la relaxation lagrangienne est développée pour la résolution de ce problème dans le but de minimiser la consommation énergétique.

Abstract

The thesis studies the Inventory Routing Problem (IRP) with explicit energy consideration. Under the Vendor Managed Inventory (VMI) model, the IRP is an integration of the inventory management and routing, where both inventory storage and transportation costs are taken into account. Under the new sustainability paradigm, green transport and logistics has become an emerging area of study, but few research focus on the ecological aspect of the classical IRP. Since the classical IRP concentrates solely on the economic benefits, it is worth studying under the energy perspective. The thesis gives an estimation of the energetic gain that a better supplying plan can provide. More specifically, this thesis integrates the energy consumption into the decision of the inventory replenishment and routing. It starts with a part supplying problem in car assembly lines, where the transported mass, the vehicle dynamics and the travelled distance are identified as main energy influencing factors. This result is extended to the classical IRP with energy objective to show the potential energy reduction that can be achieved. Then, an industrial challenge of IRP is presented and solved using a column generation approach. This problem put the limitations of the classical IRP model in evidence, which brings us to define a more realistic IRP model on a multigraph. Finally, a Lagrangian relaxation method is presented for solving this new model with the aim of energy minimization.

Mots-Clés / Keywords
Inventory routing problem; Logistics; Energy; Problème de tournées de véhicules avec gestion de stock; Logistique; Energie;

141693
17338
22/06/2017

Co-optimisation charge utile satellite et système télécom

J.CAMINO

ROC

Doctorat : Université de Toulouse III - Paul Sabatier, 22 Juin 2017, 201p., Président: P.MAHEY, Rapporteurs: A.ROSSI, V.GABREL, Examinateurs: G.DANOY, Directeurs de thèse: C.ARTIGUES, L.HOUSSIN , N° 17338

Diffusable

Plus d'informations

Résumé

L’augmentation continue des besoins en télécommunications dans notre société se traduit par une suite de défis technologiques pour les systèmes fournissant ce type de services, qu’il s’agisse de télédiffusion, de téléphonie, ou bien d’échange de données. Les satellites de télécommunications sont ainsi particulièrement concernés par ce besoin d’innover, à la fois sur les technologies mises en orbite, mais aussi et surtout au niveau de l’exploitation de ces ressources embarquées. Sur ce dernier point, pour une mission de télécommunications définie précisément en termes de zone à servir, de type, de quantité et de qualité de service à fournir, il faut effectivement être capable de dimensionner de la manière la plus adéquate possible la charge utile du satellite de télécommunications, sous les différentes contraintes auxquelles elle est soumise : masse, volume, coût, et consommation énergétique des équipements embarqués. Cette thèse développe ainsi une approche algorithmique pour un tel dimensionnement dans le cas particulier des systèmes de télécommunications dits “multifaisceaux”. Une procédure d’optimisation globale de ces systèmes satellitaires est ainsi proposée. Elle repose sur une décomposition en un ensemble de problèmes mathématiques interconnectés dont les complexités respectives, réduites par rapport au problème global, permettent d’espérer des solutions algorithmiques efficaces. Ce travail a permis d’exhiber deux problèmes phares dans ce dimensionnement de la charge utile satellite, adressés par l’angle de la recherche opérationnelle : l’optimisation du placement de faisceaux, et l’optimisation de plans de fréquences. Ce premier problème de placement de faisceaux sous contraintes de charge utile a été l’occasion de proposer des méthodologies inédites de gestion des contraintes en norme euclidienne sur des variables continues pour les problèmes mixtes non-linéaires non-convexes. Ces techniques ont alors été appliquées avec succès au sein de solutions à ce premier problème qui s’appuient pleinement sur la programmation linéaire mixte. Dans un deuxième temps, une exploitation novatrice de certaines propriétés du clustering en k-moyennes est proposée et permet de simplifier ces modèles mathématiques et ainsi accélérer l’optimisation du placement des faisceaux. Ces algorithmes de programmation mathématique sont ensuite confrontés à une heuristique gloutonne randomisée également développée dans le cadre de ces travaux. Le deuxième problème central de dimensionnement identifié au cours de ces travaux de thèse est la définition de plans de fréquences. Il s’agit d’une allocation de ressource disponible à bord du satellite aux différents faisceaux de ce dernier, tels qu’ils ont été définis dans le problème précédent de placement de faisceaux. Avec un objectif de minimisation du nombre d’un certain type d’équipement à embarquer dans la charge utile satellite, on cherche à satisfaire la mission de télécommunications qui s’exprime en une demande de chaque utilisateur au sol. Ce problème complexe a lui-même donné lieu à une décomposition en deux sous-problèmes d’allocation de fréquences, puis d’allocation d’équipements de la charge utile, qui sont traités par programmation par contraintes et programmation linéaire en nombres entiers, en exploitant des résultats théoriques qui servent à la fois à la modélisation des problèmes, mais aussi à leur résolution.

Mots-Clés / Keywords
Recherche opérationnelle; Télécommunication; Systèmes satellitaires;

141113
16478
07/12/2016

Harnessing tractability in constraint satisfaction problems

C.CARBONNEL

ROC

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

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

Diffusable

Plus d'informations

Abstract

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

Résumé

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

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

138577
16373
17/11/2016

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

G.SCANO

ROC

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

Non diffusable

Plus d'informations

Abstract

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

Résumé

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

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

138014
16382
18/10/2016

Ordonnancement sous contraintes d’énergie

M.NATTAF

ROC

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

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