Abstract not available

For thesis abstract select View Thesis Title, Contents and Abstract

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

The Constrained Shortest Path Problem (CSPP) consists of finding the shortest path in a graph or network that satisfies one or more resource constraints. Without these constraints, the shortest path problem can be solved in polynomial time; with them, the CSPP is NP-hard and thus far no polynomial-time algorithms exist for solving it optimally. The problem arises in a number of practical situations. In the case of vehicle path planning, the vehicle may be an aircraft flying through a region with obstacles such as mountains or radar detectors, with an upper bound on the fuel consumption, the travel time or the risk of attack. The vehicle may be a submarine travelling through a region with sonar detectors, with a time or risk budget. These problems all involve a network which is a discrete model of the physical domain. Another example would be the routing of voice and data information in a communications network such as a mobile phone network, where the constraints may include maximum call delays or relay node capacities. This is a problem of current economic importance, and one for which time-sensitive solutions are not always available, especially if the networks are large. We consider the simplest form of the problem, large grid networks with a single side constraint, which have been studied in the literature. This thesis explores the application of Constraint Programming combined with Lagrange Relaxation to achieve optimal or near-optimal solutions of the CSPP. The following is a brief outline of the contribution of this thesis. Lagrange Relaxation may or may not achieve optimal or near-optimal results on its own. Often, large duality gaps are present. We make a simple modification to Dijkstra’s algorithm that does not involve any additional computational work in order to generate an estimate of path time at every node. / We then use this information to constrain the network along a bisecting meridian. The combination of Lagrange Relaxation (LR) and a heuristic for filtering along the meridian provide an aggressive method for finding near-optimal solutions in a short time. Two network problems are studied in this work. The first is a Submarine Transit Path problem in which the transit field contains four sonar detectors at known locations, each with the same detection profile. The side constraint is the total transit time, with the submarine capable of 2 speeds. For the single-speed case, the initial LR duality gap may be as high as 30%. The first hybrid method uses a single centre meridian to constrain the network based on the unused time resource, and is able to produce solutions that are generally within 1% of optimal and always below 3%. Using the computation time for the initial Lagrange Relaxation as a baseline, the average computation time for the first hybrid method is about 30% to 50% higher, and the worst case CPU times are 2 to 4 times higher. The second problem is a random valued network from the literature. Edge costs, times, and lengths are uniform, randomly generated integers in a given range. Since the values given in the literature problems do not yield problems with a high duality gap, the values are varied and from a population of approximately 100,000 problems only the worst 200 from each set are chosen for study. These problems have an initial LR duality gap as high as 40%. A second hybrid method is developed, using values for the unused time resource and the lower bound values computed by Dijkstra’s algorithm as part of the LR method. The computed values are then used to position multiple constraining meridians in order to allow LR to find better solutions. / This second hybrid method is able to produce solutions that are generally within 0.1% of optimal, with computation times that are on average 2 times the initial Lagrange Relaxation time, and in the worst case only about 5 times higher. The best method for solving the Constrained Shortest Path Problem reported in the literature thus far is the LRE-A method of Carlyle et al. (2007), which uses Lagrange Relaxation for preprocessing followed by a bounded search using aggregate constraints. We replace Lagrange Relaxation with the second hybrid method and show that optimal solutions are produced for both network problems with computation times that are between one and two orders of magnitude faster than LRE-A. In addition, these hybrid methods combined with the bounded search are up to 2 orders of magnitude faster than the commercial CPlex package using a straightforward MILP formulation of the problem. Finally, the second hybrid method is used as a preprocessing step on both network problems, prior to running CPlex. This preprocessing reduces the network size sufficiently to allow CPlex to solve all cases to optimality up to 3 orders of magnitude faster than without this preprocessing, and up to an order of magnitude faster than using Lagrange Relaxation for preprocessing. Chapter 1 provides a review of the thesis and some terminology used. Chapter 2 reviews previous approaches to the CSPP, in particular the two current best methods. Chapter 3 applies Lagrange Relaxation to the Submarine Transit Path problem with 2 speeds, to provide a baseline for comparison. The problem is reduced to a single speed, which demonstrates the large duality gap problem possible with Lagrange Relaxation, and the first hybrid method is introduced. / Chapter 4 examines a grid network problem using randomly generated edge costs and weights, and introduces the second hybrid method. Chapter 5 then applies the second hybrid method to both network problems as a preprocessing step, using both CPlex and a bounded search method from the literature to solve to optimality. The conclusion of this thesis and directions for future work are discussed in Chapter 6.

Aujourd’hui, la localisation de robots sous-marins demeure une tâche complexe. L’utilisation de capteurs habituels est impossible sous la surface, tels que ceux reposant sur les systèmes de géolocalisation par satellites. Les approches inertielles sont quant à elles limitées par leur forte dérive dans le temps. De plus, les fonds marins sont généralement homogènes et non structurés, rendant difficile l’utilisation de méthodes SLAM connues, qui couplent la localisation et la cartographie de manière simultanée. Il devient donc nécessaire d’explorer de nouvelles alternatives. Notre approche consiste à traiter un problème de SLAM de manière purement temporelle. L’originalité de ce travail est de représenter le temps comme une variable classique qu’il faut estimer. Cette stratégie soulève de nouvelles opportunités dans le domaine de l’estimation d’état, permettant de traiter de nombreux problèmes sous un autre angle. Toutefois, une telle résolution temporelle demande un ensemble d’outils théoriques qu’il convient de développer. Cette thèse n’est donc pas seulement une contribution dans le monde de la robotique mobile, elle propose également une nouvelle démarche dans les domaines de la propagation de contraintes et des méthodes ensemblistes. Cette étude apporte de nouveaux outils de programmation par contracteurs qui permettent le développement de solveurs pour des systèmes dynamiques. Les composants étudiés sont mis en application tout au long de ce document autours de problèmes robotiques concrets. / The localization of underwater robots remains a challenging issue. Usual sensors, such as Global NavigationSatellite System (GNSS) receivers, cannot be used under the surface and other inertial systems suffer from a strong integration drift. On top of that, the seabed is generally uniform and unstructured, making it difficult to apply usual Simultaneous Localization and Mapping (SLAM) methods to perform a localization.Hence, innovative approaches have to be explored. The presented method can be characterized as a raw-data SLAM approach, but we propose a temporal resolution – which differs from usual methods – by considering time as a standard variable to be estimated. This concept raises new opportunities for state estimation, under-exploited so far. However, such temporal resolution is not straightforward and requires a set of theoretical tools in order to achieve the main purpose of localization.This thesis is thus not only a contribution in the field of mobile robotics, it also offers new perspectives in the areas of constraint programming and set-membership approaches. We provide a reliable contractor programming framework in order to build solvers for dynamical systems. This set of tools is illustrated throughout this document with realistic robotic applications.

Ce mémoire présente une approche basée sur des méthodes garanties pour résoudre des problèmes d’optimisation de systèmes dynamiques multi-physiques. Ces systèmes trouvent des applications directes dans des domaines variés tels que la conception en ingéniérie, la modélisation de réactions chimiques, la simulation de systèmes biologiques ou la prédiction de la performance sportive.La résolution de ces problèmes d’optimisation s’effectue en deux phases. La première consiste à mettre le problème en équations sous forme d’un modèle mathématique constitué d’un ensemble de variables, d’un ensemble de contraintes algébriques et fonctionelles ainsi que de fonctions de coût. Celles-ci sont utilisées lors de la seconde phase qui consiste à d’extraire du modèle les solutions optimales selon plusieurs critères (volume, poids, etc).Les contraintes algébriques permettent de manipuler des grandeurs statiques (quantité, taille, densité, etc). Elles sont non linéaires, non convexes et parfois discontinues.Les contraintes fonctionnelles permettent de manipuler des grandeurs dynamiques. Ces contraintes peuvent être relativement simples comme la monotonie ou la périodicité, mais aussi bien plus complexe par la prise en compte de contraintes différentielles simples ou définies par morceaux. Les équations différentielles sont utilisées pour modéliser des comportements physico-chimiques (magnétiques, thermiques, etc) et d’autres caractéristiques qui varient lors de l’évolution du système.Il existe plusieurs niveaux d’approximation pour chacune de ces deux phases. Ces approximations donnent des résultats pertinents, mais elles ne permettent pas de garantir l’optimalité ni la réalisabilité des solutions.Après avoir présenté un ensemble de méthodes garanties permettant de résoudre de manière garantie des équations différentielles ordinaires, nous formalisons un modèle particulier de systèmes hybrides sous la forme d’équations différentielles ordinaires par morceaux. A l’aide de plusieurs preuves et théorèmes nous étendons la première méthode de résolution pour résoudre de manière garantie ces équations différentielles par morceaux. Dans un second temps, nous intégrons ces deux méthodes au sein d’un module de programmation par contracteurs, que nous avons implémenté. Ce module basé sur des méthodes garantie permet de résoudre des problèmes de satisfaction de contraintes algébriques et fonctionnelles. Ce module est finalement utilisé dans un algorithme d’optimisation globale déterministe modulaire permettant de résoudre les problèmes considérés. / In this thesis a set of tools based on guaranteed methods are presented in order to solve multi-physics dynamic problems. These systems can be applied in various domains such that engineering design process, model of chemical reactions, simulation of biological systems or even to predict athletic performances.The resolution of these optimization problems is made of two stages. The first one consists in defining a mathematical model by setting up the equations for the problem. The model is made of a set of variables, a set of algebraic and functional constraints and cost functions. The latter are used in the second stage in order to extract the optimal solutions from the model depending on several criteria (volume, weight, etc).Algebraic constraints are used to describe the static properties of the system (quantity, size, density, etc). They are non-linear, non-convex and sometimes discontinuous. Functional constraints are used to manipulate dynamic quantities. These constraints can be quite simple such as monotony or periodicity or they can be more complex such as simple or piecewise differential constraints. Differential equations are used to describe physico-chemical properties (magnetic, thermal, etc) and other features evolving with the component use. Several levels of approximation exist for each of these two stages. These approximations give some relevant results but they do not guarantee the feasibility nor the optimality of the solutions.After presenting a set of guaranteed methods in order to perform the guaranteed integration of ordinary differential equations, a peculiar type of hybrid system that can be modeled with piecewise ordinary differential equation is considered. A new method that computes guaranteed integration of these piecewise ordinary differential equations is developed through an extension of the initial algorithm based on several proofs and theorems. In a second step these algorithms are gathered within a contractor programming module that have been implemented. It is used to solve algebraic and functional constraint satisfaction problems with guaranteed methods. Finally, the considered optimization problems are solved with a modular deterministic global optimization algorithm that uses the previous modules.

Cette thèse a pour objectif d'étudier l'utilisation de la programmation par contraintes pour développer un solveur de planification de production. Nous nous concentrons sur des problèmes de dimensionnement de lots de production (lot-sizing) qui sont des problèmes majeurs et difficiles de la planification de la production et profitons d'une des principales forces de la programmation par contraintes, à savoir les contraintes globales. Nous définissons une contrainte globale LotSizing qui s'appuie sur un problème générique de lot-sizing mono-produit à un seul niveau, qui tient compte des capacités de production et de stockage, des coûts unitaires de production et de stockage et des coûts fixes. Cette contrainte globale est un outil de modélisation intuitif pour les problèmes complexes de lot-sizing car elle permet de modéliser chaque nœud des réseaux de distribution. Nous utilisons des techniques de programmation dynamique classiques du lot-sizing pour développer des algorithmes de filtrage pour la contrainte globale. Nous modélisons également des problèmes multi-produits.Enfin, nous introduisons un nouvel algorithme de filtrage générique s'appuyant sur la programmation linéaire. Nous montrons que la cohérence d'arc pour les contraintes considérées peut être obtenue avec la résolution d'un seul programme linéaire lorsque la contrainte a une formulation idéale et nous généralisons le résultat pour faire du filtrage partiel lorsqu'aucune restriction n'est faite sur ces contraintes. Cette technique peut être pertinente lors de la résolution de sous-problèmes de flot ou de séquence sous-jacents au lot-sizing. / In this thesis we investigate the potential use of constraint programming to develop a production planning solver. We focus on lot-sizing problems that are crucial and challenging problems of the tactical level of production planning and use one of the main strengths of constraint programming, namely global constraints. The goal of this work is to set the grounds of a constraint programming framework for solving complex lot-sizing problems. We define a LotSizing global constraint based on a generic single-item, single-level lot-sizing problem that considers production and inventory capacities, unitary production and inventory costs and setup costs. This global constraint is an intuitive modeling tool for complex lot-sizing problems as it can model the nodes of lot-sizing networks. We use classical dynamic programming techniques of the lot-sizing field to develop powerful filtering algorithms for the global constraint. Furthermore we model multi-item problems that are natural extensions of the core problem.Finally we introduce a new generic filtering algorithm based on linear programming. We show that arc consistency can be achieved with only one call to a linear programming solver when the global constraint has an ideal formulation and adapt the result to provide partial filtering when no restriction is made on the constraints. This technique can be useful to tackle polynomial lot-sizing underlying flow and sequence sub-problems.

Le trafic aérien en Europe représente environ 30 000 vols quotidiens actuellement. Selon les prévisions de l’organisme Eurocontrol, ce trafic devrait croître de 70% d’ici l’année 2020 pour atteindre 50 000 vols quotidiens. L’espace aérien, découpé en zones géographiques appelées secteurs de contrôle, atteindra bientôt son niveau de saturation vis-à-vis des méthodes actuelles de planification et de contrôle. Afin d’augmenter la quantité de trafic que peut absorber le système, il est nécessaire de diminuer la charge de travail des contrôleurs aériens en les aidant dans leur tâche de séparation des avions. En se fondant sur les demandes de plans de vol des compagnies aériennes, nous proposons une méthode de planification des trajectoires en 4D permettant de présenter au contrôleur un trafic dont la plupart des conflits auront été évités en avance. Cette planification s’établit en deux étapes successives, ayant chacune un unique degré de liberté : une allocation de niveaux de vol permettant la résolution des conflits en croisière puis une allocation d’heures de décollage permettant de résoudre les conflits restants. Nous présentons des modèles pour ces deux problèmes d’optimisation fortement combinatoires, que nous résolvons en utilisant la programmation par contraintes ou les algorithmes évolutionnaires, ainsi que des techniques permettant de prendre en compte des incertitudes sur les heures de décollage ou le suivi de trajectoire. Les simulations conduites sur l’espace aérien français mènent à des situations où tous les conflits sont évités, avec des retards alloués de l’ordre d’une minute en moyenne (80 à 90 minutes pour le vol le plus retardé) et un écart par rapport à l’altitude optimale limité à un niveau de vol pour la quasi totalité des vols. La prise en compte d’incertitudes de manière statique dégrade fortement ces solutions peu robustes, mais nous proposons un modèle dynamique utilisant une fenêtre glissante susceptible de prendre en compte des incertitudes de quelques minutes avec un impact réduit sur le coût de l’allocation. / Air traffic in Europe represents about 30,000 flights each day and forecasts from Eurocontrol predict a growth of 70% by 2020 (50,000 flights per day). The airspace, made up of numerous control sectors, will soon be saturated given the current planification and control methods. In order to make the system able to cope with the predicted traffic growth, the air traffic controllers workload has to be reduced by automated systems that help them handle the aircraft separation task. Based on the traffic demand by airlines, this study proposes a new planning method for 4D trajectories that provides conflict-free traffic to the controller. This planning method consists of two successive steps, each handling a unique flight parameter : a flight level allocation phase followed by a ground holding scheme.We present constraint programming models and an evolutionary algorithm to solve these large scale combinatorial optimization problems, as well as techniques for improving the robustness of the model by handling uncertainties of takeoff times and trajectory prediction. Simulations carried out over the French airspace successfully solved all conflicts, with a mean of one minute allocated delay (80 to 90 minutes for the most delayed flight) and a discrepancy from optimal altitude of one flight level for most of the flights. Handling uncertainties with a static method leads to a dramatic increase in the cost of the previous non-robust solutions. However, we propose a dynamic model to deal with this matter, based on a sliding time horizon, which is likely to be able to cope with a few minutes of uncertainty with reasonable impact on the cost of the solutions.

No description available.

Dans le cadre de cette thèse, nous nous sommes intéressés à la mise en œuvre d'algorithmes auto-adaptatifs d'Intelligence Collective pour la résolution de problèmes d'optimisation modélisés dans un langage de Programmation par contraintes (PPC). Nous avons porté une attention particulière à la famille d'algorithmes de type « Ant Colony Optimization » (ACO). Nous avons développé trois contributions, à savoir : (1) Intégration des algorithmes de type ACO dans un langage de programmation par contraintes pour la résolution de problèmes de satisfaction de contraintes; (2) Proposition d'un algorithme hybride et générique où ACO est couplé à une approche complète pour résoudre des problèmes d'optimisation combinatoires (3) Proposition d'une stratégie capable d'adapter dynamiquement les paramètres de ACO. / In this thesis, we focused on the implementation of self-adaptive algorithms for solving optimization problems modeled in a Constraint Programming (CP) language. We focus on to the Ant Colony Optimization (ACO) algorithms. We have developed three contributions, namely: (1) Integration of ACO algorithms in a constraint programming language for solving constraint satisfaction problems, (2) Proposal of a generic hybrid algorithm which combines ACO and CP approach to solving combinatorial optimization problems (3) Proposal of a strategy to dynamically adjust the parameters of ACO.