Priorities in the Location of Multiple Public Facilities

A collective decision problem is described by a set of agents, a profile of single-peaked preferences over the real line and a number k of public facilities to be located. We consider public facilities that do not su¤er from congestion and are non-excludable. We provide a characterization of the class of rules satisfying Pareto-efficiency, object-population monotonicity and sovereignty. Each rule in the class is a priority rule that selects locations according to a predetermined priority ordering among interest groups. We characterize each of the subclasses of priority rules that respectively satisfy anonymity, hiding-proofness and strategy-proofness. In particular, we prove that a priority rule is strategy-proof if and only if it partitions the set of agents into a fixed hierarchy. Alternatively, any such rule can be viewed as a collection of fixed-populations generalized peak-selection median rules (Moulin, 1980), that are linked across populations, in a way that we describe.

Exploration de l’expérience de tirer son lait par les mères : constats dans une optique de design

Le tire-lait est un appareil conçu pour aider les mères durant l’allaitement. Selon la recherche préliminaire effectuée, c’est un thème très peu exploré dans les études; il est donc difficile d’affirmer si le produit répond correctement aux besoins reliés à son usage et à son utilité ou comment il s’intègre dans l’allaitement. Les fondements de l’étude exploratoire ont été bâtis sur ces enjeux dans le but de comprendre l’expérience d’usage du tire-lait. Inspirée de l’approche phénoménologique centrée sur l’usager, l’étude a permis d’amasser des données qualitatives à travers des entrevues semi-dirigées auprès de sept participantes. L’analyse de ces données a permis d’identifier les thèmes importants qui ont mené à des constats, rédigés dans une optique de design. L’étude a trouvé que c’est souvent quand la réalité de l’allaitement au sein rattrape les mères qu’elles vont vouloir se procurer un tire-lait, en s’inspirant des marques utilisées dans les hôpitaux par manque de temps. Le tire-lait devient alors principalement utile pour se désengorger et pour la liberté qu’il procure, s’intégrant dans une routine. Le tire-lait est par contre peu ergonomique; il semble y avoir un décalage entre le concept proposé et les manipulations réelles, notamment au niveau de la mise en marche, des bouteilles et des embouts. Ces résultats de l’étude pourraient être intégrés dans le tire-lait pour mieux représenter la réalité du contexte, de la pratique et de l’usage du produit. Ils pourraient ainsi nourrir le processus de conception dans un projet futur afin d’améliorer le design du tire-lait.

Un protocole de diffusion des messages dans les réseaux véhiculaires

De nos jours, la voiture est devenue le mode de transport le plus utilisé, mais malheureusement, il est accompagné d’un certain nombre de problèmes (accidents, pollution, embouteillages, etc.), qui vont aller en s’aggravant avec l’augmentation prévue du nombre de voitures particulières, malgré les efforts très importants mis en œuvre pour tenter de les réduire ; le nombre de morts sur les routes demeure très important. Les réseaux sans fil de véhicules, appelés VANET, qui consistent de plusieurs véhicules mobiles sans infrastructure préexistante pour communiquer, font actuellement l’objet d'une attention accrue de la part des constructeurs et des chercheurs, afin d’améliorer la sécurité sur les routes ou encore les aides proposées aux conducteurs. Par exemple, ils peuvent avertir d’autres automobilistes que les routes sont glissantes ou qu’un accident vient de se produire. Dans VANET, les protocoles de diffusion (broadcast) jouent un rôle très important par rapport aux messages unicast, car ils sont conçus pour transmettre des messages de sécurité importants à tous les nœuds. Ces protocoles de diffusion ne sont pas fiables et ils souffrent de plusieurs problèmes, à savoir : (1) Tempête de diffusion (broadcast storm) ; (2) Nœud caché (hidden node) ; (3) Échec de la transmission. Ces problèmes doivent être résolus afin de fournir une diffusion fiable et rapide. L’objectif de notre recherche est de résoudre certains de ces problèmes, tout en assurant le meilleur compromis entre fiabilité, délai garanti, et débit garanti (Qualité de Service : QdS). Le travail de recherche de ce mémoire a porté sur le développement d’une nouvelle technique qui peut être utilisée pour gérer le droit d’accès aux médias (protocole de gestion des émissions), la gestion de grappe (cluster) et la communication. Ce protocole intègre l'approche de gestion centralisée des grappes stables et la transmission des données. Dans cette technique, le temps est divisé en cycles, chaque cycle est partagé entre les canaux de service et de contrôle, et divisé en deux parties. La première partie s’appuie sur TDMA (Time Division Multiple Access). La deuxième partie s’appuie sur CSMA/CA (Carrier Sense Multiple Access / Collision Avoidance) pour gérer l’accès au medium. En outre, notre protocole ajuste d’une manière adaptative le temps consommé dans la diffusion des messages de sécurité, ce qui permettra une amélioration de la capacité des canaux. Il est implanté dans la couche MAC (Medium Access Control), centralisé dans les têtes de grappes (CH, cluster-head) qui s’adaptent continuellement à la dynamique des véhicules. Ainsi, l’utilisation de ce protocole centralisé nous assure une consommation efficace d’intervalles de temps pour le nombre exact de véhicules actifs, y compris les nœuds/véhicules cachés; notre protocole assure également un délai limité pour les applications de sécurité, afin d’accéder au canal de communication, et il permet aussi de réduire le surplus (overhead) à l’aide d’une propagation dirigée de diffusion.

Routage adaptatif et stabilité dans les réseaux maillés sans fil

Grâce à leur flexibilité et à leur facilité d’installation, les réseaux maillés sans fil (WMNs) permettent un déploiement d’une infrastructure à faible coût. Ces réseaux étendent la couverture des réseaux filaires permettant, ainsi, une connexion n’importe quand et n’importe où. Toutefois, leur performance est dégradée par les interférences et la congestion. Ces derniers causent des pertes de paquets et une augmentation du délai de transmission d’une façon drastique. Dans cette thèse, nous nous intéressons au routage adaptatif et à la stabilité dans ce type de réseaux. Dans une première partie de la thèse, nous nous intéressons à la conception d’une métrique de routage et à la sélection des passerelles permettant d’améliorer la performance des WMNs. Dans ce contexte nous proposons un protocole de routage à la source basé sur une nouvelle métrique. Cette métrique permet non seulement de capturer certaines caractéristiques des liens tels que les interférences inter-flux et intra-flux, le taux de perte des paquets mais également la surcharge des passerelles. Les résultats numériques montrent que la performance de cette métrique est meilleure que celle des solutions proposées dans la littérature. Dans une deuxième partie de la thèse, nous nous intéressons à certaines zones critiques dans les WMNs. Ces zones se trouvent autour des passerelles qui connaissent une concentration plus élevé du trafic ; elles risquent de provoquer des interférences et des congestions. À cet égard, nous proposons un protocole de routage proactif et adaptatif basé sur l’apprentissage par renforcement et qui pénalise les liens de mauvaise qualité lorsqu’on s’approche des passerelles. Un chemin dont la qualité des liens autour d’une passerelle est meilleure sera plus favorisé que les autres chemins de moindre qualité. Nous utilisons l’algorithme de Q-learning pour mettre à jour dynamiquement les coûts des chemins, sélectionner les prochains nœuds pour faire suivre les paquets vers les passerelles choisies et explorer d’autres nœuds voisins. Les résultats numériques montrent que notre protocole distribué, présente de meilleurs résultats comparativement aux protocoles présentés dans la littérature. Dans une troisième partie de cette thèse, nous nous intéressons aux problèmes d’instabilité des réseaux maillés sans fil. En effet, l’instabilité se produit à cause des changements fréquents des routes qui sont causés par les variations instantanées des qualités des liens dues à la présence des interférences et de la congestion. Ainsi, après une analyse de l’instabilité, nous proposons d’utiliser le nombre de variations des chemins dans une table de routage comme indicateur de perturbation des réseaux et nous utilisons la fonction d’entropie, connue dans les mesures de l’incertitude et du désordre des systèmes, pour sélectionner les routes stables. Les résultats numériques montrent de meilleures performances de notre protocole en comparaison avec d’autres protocoles dans la littérature en termes de débit, délai, taux de perte des paquets et l’indice de Gini.

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.

The exploration of mixed-use principle as an ingredient to improve the viability and vitality of town centres in Mauritius

This thesis has been realised through a scholarship offered by the Government of Canada to the Government of the Republic of Mauritius under the Programme Canadien de Bourses de la Francophonie

Le sens de l’urgence à l’hôpital

Article