A heuristic algorithm for the Capacitated Vehicle Routing Problem with Synchronized Pick-ups and Drop-offs : a case study for medications delivery and supervision in DR Congo

Dans des contextes de post-urgence tels que le vit la partie occidentale de la République Démocratique du Congo (RDC), l’un des défis cruciaux auxquels font face les hôpitaux ruraux est de maintenir un niveau de médicaments essentiels dans la pharmacie. Sans ces médicaments pour traiter les maladies graves, l’impact sur la santé de la population est significatif. Les hôpitaux encourent également des pertes financières dues à la péremption lorsque trop de médicaments sont commandés. De plus, les coûts du transport des médicaments ainsi que du superviseur sont très élevés pour les hôpitaux isolés ; les coûts du transport peuvent à eux seuls dépasser ceux des médicaments. En utilisant la province du Bandundu, RDC pour une étude de cas, notre recherche tente de déterminer la faisabilité (en termes et de la complexité du problème et des économies potentielles) d’un problème de routage synchronisé pour la livraison de médicaments et pour les visites de supervision. Nous proposons une formulation du problème de tournées de véhicules avec capacité limitée qui gère plusieurs exigences nouvelles, soit la synchronisation des activités, la préséance et deux fréquences d’activités. Nous mettons en œuvre une heuristique « cluster first, route second » avec une base de données géospatiales qui permet de résoudre le problème. Nous présentons également un outil Internet qui permet de visualiser les solutions sur des cartes. Les résultats préliminaires de notre étude suggèrent qu’une solution synchronisée pourrait offrir la possibilité aux hôpitaux ruraux d’augmenter l’accessibilité des services médicaux aux populations rurales avec une augmentation modique du coût de transport actuel.

On Complexity of Lobbying in Multiple Referenda

In this paper we show that lobbying in conditions of “direct democracy” is virtually impossible, even in conditions of complete information about voters preferences, since it would require solving a very computationally hard problem. We use the apparatus of parametrized complexity for this purpose.

Investment Under Demand Uncertainty: the Newsboy Problem Revisited.

In this article we study the effect of uncertainty on an entrepreneur who must choose the capacity of his business before knowing the demand for his product. The unit profit of operation is known with certainty but there is no flexibility in our one-period framework. We show how the introduction of global uncertainty reduces the investment of the risk neutral entrepreneur and, even more, that the risk averse one. We also show how marginal increases in risk reduce the optimal capacity of both the risk neutral and the risk averse entrepreneur, without any restriction on the concave utility function and with limited restrictions on the definition of a mean preserving spread. These general results are explained by the fact that the newsboy has a piecewise-linear, and concave, monetary payoff witha kink endogenously determined at the level of optimal capacity. Our results are compared with those in the two literatures on price uncertainty and demand uncertainty, and particularly, with the recent contributions of Eeckhoudt, Gollier and Schlesinger (1991, 1995).

The Transformation Problem : an Aleternative Solution with an Identical Aggregate Profit Rate in the Labor value and the Monetary Space.

The aim of this paper is to demonstrate that, even if Marx's solution to the transformation problem can be modified, his basic conclusions remain valid. the proposed alternative solution which is presented hare is based on the constraint of a common general profit rate in both spaces and a money wage level which will be determined simultaneously with prices.

The Wage Rate and the Profit Rate in the Price of Production Equation: a New Solution to an Old Problem

The aim of this paper is to demonstrate that, even if Marx's solution to the transformation problem can be modified, his basic concusions remain valid.

The Transformation Problem : an Aleternative Solution with an Identical Aggregate Profit Rate in the Labor value and the Monetary Space.

The aim of this paper is to demonstrate that, even if Marx's solution to the transformation problem can be modified, his basic conclusions remain valid. the proposed alternative solution which is presented hare is based on the constraint of a common general profit rate in both spaces and a money wage level which will be determined simultaneously with prices.

Investment Under Demand Uncertainty: the Newsboy Problem Revisited.

In this article we study the effect of uncertainty on an entrepreneur who must choose the capacity of his business before knowing the demand for his product. The unit profit of operation is known with certainty but there is no flexibility in our one-period framework. We show how the introduction of global uncertainty reduces the investment of the risk neutral entrepreneur and, even more, that the risk averse one. We also show how marginal increases in risk reduce the optimal capacity of both the risk neutral and the risk averse entrepreneur, without any restriction on the concave utility function and with limited restrictions on the definition of a mean preserving spread. These general results are explained by the fact that the newsboy has a piecewise-linear, and concave, monetary payoff witha kink endogenously determined at the level of optimal capacity. Our results are compared with those in the two literatures on price uncertainty and demand uncertainty, and particularly, with the recent contributions of Eeckhoudt, Gollier and Schlesinger (1991, 1995).

La circoncision des femmes en Afrique : repenser les politiques de santé

Section des étudiants / Student's section

Public Reason that Speaks to People : Iris Marion Young and the Problem of Internal Exclusion

Dossier : In Memoriam, Iris Marion Young (1949-2006)

Estimation des longueurs de branche et artefact sur la datation moléculaire

La phylogénie moléculaire fournit un outil complémentaire aux études paléontologiques et géologiques en permettant la construction des relations phylogénétiques entre espèces ainsi que l’estimation du temps de leur divergence. Cependant lorsqu’un arbre phylogénétique est inféré, les chercheurs se focalisent surtout sur la topologie, c'est-à-dire l’ordre de branchement relatif des différents nœuds. Les longueurs des branches de cette phylogénie sont souvent considérées comme des sous-produits, des paramètres de nuisances apportant peu d’information. Elles constituent cependant l’information primaire pour réaliser des datations moléculaires. Or la saturation, la présence de substitutions multiples à une même position, est un artefact qui conduit à une sous-estimation systématique des longueurs de branche. Nous avons décidé d’estimer l‘influence de la saturation et son impact sur l’estimation de l’âge de divergence. Nous avons choisi d’étudier le génome mitochondrial des mammifères qui est supposé avoir un niveau élevé de saturation et qui est disponible pour de nombreuses espèces. De plus, les relations phylogénétiques des mammifères sont connues, ce qui nous a permis de fixer la topologie, contrôlant ainsi un des paramètres influant la longueur des branches. Nous avons utilisé principalement deux méthodes pour améliorer la détection des substitutions multiples : (i) l’augmentation du nombre d’espèces afin de briser les plus longues branches de l’arbre et (ii) des modèles d’évolution des séquences plus ou moins réalistes. Les résultats montrèrent que la sous-estimation des longueurs de branche était très importante (jusqu'à un facteur de 3) et que l’utilisation d'un grand nombre d’espèces est un facteur qui influence beaucoup plus la détection de substitutions multiples que l’amélioration des modèles d’évolutions de séquences. Cela suggère que même les modèles d’évolution les plus complexes disponibles actuellement, (exemple: modèle CAT+Covarion, qui prend en compte l’hétérogénéité des processus de substitution entre positions et des vitesses d’évolution au cours du temps) sont encore loin de capter toute la complexité des processus biologiques. Malgré l’importance de la sous-estimation des longueurs de branche, l’impact sur les datations est apparu être relativement faible, car la sous-estimation est plus ou moins homothétique. Cela est particulièrement vrai pour les modèles d’évolution. Cependant, comme les substitutions multiples sont le plus efficacement détectées en brisant les branches en fragments les plus courts possibles via l’ajout d’espèces, se pose le problème du biais dans l’échantillonnage taxonomique, biais dû à l‘extinction pendant l’histoire de la vie sur terre. Comme ce biais entraine une sous-estimation non-homothétique, nous considérons qu’il est indispensable d’améliorer les modèles d’évolution des séquences et proposons que le protocole élaboré dans ce travail permettra d’évaluer leur efficacité vis-à-vis de la saturation.

User Generated Content in Researching for Design: How the Internet Supports Creativity

Résumé Cette recherche a débuté avec l’idée que l’Internet est en train de changer la manière dont nous créons des connaissances et du contenu culturel. Notre point de départ était d’utiliser l’Internet afin de rassembler et amplifier plusieurs points de vue dans un processus de design. Une approche complexe a exposé l’Internet comme un système et conséquemment comme une plateforme pour l’innovation. La structure ouverte de l’Internet a soutenu le mouvement participatif des usagers qui ont choisi de partager leurs besoins, leurs désirs et leurs solutions. Notre recherche a pour but d’étudier ce contenu généré par les usagers en ligne et comprendre sa valeur pour les designers. Les usagers créatifs veulent s’exprimer et participer activement dans le processus de design. Notre recherche tente de démontrer que les designers ont beaucoup à apprendre du contenu généré par les usagers car ceux-ci soumettent des éléments qui ont attrait à toutes les étapes du processus de design et révèlent des relations présentes dans la situation de design à l’étude. Pour en apprendre plus sur ce contenu nous nous demandons : Quel type d’information offre le contenu généré par les usagers pour la phase de recherche dans le processus de design. Afin de centrer la portée de l’étude, nous nous sommes aussi questionné si cette information est plus pertinente au design de produits, au design de services ou au design de système de produits et de services. Aspirant aux idéaux du design participatif, notre méthodologie fut développée afin d’apprendre comment le contenu généré par les usagers pourrait influencer le processus de design. Pour ce faire, nous avons choisi de chercher sur l’Internet pour du contenu qui concerne la mobilité via l’usage d’une automobile. Les trois différents types de média considérés étaient les vidéos sur YouTube, les images sur Flickr et les textes sur Blogger. Afin de répondre à notre première question de recherche, nous nous sommes penchés sur deux éléments lorsque l’on recherche pour le design : les espaces de design et les relations de design. Premièrement, nous avons catégorisé le contenu récolté selon l’espace problème, créatif et solution. Deuxièmement, nous avons catégorisé le contenu dépendant de laquelle des relations de design elle démontrait soit une combinaison d’usagers, objets et contextes. Dans le but de répondre à la deuxième question de cette recherche, nous avons examiné trois types V de produits de design : les automobiles privées comme produit, le partage de voiture comme système de produit et de service, et le taxi comme service. Chaque élément pertinent généré par les usagés trouvé dans cette recherche fut catégorisé jusqu’à ce que l’on récolte 50 échantillons pour chaque combinaison de ces variables. Nous en sommes arrivés avec une matrice de 50 éléments de chaque produit de design, pour chacun des médias, puis catégorisé selon les espaces de design et les relations dans le design. Cette recherche démontre que l’Internet, comme médium, produit les conditions avantageuses pour que les usagers partagent de grandes quantités de contenu original et diversifié qui est pertinent aux situations de design. À partir de nos données de recherche, nous avons identifié des tendances dans le contenu généré par les usagers. Notamment, nous sommes en mesure d’affirmer que le contenu généré par les usagers offre de l’information pertinente à la recherche pour le design, et ce dans tous les espaces de design et toutes les relations de design. Il en fut de même pour les différentes issues du design car du contenu sur les produits, les systèmes de produits et de services et les services était présent et pertinent. Bref, nous avons démontré que l’Internet supporte la créativité et conséquemment il y abonde de contenu créatif produit par les usagers. Suivant dans les traces dessinées par d’autres chercheurs en design participatif, cette étude devrait être considérée comme un nouvel exemple des moyens qu’ont les designers pour percevoir les besoins tacites des usagers en leur permettant d’exprimer leurs idées. Alors que ceux-ci créent librement et intuitivement ainsi exposant leurs besoins, solutions et idées, les designers peuvent porter un regard de tierce partie sur les résultats. Jumelant des techniques comme le crowdsourcing et le brainstorming, nous avons créé une nouvelle activité et le néologisme : brainsourcing. En demeurant dans une forme de pratique réflexive, les designers peuvent réfléchir et ajouter au contenu généré par les usagers qui lui n’est pas biaisé par une éducation ou une culture du design. Ce processus est similaire au design participatif professionnel où le brainsourcing est une activité parallèle lorsque le designer fait des recherches pour le design. C’est cette perspective sur la somme des idées des participants qui peut contribuer à comprendre la complexité de la situation de design. VI Cette recherche a aussi soulevé des questions par rapport à l’effet de démocratisation de l’Internet. Bien que les usagers n’ont pas l’éducation, ni les habiletés des designers, ils aspirent à démocratiser le processus du design en voulant participer activement et en exposant leurs besoins, idées et solutions. Nous avons pu déterminer que les usagers n’étaient pas qualifiés pour entreprendre le processus complet du design comme les designers professionnels, mais nous avons observé directement la capacité des usagers à mettre de l’avant leur créativité. À propos de la relation entre les usagers créatifs et les designers, nous avons étudié des langages communs tels les scénarios et les prototypes. Tous deux sont présents dans le contenu généré par les usagers que nous avons récolté dans nos recherches sur Internet. Ceci nous a mené vers une nouvelle perspective sur l’activité du design où des opportunités créatives ressortent d’une conversation avec les usagers. Cette recherche a dévoilé de grandes tendances dans la manière dont les usagers communiquent naturellement dans un processus de design. Nous espérons avoir offert un aperçu de comment les designers peuvent prendre avantage de tous les types de contenu généré par les usagers en ligne. Dans le futur, nous souhaitons que les designers aient la possibilité d’interagir avec les participants en prenant le rôle de facilitateur de la conversation. La responsabilité du résultat ne tombe pas sur les épaules du designer car son mandat est d’assurer le bon fonctionnement du processus. Les designers rejoignent les usagers en ne demandant plus comment les choses peuvent être créées, mais pourquoi elles devraient exister. En tant que designers, nous aspirons à générer plus à partir de nouvelles connaissances, nous aspirons à créer plus de sens. Mots clés: Recherche en design, complexité, design participatif, contenu généré par les usagers, démocratisation, Internet, créativité, crowdsourcing, brainstorming, brainsourcing, réflexion-en-action.

Quand le problème est de définir le problème : les compétences mobilisées par les acteurs de la problématisation des projets de stage de coopération internationale

Cette étude a été réalisée dans le cadre d’une maîtrise en Aménagement. Elle s’efforce à démontrer que l’étape d’un projet que l’on appelle problématisation, c’est-à-dire l’étape de construction des problèmes à être résolus, permet de s’assurer que les actions entreprises soient en cohérence et en pertinence avec le contexte du projet. Nous constatons désormais que nous ne pouvons plus nous contenter d’évaluer les projets sur la seule base de son efficience, c’est-à-dire la concordance de ses résultats avec les objectifs prévus. Dans ces circonstances, nous émettons l’hypothèse que la problématisation fait appel à des compétences particulières et généralement peu utilisées par rapport à d’autres étapes de la réalisation d’un projet. À cet égard, nous avons réalisé un travail de recherche exploratoire sur ce thème en ayant comme objectif d’obtenir une compréhension des compétences mobilisées lors de la problématisation en situation de projet en général et d’identifier plus spécifiquement ces compétences dans une situation de projet en particulier, celle des projets de coopération internationale. Pour y arriver, nous avons procédé à la construction d’un référentiel d’emploi et d’activités pour en déduire un référentiel de compétences de la problématisation. Pour ce faire, nous avons réalisé une étude de cas sur les projets de stage de coopération internationale. L’utilisation de la technique de l’« instruction au sosie » et d’une rechercheintervention nous ont permis de dégager les principaux résultats suivant: la problématisation fait appel à des compétences particulières de gestion de l’information et de médiation. Les compétences générales de problématisation que les responsables des stages dans les organisations de coopération internationale v doivent maîtriser sont : être capable de générer les disponibilités de projets à partir de données primaires et secondaires; être capable de faire des choix et de justifier ces choix en fonction de l’analyse des données; être capable de présenter des informations écrites claires, respectueuses des idées des partenaires en fonction du langage de projet utilisé par le public auquel s’adresse la proposition; être capable d’utiliser les commentaires des évaluateurs pour améliorer un projet et être capable de mener à terme un projet. La contribution principale de ce travail de recherche réside dans la proposition d’un outil précieux pour le recrutement et la sélection, l’évaluation du rendement, la formation et le perfectionnement des acteurs de la problématisation.

Planification et dimensionnement des réseaux optiques de longues distances

Le projet de recherche porte sur l'étude des problèmes de conception et de planification d'un réseau optique de longue distance, aussi appelé réseau de coeur (OWAN-Optical Wide Area Network en anglais). Il s'agit d'un réseau qui transporte des flots agrégés en mode commutation de circuits. Un réseau OWAN relie différents sites à l'aide de fibres optiques connectées par des commutateurs/routeurs optiques et/ou électriques. Un réseau OWAN est maillé à l'échelle d'un pays ou d’un continent et permet le transit des données à très haut débit. Dans une première partie du projet de thèse, nous nous intéressons au problème de conception de réseaux optiques agiles. Le problème d'agilité est motivé par la croissance de la demande en bande passante et par la nature dynamique du trafic. Les équipements déployés par les opérateurs de réseaux doivent disposer d'outils de configuration plus performants et plus flexibles pour gérer au mieux la complexité des connexions entre les clients et tenir compte de la nature évolutive du trafic. Souvent, le problème de conception d'un réseau consiste à prévoir la bande passante nécessaire pour écouler un trafic donné. Ici, nous cherchons en plus à choisir la meilleure configuration nodale ayant un niveau d'agilité capable de garantir une affectation optimale des ressources du réseau. Nous étudierons également deux autres types de problèmes auxquels un opérateur de réseau est confronté. Le premier problème est l'affectation de ressources du réseau. Une fois que l'architecture du réseau en termes d'équipements est choisie, la question qui reste est de savoir : comment dimensionner et optimiser cette architecture pour qu'elle rencontre le meilleur niveau possible d'agilité pour satisfaire toute la demande. La définition de la topologie de routage est un problème d'optimisation complexe. Elle consiste à définir un ensemble de chemins optiques logiques, choisir les routes physiques suivies par ces derniers, ainsi que les longueurs d'onde qu'ils utilisent, de manière à optimiser la qualité de la solution obtenue par rapport à un ensemble de métriques pour mesurer la performance du réseau. De plus, nous devons définir la meilleure stratégie de dimensionnement du réseau de façon à ce qu'elle soit adaptée à la nature dynamique du trafic. Le second problème est celui d'optimiser les coûts d'investissement en capital(CAPEX) et d'opération (OPEX) de l'architecture de transport proposée. Dans le cas du type d'architecture de dimensionnement considérée dans cette thèse, le CAPEX inclut les coûts de routage, d'installation et de mise en service de tous les équipements de type réseau installés aux extrémités des connexions et dans les noeuds intermédiaires. Les coûts d'opération OPEX correspondent à tous les frais liés à l'exploitation du réseau de transport. Étant donné la nature symétrique et le nombre exponentiel de variables dans la plupart des formulations mathématiques développées pour ces types de problèmes, nous avons particulièrement exploré des approches de résolution de type génération de colonnes et algorithme glouton qui s'adaptent bien à la résolution des grands problèmes d'optimisation. Une étude comparative de plusieurs stratégies d'allocation de ressources et d'algorithmes de résolution, sur différents jeux de données et de réseaux de transport de type OWAN démontre que le meilleur coût réseau est obtenu dans deux cas : une stratégie de dimensionnement anticipative combinée avec une méthode de résolution de type génération de colonnes dans les cas où nous autorisons/interdisons le dérangement des connexions déjà établies. Aussi, une bonne répartition de l'utilisation des ressources du réseau est observée avec les scénarios utilisant une stratégie de dimensionnement myope combinée à une approche d'allocation de ressources avec une résolution utilisant les techniques de génération de colonnes. Les résultats obtenus à l'issue de ces travaux ont également démontré que des gains considérables sont possibles pour les coûts d'investissement en capital et d'opération. En effet, une répartition intelligente et hétérogène de ressources d’un réseau sur l'ensemble des noeuds permet de réaliser une réduction substantielle des coûts du réseau par rapport à une solution d'allocation de ressources classique qui adopte une architecture homogène utilisant la même configuration nodale dans tous les noeuds. En effet, nous avons démontré qu'il est possible de réduire le nombre de commutateurs photoniques tout en satisfaisant la demande de trafic et en gardant le coût global d'allocation de ressources de réseau inchangé par rapport à l'architecture classique. Cela implique une réduction substantielle des coûts CAPEX et OPEX. Dans nos expériences de calcul, les résultats démontrent que la réduction de coûts peut atteindre jusqu'à 65% dans certaines jeux de données et de réseau.