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.

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

Excitabilité du système miroir : une étude de stimulation magnétique transcrânienne sur le chant et le langage

La perception de mouvements est associée à une augmentation de l’excitabilité du cortex moteur humain. Ce système appelé « miroir » sous-tendrait notre habileté à comprendre les gestes posés par une tierce personne puisqu’il est impliqué dans la reconnaissance, la compréhension et l’imitation de ces gestes. Dans cette étude, nous examinons de quelle façon ce système miroir s’implique et se latéralise dans la perception du chant et de la parole. Une stimulation magnétique transcrânienne (TMS) à impulsion unique a été appliquée sur la représentation de la bouche du cortex moteur de 11 participants. La réponse motrice engendrée a été mesurée sous la forme de potentiels évoqués moteurs (PÉMs), enregistrés à partir du muscle de la bouche. Ceux-ci ont été comparés lors de la perception de chant et de parole, dans chaque hémisphère cérébral. Afin d’examiner l’activation de ce système moteur dans le temps, les impulsions de la TMS ont été envoyées aléatoirement à l’intérieur de 7 fenêtres temporelles (500-3500 ms). Les stimuli pour la tâche de perception du chant correspondaient à des vidéos de 4 secondes dans lesquelles une chanteuse produisait un intervalle ascendant de deux notes que les participants devaient juger comme correspondant ou non à un intervalle écrit. Pour la tâche de perception de la parole, les participants regardaient des vidéos de 4 secondes montrant une personne expliquant un proverbe et devaient juger si cette explication correspondait bien à un proverbe écrit. Les résultats de cette étude montrent que les amplitudes des PÉMs recueillis dans la tâche de perception de chant étaient plus grandes après stimulation de l’hémisphère droit que de l’hémisphère gauche, surtout lorsque l’impulsion était envoyée entre 1000 et 1500 ms. Aucun effet significatif n’est ressorti de la condition de perception de la parole. Ces résultats suggèrent que le système miroir de l’hémisphère droit s’active davantage après une présentation motrice audio-visuelle, en comparaison de l’hémisphère gauche.

Étude du traitement visuel simple et complexe chez les enfants autistes

Les personnes ayant un trouble du spectre autistique (TSA) manifestent des particularités perceptives. En vision, des travaux influents chez les adultes ont mené à l’élaboration d’un modèle explicatif du fonctionnement perceptif autistique qui suggère que l’efficacité du traitement visuel varie en fonction de la complexité des réseaux neuronaux impliqués (Hypothèse spécifique à la complexité). Ainsi, lorsque plusieurs aires corticales sont recrutées pour traiter un stimulus complexe (e.g., modulations de texture; attributs de deuxième ordre), les adultes autistes démontrent une sensibilité diminuée. À l’inverse, lorsque le traitement repose principalement sur le cortex visuel primaire V1 (e.g., modulations locales de luminance; attributs de premier ordre), leur sensibilité est augmentée (matériel statique) ou intacte (matériel dynamique). Cette dissociation de performance est spécifique aux TSA et peut s’expliquer, entre autre, par une connectivité atypique au sein de leur cortex visuel. Les mécanismes neuronaux précis demeurent néanmoins méconnus. De plus, on ignore si cette signature perceptuelle est présente à l’enfance, information cruciale pour les théories perceptives de l’autisme. Le premier volet de cette thèse cherche à vérifier, à l’aide de la psychophysique et l’électrophysiologie, si la double dissociation de performance entre les attributs statiques de premier et deuxième ordre se retrouve également chez les enfants autistes d’âge scolaire. Le second volet vise à évaluer chez les enfants autistes l’intégrité des connexions visuelles descendantes impliquées dans le traitement des textures. À cet effet, une composante électrophysiologique reflétant principalement des processus de rétroaction corticale a été obtenue lors d’une tâche de ségrégation des textures. Les résultats comportementaux obtenus à l’étude 1 révèlent des seuils sensoriels similaires entre les enfants typiques et autistes à l’égard des stimuli définis par des variations de luminance et de texture. Quant aux données électrophysiologiques, il n’y a pas de différence de groupe en ce qui concerne le traitement cérébral associé aux stimuli définis par des variations de luminance. Cependant, contrairement aux enfants typiques, les enfants autistes ne démontrent pas une augmentation systématique d’activité cérébrale en réponse aux stimuli définis par des variations de texture pendant les fenêtres temporelles préférentiellement associées au traitement de deuxième ordre. Ces différences d’activation émergent après 200 ms et engagent les aires visuelles extrastriées des régions occipito-temporales et pariétales. Concernant la connectivité cérébrale, l’étude 2 indique que les connexions visuelles descendantes sont fortement asymétriques chez les enfants autistes, en défaveur de la région occipito-temporale droite. Ceci diffère des enfants typiques pour qui le signal électrophysiologique reflétant l’intégration visuo-corticale est similaire entre l’hémisphère gauche et droit du cerveau. En somme, en accord avec l’hypothèse spécifique à la complexité, la représentation corticale du traitement de deuxième ordre (texture) est atypiquement diminuée chez les enfants autistes, et un des mécanismes cérébraux impliqués est une altération des processus de rétroaction visuelle entre les aires visuelles de haut et bas niveau. En revanche, contrairement aux résultats obtenus chez les adultes, il n’y a aucun indice qui laisse suggérer la présence de mécanismes supérieurs pour le traitement de premier ordre (luminance) chez les enfants autistes.

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.

Une heuristique de recherche à voisinage variable pour le problème du voyageur de commerce avec fenêtres de temps

Nous adaptons une heuristique de recherche à voisinage variable pour traiter le problème du voyageur de commerce avec fenêtres de temps (TSPTW) lorsque l'objectif est la minimisation du temps d'arrivée au dépôt de destination. Nous utilisons des méthodes efficientes pour la vérification de la réalisabilité et de la rentabilité d'un mouvement. Nous explorons les voisinages dans des ordres permettant de réduire l'espace de recherche. La méthode résultante est compétitive avec l'état de l'art. Nous améliorons les meilleures solutions connues pour deux classes d'instances et nous fournissons les résultats de plusieurs instances du TSPTW pour la première fois.