Texte remanié de: Th. doct.--Department of economics--University of Warwick. / Bibliogr. p. 137-141.

Th. doct.--Informatique--Nice, 1997. / Bibliogr. p. 159-165. Résumé en français et en anglais. 1997 d'après la déclaration de dépôt légal.

Étant donnés un planning aérien et des prévisions de demande, le problème d'affectation de flotte aérienne consiste à déterminer la meilleure façon de répartir les types d'appareils sur les vols. Cette répartition a un impact majeur sur le profit d'une compagnie aérienne, puisqu'elle détermine les quantités de places disponibles sur les itinéraires du réseau aérien, ainsi que le coût de fonctionnement de celui-ci. Des décennies de recherche ont rendues les modélisations de ce problème de plus en plus réalistes. Cette thèse s'inscrit dans la continuité de ces recherches en considérant le problème d'affectation de flotte dans un contexte où les demandes des passagers sont incertaines. Nous proposons dans un premier temps une étude autour des deux modèles de la littérature les plus utilisés dans l'industrie, FAM et IFAM. Nous montrons que FAM peut être vu comme une Relaxation Lagrangienne de IFAM, avec des multiplicateurs Lagrangiens particuliers. Nous implémentons cette relaxation, et nous appliquons des résultats connus pour l'étendre en une génération de colonnes basée sur une décomposition de Dantzig-Wolfe de IFAM. Nous étudions ensuite les effets que l'imprécision des prévisions peut avoir sur la performance d'IFAM, et nous présentons au terme de cette étude une nouvelle approche pour modéliser le problème d'affectation de flotte. Notre modèle, Market Driven Fleet Assignment Model (MDFAM), intègre les demandes par itinéraires comme variables de décision, et contraint ces demandes plutôt que de les considérer comme une entrée fixe. Nous appelons les contraintes résultantes des contraintes de Marché. Nous illustrons la flexibilité de cette approche à travers divers exemples, et nous proposons une série d'expériences visant à déterminer quelles sont les contraintes de marché donnant les meilleurs résultats. Nous comparons les différents modèles, et nous montrons que MDFAM peut atteindre des niveaux de performance similaires à ceux offert par IFAM, tout en étant plus facile à utiliser et à implémenter. / Given an airline schedule and demand forecasts, the Fleet Assignment Problem consists in determining how to assign aircraft types to flight legs in the best possible way. This assignment has a major impact on the profit of an airline, since it determines the quantities of seats available over the itineraries of the flight network, along with the associated operating cost. Decades of research on this problem have improved the formulations to be more and more realistic. This thesis extends the ongoing work, considering the problem of doing Fleet Assignment taking demand volatility into account. We first propose a study involving the two models of the literature that are the most widely used by the industry, FAM and IFAM. We show that FAM can be seen as a Lagrangian Relaxation of IFAM, with particular Lagrangian multipliers. We implement this relaxation, and we apply known results to extend it in a column generation based on a Dantzig-Wolfe decomposition of IFAM. We then study the effects of forecasts inaccuracy over the performance of IFAM, and we present a novel approach for modeling the Fleet Assignment Problem. Our model, Market Driven Fleet Assignment Model (MDFAM), makes the itinerary demands part of the decision variables. We propose to constraint these variables rather than consider them as a fixed input of the problem, and we call the resulting constraints Market Constraints. We illustrate the flexibility of this approach through various examples, and we provide a series of experiments in order to determine which Market Constraints give the best results. We compare the different models, and we show that MDFAM can reach a performance which is similar to IFAM's, while being easier to use and to implement.

Avec l’avènement de la décentralisation au Sahel depuis les années 90 et l’expérience acquise par les pays du Sahel, suite aux sécheresses à répétition1 qui ont affecté leurs zones, des systèmes d’information pour la planification d’actions de développement voient le jour à différentes échelles territoriales. Mais, selon l’avis des communautés de base, ces outils mis en place au niveau local et destinés à l’aménagement du territoire, tant au niveau de la collecte des données que de l’usage du système d’information obtenu, demeurent toujours en deçà de leurs attentes et reste à la disposition et au service exclusifs des décideurs et des techniciens.Or, la prise en compte des connaissances locales des populations, notamment celles relatives à l’information géographique, donne des moyens plus efficients de collecte de données, à partir desquelles peuvent être construits des outils adaptés à la participation et à la négociation entre les différents acteurs et à la planification de projets économiques, ce qui nécessite l’élaboration d’une approche basée sur l’analyse et une gestion participative de l’information géographique issues des connaissances des dites populations.La présente thèse veut accompagner les acteurs locaux des régions sahéliennes dans la mise en oeuvre du développement local de leurs collectivités territoriales, et dans le renforcement de leur citoyenneté par une meilleure participation aux prises de décision. Il s’agira de contribuer à une bonne gestion des ressources naturelles par l’élaboration de plans d’aménagement des différentes zones à travers une gestion participative de l’information géographique locale et la mobilisation des connaissances et savoir-faire locaux.La question est de savoir comment co-définir avec les populations sahéliennes les plans de développement locaux, avec chacune ses spécificités socio-économiques (pasteurs, agropasteurs, agriculteurs, leaders d’opinions, agents d’Etat…) et intégrer leurs connaissances, notamment spatiales, dans la conception d’outils de planification de projets de développement économique.Les résultats de l’expérience menée dans le Nord du Mali ont permis de faire le point surl’état d’avancement des processus de décentralisation, des difficultés de participation despopulations locales dans les prises de décision, des approches du développement local et l’immense connaissance des communautés. Ces résultats ouvrent également des perspectives pour le développement local des collectivités spécifiques du Sahel en les dotant d’outils de planification issus d’une gestion harmonieuse et participative de l’information géographique locale. / When decentralization came to the Sahel in the 90s, and with the experienced gained after repeated droughts impacting their countries, information systems for planning development actions were implemented at various levels. But, according to the communities, these tools implemented at the local level for land planning, both for data collection and using the information system thus obtained, fell short of expectations and remain in the exclusive hands of decision-makers and technicians.Yet, when the expertise of the people is taken into account, including geographic information,data collecting is made easier and can help build tools tailored to the participation and negotiation between the various operators and program economic projects, which requires an approach based on the analysis and participative management of geographical management based on the expertise of these peoples.This thesis aims to be a support for local operators in the Sahel region when implementinglocal development plans and empower them by allowing a larger say in the decision making process. The aim is to contribute to a sound natural resources management by the development of management plans in the various areas, through a participative management of local geographical information and by mobilizing local expertise and knowhow.The question is how to define local development plans with the Sahel peoples, each with its own socio-economic specificity (pastoralists, agro-pastoralists, farmers, public figures, state officials ...) and to integrate their expertise, including their spatial expertise, in the developments of planning tools for economic development programmes.The results of the Southern Mali experience was an opportunity to take stock of the progress in the decentralization process, of the difficulties in having local peoples participate in decision making, of local development approaches and the vast expertise of the communities. These results offer prospects for the local development of specific communities in the Sahel, giving them planning tools based on a well-balanced participative management of local geographic expertise.

Est-il encore possible, dans les conditions économiques, démographiques, sociales et politiques actuelles, de planifier l’aménagement des villes ?Ou faut-il considérer que, pour le développement urbain, « planifier l’avenir ou même simplement élaborer une stratégie à partir d’une évaluation à priori des besoins à satisfaire n’apparaît plus ni possible ni utile » (Crozier, 1989) ?Qu’il s’agisse de la programmation du sol, de l’organisation de l’espace bâti ou de la gestion des rapports entre programmation du sol et espace bâti, nous tentons, dans cette recherche, d’identifier les instruments susceptibles de rendre opérationnelle l’action publique d’aménagement urbain ainsi que les conditions qui permettent aux acteurs qui y participent de s’en saisir. / Doctorat en Art de bâtir et urbanisme (Architecture) / info:eu-repo/semantics/nonPublished

La production de la circulation ferroviaire nécessite l’utilisation et le partage deressources critiques et hétérogènes, notamment le réseau ferroviaire et lesressources roulantes et humaines. Un schéma communément adopté décompose laplanification selon les niveaux décisionnels et les ressources.Depuis les dernières années, les acteurs ferroviaires accordent un intérêt croissant àla robustesse de la circulation ferroviaire. Néanmoins, toutes les stratégies étudiéesse concentrent sur une seule ressource à la fois, négligeant ainsi le partage desressources et son impact sur la robustesse. Or, la séquentialité de la planificationdes ressources peut augmenter la propagation des retards sur les autres trains.L’intégration des décisions tactiques des trois ressources infrastructure, engins etagents de conduite peut aboutir à un plan de transport plus robuste dans le sens dela propagation des retards. Les motivations principales de la thèse émanent de cetteidée.L’objectif de ce travail est d’aboutir à des outils d’aide à la décision pour proposerune planification intégrée et robuste des ressources ferroviaires au niveau tactique.Nous proposons dans cette thèse plusieurs contributions :1. Un modèle d’optimisation qui vise à élaborer un plan de transport robuste destrois ressources critiques simultanément.2. Un modèle de simulation à événements discrets pour évaluer la robustesse desplans de transport. Nous tentons dans cette phase de reproduire le comportementréel du système ferroviaire et l’utilisation des trois ressources critiques. / The railway operations' planning consists in finding the best use of the available infrastructure, rollingstock and crew units to cover a given timetable. A commonly adopted scheme breaks down planningas decision-making levels and resources.However, the occurrence of perturbations may deteriorate the quality of the solutions or even makethem infeasible. Therefore, railway operators aim to find robust schedules that minimize the impact ofperturbations. To this purpose, the decisions made for each resource (infrastructure, rolling stock andcrew) must include the demand cover as well as the robustness objectives.Nevertheless, all tested strategies focus on a single resource at a time, neglecting resource sharing andits impact on the robustness. But the sequential scheme of resource planning can increase thepropagation delays on other trains. Integrating of tactical decisions of the three resourcesinfrastructure, rolling stock and crew can result in a more robust schedule that minimizes thepropagation of delays. The main motivations of the thesis come from this idea.The objective of this work is to develop decision support tools that provide an integrated and robustplanning of railway resources at the tactical level. We propose in this thesis several contributions:1. An optimization model that aims to develop a robust transport plan of the three critical resourcessimultaneously.2. A simulation model (discrete event) to assess the robustness of transport plans. We are trying at thisstage to reproduce the actual behavior of the rail system and the use of three critical resources.

Ce travail de thèse s'inscrit dans le développement d'un véhicule autonome en milieu autoroutier. Plus précisément, il s'agit de proposer une architecture unifiée de génération de trajectoires avec une prise de décision prenant en compte les limitations de l'environnement et des informations disponibles actuellement sur un véhicule automatisé.La méthode propose d'une part de générer des trajectoires sous forme de sigmoı̈de dans une représentation spatiotemporelle continue de l'espace de navigation, préalablement réduit par la modélisation d'intervalles sans collision en conditionnominale de conduite. Les paramètres de la sigmoı̈de sont ensuite optimisés par une stratégie de recuit simulé utilisant l'algorithme de prise de décision comme fonction d'évaluation de la trajectoire générée. De cette manière, les problèmes de discrétisation et de découplage position/vitesse sont évités. D'autre part, l'agrégation des théories de logique floue etdes croyances permet une prise de décision sur des critères hétérogènes et des données incertaines. Le formalisme présenté offre la possibilité d'adapter le comportement du véhicule aux passagers, notamment selon leur perception du risque et leur souhait d'une conduite souple ou sportive.L'approche développée a finalement été évaluée et validée en environnement de simulation puis sur un véhicule de test. La brique de planification a alors été intégrée à l'architecture existante du véhicule, en aval des briques de localisation et de perception des obstacles et en amont de la brique de contrôle. / This thesis work is part of the development of a self-driving car in highway environments. More precisely, it aims to propose a unified architecture of trajectory planner and decision-maker taking into account the limitations of the environment and the available data within the current development of sensors technologies (distance limitations, uncertainties).On the one hand, the method generates sigmoid trajectories in a continuous spatiotemporal representation of the evolution space, which is reduced beforehand by modeling collision-free intervals in nominal conditions of driving. The sigmoid parameters are subsequently optimized with a simulated annealing approach that uses the decision-maker algorithm as the evaluation function for the generated trajectory. It thus makes it possible to elude both the discretization and position/speed decoupling problems. On the other hand, the aggregation of fuzzy logic and belief theory allows decision making on heterogeneous criteria and uncertain data. The proposed framework also handles personalization of the vehicle's behavior, depending on the passengers' risk perception and an aggressive or conservative driving style.The presented approach was finally evaluated and validated in a simulation environment, and then in a test vehicle. The planning block was integrated into the existing vehicle's architecture, interfaced with the localization, obstacles' perception and control blocks.

Le stockage de contenu populaire dans des caches disponibles aux utilisateurs, est une technique émergente qui permet de réduire le trafic dans les réseaux sans fil. En particulier, le coded caching proposée par Maddah-Ali et Niesen a été considéré comme une approche prometteuse pour atteindre un temps de livraison constant au fur et à mesure que la dimension augmente. Toutefois, plusieurs limitations empêchent ses applications. Nous avons adressé les limitations de coded caching dans les réseaux sans fil et avons proposé des schémas de livraison qui exploitent le gain de coded caching. Dans la première partie de la thèse, nous étudions la région de capacité pour un canal à effacement avec cache et retour d'information. Nous proposons un schéma et prouvons son optimalité pour des cas particuliers. Ces résultats sontgénéralisés pour le canal à diffusion avec desantennes multiples et retour d'information. Dans la deuxième partie, nous étudions la livraison de contenu sur un canal d'atténuation asymétrique, où la qualité du canal varie à travers les utilisateurs et le temps. En supposant que les demandes des utilisateurs arrivent de manière dynamique, nous concevons un schéma basé sur une structure de queues et nous prouvons qu’il maximise la fonction d'utilité par rapport à tous les schémas limités au cache décentralisé. Dans la dernière partie, nous étudions la planification opportuniste pour un canal d'atténuation asymétrique, en assurant une métrique de justice entre des utilisateurs. Nous proposons une politique de planification simple à base de seuil avec une complexité linéaire et qui exige seulement un bit de retour de chaque utilisateur. / Caching, i.e. storing popular contents at caches available at end users, has received a significant interest as a technique to reduce the peak traffic in wireless networks. In particular, coded caching proposed by Maddah-Ali and Niesen has been considered as a promising approach to achieve a constant delivery time as the dimension grows. However, several limitations prevent its applications in practical wireless systems. Throughout the thesis, we address the limitations of classical coded caching in various wireless channels. Then, we propose novel delivery schemes that exploit opportunistically the underlying wireless channels while preserving partly the promising gain of coded caching. In the first part of the thesis, we study the achievable rate region of the erasure broadcast channel with cache and state feedback. We propose an achievable schemeand prove its optimality for special cases of interest. These results are generalized to the multi-antenna broadcast channel with state feedback. In the second part, we study the content delivery over asymmetric block-fading broadcast channels, where the channel quality varies across users and time. Assuming that user requests arrive dynamically, we design an online scheme based on queuing structure and prove that it maximizes the alpha-fair utility among all schemes restricted to decentralized placement. In the last part, we study opportunistic scheduling over the asymmetric fading broadcast channel and aim to design a scalable delivery scheme while ensuring fairness among users. We propose a simple threshold-based scheduling policy of linear complexity that requires only a one-bit feedback from each user.

Afin que les robots humanoïdes puissent travailler avec les humains et être en mesure de résoudre des tâches répétitives, nous devons leur permettre de planifier leurs mouvements de façon autonome. La planification de mouvement est un problème de longue date en robotique, et tandis que sa fondation algorithmique a été étudiée en profondeur, la planification de mouvement est encore un problème NP-difficile et qui manque de solutions efficaces. Nous souhaitons ouvrir une nouvelle perspective sur le problème en mettant en évidence sa structure: le comportement du robot, le système mécanique du robot et l’environnement du robot. Nous allons nous intéresser à l’hypothèse que chaque composante structurelle peut être exploitée pour créer des algorithmes de planification de mouvement plus efficaces. Nous présentons trois algorithmes exploitant la structure, basés sur des arguments géométriques et topologiques: d’abord, nous exploitons le comportement d’un robot de marche en étudiant la faisabilité des transitions des traces de pas. L’algorithme qui en résulte est capable de planifier des traces de pas tout en évitant jusqu’à 60 objets situés sur une surface plane 6 mètres carrés. Deuxièmement, nous exploitons le système mécanique d’un robot humanoïde en étudiant les structures des liaisons linéaires de ses bras et de ses jambes. Nous introduisons le concept d’une trajectoire irréductible, qui est une technique de réduction de dimension préservant la complétude. L’algorithme résultant est capable de trouver des mouvements dans des environnements étroits, où les méthodes d’échantillonnage ne pouvaient pas être appliquées. Troisièmement, nous exploitons l’environnement en raisonnant sur la structure topologique des transitions de contact. Nous montrons que l’analyse de l’environnement est une méthode efficace pour pré-calculer les informations pertinentes pour une planification de mouvement efficace. En s’appuyant sur ces résultats, nous arrivons à la conclusion que l’exploitation de la structure est une composante essentielle de la planification de mouvement efficace. Il en résulte que tout robot humanoïde, qui veut agir efficacement dans le monde réel, doit être capable de comprendre et d’exploiter la structure. / If humanoid robots should work along with humans and should be able to solve repetitive tasks, we need to enable them with a skill to autonomously plan motions. Motion planning is a longstanding core problem in robotics, and while its algorithmic foundation has been studied in depth, motion planning is still an NP-hard problem lacking efficient solutions. We want to open up a new perspective on the problem by highlighting its structure: the behavior of the robot, the mechanical system of the robot, and the environment of the robot. We will investigate the hypothesis that each structural component can be exploited to create more efficient motion planning algorithms. We present three algorithms exploiting structure, based on geometrical and topological arguments: first, we exploit the behavior of a walking robot by studying the feasibility of footstep transitions. The resulting algorithm is able to plan footsteps avoiding up to 60 objects on a 6 square meters planar surface. Second, we exploit the mechanical system of a humanoid robot by studying the linear linkage structures of its arms and legs. We introduce the concept of an irreducible motion, which is a completeness-preserving dimensionality reduction technique. The resulting algorithm is able to find motions in narrow environments, where previous sampling-based methods could not be applied. Third, we exploit the environment by reasoning about the topological structure of contact transitions. We show that analyzing the environment is an efficient method to precompute relevant information for efficient motion planning. Based on those results, we come to the conclusion that exploiting structure is an essential component of efficient motion planning. It follows that any humanoid robot, who wants to act efficiently in the real world, needs to be able to understand and to exploit structure.

Dans cette thèse, nous analysons le problème de l'intégration de la planification de production et de la maintenance préventive, ainsi que l'élaboration du système de contrôle de la qualité. Premièrement, on considère un système de production composé d'une machine et de plusieurs produits dans un contexte incertain, dont les prix et le coût changent d'une période à l'autre. La machine se détériore avec le temps et sa probabilité de défaillance, ainsi que le risque de passage à un état hors contrôle augmentent. Le taux de défaillance dans un état dégradé est plus élevé et donc, des coûts liés à la qualité s’imposent. Lorsque la machine tombe en panne, une maintenance corrective ou une réparation minimale seront initiées pour la remettre en marche sans influer ses conditions ou le processus de détérioration. L'augmentation du nombre de défaillances de la machine se traduit par un temps d'arrêt supérieur et un taux de disponibilité inférieur. D'autre part, la réalisation des plans de production est fortement influencée par la disponibilité et la fiabilité de la machine. Les interactions entre la planification de la maintenance et celle de la production sont incorporées dans notre modèle mathématique. Dans la première étape, l'effet de maintenance sur la qualité est pris en compte. La maintenance préventive est considérée comme imparfaite. La condition de la machine est définie par l’âge actuel, et la machine dispose de plusieurs niveaux de maintenance avec des caractéristiques différentes (coûts, délais d'exécution et impacts sur les conditions du système). La détermination des niveaux de maintenance préventive optimaux conduit à un problème d’optimisation difficile. Un modèle de maximisation du profit est développé, dans lequel la vente des produits conformes et non conformes, les coûts de la production, les stocks tenus, la rupture de stock, la configuration de la machine, la maintenance préventive et corrective, le remplacement de la machine et le coût de la qualité sont considérés dans la fonction de l’objectif. De plus, un système composé de plusieurs machines est étudié. Dans cette extension, les nombres optimaux d’inspections est également considéré. La fonction de l’objectif consiste à minimiser le coût total qui est la somme des coûts liés à la maintenance, la production et la qualité. Ensuite, en tenant compte de la complexité des modèles préposés, nous développons des méthodes de résolution efficaces qui sont fondées sur la combinaison d'algorithmes génétiques avec des méthodes de recherches locales. On présente un algorithme mimétique qui emploi l’algorithme Nelder-Mead, avec un logiciel d'optimisation pour déterminer les valeurs exactes de plusieurs variables de décisions à chaque évaluation. La méthode de résolution proposée est comparée, en termes de temps d’exécution et de qualités des solutions, avec plusieurs méthodes Métaheuristiques. Mots-clés : Planification de la production, Maintenance préventive imparfaite, Inspection, Qualité, Modèles intégrés, Métaheuristiques / In this thesis, we study the integrated planning of production, maintenance, and quality in multi-product, multi-period imperfect systems. First, we consider a production system composed of one machine and several products in a time-varying context. The machine deteriorates with time and so, the probability of machine failure, or the risk of a shift to an out-of-control state, increases. The defective rate in the shifted state is higher and so, quality related costs will be imposed. When the machine fails, a corrective maintenance or a minimal repair will be initiated to bring the machine in operation without influencing on its conditions or on the deterioration process. Increasing the expected number of machine failures results in a higher downtime and a lower availability rate. On the other hand, realization of the production plans is significantly influenced by the machine availability and reliability. The interactions between maintenance scheduling and production planning are incorporated in the mathematical model. In the first step, the impact of maintenance on the expected quality level is addressed. The maintenance is also imperfect and the machine conditions after maintenance can be anywhere between as-good-as-new and as-bad-as-old situations. Machine conditions are stated by its effective age, and the machine has several maintenance levels with different costs, execution times, and impacts on the system conditions. High level maintenances on the one hand have greater influences on the improvement of the system state and on the other hand, they occupy more the available production time. The optimal determination of such preventive maintenance levels to be performed at each maintenance intrusion is a challenging problem. A profit maximization model is developed, where the sale of conforming and non-conforming products, costs of production, inventory holding, backorder, setup, preventive and corrective maintenance, machine replacement, and the quality cost are addressed in the objective function. Then, a system with multiple machines is taken into account. In this extension, the number of quality inspections is involved in the joint model. The objective function minimizes the total cost which is the sum of maintenance, production and quality costs. In order to reduce the gap between the theory and the application of joint models, and taking into account the complexity of the integrated problems, we have developed an efficient solution method that is based on the combination of genetic algorithms with local search and problem specific methods. The proposed memetic algorithm employs Nelder-Mead algorithm along with an optimization package for exact determination of the values of several decision variables in each chromosome evolution. The method extracts not only the positive knowledge in good solutions, but also the negative knowledge in poor individuals to determine the algorithm transitions. The method is compared in terms of the solution time and quality to several heuristic methods. Keywords : Multi-period production planning, Imperfect preventive maintenance, Inspection, Quality, Integrated model, Metaheuristics