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.

Modeling High-Dimensional Audio Sequences with Recurrent Neural Networks

Cette thèse étudie des modèles de séquences de haute dimension basés sur des réseaux de neurones récurrents (RNN) et leur application à la musique et à la parole. Bien qu'en principe les RNN puissent représenter les dépendances à long terme et la dynamique temporelle complexe propres aux séquences d'intérêt comme la vidéo, l'audio et la langue naturelle, ceux-ci n'ont pas été utilisés à leur plein potentiel depuis leur introduction par Rumelhart et al. (1986a) en raison de la difficulté de les entraîner efficacement par descente de gradient. Récemment, l'application fructueuse de l'optimisation Hessian-free et d'autres techniques d'entraînement avancées ont entraîné la recrudescence de leur utilisation dans plusieurs systèmes de l'état de l'art. Le travail de cette thèse prend part à ce développement. L'idée centrale consiste à exploiter la flexibilité des RNN pour apprendre une description probabiliste de séquences de symboles, c'est-à-dire une information de haut niveau associée aux signaux observés, qui en retour pourra servir d'à priori pour améliorer la précision de la recherche d'information. Par exemple, en modélisant l'évolution de groupes de notes dans la musique polyphonique, d'accords dans une progression harmonique, de phonèmes dans un énoncé oral ou encore de sources individuelles dans un mélange audio, nous pouvons améliorer significativement les méthodes de transcription polyphonique, de reconnaissance d'accords, de reconnaissance de la parole et de séparation de sources audio respectivement. L'application pratique de nos modèles à ces tâches est détaillée dans les quatre derniers articles présentés dans cette thèse. Dans le premier article, nous remplaçons la couche de sortie d'un RNN par des machines de Boltzmann restreintes conditionnelles pour décrire des distributions de sortie multimodales beaucoup plus riches. Dans le deuxième article, nous évaluons et proposons des méthodes avancées pour entraîner les RNN. Dans les quatre derniers articles, nous examinons différentes façons de combiner nos modèles symboliques à des réseaux profonds et à la factorisation matricielle non-négative, notamment par des produits d'experts, des architectures entrée/sortie et des cadres génératifs généralisant les modèles de Markov cachés. Nous proposons et analysons également des méthodes d'inférence efficaces pour ces modèles, telles la recherche vorace chronologique, la recherche en faisceau à haute dimension, la recherche en faisceau élagué et la descente de gradient. Finalement, nous abordons les questions de l'étiquette biaisée, du maître imposant, du lissage temporel, de la régularisation et du pré-entraînement.

Deep learning of representations and its application to computer vision

L’objectif de cette thèse par articles est de présenter modestement quelques étapes du parcours qui mènera (on espère) à une solution générale du problème de l’intelligence artificielle. Cette thèse contient quatre articles qui présentent chacun une différente nouvelle méthode d’inférence perceptive en utilisant l’apprentissage machine et, plus particulièrement, les réseaux neuronaux profonds. Chacun de ces documents met en évidence l’utilité de sa méthode proposée dans le cadre d’une tâche de vision par ordinateur. Ces méthodes sont applicables dans un contexte plus général, et dans certains cas elles on tété appliquées ailleurs, mais ceci ne sera pas abordé dans le contexte de cette de thèse. Dans le premier article, nous présentons deux nouveaux algorithmes d’inférence variationelle pour le modèle génératif d’images appelé codage parcimonieux “spike- and-slab” (CPSS). Ces méthodes d’inférence plus rapides nous permettent d’utiliser des modèles CPSS de tailles beaucoup plus grandes qu’auparavant. Nous démontrons qu’elles sont meilleures pour extraire des détecteur de caractéristiques quand très peu d’exemples étiquetés sont disponibles pour l’entraînement. Partant d’un modèle CPSS, nous construisons ensuite une architecture profonde, la machine de Boltzmann profonde partiellement dirigée (MBP-PD). Ce modèle a été conçu de manière à simplifier d’entraînement des machines de Boltzmann profondes qui nécessitent normalement une phase de pré-entraînement glouton pour chaque couche. Ce problème est réglé dans une certaine mesure, mais le coût d’inférence dans le nouveau modèle est relativement trop élevé pour permettre de l’utiliser de manière pratique. Dans le deuxième article, nous revenons au problème d’entraînement joint de machines de Boltzmann profondes. Cette fois, au lieu de changer de famille de modèles, nous introduisons un nouveau critère d’entraînement qui donne naissance aux machines de Boltzmann profondes à multiples prédictions (MBP-MP). Les MBP-MP sont entraînables en une seule étape et ont un meilleur taux de succès en classification que les MBP classiques. Elles s’entraînent aussi avec des méthodes variationelles standard au lieu de nécessiter un classificateur discriminant pour obtenir un bon taux de succès en classification. Par contre, un des inconvénients de tels modèles est leur incapacité de générer deséchantillons, mais ceci n’est pas trop grave puisque la performance de classification des machines de Boltzmann profondes n’est plus une priorité étant donné les dernières avancées en apprentissage supervisé. Malgré cela, les MBP-MP demeurent intéressantes parce qu’elles sont capable d’accomplir certaines tâches que des modèles purement supervisés ne peuvent pas faire, telles que celle de classifier des données incomplètes ou encore celle de combler intelligemment l’information manquante dans ces données incomplètes. Le travail présenté dans cette thèse s’est déroulé au milieu d’une période de transformations importantes du domaine de l’apprentissage à réseaux neuronaux profonds qui a été déclenchée par la découverte de l’algorithme de “dropout” par Geoffrey Hinton. Dropout rend possible un entraînement purement supervisé d’architectures de propagation unidirectionnel sans être exposé au danger de sur- entraînement. Le troisième article présenté dans cette thèse introduit une nouvelle fonction d’activation spécialement con ̧cue pour aller avec l’algorithme de Dropout. Cette fonction d’activation, appelée maxout, permet l’utilisation de aggrégation multi-canal dans un contexte d’apprentissage purement supervisé. Nous démontrons comment plusieurs tâches de reconnaissance d’objets sont mieux accomplies par l’utilisation de maxout. Pour terminer, sont présentons un vrai cas d’utilisation dans l’industrie pour la transcription d’adresses de maisons à plusieurs chiffres. En combinant maxout avec une nouvelle sorte de couche de sortie pour des réseaux neuronaux de convolution, nous démontrons qu’il est possible d’atteindre un taux de succès comparable à celui des humains sur un ensemble de données coriace constitué de photos prises par les voitures de Google. Ce système a été déployé avec succès chez Google pour lire environ cent million d’adresses de maisons.

Information utile à la catégorisation du sexe des visages

La présente thèse avait pour mandat d’examiner la question suivante : quels sont les indices visuels utilisés pour catégoriser le sexe d’un visage et comment sont-ils traités par le cerveau humain? La plupart des études examinant l’importance de certaines régions faciales pour la catégorisation du sexe des visages présentaient des limites quant à leur validité externe. L’article 1 visait à investiguer l’utilisation des indices achromatiques et chromatiques (sur l’axe xy) dans un contexte de plus grande validité externe. Pour ce faire, nous avons utilisé la technique Bubbles afin d’échantillonner l’espace xy de visages en couleurs n’ayant subi aucune transformation. Afin d’éviter les problèmes liés à la grande répétition des mêmes visages, nous avons utilisé un grand nombre de visages (c.-à-d. 300 visages caucasiens d’hommes et de femmes) et chaque visage n’a été présenté qu’une seule fois à chacun des 30 participants. Les résultats indiquent que la région des yeux et des sourcils—probablement dans le canal blanc-noir—est l’indice le plus important pour discriminer correctement le genre des visages; et que la région de la bouche—probablement dans le canal rouge-vert—est l’indice le plus important pour discriminer rapidement et correctement le genre des visages. Plusieurs études suggèrent qu’un indice facial que nous n’avons pas étudié dans l’article 1—les distances interattributs—est crucial à la catégorisation du sexe. L’étude de Taschereau et al. (2010) présente toutefois des données allant à l’encontre de cette hypothèse : les performances d’identification des visages étaient beaucoup plus faibles lorsque seules les distances interattributs réalistes étaient disponibles que lorsque toutes les autres informations faciales à l’exception des distances interattributs réalistes étaient disponibles. Quoi qu’il en soit, il est possible que la faible performance observée dans la condition où seules les distances interattributs étaient disponibles soit explicable non par une incapacité d’utiliser ces indices efficacement, mais plutôt par le peu d’information contenue dans ces indices. L’article 2 avait donc comme objectif principal d’évaluer l’efficacité—une mesure de performance qui compense pour la faiblesse de l’information disponible—des distances interattributs réalistes pour la catégorisation du sexe des visages chez 60 participants. Afin de maximiser la validité externe, les distances interattributs manipulées respectaient la distribution et la matrice de covariance observées dans un large échantillon de visages (N=515). Les résultats indiquent que les efficacités associées aux visages ne possédant que de l’information au niveau des distances interattributs sont un ordre de magnitude plus faibles que celles associées aux visages possédant toute l’information que possèdent normalement les visages sauf les distances interattributs et donnent le coup de grâce à l’hypothèse selon laquelle les distances interattributs seraient cuciale à la discrimination du sexe des visages. L’article 3 avait pour objectif principal de tester l’hypothèse formulée à la fin de l’article 1 suivant laquelle l’information chromatique dans la région de la bouche serait extraite très rapidement par le système visuel lors de la discrimination du sexe. Cent douze participants ont chacun complété 900 essais d’une tâche de discrimination du genre pendant laquelle l’information achromatique et chromatique des visages était échantillonnée spatiotemporellement avec la technique Bubbles. Les résultats d’une analyse présentée en Discussion seulement confirme l’utilisation rapide de l’information chromatique dans la région de la bouche. De plus, l’utilisation d’un échantillonnage spatiotemporel nous a permis de faire des analyses temps-fréquences desquelles a découlé une découverte intéressante quant aux mécanismes d’encodage des informations spatiales dans le temps. Il semblerait que l’information achromatique et chromatique à l’intérieur d’une même région faciale est échantillonnée à la même fréquence par le cerveau alors que les différentes parties du visage sont échantillonnées à des fréquences différentes (entre 6 et 10 Hz). Ce code fréquentiel est compatible avec certaines évidences électrophysiologiques récentes qui suggèrent que les parties de visages sont « multiplexées » par la fréquence d’oscillations transitoires synchronisées dans le cerveau.

L'Approximation diophantienne simultanée et l'optimisation discrète

Étant donnée une fonction bornée (supérieurement ou inférieurement) $f:\mathbb{N}^k \To \Real$ par une expression mathématique, le problème de trouver les points extrémaux de $f$ sur chaque ensemble fini $S \subset \mathbb{N}^k$ est bien défini du point de vu classique. Du point de vue de la théorie de la calculabilité néanmoins il faut éviter les cas pathologiques où ce problème a une complexité de Kolmogorov infinie. La principale restriction consiste à définir l'ordre, parce que la comparaison entre les nombres réels n'est pas décidable. On résout ce problème grâce à une structure qui contient deux algorithmes, un algorithme d'analyse réelle récursive pour évaluer la fonction-coût en arithmétique à précision infinie et un autre algorithme qui transforme chaque valeur de cette fonction en un vecteur d'un espace, qui en général est de dimension infinie. On développe trois cas particuliers de cette structure, un de eux correspondant à la méthode d'approximation de Rauzy. Finalement, on établit une comparaison entre les meilleures approximations diophantiennes simultanées obtenues par la méthode de Rauzy (selon l'interprétation donnée ici) et une autre méthode, appelée tétraédrique, que l'on introduit à partir de l'espace vectoriel engendré par les logarithmes de nombres premiers.

Logarithme d'harmoniques sphériques pour le rendu d'ombres douces de champs de hauteurs et de maillages

Les ombres sont un élément important pour la compréhension d'une scène. Grâce à elles, il est possible de résoudre des situations autrement ambigües, notamment concernant les mouvements, ou encore les positions relatives des objets de la scène. Il y a principalement deux types d'ombres: des ombres dures, aux limites très nettes, qui résultent souvent de lumières ponctuelles ou directionnelles; et des ombres douces, plus floues, qui contribuent à l'atmosphère et à la qualité visuelle de la scène. Les ombres douces résultent de grandes sources de lumière, comme des cartes environnementales, et sont difficiles à échantillonner efficacement en temps réel. Lorsque l'interactivité est prioritaire sur la qualité, des méthodes d'approximation peuvent être utilisées pour améliorer le rendu d'une scène à moindre coût en temps de calcul. Nous calculons interactivement les ombres douces résultant de sources de lumière environnementales, pour des scènes composées d'objets en mouvement et d'un champ de hauteurs dynamique. Notre méthode enrichit la méthode d'exponentiation des harmoniques sphériques, jusque là limitée aux bloqueurs sphériques, pour pouvoir traiter des champs de hauteurs. Nous ajoutons également une représentation pour les BRDFs diffuses et glossy. Nous pouvons ainsi combiner les visibilités et BRDFs dans un même espace, afin de calculer efficacement les ombres douces et les réflexions de scènes complexes. Un algorithme hybride, qui associe les visibilités en espace écran et en espace objet, permet de découpler la complexité des ombres de la complexité de la scène.

Le programme cognitif-comportemental au CJM-IU : l'effet du degré d'exposition au programme sur l'ampleur des troubles de comportement des adolescentes six mois après leur admission au CJM-IU

L’implantation de programmes probants dans les milieux d’intervention peut comporter son lot de difficultés pour les gestionnaires ainsi que les intervenants en contexte de réadaptation pour adolescents. En effet, les contraintes auxquelles peuvent être confrontés les milieux de pratique mènent parfois à la modification des programmes, ceci en vue de faciliter leur implantation. Il devient alors important de documenter ainsi qu’identifier l’effet des éléments associés à la fidélité d’implantation lorsque les programmes d’intervention sont évalués. En plus d’évaluer l’effet du degré d’exposition au programme cognitif-comportemental implanté dans les unités d’hébergement du Centre jeunesse de Montréal – Institut universitaire (CJM-IU) sur l’ampleur des troubles de comportement des adolescentes, ce mémoire propose une nouvelle piste de recherche. Puisque la recherche empirique ne permet pas encore d’identifier les conditions selon lesquelles il serait possible de modifier les programmes d’intervention qui sont adoptés dans le contexte de la pratique, cette étude propose d’élaborer une logique d’exposition au programme qui s’inspire des principes d’intervention efficace élaborés par Andrews et ses collègues (1990). Cette approche permettrait d’adapter le niveau d’intervention aux caractéristiques de la clientèle, et ce, tout en s’assurant de l’efficacité du programme cognitif-comportemental. L’échantillon de cette étude est donc constitué de 74 adolescentes hébergées au CJM-IU pour une durée de six mois. Les résultats indiquent d’abord que les activités du programme cognitif-comportemental ont été appliquées de façon plutôt irrégulière et bien en deçà de la fréquence initialement prévue, ce qui rend bien compte des difficultés à implanter des programmes en contexte de pratique. Les résultats suggèrent aussi une diminution de l’ampleur des troubles de comportement six mois après l’admission au CJM-IU pour les adolescentes qui étaient caractérisées par une ampleur des troubles de comportement plus marquée au moment de leur admission et qui ont complété un plus grand nombre d’auto-observations durant leur placement.

L’efficacité contestée du recours aux agents de santé communautaires pour la prise en charge du paludisme : évaluation du programme burkinabé dans les districts de Kaya et de Zorgho

Contexte. Le paludisme provoque annuellement le décès d’environ 25 000 enfants de moins de cinq ans au Burkina Faso. Afin d’améliorer un accès rapide à des traitements efficaces, les autorités burkinabées ont introduit en 2010 la prise en charge du paludisme par les agents de santé communautaires (ASC). Alors que son efficacité a été démontrée dans des études contrôlées, très peu d’études ont évalué cette stratégie implantée dans des conditions naturelles et à l’échelle nationale. Objectif. L’objectif central de cette thèse est d’évaluer, dans des conditions réelles d’implantation, les effets du programme burkinabé de prise en charge communautaire du paludisme sur le recours aux soins des enfants fébriles. Les objectifs spécifiques sont : (1) de sonder les perceptions des ASC à l’égard du programme et explorer les facteurs contextuels susceptibles d’affecter leur performance ; (2) d’estimer le recours aux ASC par les enfants fébriles et identifier ses déterminants ; (3) de mesurer, auprès des enfants fébriles, le changement des pratiques de recours aux soins induit par l’introduction d’une intervention concomitante – la gratuité des soins dans les centres de santé. Méthodes. L’étude a été conduite dans deux districts sanitaires similaires, Kaya et Zorgho. Le devis d’évaluation combine des volets qualitatifs et quantitatifs. Des entrevues ont été menées avec tous les ASC de la zone à l’étude (N=27). Des enquêtes ont été répétées annuellement entre 2011 et 2013 auprès de 3002 ménages sélectionnés aléatoirement. Les pratiques de recours aux soins de tous les enfants de moins de cinq ans ayant connu un récent épisode de maladie ont été étudiées (N2011=707 ; N2012=787 ; N2013=831). Résultats. Les résultats montrent que le recours aux ASC est très modeste en comparaison de précédentes études réalisées dans des milieux contrôlés. Des obstacles liés à l’implantation du programme de prise en charge communautaire du paludisme ont été identifiés ainsi qu’un défaut de faisabilité dans les milieux urbains. Enfin, l’efficacité du programme communautaire a été négativement affectée par l’introduction de la gratuité dans les centres de santé. Conclusion. La prise en charge communautaire du paludisme rencontre au Burkina Faso des obstacles importants de faisabilité et d’implantation qui compromettent son efficacité potentielle pour réduire la mortalité infantile. Le manque de coordination entre le programme et des interventions locales concomitantes peut générer des effets néfastes et inattendus.