35 resultados para Recherche adaptative à voisinage large
em Université de Montréal, Canada
Resumo:
Cette thse porte sur les problmes de tournes de vhicules avec fentres de temps o un gain est associ chaque client et o l'objectif est de maximiser la somme des gains recueillis moins les cots de transport. De plus, un mme vhicule peut effectuer plusieurs tournes durant l'horizon de planification. Ce problme a t relativement peu tudi en dpit de son importance en pratique. Par exemple, dans le domaine de la livraison de denres prissables, plusieurs tournes de courte dure doivent tre combines afin de former des journes compltes de travail. Nous croyons que ce type de problme aura une importance de plus en plus grande dans le futur avec l'avnement du commerce lectronique, comme les piceries lectroniques, o les clients peuvent commander des produits par internet pour la livraison domicile. Dans le premier chapitre de cette thse, nous prsentons d'abord une revue de la littrature consacre aux problmes de tournes de vhicules avec gains ainsi qu'aux problmes permettant une rutilisation des vhicules. Nous prsentons les mthodologies gnrales adoptes pour les rsoudre, soit les mthodes exactes, les mthodes heuristiques et les mta-heuristiques. Nous discutons enfin des problmes de tournes dynamiques o certaines donnes sur le problme ne sont pas connues l'avance. Dans le second chapitre, nous dcrivons un algorithme exact pour rsoudre un problme de tournes avec fentres de temps et rutilisation de vhicules o l'objectif premier est de maximiser le nombre de clients desservis. Pour ce faire, le problme est modlis comme un problme de tournes avec gains. L'algorithme exact est bas sur une mthode de gnration de colonnes couple avec un algorithme de plus court chemin lmentaire avec contraintes de ressources. Pour rsoudre des instances de taille raliste dans des temps de calcul raisonnables, une approche de rsolution de nature heuristique est requise. Le troisime chapitre propose donc une mthode de recherche adaptative grand voisinage qui exploite les diffrents niveaux hirarchiques du problme (soit les journes compltes de travail des vhicules, les routes qui composent ces journes et les clients qui composent les routes). Dans le quatrime chapitre, qui traite du cas dynamique, une stratgie d'acceptation et de refus des nouvelles requtes de service est propose, base sur une anticipation des requtes venir. L'approche repose sur la gnration de scnarios pour diffrentes ralisations possibles des requtes futures. Le cot d'opportunit de servir une nouvelle requte est bas sur une valuation des scnarios avec et sans cette nouvelle requte. Enfin, le dernier chapitre rsume les contributions de cette thse et propose quelques avenues de recherche future.
Resumo:
Dans ce mmoire, nous tudions un problme de tournes de vhicules dans lequel une flotte prive de vhicules na pas la capacit suffisante pour desservir les demandes des clients. Dans un tel cas, on fait appel un transporteur externe. Ce dernier na aucune contrainte de capacit, mais un cot est encouru lorsquun client lui est affect. Il nest pas ncessaire de mettre tous les vhicules de la flotte prive en service si cette approche se rvle plus conomique. Lobjectif consiste minimiser le cot fixe des vhicules, puis le cot variable de transport et le cot charg par le transporteur externe. Notre travail consiste appliquer la mtaheuristique de recherche adaptative grand voisinage sur ce problme. Nous comparons nos rsultats avec ceux obtenus prcdemment avec diffrentes techniques connues sur les instances de Christofides et celles de Golden.
Resumo:
De nombreux problmes pratiques qui se posent dans dans le domaine de la logistique, peuvent tre modliss comme des problmes de tournes de vhicules. De faon gnrale, cette famille de problmes implique la conception de routes, dbutant et se terminant un dpt, qui sont utilises pour distribuer des biens un nombre de clients gographiquement dispers dans un contexte o les cots associs aux routes sont minimiss. Selon le type de problme, un ou plusieurs dpts peuvent-tre prsents. Les problmes de tournes de vhicules sont parmi les problmes combinatoires les plus difficiles rsoudre. Dans cette thse, nous tudions un problme doptimisation combinatoire, appartenant aux classes des problmes de tournes de vhicules, qui est lie au contexte des rseaux de transport. Nous introduisons un nouveau problme qui est principalement inspir des activits de collecte de lait des fermes de production, et de la redistribution du produit collect aux usines de transformation, pour la province de Qubec. Deux variantes de ce problme sont considres. La premire, vise la conception dun plan tactique de routage pour le problme de la collecte-redistribution de lait sur un horizon donn, en supposant que le niveau de la production au cours de lhorizon est fix. La deuxime variante, vise fournir un plan plus prcis en tenant compte de la variation potentielle de niveau de production pouvant survenir au cours de lhorizon considr. Dans la premire partie de cette thse, nous dcrivons un algorithme exact pour la premire variante du problme qui se caractrise par la prsence de fentres de temps, plusieurs dpts, et une flotte htrogne de vhicules, et dont lobjectif est de minimiser le cot de routage. cette fin, le problme est modlis comme un problme multi-attributs de tournes de vhicules. Lalgorithme exact est bas sur la gnration de colonnes impliquant un algorithme de plus court chemin lmentaire avec contraintes de ressources. Dans la deuxime partie, nous concevons un algorithme exact pour rsoudre la deuxime variante du problme. cette fin, le problme est modlis comme un problme de tournes de vhicules multi-priodes prenant en compte explicitement les variations potentielles du niveau de production sur un horizon donn. De nouvelles stratgies sont proposes pour rsoudre le problme de plus court chemin lmentaire avec contraintes de ressources, impliquant dans ce cas une structure particulire tant donn la caractristique multi-priodes du problme gnral. Pour rsoudre des instances de taille raliste dans des temps de calcul raisonnables, une approche de rsolution de nature heuristique est requise. La troisime partie propose un algorithme de recherche adaptative grands voisinages o de nombreuses nouvelles stratgies dexploration et dexploitation sont proposes pour amliorer la performances de lalgorithme propos en termes de la qualit de la solution obtenue et du temps de calcul ncessaire.
Resumo:
Nous proposons de construire un atlas numrique 3D contenant les caractristiques moyennes et les variabilits de la morphologie dun organe. Nos travaux seront appliqus particulirement la construction d'un atlas numrique 3D de la totalit de la corne humaine incluant la surface antrieure et postrieure partir des cartes topographiques fournies par le topographe Orbscan II. Nous procdons tout d'abord par normalisation de toute une population de cornes. Dans cette tape, nous nous sommes bass sur l'algorithme de recalage ICP (iterative closest point) pour aligner simultanment les surfaces antrieures et postrieures d'une population de corne vers les surfaces antrieure et postrieure d'une corne de rfrence. En effet, nous avons labor une variante de l'algorithme ICP adapt aux images (cartes) de cornes qui tient compte de changement d'chelle pendant le recalage et qui se base sur la recherche par voisinage via la distance euclidienne pour tablir la correspondance entre les points. Aprs, nous avons procd pour la construction de l'atlas cornen par le calcul des moyennes des lvations de surfaces antrieures et postrieures recales et leurs carts-types associs. Une population de 100 cornes saines a t utilise pour construire l'atlas cornen normal. Pour visualiser latlas, on a eu recours des cartes topographiques couleurs similairement ce quoffrent dj les systmes topographiques actuels. Enfin, des observations ont t ralises sur l'atlas cornen refltant sa prcision et permettant de dvelopper une meilleure connaissance de lanatomie cornenne.
Resumo:
Les tudiants gradus et les professeurs (les chercheurs, en gnral), accdent, passent en revue et utilisent rgulirement un grand nombre darticles, cependant aucun des outils et solutions existants ne fournit la vaste gamme de fonctionnalits exiges pour grer correctement ces ressources. En effet, les systmes de gestion de bibliographie grent les rfrences et les citations, mais ne parviennent pas aider les chercheurs manipuler et localiser des ressources. D'autre part, les systmes de recommandation darticles de recherche et les moteurs de recherche spcialiss aident les chercheurs localiser de nouvelles ressources, mais l encore chouent dans laide les grer. Finalement, les systmes de gestion de contenu d'entreprise offrent les fonctionnalits de gestion de documents et des connaissances, mais ne sont pas conus pour les articles de recherche. Dans ce mmoire, nous prsentons une nouvelle classe de systmes de gestion : systme de gestion et de recommandation darticles de recherche. Papyres (Naak, Hage, & Ameur, 2008, 2009) est un prototype qui lillustre. Il combine des fonctionnalits de bibliographie avec des techniques de recommandation darticles et des outils de gestion de contenu, afin de fournir un ensemble de fonctionnalits pour localiser les articles de recherche, manipuler et maintenir les bibliographies. De plus, il permet de grer et partager les connaissances relatives la littrature. La technique de recommandation utilise dans Papyres est originale. Sa particularit rside dans l'aspect multicritre introduit dans le processus de filtrage collaboratif, permettant ainsi aux chercheurs d'indiquer leur intrt pour des parties spcifiques des articles. De plus, nous proposons de tester et de comparer plusieurs approches afin de dterminer le voisinage dans le processus de Filtrage Collaboratif Multicritre, de telle sorte accrotre la prcision de la recommandation. Enfin, nous ferons un rapport global sur la mise en uvre et la validation de Papyres.
Resumo:
Dans ce memoire, nous presentons un nouveau type de probleme de confection de tour- nee pour un seul vehicule avec cueillettes et livraisons et contrainte de chargement. Cette variante est motivee par des problemes similaires rapportes dans la litterature. Le vehi- cule en question contient plusieurs piles ou des colis de hauteurs differentes sont empiles durant leur transport. La hauteur totale des items contenus dans chacune des piles ne peut depasser une certaine hauteur maximale. Aucun deplacement nest permis lors de la li- vraison dun colis, ce qui signifie que le colis doit etre sur le dessus dune pile au moment detre livre. De plus, tout colis i ramasse avant un colis j et contenu dans la meme pile doit etre livre apres j. Une heuristique a grand voisinage, base sur des travaux recents dans le domaine, est proposee comme methode de resolution. Des resultats numeriques sont rapportes pour plusieurs instances classiques ainsi que pour de nouvelles instances.
Resumo:
Formes lors de leffondrement gravitationnel dun nuage de gaz molculaire, les toiles naissantes auront diffrentes masses variant entre 0.08 et environ 100M . La majorit de la population stellaire de la Galaxie est constitue dtoiles dont la masse est infrieure environ 0.6 M . Le dernier vnement de formation stellaire dans le voisinage solaire sest produit dans la bulle locale il y a au plus 100 millions dannes, vraisemblablement provoqu par le passage dune onde de choc dans le bras local de la Galaxie. Cest ainsi que se formrent de jeunes associations dtoiles dont les membres se caractrisent en particulier par une vitesse spatiale et une position commune dans la Galaxie. Les associations jeunes tant peu densment peuples et relativement proches du Soleil, leurs membres se font plutt rares et disperss sur toute la vote cleste. Jusqu prsent, surtout les toiles les plus massives (brillantes) ont t rpertories. Les toiles jeunes de faible masse, constituant la majorit de la population, restent pour la plupart tre identifies. Les toiles jeunes de faible masse reprsentent une population clef pour contraindre les modles volutifs des toiles M et des naines brunes. Elles sont galement dexcellentes candidates pour chercher des exoplantes via les techniques dimagerie directe. Ce mmoire prsente une nouvelle mthode utilisant un modle cinmatique enrichi dune analyse statistique Bayesienne pour identifier des toiles jeunes de faible masse dans les associations beta Pictoris, Tucana-Horologium et AB Doradus. partir dun chantillon de 1080 toiles K et M, toutes comportant des indicateurs de jeunesse tels lmission Halpha et une forte luminosit dans les rayons X, leurs proprits cinmatiques (mouvement propre) et photomtriques sont analyses pour en extraire 98 candidates hautement probables membres dune des trois associations. Une confirmation de leur statut comme membre ncessitera en particulier une mesure de leur vitesse radiale (prdit par notre analyse) et une mesure de la largeur quivalente du lithium 6708 pour mieux contraindre leur ge.
Resumo:
L'outil dvelopp dans le cadre de cette thse est disponible l'adresse suivante: www.astro.umontreal.ca/~malo/banyan.php
Resumo:
Lobjectif principal de cette thse est didentifier les toiles de faible masse et naines brunes membres dassociations cinmatiques jeunes du voisinage solaire. Ces associations sont typiquement ges de moins de 200 millions dannes et regroupent chacune un ensemble dtoiles stant formes au mme moment et dans un mme environnement. La majorit de leurs membres d'environ plus de 0.3 fois la masse du Soleil sont dj connus, cependant les membres moins massifs (et moins brillants) nous chappent encore. Leur identification permettra de lever le voile sur plusieurs questions fondamentales en astrophysique. En particulier, le fait de cibler des objets jeunes, encore chauds et lumineux par leur formation rcente, permettra datteindre un rgime de masses encore peu explor, jusqu' seulement quelques fois la masse de Jupiter. Elles nous permettront entre autres de contraindre la fonction de masse initiale et d'explorer la connection entre naines brunes et exoplantes, tant donn que les moins massives des naines brunes jeunes auront des proprits physiques trs semblables aux exoplantes gantes gazeuses. Pour mener bien ce projet, nous avons adapt l'outil statistique BANYAN I pour qu'il soit applicable aux objets de trs faibles masses en plus de lui apporter plusieurs amliorations. Nous avons entre autres inclus l'utilisation de deux diagrammes couleur-magnitude permettant de diffrencier les toiles de faible masse et naines brunes jeunes celles plus vieilles, ajout l'utilisation de probabilits a priori pour rendre les rsultats plus ralistes, adapt les modles spatiaux et cinmatiques des associations jeunes en utilisant des ellipsodes gaussiennes tridimensionnelles dont l'alignement des axes est libre, effectu une analyse Monte Carlo pour caractriser le taux de faux-positifs et faux-ngatifs, puis revu la structure du code informatique pour le rendre plus efficace. Dans un premier temps, nous avons utilis ce nouvel algorithme, BANYAN II, pour identifier 25 nouvelles candidates membres d'associations jeunes parmi un chantillon de 158 toiles de faible masse (de types spectraux > M4) et naines brunes jeunes dj connues. Nous avons ensuite effectu la corrlation croise de deux catalogues couvrant tout le ciel en lumire proche-infrarouge et contenant ~ 500 millions dobjets clestes pour identifier environ 100 000 candidates naines brunes et toiles de faible masse du voisinage solaire. l'aide de l'outil BANYAN II, nous avons alors identifi quelques centaines d'objets appartenant fort probablement une association jeune parmi cet chantillon et effectu un suivi spectroscopique en lumire proche-infrarouge pour les caractriser. Les travaux prsents ici ont men l'identification de 79 candidates naines brunes jeunes ainsi que 150 candidates toiles de faible masse jeunes, puis un suivi spectroscopique nous a permis de confirmer le jeune ge de 49 de ces naines brunes et 62 de ces toiles de faible masse. Nous avons ainsi approximativement doubl le nombre de naines brunes jeunes connues, ce qui a ouvert la porte une caractrisation statistique de leur population. Ces nouvelles naines brunes jeunes reprsentent un laboratoire idal pour mieux comprendre l'atmosphre des exoplantes gantes gazeuses. Nous avons identifi les premiers signes dune remonte dans la fonction de masse initiale des naines brunes aux trs faibles masses dans l'association jeune Tucana-Horologium, ce qui pourrait indiquer que ljection dexoplantes joue un rle important dans la composition de leur population. Les rsultats du suivi spectroscopique nous ont permis de construire une squence empirique complte pour les types spectraux M5-L5 l'ge du champ, faible () et trs faible () gravit de surface. Nous avons effectu une comparaison de ces donnes aux modles d'volution et d'atmosphre, puis nous avons construit un ensemble de squences empiriques de couleur-magnitude et types spectraux-magnitude pour les naines brunes jeunes. Finalement, nous avons dcouvert deux nouvelles exoplantes par un suivi en imagerie directe des toiles jeunes de faible masse identifies dans ce projet. La future mission GAIA et le suivi spectroscopique complet des candidates prsentes dans cette thse permettront de confirmer leur appartenance aux associations jeunes et de contraindre la fonction de masse initiale dans le rgime sous-stellaire.
Resumo:
Nous adaptons une heuristique de recherche voisinage variable pour traiter le problme du voyageur de commerce avec fentres de temps (TSPTW) lorsque l'objectif est la minimisation du temps d'arrive au dpt de destination. Nous utilisons des mthodes efficientes pour la vrification de la ralisabilit et de la rentabilit d'un mouvement. Nous explorons les voisinages dans des ordres permettant de rduire l'espace de recherche. La mthode rsultante est comptitive avec l'tat de l'art. Nous amliorons les meilleures solutions connues pour deux classes d'instances et nous fournissons les rsultats de plusieurs instances du TSPTW pour la premire fois.
Resumo:
Les mtaheuristiques sont trs utilises dans le domaine de l'optimisation discrte. Elles permettent dobtenir une solution de bonne qualit en un temps raisonnable, pour des problmes qui sont de grande taille, complexes, et difficiles rsoudre. Souvent, les mtaheuristiques ont beaucoup de paramtres que lutilisateur doit ajuster manuellement pour un problme donn. L'objectif d'une mtaheuristique adaptative est de permettre l'ajustement automatique de certains paramtres par la mthode, en se basant sur linstance rsoudre. La mtaheuristique adaptative, en utilisant les connaissances pralables dans la comprhension du problme, des notions de l'apprentissage machine et des domaines associs, cre une mthode plus gnrale et automatique pour rsoudre des problmes. Loptimisation globale des complexes miniers vise tablir les mouvements des matriaux dans les mines et les flux de traitement afin de maximiser la valeur conomique du systme. Souvent, en raison du grand nombre de variables entires dans le modle, de la prsence de contraintes complexes et de contraintes non-linaires, il devient prohibitif de rsoudre ces modles en utilisant les optimiseurs disponibles dans lindustrie. Par consquent, les mtaheuristiques sont souvent utilises pour loptimisation de complexes miniers. Ce mmoire amliore un procd de recuit simul dvelopp par Goodfellow & Dimitrakopoulos (2016) pour loptimisation stochastique des complexes miniers stochastiques. La mthode dveloppe par les auteurs ncessite beaucoup de paramtres pour fonctionner. Un de ceux-ci est de savoir comment la mthode de recuit simul cherche dans le voisinage local de solutions. Ce mmoire implmente une mthode adaptative de recherche dans le voisinage pour amliorer la qualit d'une solution. Les rsultats numriques montrent une augmentation jusqu' 10% de la valeur de la fonction conomique.
Resumo:
In the context of multivariate linear regression (MLR) models, it is well known that commonly employed asymptotic test criteria are seriously biased towards overrejection. In this paper, we propose a general method for constructing exact tests of possibly nonlinear hypotheses on the coefficients of MLR systems. For the case of uniform linear hypotheses, we present exact distributional invariance results concerning several standard test criteria. These include Wilks' likelihood ratio (LR) criterion as well as trace and maximum root criteria. The normality assumption is not necessary for most of the results to hold. Implications for inference are two-fold. First, invariance to nuisance parameters entails that the technique of Monte Carlo tests can be applied on all these statistics to obtain exact tests of uniform linear hypotheses. Second, the invariance property of the latter statistic is exploited to derive general nuisance-parameter-free bounds on the distribution of the LR statistic for arbitrary hypotheses. Even though it may be difficult to compute these bounds analytically, they can easily be simulated, hence yielding exact bounds Monte Carlo tests. Illustrative simulation experiments show that the bounds are sufficiently tight to provide conclusive results with a high probability. Our findings illustrate the value of the bounds as a tool to be used in conjunction with more traditional simulation-based test methods (e.g., the parametric bootstrap) which may be applied when the bounds are not conclusive.
Resumo:
In the context of multivariate regression (MLR) and seemingly unrelated regressions (SURE) models, it is well known that commonly employed asymptotic test criteria are seriously biased towards overrejection. in this paper, we propose finite-and large-sample likelihood-based test procedures for possibly non-linear hypotheses on the coefficients of MLR and SURE systems.
Resumo:
McCausland (2004a) describes a new theory of random consumer demand. Theoretically consistent random demand can be represented by a \"regular\" \"L-utility\" function on the consumption set X. The present paper is about Bayesian inference for regular L-utility functions. We express prior and posterior uncertainty in terms of distributions over the indefinite-dimensional parameter set of a flexible functional form. We propose a class of proper priors on the parameter set. The priors are flexible, in the sense that they put positive probability in the neighborhood of any L-utility function that is regular on a large subset bar(X) of X; and regular, in the sense that they assign zero probability to the set of L-utility functions that are irregular on bar(X). We propose methods of Bayesian inference for an environment with indivisible goods, leaving the more difficult case of indefinitely divisible goods for another paper. We analyse individual choice data from a consumer experiment described in Harbaugh et al. (2001).
