Méthodes exactes et heuristiques pour le problème de tournées de véhicules avec fenêtres de temps et réutilisation de véhicules

Cette thèse porte sur les problèmes de tournées de véhicules avec fenêtres de temps où un gain est associé à chaque client et où l'objectif est de maximiser la somme des gains recueillis moins les coûts de transport. De plus, un même véhicule peut effectuer plusieurs tournées durant l'horizon de planification. Ce problème a été relativement peu étudié en dépit de son importance en pratique. Par exemple, dans le domaine de la livraison de denrées périssables, plusieurs tournées de courte durée doivent être combinées afin de former des journées complètes de travail. Nous croyons que ce type de problème aura une importance de plus en plus grande dans le futur avec l'avènement du commerce électronique, comme les épiceries électroniques, où les clients peuvent commander des produits par internet pour la livraison à domicile. Dans le premier chapitre de cette thèse, nous présentons d'abord une revue de la littérature consacrée aux problèmes de tournées de véhicules avec gains ainsi qu'aux problèmes permettant une réutilisation des véhicules. Nous présentons les méthodologies générales adoptées pour les résoudre, soit les méthodes exactes, les méthodes heuristiques et les méta-heuristiques. Nous discutons enfin des problèmes de tournées dynamiques où certaines données sur le problème ne sont pas connues à l'avance. Dans le second chapitre, nous décrivons un algorithme exact pour résoudre un problème de tournées avec fenêtres de temps et réutilisation de véhicules où l'objectif premier est de maximiser le nombre de clients desservis. Pour ce faire, le problème est modélisé comme un problème de tournées avec gains. L'algorithme exact est basé sur une méthode de génération de colonnes couplée avec un algorithme de plus court chemin élémentaire avec contraintes de ressources. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. Le troisième chapitre propose donc une méthode de recherche adaptative à grand voisinage qui exploite les différents niveaux hiérarchiques du problème (soit les journées complètes de travail des véhicules, les routes qui composent ces journées et les clients qui composent les routes). Dans le quatrième chapitre, qui traite du cas dynamique, une stratégie d'acceptation et de refus des nouvelles requêtes de service est proposée, basée sur une anticipation des requêtes à venir. L'approche repose sur la génération de scénarios pour différentes réalisations possibles des requêtes futures. Le coût d'opportunité de servir une nouvelle requête est basé sur une évaluation des scénarios avec et sans cette nouvelle requête. Enfin, le dernier chapitre résume les contributions de cette thèse et propose quelques avenues de recherche future.

Complexité des homomorphismes de graphes avec listes

Les problèmes de satisfaction de contraintes, qui consistent à attribuer des valeurs à des variables en respectant un ensemble de contraintes, constituent une large classe de problèmes naturels. Pour étudier la complexité de ces problèmes, il est commode de les voir comme des problèmes d'homomorphismes vers des structures relationnelles. Un axe de recherche actuel est la caractérisation des classes de complexité auxquelles appartient le problème d'homomorphisme, ceci dans la perspective de confirmer des conjectures reliant les propriétés algébriques des structures relationelles à la complexité du problème d'homomorphisme. Cette thèse propose dans un premier temps la caractérisation des digraphes pour lesquels le problème d'homomorphisme avec listes appartient à FO. On montre également que dans le cas du problèmes d'homomorphisme avec listes sur les digraphes télescopiques, les conjectures reliant algèbre et complexité sont confirmées. Dans un deuxième temps, on caractérise les graphes pour lesquels le problème d'homomorphisme avec listes est résoluble par cohérence d'arc. On introduit la notion de polymorphisme monochromatique et on propose un algorithme simple qui résoud le problème d'homomorphisme avec listes si le graphe cible admet un polymorphisme monochromatique TSI d'arité k pour tout k ≥ 2.

Tactical Vehicle Routing Planning with Application to Milk Collection and Distribution

De nombreux problèmes pratiques qui se posent dans dans le domaine de la logistique, peuvent être modélisés comme des problèmes de tournées de véhicules. De façon générale, cette famille de problèmes implique la conception de routes, débutant et se terminant à un dépôt, qui sont utilisées pour distribuer des biens à un nombre de clients géographiquement dispersé dans un contexte où les coûts associés aux routes sont minimisés. Selon le type de problème, un ou plusieurs dépôts peuvent-être présents. Les problèmes de tournées de véhicules sont parmi les problèmes combinatoires les plus difficiles à résoudre. Dans cette thèse, nous étudions un problème d’optimisation combinatoire, appartenant aux classes des problèmes de tournées de véhicules, qui est liée au contexte des réseaux de transport. Nous introduisons un nouveau problème qui est principalement inspiré des activités de collecte de lait des fermes de production, et de la redistribution du produit collecté aux usines de transformation, pour la province de Québec. Deux variantes de ce problème sont considérées. La première, vise la conception d’un plan tactique de routage pour le problème de la collecte-redistribution de lait sur un horizon donné, en supposant que le niveau de la production au cours de l’horizon est fixé. La deuxième variante, vise à fournir un plan plus précis en tenant compte de la variation potentielle de niveau de production pouvant survenir au cours de l’horizon considéré. Dans la première partie de cette thèse, nous décrivons un algorithme exact pour la première variante du problème qui se caractérise par la présence de fenêtres de temps, plusieurs dépôts, et une flotte hétérogène de véhicules, et dont l’objectif est de minimiser le coût de routage. À cette fin, le problème est modélisé comme un problème multi-attributs de tournées de véhicules. L’algorithme exact est basé sur la génération de colonnes impliquant un algorithme de plus court chemin élémentaire avec contraintes de ressources. Dans la deuxième partie, nous concevons un algorithme exact pour résoudre la deuxième variante du problème. À cette fin, le problème est modélisé comme un problème de tournées de véhicules multi-périodes prenant en compte explicitement les variations potentielles du niveau de production sur un horizon donné. De nouvelles stratégies sont proposées pour résoudre le problème de plus court chemin élémentaire avec contraintes de ressources, impliquant dans ce cas une structure particulière étant donné la caractéristique multi-périodes du problème général. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. La troisième partie propose un algorithme de recherche adaptative à grands voisinages où de nombreuses nouvelles stratégies d’exploration et d’exploitation sont proposées pour améliorer la performances de l’algorithme proposé en termes de la qualité de la solution obtenue et du temps de calcul nécessaire.

Meta-heuristic Solution Methods for Rich Vehicle Routing Problems

Le problème de tournées de véhicules (VRP), introduit par Dantzig and Ramser en 1959, est devenu l'un des problèmes les plus étudiés en recherche opérationnelle, et ce, en raison de son intérêt méthodologique et de ses retombées pratiques dans de nombreux domaines tels que le transport, la logistique, les télécommunications et la production. L'objectif général du VRP est d'optimiser l'utilisation des ressources de transport afin de répondre aux besoins des clients tout en respectant les contraintes découlant des exigences du contexte d’application. Les applications réelles du VRP doivent tenir compte d’une grande variété de contraintes et plus ces contraintes sont nombreuse, plus le problème est difficile à résoudre. Les VRPs qui tiennent compte de l’ensemble de ces contraintes rencontrées en pratique et qui se rapprochent des applications réelles forment la classe des problèmes ‘riches’ de tournées de véhicules. Résoudre ces problèmes de manière efficiente pose des défis considérables pour la communauté de chercheurs qui se penchent sur les VRPs. Cette thèse, composée de deux parties, explore certaines extensions du VRP vers ces problèmes. La première partie de cette thèse porte sur le VRP périodique avec des contraintes de fenêtres de temps (PVRPTW). Celui-ci est une extension du VRP classique avec fenêtres de temps (VRPTW) puisqu’il considère un horizon de planification de plusieurs jours pendant lesquels les clients n'ont généralement pas besoin d’être desservi à tous les jours, mais plutôt peuvent être visités selon un certain nombre de combinaisons possibles de jours de livraison. Cette généralisation étend l'éventail d'applications de ce problème à diverses activités de distributions commerciales, telle la collecte des déchets, le balayage des rues, la distribution de produits alimentaires, la livraison du courrier, etc. La principale contribution scientifique de la première partie de cette thèse est le développement d'une méta-heuristique hybride dans la quelle un ensemble de procédures de recherche locales et de méta-heuristiques basées sur les principes de voisinages coopèrent avec un algorithme génétique afin d’améliorer la qualité des solutions et de promouvoir la diversité de la population. Les résultats obtenus montrent que la méthode proposée est très performante et donne de nouvelles meilleures solutions pour certains grands exemplaires du problème. La deuxième partie de cette étude a pour but de présenter, modéliser et résoudre deux problèmes riches de tournées de véhicules, qui sont des extensions du VRPTW en ce sens qu'ils incluent des demandes dépendantes du temps de ramassage et de livraison avec des restrictions au niveau de la synchronization temporelle. Ces problèmes sont connus respectivement sous le nom de Time-dependent Multi-zone Multi-Trip Vehicle Routing Problem with Time Windows (TMZT-VRPTW) et de Multi-zone Mult-Trip Pickup and Delivery Problem with Time Windows and Synchronization (MZT-PDTWS). Ces deux problèmes proviennent de la planification des opérations de systèmes logistiques urbains à deux niveaux. La difficulté de ces problèmes réside dans la manipulation de deux ensembles entrelacés de décisions: la composante des tournées de véhicules qui vise à déterminer les séquences de clients visités par chaque véhicule, et la composante de planification qui vise à faciliter l'arrivée des véhicules selon des restrictions au niveau de la synchronisation temporelle. Auparavant, ces questions ont été abordées séparément. La combinaison de ces types de décisions dans une seule formulation mathématique et dans une même méthode de résolution devrait donc donner de meilleurs résultats que de considérer ces décisions séparément. Dans cette étude, nous proposons des solutions heuristiques qui tiennent compte de ces deux types de décisions simultanément, et ce, d'une manière complète et efficace. Les résultats de tests expérimentaux confirment la performance de la méthode proposée lorsqu’on la compare aux autres méthodes présentées dans la littérature. En effet, la méthode développée propose des solutions nécessitant moins de véhicules et engendrant de moindres frais de déplacement pour effectuer efficacement la même quantité de travail. Dans le contexte des systèmes logistiques urbains, nos résultats impliquent une réduction de la présence de véhicules dans les rues de la ville et, par conséquent, de leur impact négatif sur la congestion et sur l’environnement.

Problème de déploiement de ressources dans le cas des feux de forêts majeurs - Opérations aériennes

Chaque année le feu brûle quelques dizaines de milliers d’hectares de forêts québécoises. Le coût annuel de prévention et de lutte contre les feux de forêts au Québec est de l’ordre de plusieurs dizaines de millions de dollars. Le présent travail contribue à la réduction de ces coûts à travers l’automatisation du processus de planification des opérations de suppression des feux de forêts majeurs. Pour ce faire, un modèle mathématique linéaire en nombres entiers a été élaboré, résolu et testé; introduisant un nouveau cas particulier à la littérature des Problèmes de Tournées de Véhicules (VRP). Ce modèle mathématique concerne le déploiement aérien des ressources disponibles pour l’extinction des incendies. Le modèle élaboré a été testé avec CPLEX sur des cas tirés de données réelles. Il a permis de réduire le temps de planification des opérations d’extinction des feux de forêts majeurs de 75% dans les situations courantes.

Evaluation de la phase pilote du Dispositif cantonal d'indication et de suivi des personnes toxicodépendantes (DCIST)

Le Dispositif Cantonal d'Indication et de Suivi des personnes Toxicodépendantes (DCIST) s'inscrit dans l'axe numéro 1 de la politique vaudoise concernant la prévention et la lutte contre la toxicodépendance qui vise l'amélioration de l'adéquation entre l'offre de prestations et les besoins des usagers ainsi que dans le Plan Stratégique Vaudois 2011 établi dans le cadre de la reprise par le canton de Vaud des tâches de la Confédération. Le DCIST est un processus organisationnel de travail en réseau appuyé sur des outils standardisés d'évaluation des conditions de vie et de consommation des personnes toxicodépendantes qui a pour objectifs :1. d'ajuster au mieux les prestations proposées au regard des besoins rencontrés par les personnes toxicodépendantes;2. de développer un réseau de soins coordonné : a. améliorer l'efficacité de la prise en charge des personnes toxicodépendantes;b. favoriser le suivi et le maintien de ces personnes dans le réseau social et médical;c. favoriser le continuum dans la prise en charge médicosociale (des structures généralistes, de première ligne, aux institutions résidentielles spécialisées).Le DCIST a donc pour but de renforcer le rôle du canton de Vaud dans le pilotage et la planification des prestations dans le domaine de l'aide aux personnes concernées par la toxicodépendance. Il est indiqué et nécessaire pour toute personne souhaitant entrer dans une structure résidentielle pour des problèmes de toxicodépendance, avec ou sans problématique d'alcool associée.La mise en place du dispositif a été pilotée par les instances suivantes qui se sont réunies à intervalles réguliers : la cellule de projet (les responsables des deux services concernés - SSP et SPASa) et le/la chef-fe de projetb), le groupe de travail (GT) et ses différents sous-groupes et finalement le comité de pilotage (CoPil). Ces deux derniers groupes rassemblaient des professionnels représentatifs des différents secteurs concernés par le DCIST.La phase pilote du DCIST a duré du 1er octobre 2010 au 31 mars 2011. L'objectif de cette phase était d'éprouver les outils, la structure ainsi que les procédures élaborées et d'effectuer les ajustements nécessaires.Durant cette phase pilote, des formations sur la façon d'utiliser les outils du DCIST ont été dispensées aux personnes chargées d'indication dans les structures ou à d'autres collaborateurs intéressés.Des plateformes d'échange ont réuni les personnes concernées des différentes structures (centres d'indication, établissements socio-éducatifs [ESE]) et les responsables du projet. Ces réunions ont permis de faire émerger et d'échanger les points de vue sur les problèmes rencontrés et de discuter de solutions communes. [Auteurs, p. 5]

Timing pubertaire et adaptation psychosociale à l'adolescence : le rôle des relations interpersonnelles et des vulnérabilités individuelles

Cette thèse avait pour objectif d’examiner les liens longitudinaux entre le timing pubertaire et les problèmes de comportement intériorisés et extériorisés à l’adolescence, soit les problèmes de conduite et les symptômes dépressifs. Guidé par la perspective théorique biosociale et le modèle de vulnérabilité-stress, le rôle modérateur de l’environnement social et des vulnérabilités personnelles préexistantes était également évalué. Les hypothèses initiales étaient qu’un timing pubertaire précoce ou déviant de la norme (précoce et tardif) serait associé à des niveaux plus élevés de problèmes de conduite et de symptômes dépressifs, mais que ce lien serait accentué dans des contextes sociaux et interpersonnels plus à risque et en présence de vulnérabilités individuelles chez les adolescents. Pour vérifier ces hypothèses, des données provenant de l’Enquête Longitudinale Nationale sur les Enfants et les Jeunes (ELNEJ) ont été analysées. Gérée par Statistique Canada, l’ELNEJ est une enquête prospective biennale comportant différents échantillons représentatifs d’enfants et d’adolescents canadiens. Les mesures utilisées dans cette thèse ont été collectées à différents cycles de l’enquête, soit à 10–11 ans, 12–13 ans, 14–15 ans et 16–17 ans, directement auprès des adolescents et de leurs parents par le biais de questionnaires et d’entrevues. Le premier article de la thèse a vérifié si l’interaction entre le timing pubertaire et des caractéristiques du contexte social des pairs (c.-à-d. l’affiliation avec des pairs déviants et l’implication amoureuse en début d’adolescence) prédisait la présentation de problèmes de conduite avec et sans agressivité physique à l’adolescence. Les résultats ont montré que le contexte social des pairs modérait l’association entre le timing pubertaire et les problèmes de conduite. Une interaction significative entre le timing pubertaire et l’affiliation à des pairs déviants a indiqué qu’une puberté plus précoce était associée à des fréquences plus élevées de problèmes de conduite agressive seulement chez les filles et les garçons qui fréquentaient des pairs déviants. Autrement dit, parmi les adolescents s’affiliant à des pairs déviants en début d’adolescence, les adolescents pubères précoces tendaient à présenter plus de problèmes de conduite agressive deux ans plus tard, en comparaison à leurs pairs pubères dans les temps moyens ou tardifs. Une seconde interaction significative obtenue chez les filles a montré que la puberté plus précoce était prédictrice des problèmes de conduite non-agressive seulement en présence d’un engagement amoureux en début d’adolescence. En effet, dans un contexte d’implication amoureuse, les filles pubères précoces présentaient plus de problèmes de conduite non-agressive que leurs pairs. Le deuxième article de la thèse avait pour objectif d’évaluer le rôle modérateur des vulnérabilités individuelles à la dépression (présence de symptômes intériorisés à la fin de l’enfance), du contexte social des pairs (affiliation à des pairs déviants, expérience amoureuse précoce et perception de popularité auprès des pairs) et des relations parent-adolescent (perception de rejet de la part des parents) dans l’association longitudinale entre le timing pubertaire et les symptômes dépressifs en fin d’adolescence. Chez les filles, une interaction triple a révélé que la puberté plus précoce était liée à davantage de symptômes dépressifs, mais seulement chez celles qui présentaient des symptômes intériorisés à la fin de l’enfance et une implication amoureuse précoce. Chez les garçons, un effet curvilinéaire du timing pubertaire a été observé alors que la puberté précoce et tardive était associée à plus de symptômes dépressifs, mais seulement chez les garçons qui manifestaient des symptômes intériorisés à la fin de l’enfance. La puberté plus précoce était aussi liée à des niveaux plus élevés de symptômes dépressifs en présence d’affiliation à des pairs déviants (garçons) et de perceptions plus importantes de rejet parental (filles et garçons). En somme, la mise en évidence d’interactions significatives entre le timing pubertaire, les caractéristiques de l’environnement social et les vulnérabilités individuelles suscite différentes réflexions au plan théorique et pratique. Tout d’abord, les résultats suggèrent que le timing pubertaire en lui-même ne paraît pas représenter un facteur de risque généralisé des problèmes de comportement intériorisés et extériorisés à l’adolescence. Plus particulièrement, ces résultats soulignent l’importance de considérer l’environnement social et les facteurs de risque individuels préexistants afin de mieux comprendre l’effet de la transition pubertaire sur l’adaptation psychosociale des adolescents.

Heuristic solution methods for multi-attribute vehicle routing problems

Le Problème de Tournées de Véhicules (PTV) est une clé importante pour gérér efficacement des systèmes logistiques, ce qui peut entraîner une amélioration du niveau de satisfaction de la clientèle. Ceci est fait en servant plus de clients dans un temps plus court. En terme général, il implique la planification des tournées d'une flotte de véhicules de capacité donnée basée à un ou plusieurs dépôts. Le but est de livrer ou collecter une certain quantité de marchandises à un ensemble des clients géographiquement dispersés, tout en respectant les contraintes de capacité des véhicules. Le PTV, comme classe de problèmes d'optimisation discrète et de grande complexité, a été étudié par de nombreux au cours des dernières décennies. Étant donné son importance pratique, des chercheurs dans les domaines de l'informatique, de la recherche opérationnelle et du génie industrielle ont mis au point des algorithmes très efficaces, de nature exacte ou heuristique, pour faire face aux différents types du PTV. Toutefois, les approches proposées pour le PTV ont souvent été accusées d'être trop concentrées sur des versions simplistes des problèmes de tournées de véhicules rencontrés dans des applications réelles. Par conséquent, les chercheurs sont récemment tournés vers des variantes du PTV qui auparavant étaient considérées trop difficiles à résoudre. Ces variantes incluent les attributs et les contraintes complexes observés dans les cas réels et fournissent des solutions qui sont exécutables dans la pratique. Ces extensions du PTV s'appellent Problème de Tournées de Véhicules Multi-Attributs (PTVMA). Le but principal de cette thèse est d'étudier les différents aspects pratiques de trois types de problèmes de tournées de véhicules multi-attributs qui seront modélisés dans celle-ci. En plus, puisque pour le PTV, comme pour la plupart des problèmes NP-complets, il est difficile de résoudre des instances de grande taille de façon optimale et dans un temps d'exécution raisonnable, nous nous tournons vers des méthodes approcheés à base d’heuristiques.

Dynamic Facility Location with Modular Capacities : Models, Algorithms and Applications in Forestry

Les décisions de localisation sont souvent soumises à des aspects dynamiques comme des changements dans la demande des clients. Pour y répondre, la solution consiste à considérer une flexibilité accrue concernant l’emplacement et la capacité des installations. Même lorsque la demande est prévisible, trouver le planning optimal pour le déploiement et l'ajustement dynamique des capacités reste un défi. Dans cette thèse, nous nous concentrons sur des problèmes de localisation avec périodes multiples, et permettant l'ajustement dynamique des capacités, en particulier ceux avec des structures de coûts complexes. Nous étudions ces problèmes sous différents points de vue de recherche opérationnelle, en présentant et en comparant plusieurs modèles de programmation linéaire en nombres entiers (PLNE), l'évaluation de leur utilisation dans la pratique et en développant des algorithmes de résolution efficaces. Cette thèse est divisée en quatre parties. Tout d’abord, nous présentons le contexte industriel à l’origine de nos travaux: une compagnie forestière qui a besoin de localiser des campements pour accueillir les travailleurs forestiers. Nous présentons un modèle PLNE permettant la construction de nouveaux campements, l’extension, le déplacement et la fermeture temporaire partielle des campements existants. Ce modèle utilise des contraintes de capacité particulières, ainsi qu’une structure de coût à économie d’échelle sur plusieurs niveaux. L'utilité du modèle est évaluée par deux études de cas. La deuxième partie introduit le problème dynamique de localisation avec des capacités modulaires généralisées. Le modèle généralise plusieurs problèmes dynamiques de localisation et fournit de meilleures bornes de la relaxation linéaire que leurs formulations spécialisées. Le modèle peut résoudre des problèmes de localisation où les coûts pour les changements de capacité sont définis pour toutes les paires de niveaux de capacité, comme c'est le cas dans le problème industriel mentionnée ci-dessus. Il est appliqué à trois cas particuliers: l'expansion et la réduction des capacités, la fermeture temporaire des installations, et la combinaison des deux. Nous démontrons des relations de dominance entre notre formulation et les modèles existants pour les cas particuliers. Des expériences de calcul sur un grand nombre d’instances générées aléatoirement jusqu’à 100 installations et 1000 clients, montrent que notre modèle peut obtenir des solutions optimales plus rapidement que les formulations spécialisées existantes. Compte tenu de la complexité des modèles précédents pour les grandes instances, la troisième partie de la thèse propose des heuristiques lagrangiennes. Basées sur les méthodes du sous-gradient et des faisceaux, elles trouvent des solutions de bonne qualité même pour les instances de grande taille comportant jusqu’à 250 installations et 1000 clients. Nous améliorons ensuite la qualité de la solution obtenue en résolvent un modèle PLNE restreint qui tire parti des informations recueillies lors de la résolution du dual lagrangien. Les résultats des calculs montrent que les heuristiques donnent rapidement des solutions de bonne qualité, même pour les instances où les solveurs génériques ne trouvent pas de solutions réalisables. Finalement, nous adaptons les heuristiques précédentes pour résoudre le problème industriel. Deux relaxations différentes sont proposées et comparées. Des extensions des concepts précédents sont présentées afin d'assurer une résolution fiable en un temps raisonnable.

Étude d'un problème de tournées de véhicules sur les arcs avec contraintes de capacité et coûts de service dépendants du temps

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

Approches générales de résolution pour les problèmes multi-attributs de tournées de véhicules et confection d'horaires

Thèse réalisée en cotutelle entre l'Université de Montréal et l'Université de Technologie de Troyes

Prise en charge des patients avec des problèmes d'alcool: quelle efficacité? Quelques éléments de réponse à partir d'une revue de la littérature [Management of patients with alcohol problems: how effective? Several response factors based on a review of the literature]

What do we know about the effectiveness of various treatments of alcoholism? This review of literature shows that lack--or weaknesses--of published studies make it impossible to draw definite conclusions. Rigorous controlled studies show high rates of spontaneous remission and important uncertainties about specialised treatments of alcoholism. However, except for severe dependence that may well require a different approach, brief interventions conducted by non-specialists have proved highly effective for at-risk alcohol drinkers: based on minimal medical advice, they increase the chances of lowering alcohol consumption. General practitioners may thus represent on important link in the therapeutic chain.