Le problème de tournées de véhicules (Vehicle Routing Problem - VRP) est un problème d'optimisation combinatoire utilisé généralement pour modéliser et résoudre des différents problèmes rencontrés dans les systèmes logistiques et de transport. Dans cette thèse, nous nous sommes intéressés à l'étude et la résolution d'une classe de problèmes du VRP appelée les problèmes de courses d'orientation (Team Orienteering Problem - TOP). Dans cette catégorie de problèmes, il est a priori impossible de visiter tous les clients en raison de ressources limitées. On associe plutôt un profit à chaque client qui représente sa valeur. Ce profit est collecté lorsque le client est visité par l'un des véhicules disponibles. L'objectif est donc de sélectionner un sous ensemble de clients à servir tout en maximisant le profit total collecté. Dans un premier temps, nous avons introduit une nouvelle généralisation pour le TOP que nous avons appelé le Clustered TOP ou CluTOP. Dans cette variante, les clients sont regroupés en sous-ensembles appelés clusters auxquels nous associons des profits. Pour résoudre cette variante, nous avons proposé un schéma exact basé sur l'approche des plans sécants avec des inégalités valides supplémentaires et des pré-traitements. Nous avons également conçu une méthode heuristique basée sur l'approche order first-cluster second. Cette heuristique hybride combine une heuristique de type Adaptive Large Neighborhood Search qui explore l'espace des solutions et une procédure de découpage qui explore l'espace de recherche des tours géants. De plus, la procédure de découpage est renforcée par une recherche locale afin de mieux explorer l'espace de recherche. Le deuxième problème traité dans ce travail s'appelle le Synchronized Team Orienteering Problem with Time Windows (STOPTW). Cette variante avait été initialement proposée afin de modéliser des scénarios liés à la protection des infrastructures stratégiques menacées par l'avancée des feux de forêts. En plus des contraintes de fenêtres de temps et des visites synchronisées, cette variante considère le cas d'une flotte de véhicules hétérogène. Pour résoudre ce problème, nous avons proposé une méthode heuristique basée sur l'approche GRASP×ILS qui est parvenue à dominer la seule approche existante dans la littérature. La dernière variante du TOP abordée dans cette thèse s'appelle le Set Orienteering Problem (SOP). Les clients dans cette variante sont regroupés en sous-ensembles appelés clusters. Un profit est associé à chaque groupe qui n'est obtenu que si au moins un client est desservi par le véhicule disponible. Nous avons proposé une méthode de coupes avec deux procédures de séparation pour séparer les contraintes d'élimination des sous-tours. Nous avons également proposé un algorithme Mémétique avec une procédure de découpage optimale calculée à l'aide de la programmation dynamique. / The Vehicle Routing Problem (VRP) is a family of Combinatorial Optimization Problems generally used to solve different issues related to transportation systems and logistics. In this thesis, we focused our attention on a variant of the VRP called the Team Orienteering Problem (TOP). In this family of problems, it is a priory impossible to visit all the customers due to travel time limitation on vehicles. Instead, a profit is associated with each customer to represent its value and it is collected once the customer is visited by one of the available vehicles. The objective function is then to maximize the total collected profit with respect to the maximum travel time. Firstly, we introduced a new generalization for the TOP that we called the Clustered TOP (CluTOP). In this variant, the customers are grouped into subsets called clusters to which we associate profits. To solve this variant, we proposed an exact scheme based on the cutting plane approach with additional valid inequalities and pre-processing techniques. We also designed a heuristic method based on the order first-cluster second approach for the CluTOP. This Hybrid Heuristic combines between an ANLS heuristic that explores the solutions space and a splitting procedure that explores the giant tours search space. In addition, the splitting procedure is enhanced by local search procedure in order to enhance its coverage of search space. The second problem treated in this work is called the Synchronized Team Orienteering Problem with Time Windows (STOPTW). This variant was initially proposed in order to model scenarios related to asset protection during escaped wildfires. It considers the case of a heterogeneous fleet of vehicles along with time windows and synchronized visits. To solve this problem, we proposed a heuristic method based on the GRASP×ILS approach that led to a very outstanding results compared to the literature. The last variant of the TOP tackled in this thesis called the Set Orienteering Problem (SOP). Customers in this variant are grouped into subsets called clusters. Each cluster is associated with a profit which is gained if at least one customer is served by the single available vehicle. We proposed a Branch-and-Cut with two separation procedures to separate subtours elimination constraints. We also proposed a Memetic Algorithm with an optimal splitting procedure based on dynamic programming.

Cette thèse, fruit d'un contrat de recherche avec Générale des Eaux,<br />porte sur le problème de tournées de service multi-périodes avec fenêtres de temps et flotte limitée. Nous proposons plusieurs méthodes de résolution approchées, ainsi qu'une méthode optimale. La méthode optimale est basée sur la génération de colonnes. Une des méthodes approchées est un algorithme mémétique basé sur une heuristique également développée dans cette thèse. Enfin, la méthode optimale est dérivée en méthode approchée par l'utilisation d'une heuristique pour la résolution du sous-problème.<br />Les algorithmes proposés permettent d'apporter des solutions efficaces à des problèmes comportant jusqu'à 300 clients, dans des temps variant de quelques secondes à quelques dizaines de minutes. Dans un second temps, nous appliquons ces méthodes à des scénarios issus de problématiques réelles, dans une logique d'aide à la décision.

Les entreprises de transport et de distribution sont confrontées à des difficultés d'exploitation liées à la taille et à la complexité de leur processus de livraison. Dans cette problématique, nous proposons une approche globale du Problème Général de Livraison (PGL).Au niveau méthodologique, c'est une approche hiérarchique (stratégique, tactique, opérationnelle) et structurée. Il s'agit de concevoir et d'exploiter un PGL en le décomposant en problèmes de livraisons élémentaires identifiés et le plus possible indépendants les uns des autres (problèmes de transport, de hubs, d'agences, de tournées...).Au niveau algorithmique, des modèles et algorithmes de résolution ont été proposés pour résoudre ces problèmes élémentaires de livraison dans la phase opérationnelle en tenant compte, en particulier, du nombre et de la capacité limités des moyens de transport.Au niveau applicatif, deux exemples réels sont traités : le système de livraison d'une entreprise de Vente à Distance et le système de livraison des casernes de pompiers du Nord de la France à partir de la pharmacie centrale de Lille

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.

Le management de la chaîne logistique concerne un large éventail d'activités. Nombreuses ceux qui ont un caractère incertain apportant souvent des conséquences inattendues. Malgré cela, l'incertitude est fréquemment non considérée dans la gestion de la chaîne logistique traditionnelle. En plus de l'incertitude, l'indisponibilité des ressources augmentera la complexité du problème. En prenons en compte les contraintes d'incertitude et de disponibilité nous étudions le management de la chaîne logistique selon différents aspects. Cette thèse représente une tentative de recherche afin d'aborder ce problème d'une façon systématique et complète et nous espérons que notre travail contribuera aux futurs travaux de recherche et sera utile aux gestionnaires de la chaîne logistique. Nous nous concentrons sur trois sources classiques de l'incertitude ; celle de la demande, celle la fabrication et celle liée à la distribution. Pour chaque source d'incertitude, nous analysons ses causes et ses impacts sur les performances de la chaîne logistique. L'incertitude est spécifiée dans des problèmes classiques concrets et des approches sont proposées pour les résoudre. Nous nous sommes également focalisés sur le problème bi-niveau de vendeur de journaux qui représente une chaîne logistique miniature, concerné par une double incertitude. Les méthodes utilisées offrent une bonne démonstration du traitement des variables incertaines dans les problèmes de décision.

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

Les entreprises de transport font face à des problèmes de taille grandissante où l'utilisation de transbordement peut avoir un impact significatif sur les coûts. ILOG TPO est un logiciel capable de résoudre de tels problèmes, mais il lui est difficile de prendre de bonnes décisions concernant le transbordement. De plus, le processus de résolution d'ILOG TPO est basé sur la recherche locale, et il peut être aidé pour certaines décisions globales comme le transbordement. Cette thèse se place dans ce contexte, et son objectif est d'aider ILOG TPO à trouver de meilleures solutions. Pour cela, une formulation complète est d'abord proposée pour résoudre les plus petites instances, et avec une technique de plans coupants, les solutions optimales sont généralement trouvées en un temps raisonnable. Ensuite, un algorithme à deux phases qui inclut un programme en variables mixtes (MIP) sur une relaxation de type réseau du problème est donné pour de plus grandes instances. Cet algorithme est une coopération entre le MIP et ILOG TPO, où le MIP donne à ILOG TPO, pour chaque ordre de transport, le chemin de hubs par lequel il devrait être acheminé. Cette heuristique trouve des solutions similaires à ILOG TPO seul, mais le temps de calcul est réduit de façon significative.

Dans cette thèse, nous proposons d'aborder l'ordonnancement des transports par une approche interdisciplinaire. L'idée est d'intégrer les facteurs humains dans le système d'aide à la décision réalisé, de façon à ce que l'homme puisse agir sur la modélisation et la résolution du problème. Le système proposé doit offrir de la flexibilité, afin d'être capable de s'adapter aux nouvelles situations et aux changements, même si ceux-ci n'ont pas été prévus initialement par le concepteur du système. Pour atteindre l'objectif fixé, nous nous sommes notamment appuyé sur une analyse du domaine de travail (" Work Domain Analysis ") basée sur une hiérarchie d'abstraction des entités (physiques ou plus abstraites) manipulées dans ce type de problèmes. Nous avons proposé une architecture pour le système d'aide à la décision basée sur cette analyse du domaine et la programmation par contraintes. Nous avons également conçu, et intégré dans le système, des algorithmes dédiés et des méthodes de résolution basés sur le principe d'inversion de modèle. Enfin, nous avons proposé une architecture d'interfaces avec l'objectif d'assister efficacement l'opérateur humain dans la réalisation des différentes sous-tâches nécessaires à la résolution globale du problème. L'étude du sujet interdisciplinaire a été précédée d'une analyse focalisée sur la résolution de problèmes théoriques d'ordonnancement à machines parallèles avec contraintes de précédence et temps de préparation des machines entre opérations, utilisant des méthodes de recherche arborescente basée sur les divergences.

Nous nous sommes intéressés à la problématique d’organisation des tournées de soins à domicile dans le cadre de structures de maintien à domicile comme par exemple les service d’Hospitalisation À Domicile ou les Services de Soins Infirmiers À Domicile. Les soins sont prodigués au domicile des patients par un ou deux soignants d’un type défini, comme médecin ou infirmier par exemple pendant une période de disponibilité du patient. Le patient est caractérisé par un niveau de dépendance et peut exprimer une préférence pour être soigné par un soignant plutôt qu’un autre. L’objectif est de construire les tournées des soignants en rendant visite à tous les patients tout en minimisant la longueur (ou durée) des tournées, en équilibrant les tournées suivant le niveau de dépendance des patients et en favorisant la préférence des patients. Après avoir réalisé un état de l’art des problèmes d’organisation de tournées de soins à domicile, nous proposons deux modélisations mathématiques de notre problème sous la forme d’un multiple Traveling Salesman Problem avec fenêtres de temps (m-TSPTW) auquel s’ajoute des contraintes spécifiques comme la synchronisation d’activités ou la prise en compte de types de ressource et des critères de performance propres au problème (équilibrage et préférence). Nous avons ensuite proposé des méthodes approchées basées sur des couplages métaheuristique - modèle de simulation testées sur des instances de la littérature d’un problème proche du nôtre et des instances adaptées à notre problème. Pour terminer, nous abordons trois perspectives de recherche :- la réorganisation des tournées suite à l’absence d’un soignant,- la prise en compte de temps de transport stochastique,- la localisation de structures de maintien à domicile et l’impact sur la construction des tournées. / We are interested in a routing problem within the context of home health care. The cares are provided by one or two caregivers with the required type at the patient’s home during the patients’ availability. A type is doctor or nurse for instance. Each patient is characterized by a dependency level and may give a preference for a caregiver. The goal is to construct the tour for each caregiver visiting all patients, minimizing the length of the tours, balancing the workload of the caregivers and maximizing the satisfaction of the patients. We present a state of the art of the home health care problem. Then we propose two mathematical models of our problem based on the multiple Traveling Salesman Problem with Time Windows (m-TSPTW) with specific constraints like the activities’s synchronization or ressources’ type. The performance criteria are specific of our problem : workload balancing and patients’ satisfaction. We then propose approached methods based on combination between Metaheuristics and simulation model. This méthods have been tested on dataset from the literature and dataset adapted to our problem. We conclude with three research perspectives :- the reorganization of the tours when a caregiver is not available,- the integration of stochastic transport time,- the location of home support structure and its impact on the routes’ construction.

En réponse aux contraintes économiques, au problème du vieillissement de la population et aussi à la volonté des patients de se faire soigner dans le milieu familial, l’Hospitalisation À Domicile (HAD) prend de plus en plus d’ampleur. Dans ce travail de recherche, nous nous intéressons aux établissements d’hospitalisation à domicile, parmi les différentes problématiques qui existent dans ce domaine, nous étudions le problème de routage et de planification des personnels.Nous développons tout d’abord un modèle de programmation linéaire en nombres entiers qui permet de formuler clairement les contraintes du problème.Nous présentons par la suite, une matheuristique permettant de résoudre le problème défini sur une journée de planification. Nous développons également une variante de notre matheuristique sur un horizon de 14 jours. Cette dernière prend en considération plusieurs contraintes en plus de celles considérées pour la planification sur une journée. Enfin, nous introduisons un problème de réoptimisation de routage et de la planification des personnels pour l’hospitalisation à domicile et présentons quelques approches de résolutions. Ces différentes méthodes combinent des heuristiques, la programmation dynamique et la programmation mathématique. / Home health care (HHC), i.e., visiting and nursing patients athome, is a growing sector in the medical care system. There fore, the optimal scheduling of the health care staffs arises. The objective of this problem consists in constructing routes and rosters for the staffs while optimizing costs. We propose an integer linear programming formulation (ILP) that clearly formulate the constraints of the problem. We present a matheuristic to solve the daily routing and rostering problem. We also develop a variant of our matheuristic defined for a period of 14 days. It takes into account several constraints in addition to those considered in the daily planning. Finally, we introduce the problem of reoptimizing the routing and rostering staffs and we give some ideas to solve this problem. These methods combine heuristic algorithms, dynamic programming and mathematical programming.