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

House allocation via deferred-acceptance

We study the simple model of assigning indivisible and heterogenous objects (e.g., houses, jobs, offi ces, etc.) to agents. Each agent receives at most one object and monetary compensations are not possible. For this model, known as the house allocation model, we characterize the class of rules satisfying unavailable object invariance, individual rationality, weak non-wastefulness, resource-monotonicity, truncation invariance, and strategy-proofness: any rule with these properties must allocate objects based on (implicitly induced) objects' priorities over agents and the agent-proposing deferred-acceptance-algorithm.

Choix de portefeuille de grande taille et mesures de risque pour preneurs de décision pessimistes

Cette thèse de doctorat consiste en trois chapitres qui traitent des sujets de choix de portefeuilles de grande taille, et de mesure de risque. Le premier chapitre traite du problème d’erreur d’estimation dans les portefeuilles de grande taille, et utilise le cadre d'analyse moyenne-variance. Le second chapitre explore l'importance du risque de devise pour les portefeuilles d'actifs domestiques, et étudie les liens entre la stabilité des poids de portefeuille de grande taille et le risque de devise. Pour finir, sous l'hypothèse que le preneur de décision est pessimiste, le troisième chapitre dérive la prime de risque, une mesure du pessimisme, et propose une méthodologie pour estimer les mesures dérivées. Le premier chapitre améliore le choix optimal de portefeuille dans le cadre du principe moyenne-variance de Markowitz (1952). Ceci est motivé par les résultats très décevants obtenus, lorsque la moyenne et la variance sont remplacées par leurs estimations empiriques. Ce problème est amplifié lorsque le nombre d’actifs est grand et que la matrice de covariance empirique est singulière ou presque singulière. Dans ce chapitre, nous examinons quatre techniques de régularisation pour stabiliser l’inverse de la matrice de covariance: le ridge, spectral cut-off, Landweber-Fridman et LARS Lasso. Ces méthodes font chacune intervenir un paramètre d’ajustement, qui doit être sélectionné. La contribution principale de cette partie, est de dériver une méthode basée uniquement sur les données pour sélectionner le paramètre de régularisation de manière optimale, i.e. pour minimiser la perte espérée d’utilité. Précisément, un critère de validation croisée qui prend une même forme pour les quatre méthodes de régularisation est dérivé. Les règles régularisées obtenues sont alors comparées à la règle utilisant directement les données et à la stratégie naïve 1/N, selon leur perte espérée d’utilité et leur ratio de Sharpe. Ces performances sont mesurée dans l’échantillon (in-sample) et hors-échantillon (out-of-sample) en considérant différentes tailles d’échantillon et nombre d’actifs. Des simulations et de l’illustration empirique menées, il ressort principalement que la régularisation de la matrice de covariance améliore de manière significative la règle de Markowitz basée sur les données, et donne de meilleurs résultats que le portefeuille naïf, surtout dans les cas le problème d’erreur d’estimation est très sévère. Dans le second chapitre, nous investiguons dans quelle mesure, les portefeuilles optimaux et stables d'actifs domestiques, peuvent réduire ou éliminer le risque de devise. Pour cela nous utilisons des rendements mensuelles de 48 industries américaines, au cours de la période 1976-2008. Pour résoudre les problèmes d'instabilité inhérents aux portefeuilles de grandes tailles, nous adoptons la méthode de régularisation spectral cut-off. Ceci aboutit à une famille de portefeuilles optimaux et stables, en permettant aux investisseurs de choisir différents pourcentages des composantes principales (ou dégrées de stabilité). Nos tests empiriques sont basés sur un modèle International d'évaluation d'actifs financiers (IAPM). Dans ce modèle, le risque de devise est décomposé en deux facteurs représentant les devises des pays industrialisés d'une part, et celles des pays émergents d'autres part. Nos résultats indiquent que le risque de devise est primé et varie à travers le temps pour les portefeuilles stables de risque minimum. De plus ces stratégies conduisent à une réduction significative de l'exposition au risque de change, tandis que la contribution de la prime risque de change reste en moyenne inchangée. Les poids de portefeuille optimaux sont une alternative aux poids de capitalisation boursière. Par conséquent ce chapitre complète la littérature selon laquelle la prime de risque est importante au niveau de l'industrie et au niveau national dans la plupart des pays. Dans le dernier chapitre, nous dérivons une mesure de la prime de risque pour des préférences dépendent du rang et proposons une mesure du degré de pessimisme, étant donné une fonction de distorsion. Les mesures introduites généralisent la mesure de prime de risque dérivée dans le cadre de la théorie de l'utilité espérée, qui est fréquemment violée aussi bien dans des situations expérimentales que dans des situations réelles. Dans la grande famille des préférences considérées, une attention particulière est accordée à la CVaR (valeur à risque conditionnelle). Cette dernière mesure de risque est de plus en plus utilisée pour la construction de portefeuilles et est préconisée pour compléter la VaR (valeur à risque) utilisée depuis 1996 par le comité de Bâle. De plus, nous fournissons le cadre statistique nécessaire pour faire de l’inférence sur les mesures proposées. Pour finir, les propriétés des estimateurs proposés sont évaluées à travers une étude Monte-Carlo, et une illustration empirique en utilisant les rendements journaliers du marché boursier américain sur de la période 2000-2011.

Strategy-proofness and essentially single-valued cores revisited

We consider general allocation problems with indivisibilities where agents' preferences possibly exhibit externalities. In such contexts many different core notions were proposed. One is the gamma-core whereby blocking is only allowed via allocations where the non-blocking agents receive their endowment. We show that if there exists an allocation rule satisfying ‘individual rationality’, ‘efficiency’, and ‘strategy-proofness’, then for any problem for which the gamma-core is non-empty, the allocation rule must choose a gamma-core allocation and all agents are indifferent between all allocations in the gamma-core. We apply our result to housing markets, coalition formation and networks.

Solution Methods for Service Network Design with Resource Management Consideration

La gestion des ressources, équipements, équipes de travail, et autres, devrait être prise en compte lors de la conception de tout plan réalisable pour le problème de conception de réseaux de services. Cependant, les travaux de recherche portant sur la gestion des ressources et la conception de réseaux de services restent limités. La présente thèse a pour objectif de combler cette lacune en faisant l’examen de problèmes de conception de réseaux de services prenant en compte la gestion des ressources. Pour ce faire, cette thèse se décline en trois études portant sur la conception de réseaux. La première étude considère le problème de capacitated multi-commodity fixed cost network design with design-balance constraints(DBCMND). La structure multi-produits avec capacité sur les arcs du DBCMND, de même que ses contraintes design-balance, font qu’il apparaît comme sous-problème dans de nombreux problèmes reliés à la conception de réseaux de services, d’où l’intérêt d’étudier le DBCMND dans le contexte de cette thèse. Nous proposons une nouvelle approche pour résoudre ce problème combinant la recherche tabou, la recomposition de chemin, et une procédure d’intensification de la recherche dans une région particulière de l’espace de solutions. Dans un premier temps la recherche tabou identifie de bonnes solutions réalisables. Ensuite la recomposition de chemin est utilisée pour augmenter le nombre de solutions réalisables. Les solutions trouvées par ces deux méta-heuristiques permettent d’identifier un sous-ensemble d’arcs qui ont de bonnes chances d’avoir un statut ouvert ou fermé dans une solution optimale. Le statut de ces arcs est alors fixé selon la valeur qui prédomine dans les solutions trouvées préalablement. Enfin, nous utilisons la puissance d’un solveur de programmation mixte en nombres entiers pour intensifier la recherche sur le problème restreint par le statut fixé ouvert/fermé de certains arcs. Les tests montrent que cette approche est capable de trouver de bonnes solutions aux problèmes de grandes tailles dans des temps raisonnables. Cette recherche est publiée dans la revue scientifique Journal of heuristics. La deuxième étude introduit la gestion des ressources au niveau de la conception de réseaux de services en prenant en compte explicitement le nombre fini de véhicules utilisés à chaque terminal pour le transport de produits. Une approche de solution faisant appel au slope-scaling, la génération de colonnes et des heuristiques basées sur une formulation en cycles est ainsi proposée. La génération de colonnes résout une relaxation linéaire du problème de conception de réseaux, générant des colonnes qui sont ensuite utilisées par le slope-scaling. Le slope-scaling résout une approximation linéaire du problème de conception de réseaux, d’où l’utilisation d’une heuristique pour convertir les solutions obtenues par le slope-scaling en solutions réalisables pour le problème original. L’algorithme se termine avec une procédure de perturbation qui améliore les solutions réalisables. Les tests montrent que l’algorithme proposé est capable de trouver de bonnes solutions au problème de conception de réseaux de services avec un nombre fixe des ressources à chaque terminal. Les résultats de cette recherche seront publiés dans la revue scientifique Transportation Science. La troisième étude élargie nos considérations sur la gestion des ressources en prenant en compte l’achat ou la location de nouvelles ressources de même que le repositionnement de ressources existantes. Nous faisons les hypothèses suivantes: une unité de ressource est nécessaire pour faire fonctionner un service, chaque ressource doit retourner à son terminal d’origine, il existe un nombre fixe de ressources à chaque terminal, et la longueur du circuit des ressources est limitée. Nous considérons les alternatives suivantes dans la gestion des ressources: 1) repositionnement de ressources entre les terminaux pour tenir compte des changements de la demande, 2) achat et/ou location de nouvelles ressources et leur distribution à différents terminaux, 3) externalisation de certains services. Nous présentons une formulation intégrée combinant les décisions reliées à la gestion des ressources avec les décisions reliées à la conception des réseaux de services. Nous présentons également une méthode de résolution matheuristique combinant le slope-scaling et la génération de colonnes. Nous discutons des performances de cette méthode de résolution, et nous faisons une analyse de l’impact de différentes décisions de gestion des ressources dans le contexte de la conception de réseaux de services. Cette étude sera présentée au XII International Symposium On Locational Decision, en conjonction avec XXI Meeting of EURO Working Group on Locational Analysis, Naples/Capri (Italy), 2014. En résumé, trois études différentes sont considérées dans la présente thèse. La première porte sur une nouvelle méthode de solution pour le "capacitated multi-commodity fixed cost network design with design-balance constraints". Nous y proposons une matheuristique comprenant la recherche tabou, la recomposition de chemin, et l’optimisation exacte. Dans la deuxième étude, nous présentons un nouveau modèle de conception de réseaux de services prenant en compte un nombre fini de ressources à chaque terminal. Nous y proposons une matheuristique avancée basée sur la formulation en cycles comprenant le slope-scaling, la génération de colonnes, des heuristiques et l’optimisation exacte. Enfin, nous étudions l’allocation des ressources dans la conception de réseaux de services en introduisant des formulations qui modèlent le repositionnement, l’acquisition et la location de ressources, et l’externalisation de certains services. À cet égard, un cadre de solution slope-scaling développé à partir d’une formulation en cycles est proposé. Ce dernier comporte la génération de colonnes et une heuristique. Les méthodes proposées dans ces trois études ont montré leur capacité à trouver de bonnes solutions.

Variabilité individuelle de l'allocation fonctionnelle des régions cérébrales perceptives dans l'autisme

Introduction : Une augmentation de la plasticité cérébrale est susceptible d’être impliquée dans la réallocation des régions corticales et dans les nombreuses altérations microstructurelles observées en autisme. Considérant les nombreux résultats démontrant un surfonctionnement perceptif et un fonctionnement moteur atypique en autisme, l’augmentation de la plasticité cérébrale suggère une plus grande variabilité individuelle de l’allocation fonctionnelle chez cette population, plus spécifiquement dans les régions perceptives et motrices. Méthode : Afin de tester cette hypothèse, 23 participants autistes de haut-niveau et 22 non-autistes appariés pour l’âge, le quotient intellectuel, les résultats au test des Matrices de Raven et la latéralité, ont réalisé une tâche d’imitation visuo-motrice dans un appareil d’imagerie par résonnance magnétique fonctionnelle (IRMf). Pour chaque participant, les coordonnées du pic d’activation le plus élevé ont été extraites des aires motrices primaires (Aire de Brodmann 4 (BA4)) et supplémentaires (BA6), du cortex visuo-moteur pariétal supérieur (BA7) ainsi que des aires visuelles primaires (BA17) et associatives (BA18+19) des deux hémisphères. L’étendue des activations, mesurée en fonction du nombre de voxels activés, et la différence d’intensité des activations, calculée en fonction du changement moyen d’intensité du signal ont également été considérées. Pour chaque région d’intérêt et hémisphère, la distance entre la localisation de l’activation maximale de chaque participant par rapport à celle de la moyenne de son groupe a servi de variable d’intérêt. Les moyennes de ces distances individuelles obtenues pour chaque groupe et chacune des régions d’intérêt ont ensuite été soumises à une ANOVA à mesures répétées afin de déterminer s’il existait des différences de variabilité dans la localisation des activations entre les groupes. Enfin, l’activation fonctionnelle générale à l’intérieur de chaque groupe et entre les groupes a également été étudiée. Résultats : Les résultats démontrent qu’une augmentation de la variabilité individuelle en terme de localisation des activations s’est produite à l’intérieur des deux groupes dans les aires associatives motrices et visuelles comparativement aux aires primaires associées. Néanmoins, malgré le fait que cette augmentation de variabilité dans les aires associatives soit partagée, une comparaison directe de celle-ci entre les groupes a démontré que les autistes présentaient une plus grande variabilité de la localisation des activations fonctionnelles dans le cortex visuo-moteur pariétal supérieur (BA7) et les aires associatives visuelles (BA18+19) de l’hémisphère gauche. Conclusion : Des stratégies différentes et possiblement uniques pour chaque individu semblent être observées en autisme. L’augmentation de la variabilité individuelle de la localisation des activations fonctionnelles retrouvée chez les autistes dans les aires associatives, où l’on observe également davantage de variabilité chez les non-autistes, suggère qu’une augmentation et/ou une altération des mécanismes de plasticité est impliquée dans l’autisme.

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.

Essays in resource economics

Cette thèse comporte trois essais en économie des ressources naturelles. Le Chapitre 2 analyse les effets du stockage d’une ressource naturelle sur le bien-être et sur le stock de celle-ci, dans le contexte de la rizipisciculture. La rizipisciculture consiste à élever des poissons dans une rizière en même temps que la culture du riz. Je développe un modèle d’équilibre général, qui contient trois composantes principales : une ressource renouvelable à accès libre, deux secteurs de production et le stockage du bien produit à partir de la ressource. Les consommateurs stockent la ressource lorsqu’ils spéculent que le prix de cette ressource sera plus élevé dans le futur. Le stockage a un effet ambigu sur le bien-être, négatif sur le stock de ressource au moment où le stockage a lieu et positive sur le stock de ressource dans le futur. Le Chapitre 3 étudie les effects de la migration de travailleurs qualifiés dans un modèle de commerce international lorsqu’il y a présence de pollution. Je développe un modèle de commerce à deux secteurs dans lequel j’introduis les questions de pollution et de migration dans l’objectif de montrer que le commerce interrégional peut affecter le niveau de pollution dans un pays composé de régions qui ont des structures industrielles différentes. La mobilité des travailleurs amplifie les effets du commerce sur le capital environnemental. Le capital environnemental de la région qui a la technologie la moins (plus) polluante est positivement (négativement) affecté par le commerce. De plus, je montre que le commerce interrégional est toujours bénéfique pour la région avec la technologie la moins polluante, ce qui n’est pas toujours le cas pour la région qui a la technologie la plus polluante. Finalement, le Chapitre 4 est coécrit avec Yves Richelle. Dans ce chapitre, nous étudions l’allocation efficace de l’eau d’un lac entre différents utilisateurs. Nous considérons dans le modèle deux types d’irréversibilités : l’irréversibilité d’un investissement qui crée un dommage à l’écosystème et l’irréversibilité dans l’allocation des droits d’usage de l’eau qui provient de la loi sur l’eau (irréversibilité légale). Nous déterminons d’abord la valeur de l’eau pour chacun des utilisateurs. Par la suite, nous caractérisons l’allocation optimale de l’eau entre les utilisateurs. Nous montrons que l’irréversibilité légale entraîne qu’il est parfois optimal de réduire la quantité d’eau allouée à la firme, même s’il n’y a pas de rivalité d’usage. De plus, nous montrons qu’il n’est pas toujours optimal de prévenir le dommage créé par un investissement. Dans l’ensemble, nous prouvons que les irréversibilités entraînent que l’égalité de la valeur entre les utilisateurs ne tient plus à l’allocation optimale. Nous montrons que lorsqu’il n’y a pas de rivalité d’usage, l’eau non utilisée ne doit pas être considérée comme une ressource sans limite qui doit être utilisée de n’importe quelle façon.

Martin Heidegger and the problem of transcendence

Cette thèse a pour point de départ l’idée du jeune Heidegger selon laquelle le sens de l’être doit être recherché au moyen d’une phénoménologie ontologique, plus précisément par l’analytique existentiale du Dasein et la destruction de l’histoire de l’ontologie ; ou, comme nous l’interprétons, dans la transcendance du Dasein et la transcendance de l’être. L’étude du problème de la transcendance fait l’objet d’une approche phénoménologique, laquelle porte une attention particulière au vécu en tant que tel ainsi qu’aux conditions de possibilité de ce vécu, et repose sur une lecture attentive et critique des œuvres de Heidegger. C’est une telle approche phénoménologique qui nous permettra de mener à bien notre analyse du problème de la transcendance dans le corpus heideggérien. Nous serons par ailleurs en mesure d’aborder le débat opposant à ce sujet la tradition analytique (plus particulièrement l’approche pragmatiste) et la tradition continentale, notre étude s’inscrivant dans le cadre de cette dernière. Nous proposons ici une phénoménologie du problème de la transcendance qui fait également figure de phénoménologie du sens, de la possibilité et de la normativité. Prenant pour point de départ certaines contributions issues de la tradition continentale, nous soutenons que le sens de l’être peut être compris comme le problème de la transcendance. L’histoire de la philosophie doit être perturbée, déconstruite et repensée afin que le chemin de la philosophie, encore non pensé, puisse être mis au jour. L’accès à cet autre commencement doit être recherché dans la transcendance en tant que telle – de l’appel de la conscience fondé dans la nullité à l’encontre authentique avec la mort et l’ouverture de la temporalité ; de l’avènement historial de l’être jusqu’à, ultimement, le i! ! ! ! refus de l’être et le retrait du rien. L’événement (Ereignis) de l’être est donc compris comme processus de dépassement de soi à partir duquel la transcendance de l’être – ou, comme le formule Heidegger, la fin des questions – est possible.

Beyond a "woman's problem" : the role of relationship processes in female genital pain

Female genital pain is a prevalent condition that can disrupt the psychosexual and relational well-being of affected women and their romantic partners. Despite the intimate context in which the pain can be elicited (i.e., during sexual intercourse), interpersonal correlates of genital pain and sexuality have not been widely studied in comparison to other psychosocial factors. This review describes several prevailing theoretical models explaining the role of the partner in female genital pain: the operant learning model, cognitive-behavioral and communal coping models, and intimacy models. The review includes a discussion of empirical research on the interpersonal and partner correlates of female genital pain and the impact of genital pain on partners’ psychosexual adjustment. Together, this research highlights a potential reciprocal interaction between both partners’ experiences of female genital pain. The direction of future theoretical, methodological, and clinical research is discussed with regard to the potential to enhance understanding of the highly interpersonal context of female genital pain

Studies on some generalizations of line graph and the power domination problem in graphs

Department of Mathematics, Cochin University of Science and Technology

Pionic branches in neutron matter and the problem of pion condensation

The pion spectrum for charged and neutral pions is investigated in pure neutron matter, by letting the pions interact with a neutron Fermi sea in a self-consistent scheme that renormalizes simultaneously the mesons, considered the source of the interaction, and the nucleons. The possibility of obtaining different kinds of pion condensates is investigated with the result that they cannot be reached even for values of the spin-spin correlation parameter, g', far below the range commonly accepted.

The Fishing Industry in Kerala - Problem and Potentials

importance of fishing and other allied industries in the economy was realised only very recently. Consequently only very few studies are available on the subject. Here an attempt is made to survey the available literature on the subject.

A Numerically efficient power optimization scheme for coded OFDM systems in achieving minimum frame error rate

Coded OFDM is a transmission technique that is used in many practical communication systems. In a coded OFDM system, source data are coded, interleaved and multiplexed for transmission over many frequency sub-channels. In a conventional coded OFDM system, the transmission power of each subcarrier is the same regardless of the channel condition. However, some subcarrier can suffer deep fading with multi-paths and the power allocated to the faded subcarrier is likely to be wasted. In this paper, we compute the FER and BER bounds of a coded OFDM system given as convex functions for a given channel coder, inter-leaver and channel response. The power optimization is shown to be a convex optimization problem that can be solved numerically with great efficiency. With the proposed power optimization scheme, near-optimum power allocation for a given coded OFDM system and channel response to minimize FER or BER under a constant transmission power constraint is obtained