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.

Le problème de Coulomb-Dunkl dans le plan

Ce mémoire, composé d'un article en collaboration avec Monsieur Luc Vinet et Vincent X. Genest, est la suite du travail effectué sur les systèmes quantiques super-intégrables définis par des Hamiltoniens de type Dunkl. Plus particulièrement, ce mémoire vise l'analyse du problème de Coulomb-Dunkl dans le plan qui est une généralisation du système quantique de l'atome d'hydrogène impliquant des opérateurs de réflexion sur les variables x et y. Le modèle est défini par un potentiel en 1/r. Nous avons tout d'abord remarqué que l'Hamiltonien est séparable en coordonnées polaires et que les fonctions d'onde s'écrivent en termes de produits de polynômes de Laguerre généralisés et des harmoniques de Dunkl sur le cercle. L'algèbre générée par les opérateurs de symétrie nous a également permis de confirmer le caractère maximalement super-intégrable du problème de Coulomb-Dunkl. Nous avons aussi pu écrire explicitement les représentations de cette même algèbre. Nous avons finalement trouvé le spectre de l'énergie de manière algébrique.

Le problème goth au IIIe siècle ap. J.-C. : perceptions et réalités, solutions et échecs militaires.

Au coeur de la crise du IIIe siècle, l’Empire subit de toutes parts les assauts de Barbares soudainement plus nombreux et plus virulents. Parmi ces peuples se trouvaient les Goths, nouvellement arrivés, qui tinrent les Romains et leurs armées en échecs pendant vingt longues années. Face aux multiples défaites, parfois catastrophiques, et aux très nombreuses villes capturées et saccagées par les envahisseurs, ce mémoire se propose d’apporter une nouvelle approche à la compréhension des échecs dont les Romains firent l’expérience, mais aussi des solutions militaires qu’ils mirent en oeuvre face aux Goths au IIIe siècle. Les défaites majeures subies durant la décennie 250 sur le bas-Danube puis dans la région de la Mer Noire semblent pouvoir s’expliquer en partie par l’absence de connaissance qu’avaient Romains des Goths. Les premières victoires romaines significatives contre les Goths sous les règnes de Gallien puis Claude II ont été rendues possibles grâce à une évolution de la stratégie romaine face à cet ennemi, privilégiant l’emploi de la cavalerie et anticipant les schémas d’attaques des envahisseurs. Les décisions politiques et militaires d’Aurélien dans la région montrent que les Romains se sont enfin adaptés à la menace en modifiant leur perception des Goths, désormais mieux connus.

Algorithmes heuristiques et exacts pour le problème de l’ensemble dominant connexe minimum.

Dans ce mémoire, nous abordons le problème de l’ensemble dominant connexe de cardinalité minimale. Nous nous penchons, en particulier, sur le développement de méthodes pour sa résolution basées sur la programmation par contraintes et la programmation en nombres entiers. Nous présentons, en l’occurrence, une heuristique et quelques méthodes exactes pouvant être utilisées comme heuristiques si on limite leur temps d’exécution. Nous décrivons notamment un algorithme basé sur l’approche de décomposition de Benders, un autre combinant cette dernière avec une stratégie d’investigation itérative, une variante de celle-ci utilisant la programmation par contraintes, et enfin une méthode utilisant uniquement la programmation par contraintes. Des résultats expérimentaux montrent que ces méthodes sont efficaces puisqu’elles améliorent les méthodes connues dans la littérature. En particulier, la méthode de décomposition de Benders avec une stratégie d’investigation itérative fournit les résultats les plus performants.

Problème inverse de Galois : critère de rigidité

Dans ce mémoire, on étudie les extensions galoisiennes finies de C(x). On y démontre le théorème d'existence de Riemann. Les notions de rigidité faible, rigidité et rationalité y sont développées. On y obtient le critère de rigidité qui permet de réaliser certains groupes comme groupes de Galois sur Q. Plusieurs exemples de types de ramification sont construis.

Au carrefour de l’intégration socio-professionnelle : perspectives et questionnements de personnes vivant avec des problèmes de santé mentale

Ce travail de mémoire porte sur le processus d’insertion sociale et économique des personnes vivant des problèmes de santé mentale. Le travail est devenu un important véhicule d’intégration sociale. En effet, on prétend que la pratique d’un métier serait pour les personnes souffrant de problèmes de santé un outil de rétablissement et de mieux-être, car elle permet de réduire les symptômes et l’incidence des hospitalisations. Le travail permet, également, d’augmenter les interactions sociales et de contribuer activement à la société. Il existe, toutefois, d’autres véhicules d’intégration qui semblent, sous certains angles, apporter les mêmes avantages. Les activités bénévoles améliorent la qualité de vie, favorisent les interactions sociales et donnent, à l’individu, l’occasion de contribuer à sa communauté. Par ailleurs, le retrait social peut être un moyen de s’éloigner des pressions sociales et de s’accorder une pause bénéfique. On soutient que les personnes ayant un problème de santé mentale qui ont une lecture positive de leur situation de marginalité tendent à être moins hospitalisées. S’appuyant sur une démarche qualitative, ce travail de recherche a tenté de cerner les perspectives, les questionnements et les perceptions des personnes ayant un trouble mental à l’égard d’un processus d’intégration socioprofessionnelle, de participation sociale et de retrait social. Des entrevues semi-dirigées ont été menées auprès de onze personnes, et grâce à ces entretiens, un portrait au regard de leurs parcours social et professionnel a pu être brossé. Les entretiens ont permis d’explorer l’impact des problèmes de santé mentale sur leur réalité et sur leur identité, leurs représentations du marché de l’emploi et les motifs qui justifient le choix de s’engager ou de renoncer à un processus d’intégration socioprofessionnelle. Les résultats de cette recherche ont permis d'identifier cinq facteurs qui peuvent influencer la décision des personnes qui sont le rapport à l'environnement social, l'identité, le rapport aux institutions de l'État, les discours de légitimation et les perspectives d'avenir. Les résultats démontrent que l'on ne peut isoler les notions de vulnérabilité, d'autonomie, de bien-être ou de stabilité dans une phase spécifique. La vulnérabilité, l'autonomie, le bien-être et la stabilité sont des états que l’on peut vivre en situation de retrait social, de participation sociale et d’intégration socioprofessionnelle. Selon les circonstances et l’état émotif, ils peuvent être des modes adaptés ou inadaptés.

Problème du paradigme dans l'approche écologique de l'individualité chez Turner : une solution méréologique inspirée de Dupré et O'Malley

Ce mémoire propose une étude de la théorie de l’individualité biologique développée par Turner, des problèmes inhérents à celle-ci ainsi qu’une approche qui permet de surmonter les problèmes de la théorie de Turner tout en prenant en compte les aspects importants de cette dernière. Nous montrerons en premier lieu pourquoi, selon Turner, l’individualité est une question écologique et que l’individu ne peut être compris sans ses parties abiotiques si celles-ci jouent un rôle dans la fonctionnalité de l’individu. Par la suite, nous démontrerons que l’approche de Turner est sujette au problème du paradigme développé par Haber. Enfin, en s’inspirant de la théorie de l’individualité de Dupré et O’Malley et de leurs études sur les bactéries, nous forgerons une nouvelle théorie portée sur la fonctionnalité, qualifiée d’approche méréologique, qui surmonte les problèmes exposés tout en prenant en compte le rôle que les parties abiotiques jouent dans le fonctionnement de l’individu.

L'algorithme de Branch and Price and Cut pour le problème de conception de réseaux avec coûts fixes et sans capacité

Le problème de conception de réseaux est un problème qui a été beaucoup étudié dans le domaine de la recherche opérationnelle pour ses caractéristiques, et ses applications dans des nombreux domaines tels que le transport, les communications, et la logistique. Nous nous intéressons en particulier dans ce mémoire à résoudre le problème de conception de réseaux avec coûts fixes et sans capacité, en satisfaisant les demandes de tous les produits tout en minimisant la somme des coûts de transport de ces produits et des coûts fixes de conception du réseau. Ce problème se modélise généralement sous la forme d’un programme linéaire en nombres entiers incluant des variables continues. Pour le résoudre, nous avons appliqué la méthode exacte de Branch-and-Bound basée sur une relaxation linéaire du problème avec un critère d’arrêt, tout en exploitant les méthodes de génération de colonnes et de génération de coupes. Nous avons testé la méthode de Branch-and-Price-and-Cut sur 156 instances divisées en cinq groupes de différentes tailles, et nous l’avons comparée à Cplex, l’un des meilleurs solveurs d’optimisation mathématique, ainsi qu’à la méthode de Branch-and- Cut. Notre méthode est compétitive et plus performante sur les instances de grande taille ayant un grand nombre de produits.

Le problème de l'inclusion : l'insuffisance de la tolérance libérale

Le principe de tolérance libérale a certainement joué un rôle important depuis le XVII e siècle dans le processus de transformation sociale et politique des sociétés occidentales. De nombreuses luttes sociales ont été menées et remportées en s’appuyant sur ce principe que certains auteurs, dont Rawls, identifient comme étant un, sinon le principe central qui unit la tradition libérale. Les dernières décennies ont toutefois vu émerger de nouveaux motifs de lutte sociale, des demandes d’inclusion de nature nouvelle, que la tolérance libérale ne suffit plus à porter. La notion de reconnaissance semble permettre, et c’est ce que cet article s’attache à montrer, de pallier les lacunes d’une approche de la tolérance libérale qui ne parvient pas à accommoder les nouvelles formes de défis que posent les sociétés pluralistes occidentales. Une seconde thèse que propose cet article, à peine esquissée cependant, consiste à montrer que si le paradigme libéral n’est pas à la hauteur des attentes, le républicanisme est plus à même de répondre au problème de l’inclusion.

Une formulation hégélienne du problème de la non-identité dans les théories de justice intergénérationnelle

Le problème de la non-identité est une difficulté sérieuse qui ne peut pas être ignorée par les théories de justice intergénérationnelle dans la mesure où ce problème tend à remettre en cause l'idée de responsabilité envers les générations futures. C'est dans ces conditions que ce texte propose d'éprouver le problème de la non-identité en faisant ressortir les concepts qui semblent y être sous-tendus et articulés d'une façon particulière, à savoir les concepts de réalité et de possibilité. Or, il apparaît que la philosophie hégélienne arrive à point nommé pour exprimer l'articulation qui se joue entre réalité et possibilité dans le problème en question. De cette façon, Hegel apparaît comme étant un interlocuteur privilégié pour expliciter ce que recouvre le problème de la non-identité.

La prédation : un problème pour le conséquentialisme en éthique animale ?

Parmi les différents problèmes récents animant les débats en éthique animale, celui de la prédation pose plusieurs défis. En effet, selon certaines théories, nous devrions intervenir dans la nature pour empêcher la prédation entre les espèces, parfois pour protéger le droit des proies (Regan) ou encore pour des raisons politiques (Donaldson et Kymlicka). Toutefois, personne ne semble vouloir accepter une telle implication puisque, comme le dirait Palmer, nous avons une forte intuition de « laisser-aller » en ce qui concerne la prédation. Dans cet article, je soutiendrai que le problème de la prédation n’en est pas vraiment un pour les approches conséquentialistes. Comme je le démontrerai au terme d’une révision des articles de Everett et Milburn, les approches conséquentialistes n’autorisent une telle intervention que sous des conditions extrêmement restreintes.

Projeto em Áreas Consolidadas de Patrimônio Cultural: Propostas para a Construção de uma Metodologia de Ensino

Le thème du patrimoine culturel architectural et urbain continue d avoir une place importante dans le milieu technique et scientifique. Le concept s est élargi et aujourd hui comprend différentes procédures de projets d intervention. L importance accordée au thème amène à l inclusion de la matière de techniques rétrospectives et aux contenus qui en sont liés: conservation, restauration, restructuration et reconstruction d édifices et ensembles urbains, dans les parcours des cours d architecture et d urbanisme au Brésil établies par le Ministère de l Education Nationale (MEC) dans les années quatre-vingt-dix, postérieurement incorporés dans les directrices disciplinaires nationales. Nous partons des discussions théoriques et conceptuelles du Domaine du Patrimoine Culturel, ainsi que des principales théories pédagogiques d enseignements et d apprentissage articulées au projet. Dans ce contexte les objectifs principaux de cette thèse consistent à systématiser et à analyser les principales procédures méthodologiques contribuant pour la construction de méthodes d enseignement tournée vers des activités pratiques dans ce domaine. Pour cela, la recherche a été systématisée dans une approche à deux niveaux. En ce qui concerne le premier, basé sur des données secondaires, neuf cours d architecture et urbanisme ont étés identifiés entre institutions publiques d enseignement supérieur dont huit brésiliennes et une française, considérées représentatives en ce qui concerne les pratiques d enseignement de projet et de patrimoine culturel. Trente disciplines dédiées à la matière ont été également reconnues initialement, et postérieurement, cinq disciplines qui possèdent un emploi du temps dédié à la pratique de projet ont aussi été reconnues. Dans le deuxième cas, basée sur des données primaires, ont étés analysées les méthodologies et les stratégies d enseignement de projet basées sur les définitions des matières et des autres éléments des plans de travail avec des observations, des entrevues et des questionnaires en trois ateliers. Par rapport aux résultats nous avons constaté que toutes les écoles possèdent les contenus de la matière, mais peu d entre elles privilégient la relation du projet appliqué au patrimoine culturel. Nous avons constaté que les questions des projets dans ce contexte, même s elles sont considérées complexes, ont privilégié le listage et l analyse du site. L atelier qui intègre les fondements des théories de préservation, l histoire de l architecture et urbanisme et techniques anciennes et actuelles, est mis en valeur comme un modèle cohérent avec les propositions d intégration des connaissances théoriques et pratiques du projet appliqué à la discipline. Basé sur ces constatations il est possible de démontrer quatre étapes du projet appliqué au patrimoine culturel: 1ª) les fondements généraux qui concernent les bases théoriques sur la préservation, histoire et technique rétrospective, par exemple, l appropriation de lois et normes et la sensibilisation de l élève sur les questions de patrimoine culturel; 2ª) le contacte avec la réalité qui inclut l appropriation du problème à partir de ces acteurs, de ces échelles, de cette lecture de site et l analyse de l objet d étude; 3ª) le développement de la proposition qui inclut programmes (fonctions existantes et propositions), définitions du partit (types d intervention), conception (hypothèse et discussion) et définition de proposition; 4ª) la finalisation du projet qui consiste à développer la proposition avec sa représentation graphique et sa présentation finale. Nous concluons que le projet en Domaine du Patrimoine Culturel demande une attention spéciale et doit être présent dans les cursus considérant les principes généraux nécessaires à la formation de l élève. Le binôme projet / patrimoine signifie avoir dans le cursus universitaire les contenus et questions nécessaires les connaissances, les variables et possibilités existantes dans le projet appliqué au patrimoine culturel de façon à ce que ces connaissances soient incorporées dans l exercice de projet et n apparaissent pas comme un simple contenu théorique sans articulation avec la pratique. Naturellement ces conclusions n épuisent pas la réflexion sur la question. Nous espérons que les analyses faites contribuent à définir des méthodologies d enseignements capables d êtres vérifiées et testées dans la pratique en salle de cours, et puisse collaborer avec les nouvelles recherches surtout celles qui ont pour but des nouvelles théories pédagogiques d enseignement apprentissage du projet en Domaine du Patrimoine Culturel

A Construção social do conhecimento :a reorientação curricular via tema gerador na Escola Cabana em Belém/PA

Cette étude analyse l'expérience de réorientation curriculaire atravers le sujet générateur, vécue dans les écoles qui composent le système municipal d'éducation de Belém du Pará - École Cabana, en ayant comme locus de recherche l'École Municipale João Carlos Batista. Ce mouvement de réorientation curriculaire, qui rompt avec le modèle traditionnel d'un curriculum linéaire, hiérarchique et fragmenté a comme préssuposées théoriquesméthodologiques les principes et les catégories freireanas la pédagogie critique qui estime un curriculum interdisciplinaire, dialogique, démocratique et contextuel, à partir de la systématisation d'une proposition theorico-méthodologique de réorientation curriculaire par le thème générateur, c'est-à-dire, en partant de situations-problème de la communauté scolaire, en faisant des relations négociées par les connaissances scolaires pour la compréhension et possible intervention dans la réalité. Cette proposition est mise en oeuvre non seulement à Belém, mais aussi par d autres municipalités du Brésil. Étant donné que l'École Cabana est une expérience inovatrice dans la tentative de viabiliser une Éducation vraiment démocratique, elle dialogue encore avec autres expériences d'écoles de même nature au Brésil, (comme l'École Plural-MG, l'École Citoyen - RS et l'École Candanga DF). Á partir des idées de Paulo Freire, J. Sacristán, M. Apple, C. Linhares, A. Coulon et autres j apporte des réflexions epistemologiques concernant le problème de la recherche qui consiste sur le registre et l'analyse de la tentative de construction sociale de la connaissance par le thème générateur qui a eu lieu à l'École Cabana dans la période de 2001 à 2004. Comme procédure méthodologique, j'ai développé une Recherche qualitative, de caractère collaboratif, en utilisant comme techniques de rassemble de données l observation participative dans le quotidien écolier, des interviews semi-structurées, et l'analyse des documents et des productions de l'École. Les résultats indiquent l'importance du registre de ce type d expérience, en soulignant leurs avances et reculs qui pourront servir de référentiel pour de futures politiques de réorientation curriculaire dans la direction de la construction sociale de la connaissance et, par conséquent, d'une Éducation plus démocratique et tournée vers une citoyenneté active