Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Cette thèse est une illustration de problèmes de Recherche Opérationnelle abordés dans le contexte hospitalier du CHRU de Tours. La problématique considérée relève des transports et plus exactement de tournées de véhicules. Cette thèse s'articule autour de l'étude de deux principaux problèmes : le transport de flux de produits et le transport de flux de patients. Le premier problème de tournées de véhicules concerne toute la gestion des différents types de flux logistiques (logistique hôtelière, pharmacie, lingerie, plateaux repas, etc.) à livrer ou à collecter dans les services de soins de chaque hôpital du CHRU de Tours. Le deuxième problème concerne les transports de patients aussi bien urgents (SAMU) que planifiés (Centrale des ambulanciers). Pour résoudre ces problèmes, plusieurs méthodes s'inspirant des techniques de la RO sont proposées : des méthodes exactes (programmation linéaire en nombres entiers), des heuristiques (algorithme glouton, recherche tabou avec et sans mémoire adaptative, algorithme génétique, algorithme mémétique) et des moteurs de simulation à événements discrets ont été développés. Des expérimentations numériques valident l'interêt et la qualité des méthodes développées.

Cette thèse s’intéresse à trouver des solutions informatiques à certains problèmes de l’optimisation combinatoire, à savoir les problèmes de tournées de véhicules. Elle aborde les problèmes de Transport A la Demande (TAD). L’objectif principal visé dans cette thèse fait appel à certaines approches exactes et certaines approches méta-heuristiques pour résoudre des problèmes d’optimisation multi-objective de Transport A la Demande avec plusieurs véhicules. En effet, nos principaux objectifs de recherche consistent à : -I) Résoudre un problème multi-objectif de Transport A La Demande multi-véhicules basé sur la qualité de service ; - II) Résoudre un autre problème de Transport A la Demande multi-objectifs multi-véhicules. Ce problème traite un cas spécifique et qui consiste à l’application de ce problème aux domaines de l’Hospitalisation A Domicile (HAD). Nous avons appliqué des algorithmes exacts de "Branch and Bound" et des méthodes méta-heuristiques telles que l’algorithme évolutionnaire "Algorithme Génétique" et l’algorithme de "Colonie de Fourmis" pour apporter des solutions efficaces à ces différents problèmes. Un ensemble de résultats numériques est présenté pour chacune de ces méthodes pour montrer leurs capacités de produire des solutions de haute qualité en temps de calcul raisonnables. / This thesis focuses on finding computer science solutions for some combinatorial optimization problems, namely Vehicle Routing Problems (VRP). The thesis addresses the Dial A Ride Problems (DARP). Its main objective is to use some exact and meta-heuristics approaches to solve multi-objective optimization of Dial A Ride Problem with multi-vehicles. Hence, our main research aims are : - I)Solve a multi-objective Dial A Ride Problem with multi-vehicles based on quality of service, this problem treats a general case ; - II) Solve another multi-objective Dial A Ride Problem with multi-vehicles, this problem deals with a specific case which is an application of the Dial A Ride Problem in Home Health Care (HHC). We have also applied exact algorithms "Branch and Bound" and meta-heuristic algorithms such as evolutionary algorithms "Genetic Algorithm" and "Ant Colony" algorithm to provide effective solutions to these different problems. A set of numerical results are presented for each of these methods. Our results show that they produce high quality solutions in a reasonable execution time for all the treated problems.

Nous considérons la simulation numérique des écoulements de fluides viscoélatiques. Développant une approximation en temps par la méthode des directions alternées, nous proposons un algorithme entièrement nouveau permettant de découpler le calcul des contraintes de celui des vitesses. D'ordre deux en temps, cette méthode permet de plus le calcul rapide des solutions stationnaires. L'éléments à divergence nulle de Thomas-Raviart est utilisé pour les vitesses, et celui de Lesaint-Raviart pour les contraintes. La méthode est appliquée au problème de l'écoulement de fluides du type Oldroyd dans une contraction brusque (problème de la marche).

Les processus ponctuels spatiaux forment une branche de la statistique spatiale utilisée dans des domaines d'application variés (foresterie, géo-marketing, sismologie, épidémiologie...) et développée par de récents travaux théoriques. Nous nous intéressons principalement dans cette thèse à l'apport de la théorie des processus ponctuels spatiaux pour des problèmes de positionnement optimal, ainsi que pour la définition de nouveaux indices de concentration basés sur les distances en économétrie. Le problème de positionnement optimal s'écrit souvent comme un problème d'optimisation prenant en compte des données geo-référencées auxquelles peuvent être associées des caractéristiques. Pour prendre en compte l'aléa, nous considérons ces données issues d'un processus ponctuel spatial pour résoudre un problème de positionnement stochastique plus réaliste qu'un modèle déterministe. A travers l'étude du positionnement optimal d'une nouvelle caserne de pompiers dans la région toulousaine, nous développons une méthode de résolution stochastique permettant de juger de la variabilité de la solution optimale et de traiter des bases de données volumineuses. L'approche implémentée est validée par des premiers résultats théoriques sur le comportement asymptotique des solutions optimales empiriques. La convergence presque sure des solutions optimales empiriques de l'étude de cas précédente est obtenue dans un cadre i.i.d. en utilisant la théorie de Vapnik-Cervonenkis. Nous obtenons aussi la convergence presque sure des solutions optimales empiriques, dans un cadre plus général, pour un problème de positionnement dérivé du problème de transport de Monge-Kantorovich. Nous nous intéressons ensuite à des indices de concentration basés sur des distances en économétrie. Ces indices de concentration peuvent s'écrire comme des estimateurs de caractéristiques du second ordre de processus ponctuels marqués. Nous définissons ensuite un estimateur non-paramétrique d'une nouvelle caractéristique d'un processus ponctuel spatial marqué définissant ainsi un nouvel indice de concentration améliorant ceux déjà existants. Dans un cadre asymptotique avec fenêtre d'observation bornée, notre estimateur est asymptotiquement sans biais.

Les travaux présentés dans cette thèse visent à proposer des méthodes permettant de résoudre un problème de Transport à la Demande multicritère. Le premier travail réalisé dans cette thèse est l'étude d'un problème de Dial-a-Ride (DARP) statique multicritère. Trois critères qui peuvent être conflictuels ont été définis : le premier consiste à minimiser le coût de transport, le deuxième critère consiste à minimiser l'insatisfaction des passagers et enfin le troisième critère consiste à minimiser la quantité de CO2 émise par l'ensemble des véhicules. Nous avons développé une méthode évolutionnaire NSGA-II pour chercher un ensemble approximatif d'optimas de Pareto. Le second travail réalisé est l'étude d'un problème d'Optimal Timing dans une tournée. Ce problème consiste à calculer les dates de début de service optimales des points d'arrêts d'une tournée afin de minimiser l'insatisfaction des passagers. Le dernier travail de cette thèse a porté sur l'étude d'un problème de Transport à la Demande dynamique dans lequel de nouvelles requêtes à traiter arrivent en cours de journée. Deux méthodes ont été proposées pour résoudre ce problème : la première est une heuristique d'insertion rapide et la seconde est une méthode arborescente tronquée connue sous le nom de Recovering Beam Search. / The work presented in this thesis aims to propose methods to solve a multicriteria dial-a-ride problem (DARP). Three objective functions that have to be optimized in order to measure the potential efficiency of the DARP solution on different aspects : the cost for the transportation operator, the quality of service for users and the impact on the environment. The first work in this thesis is the study of static DARP for which a NSGA-II algorithm is developped to identify a good approximation of the Pareto optimal set. The second work deals with an optimal timing algorithm which computes pickup and delivery dates when the requests are sequenced on the vehicles, the objective is to minimize the total customer' dissatisfaction. The last problem studied in this thesis aims to solve the dynamic version of DARP for which two methods are proposed. The first one is a fast insertion heuristic based on an attractive index. However, the second methode uses a recovering beam search heuristic which unlike the insertion heuristic allows to modify the structure of the routes previously scheduled in order to schedule the new requests.

Notre sujet de recherche porte sur la résolution du problème de transport avec coûts fixes (FCTP). Le problème de transport classique consiste à déterminer le schéma optimal de distribution dans un réseau. Le réseau est divisé en deux sous-ensembles de sommets : les origines caractérisées par une offre et les destinations caractérisées par une demande. À chaque arc reliant une origine et une destination, est associé un coût variable. L'objectif est de satisfaire toutes les demandes en minimisant la somme des coûts variables de transport. Dans le FCTP, il y a aussi des coûts fixes associés à tous les arcs, en supplément de tout ce qui décrit un problème de transport classique. Ainsi, à chaque arc, est associé un coût variable et un coût fixe qui est considéré si et seulement si l'arc est utilisé. L'objectif est désormais de minimiser la somme totale des coûts, variables et fixes. Le FCTP nous confronte donc à un modèle différent et plus complexe. La complexité de résolution est accrue pour les instances de grande taille. Dans ce mémoire, nous étudions et présentons une nouvelle méthode de résolution pour les instances de grande taille du FCTP. Il s'agit d'une méthode de décomposition lagrangienne qui utilise la relaxation lagrangienne et un algorithme de sous-gradient pour trouver une borne inférieure au problème global. Nous avons intégré à la méthode une heuristique lagrangienne, incluant une procédure de ``slope scaling'' afin d'améliorer notre algorithme de sous-gradient et le résultat final de la méthode. À l'issue de notre processus de résolution, nous trouvons, pour certaines instances de grande taille, un moyen d'améliorer la solution proposée par CPLEX pour le FCTP en donnant comme paramètre à CPLEX la solution finale de notre méthode. / Our research topic focuses on solving the fixed charge transportation problem (FCTP). The classic transportation problem is to determine the optimal distribution pattern in a network. The network is divided into two subsets of vertices : the origins characterized by a supply and the destinations characterized by a demand. Each arc connecting an origin and a destination has a variable cost associated with it. The objective is to satisfy all demands while minimizing the sum of variable transportation costs. In FCTP, there are also fixed costs associated with all arcs, in addition to all others things that describe a typical transportation problem. So, each arc is associated a variable cost and a fixed cost which is considered if and only if the arc is used. The objective is now to minimize the total sum of costs, variable and fixed. The FCTP therefore confronts us with a different and more complex model. The resolution complexity is even increased for large instances. In this thesis, we study and present a new resolution method for large FCTP instances. This is a lagrangian decomposition method which uses lagrangian relaxation and a subgradient algorithm to find a lower bound to the global problem. We have integrated into the method a lagrangian heuristic, including a “slope scaling” procedure in order to improve our sub-gradient algorithm and the final result of the method. At the end of our resolution process, we find, for some large instances, a way to improve the solution proposed by CPLEX for the FCTP by giving as parameter to CPLEX the final solution of our method.

La conception de réseaux est un riche sous-domaine de l'optimisation combinatoire ayant de nombreuses applications pratiques. Du point de vue méthodologique, la plupart des problèmes de cette classe sont notoirement difficiles en raison de leur nature combinatoire et de l'interdépendance des décisions qu'ils impliquent. Ce mémoire aborde deux problèmes de conception de réseaux dont les structures respectives posent des défis bien distincts. Tout d'abord, nous examinons un problème déterministe dans lequel un client doit acquérir au prix minimum un certain nombre d'unités d'un produit auprès d'un ensemble de fournisseurs proposant différents coûts fixes et unitaires, et dont les stocks sont limités. Ensuite, nous étudions un problème probabiliste dans lequel une entreprise entrant sur un marché existant cherche, en ouvrant un certain nombre d'installations parmi un ensemble de sites disponibles, à maximiser sa part espérée d'un marché composé de clients maximisant une fonction d'utilité aléatoire. Ces deux problèmes, soit le problème de transport à coût fixe à un puits et le problème d'emplacement d'installations compétitif basé sur les choix, sont étroitement liés au problème du sac à dos et au problème de couverture maximale, respectivement. Nous introduisons de nouvelles reformulations prenant avantage de ces connexions avec des problèmes classiques d'optimisation combinatoire. Dans les deux cas, nous exploitons ces reformulations pour démontrer de nouvelles propriétés théoriques et développer des méthodes de résolution efficaces. Notre nouvel algorithme pour le problème de transport à coûts fixes à un puits domine les meilleurs algorithmes de la littérature, réduisant le temps de résolution des instances de grande taille jusqu'à quatre ordres de grandeur. Une autre contribution notable de ce mémoire est la démonstration que la fonction objectif du problème d'emplacement d'installations compétitif basé sur les choix est sous-modulaire sous n'importe quel modèle de maximisation d’utilité aléatoire. Notre méthode de résolution basée sur la simulation exploite cette propriété et améliore l'état de l'art pour plusieurs groupes d'instances. / Network design is a rich subfield of combinatorial optimization with wide-ranging real-life applications. From a methodological standpoint, most problems in this class are notoriously difficult due to their combinatorial nature and the interdependence of the decisions they involve. This thesis addresses two network design problems whose respective structures pose very distinct challenges. First, we consider a deterministic problem in which a customer must acquire at the minimum price a number of units of a product from a set of vendors offering different fixed and unit costs and whose supply is limited. Second, we study a probabilistic problem in which a firm entering an existing market seeks, by opening a number of facilities from a set of available locations, to maximize its expected share in a market composed of random utility-maximizing customers. These two problems, namely the single-sink fixed-charge-transportation problem and the choice-based competitive facility location problem, are closely related to the knapsack problem and the maximum covering problem, respectively. We introduce novel model reformulations that leverage these connections to classical combinatorial optimization problems. In both cases, we exploit these reformulations to prove new theoretical properties and to develop efficient solution methods. Our novel algorithm for the single-sink fixed-charge-transportation problem dominates the state-of-the-art methods from the literature, reducing the solving time of large instances by up to four orders of magnitude. Another notable contribution of this thesis is the demonstration that the objective function of the choice-based competitive facility location problem is submodular under any random utility maximization model. Our simulation-based method exploits this property and achieves state-of-the-art results for several groups of instances.